题目描述

给定 $m$ 个区间，求长度为 $2n$ 的字典序最小的合法括号串，满足每个区间内至少有一个左括号。若无解，则输出 $-1$。

我们规定左括号的字典序小于右括号。

输入格式

本题包含多组测试数据。

第一行包含一个整数 $T$ $(1 \leq T \leq 10^5)$，代表测试数据数量。

对于每组输入数据，第一行输入两个正整数 $n, m$ $(1 \leq n, m \leq 10^5)$，分别表示需要构造的括号串的长度的一半，以及限制区间的个数。

接下来 $m$ 行，每行两个正整数 $l, r$ $(1 \leq l \leq r \leq 2n)$，表示构造的括号串需要满足区间 $[l,r]$ 中至少有一个左括号。

保证 $\sum n \leq 2 \cdot 10^5$，且 $\sum m \leq 4 \cdot 10^5$。

输出格式

对于每组输入数据，输出一个字符串，表示构造的字典序最小的合法括号串。若无解，输出$-1$。

输入输出样例 #1

输入 #1

3
2 2
1 2
3 4
3 4
1 1
2 2
3 3
4 4
5 3
2 4
3 9
7 10

输出 #1

()()
-1
(((())()))