Bracket Query
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
Special Judge, 64bit IO Format: %lld

题目描述

输入描述:

见 PDF 题面

输出描述:

见 PDF 题面
示例1

输入

复制 
4 1
1 2 0

输出

复制 
! ()()
示例2

输入

复制 
4 1
1 2 2

输出

复制 
! (())
示例3

输入

复制 
2 2
1 1 1
2 2 -1

输出

复制 
! ()
示例4

输入

复制 
2 1
1 1 2

输出

复制 
?
示例5

输入

复制 
4 0

输出

复制 
! (())