题目描述

長さ $2N$ の文字列 $S=S_1S_2\dots\ S_{2N}$ について、 $S$ が $N$ 個の ( , および $N$ 個の ) で構成されるとき、 $S$ は「括弧列」であるといいます。

また、「括弧列」$S$ のうち、以下のいずれかに該当するものを「正しい括弧列」といいます。

• 空文字列
• ある「正しい括弧列」$A$ が存在して (, $A$, ) をこの順に連結した文字列
• ある空でない「正しい括弧列」$A,\ B$ が存在して、 $A,\ B$ をこの順に連結した文字列

$1$ から $2N$ までの整数からなる $2$ つの順列 $ P=(P_1,\ P_2,\ \dots,\ P_{2N}),\ Q=(Q_1,\ Q_2,\ \dots,\ Q_{2N}) $ が与えられます。

以下の条件を満たすような「括弧列」$S=S_1S_2\dots\ S_{2N}$ が存在するか判定してください。

• $S_{p_1}S_{p_2}\dots\ S_{p_{2N}}$ が「正しい括弧列」となるような $1$ から $2N$ までの整数の順列 $p$ のうち、辞書式順序で最小のものが $P$
• $S_{p_1}S_{p_2}\dots\ S_{p_{2N}}$ が「正しい括弧列」となるような $1$ から $2N$ までの整数の順列 $p$ のうち、辞書式順序で最大のものが $Q$

存在する場合は $1$ つ求めてください。

输入格式

入力は以下の形式で標準入力から与えられます。

$N$ $P_1$ $P_2$ $\dots$ $P_{2N}$ $Q_1$ $Q_2$ $\dots$ $Q_{2N}$

输出格式

上記のような「括弧列」$S$ が存在する場合、そのうち $1$ つを出力してください。答えが複数存在する場合はいずれを出力してもかまいません。

存在しない場合は -1 を出力してください。

题目大意

给你两个长度为 $2\times n$ 的排列 $P$ $Q$，还有一个要求的括号序列 $S$，长度也是 $2\times n$。定义一个长度为 $2\times n$ 的排列 $C$ 是合法的，当且仅当按照 $S_{C_1} S_{C_2} \cdots S_{C_2\times n}$ 的顺序写下得到的字符串是合法的括号序列，其中 $P$ 是合法的排列中字典序最小的，$Q$ 是最大的，求 $S$。

translate by Xy_top

2
1 2 4 3
4 3 1 2

())(

2
1 3 2 4
4 3 2 1

-1

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

-1

提示

制約

• $1\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ P_i,Q_i\ \leq\ 2N$
• $P,\ Q$ はそれぞれ $1$ から $2N$ までの整数の順列
• 入力される値はすべて整数

Sample Explanation 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)$ であり、 $S$ は条件を満たします。

Sample Explanation 2

条件を満たす $S$ は存在しません。