Bracket and Permutation

时间限制：2s
空间限制：1024MB

题目描述

给定正整数 $N$ 以及两个 $1$ 到 $2N$ 的排列 $P=(P_1,\ldots,P_{2N})$、$Q=(Q_1,\ldots,Q_{2N})$。

一个长度为 $2N$、恰好含有 $N$ 个左括号和 $N$ 个右括号的字符串称为括号列。若一个括号列的任意前缀中左括号数都不少于右括号数，则称它为合法括号序列。

对于括号列 $S$，考虑所有满足 $S_{p_1}S_{p_2}\cdots S_{p_{2N}}$ 为合法括号序列的排列 $p$。你需要判断是否存在括号列 $S$，使这些排列中字典序最小的恰为 $P$，字典序最大的恰为 $Q$。若存在，输出任意一个满足条件的 $S$；否则输出 -1。

输入格式

第一行一个整数 $N$。

第二行 $2N$ 个整数 $P_1,P_2,\ldots,P_{2N}$。

第三行 $2N$ 个整数 $Q_1,Q_2,\ldots,Q_{2N}$。

输出格式

若存在满足条件的括号列，输出该字符串；否则输出 -1。

样例输入 1

2
1 2 4 3
4 3 1 2

样例输出 1

())(

样例输入 2

2
1 3 2 4
4 3 2 1

样例输出 2

-1

数据范围

对于所有数据，$1\le N\le 2\times10^5$，且 $P,Q$ 均为 $1$ 到 $2N$ 的排列。