题目描述

长度为 $2N$ 的字符串 $S=S_1S_2\\dots S_{2N}$ 被称为一个 括号序列，当 $S$ 由 $N$ 个 ( 和 $N$ 个 ) 组成时。

此外，当以下情况之一时，括号序列 $S$ 被称为 正确。

• 空字符串。
• 按照 (、$A$、) 的顺序连接而成的字符串，其中 $A$ 是一个正确的括号序列。
• 按照 $A$、$B$ 的顺序连接而成的字符串，其中 $A$ 和 $B$ 是非空的正确括号序列。

给定两个排列 $P=(P_1,\\ P_2,\\ \\dots,\\ P_{2N})$ 和 $Q=(Q_1,\\ Q_2,\\ \\dots,\\ Q_{2N})$，包含整数从 $1$ 到 $2N$。

判断是否存在一个括号序列 $S=S_1S_2\\dots S_{2N}$ 满足以下条件。

• $P$ 是整数从 $1$ 到 $2N$ 的字典序最小排列 $p$，使得 $S_{p_1}S_{p_2}\\dots S_{p_{2N}}$ 是一个正确的括号序列。
• $Q$ 是整数从 $1$ 到 $2N$ 的字典序最大排列 $p$，使得 $S_{p_1}S_{p_2}\\dots S_{p_{2N}}$ 是一个正确的括号序列。

如果存在这样的括号序列，则找出其中一个。

约束条件

• $1 \\leq N \\leq 2 \\times 10^5$
• $1 \\leq P_i,Q_i \\leq 2N$
• $P$ 和 $Q$ 均为 $1$ 到 $2N$ 的排列。
• 输入中的所有值均为整数。

输入

输入以标准格式给出，格式如下：

$N$

$P_1$ $P_2$ $\\dots$ $P_{2N}$

$Q_1$ $Q_2$ $\\dots$ $Q_{2N}$

输出

如果存在满足上述条件的括号序列 $S$，则输出一个这样的序列。如果存在多个这样的序列，你可以输出任意一个。

如果不存在这样的序列，则输出 -1。

示例输入 1

2
1 2 4 3
4 3 1 2

示例输出 1

())(

对于 $S=$ ())(，其中一些满足 $S_{p_1}S_{p_2}S_{p_3}S_{p_4}$ 是正确的括号序列的排列 $p$ 是 $p=(1,\\ 4,\\ 2,\\ 3),\\ (1,\\ 4,\\ 3,\\ 2)$。其中最小和最大的字典序分别为 $p=(1,\\ 2,\\ 4,\\ 3)$ 和 $p=(4,\\ 3,\\ 1,\\ 2)$，满足条件。

示例输入 2

2
1 3 2 4
4 3 2 1

示例输出 2

-1

没有满足条件的 $S$。

示例输入 3

3
2 1 5 3 4 6
6 5 3 4 2 1

示例输出 3

-1