括号序列是优雅平衡的完美典范。这里我们讨论由 '(' 和 ')' 组成的括号序列。例如，“(())”、“()(())” 都是合法的平衡括号序列。

更正式地，一个括号序列是合法的，当且仅当它可以通过以下规则构造：

• “()” 是一个合法的括号序列。
• 如果 $A$ 是一个合法的括号序列，那么 $(A)$（即在 $A$ 前面加一个左括号，后面加一个右括号）也是一个合法的括号序列。
• 如果 $A, B$ 是合法的括号序列，那么 $AB$（即连接它们）也是一个合法的括号序列。

今天 Sayu 在和你玩一个游戏。她有一个长度为 $n$ 的合法括号序列 $S$，你可以向她询问：“$S$ 从第 $l$ 个字符到第 $r$ 个字符的子串中，左括号数量与右括号数量的差是多少？”，然后 Sayu 会告诉你答案。

你希望通过上述方法确定这个括号序列。然而，玩了一会儿后，Sayu 溜走去睡觉了。“任务完成！我可以回去睡觉了吗？”

你希望根据已知的询问推导出一个可能的合法括号序列。由于 Sayu 很困，你可能会发现询问中存在矛盾，这种情况下你应该报告无解。

输入格式

第一行包含两个整数 $n, q$ ($2 \le n \le 3000, 0 \le q \le \min(\frac{n+1}{2}, 5 \times 10^5)$)，分别表示括号序列的长度和已知询问的数量。

在接下来的 $q$ 行中，第 $i$ 行包含三个整数 $l_i, r_i, c_i$ ($1 \le l_i \le r_i \le n, -n \le c_i \le n$)，表示第 $i$ 个询问的区间 $q_i = [l_i, r_i]$，且该询问的答案为 $c_i$，即区间内左括号数量减去右括号数量的值。

保证 $n$ 是偶数，且询问的区间各不相同。

输出格式

如果没有合法的解，输出 “?”。

否则，输出 “! S”，其中 $S$ 是一个符合输入条件的合法括号序列。

样例

输入 1

4 1
1 2 0

输出 1

! ()()

输入 2

4 1
1 2 2

输出 2

! (())

输入 3

2 2
1 1 1
2 2 -1

输出 3

! ()

输入 4

2 1
1 1 2

输出 4

?

输入 5

4 0

输出 5

! (())

说明

对于第一个和第二个测试用例，长度为 4 的合法括号序列只有 “(())” 和 “()()”。通过询问包含前两个字符的子串，可以区分这两个不同的子串，因为答案分别为 2 和 0。