{"raw_statement":[{"iden":"problem statement","content":"A string of length $2N$, $S=S_1S_2\\dots S_{2N}$, is said to be a _parenthesis sequence_ when $S$ is composed of $N$ `(`s and $N$ `)`s.\nAdditionally, a parenthesis sequence $S$ is said to be _correct_ when it is one of the following.\n\n*   An empty string.\n*   The concatenation of `(`, $A$, `)` in this order, where $A$ is a correct parenthesis sequence.\n*   The concatenation of $A$, $B$ in this order, where $A$ and $B$ are non-empty correct parenthesis sequences.\n\nYou are given two permutations $P=(P_1,\\ P_2,\\ \\dots,\\ P_{2N})$ and $Q=(Q_1,\\ Q_2,\\ \\dots,\\ Q_{2N})$ of the integers from $1$ to $2N$.\nDetermine whether there exists a parenthesis sequence $S=S_1S_2\\dots S_{2N}$ that satisfies the following conditions.\n\n*   $P$ is the lexicographically smallest permutation $p$ of the integers from $1$ to $2N$ such that $S_{p_1}S_{p_2}\\dots S_{p_{2N}}$ is a correct parenthesis sequence.\n*   $Q$ is the lexicographically largest permutation $p$ of the integers from $1$ to $2N$ such that $S_{p_1}S_{p_2}\\dots S_{p_{2N}}$ is a correct parenthesis sequence.\n\nIf such a parenthesis sequence exists, find one."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq P_i,Q_i \\leq 2N$\n*   Each of $P$ and $Q$ is a permutation of $1$ to $2N$.\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$P_1$ $P_2$ $\\dots$ $P_{2N}$\n$Q_1$ $Q_2$ $\\dots$ $Q_{2N}$"},{"iden":"sample input 1","content":"2\n1 2 4 3\n4 3 1 2"},{"iden":"sample output 1","content":"())(\n\nFor $S=$ `())(`, some of the permutations $p$ such that $S_{p_1}S_{p_2}S_{p_3}S_{p_4}$ is a correct parenthesis sequence are $p=(1,\\ 4,\\ 2,\\ 3),\\ (1,\\ 4,\\ 3,\\ 2)$. The lexicographically smallest and largest among them are $p=(1,\\ 2,\\ 4,\\ 3)$ and $p=(4,\\ 3,\\ 1,\\ 2)$, satisfying the conditions."},{"iden":"sample input 2","content":"2\n1 3 2 4\n4 3 2 1"},{"iden":"sample output 2","content":"\\-1\n\nNo $S$ satisfies the conditions."},{"iden":"sample input 3","content":"3\n2 1 5 3 4 6\n6 5 3 4 2 1"},{"iden":"sample output 3","content":"\\-1"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}