学生们正在准备参加一场四轴飞行器编程比赛。比赛中使用的四轴飞行器可以执行两条指令：向上飞行 1 米和向下飞行 1 米。向上指令用字符 ( 表示，向下指令用字符 ) 表示。

四轴飞行器的程序是一系列指令的序列。如果程序从地面开始执行，且在依次执行完所有指令后，四轴飞行器再次回到地面，则该程序被认为是正确的。此外，在程序执行过程中，四轴飞行器不得尝试降落到地面以下。

例如，以下程序是正确的：()(())，((()))。程序 ((( 是不正确的，因为四轴飞行器执行完后停留在地面上方 3 米处；程序 ())( 也是不正确的，因为在执行第三条指令时，四轴飞行器试图降落到地面以下。

一名参赛选手编写了一个由 $n$ 条指令组成的正确程序，指令编号从 $1$ 到 $n$。他将程序加载到四轴飞行器的内存中以供比赛期间演示。遗憾的是，在将程序加载到四轴飞行器后，选手不小心删除了自己电脑上的程序，而四轴飞行器不允许从其内存中导出程序。

幸运的是，四轴飞行器支持一种特殊的程序调试模式。在此模式下，加载了程序的四轴飞行器可以回答特定的查询。每个查询由两个整数 $l$ 和 $r$ 组成，$1 \le l \le r \le n$。作为回应，四轴飞行器会告知加载程序中从第 $l$ 条到第 $r$ 条指令（包含两端）组成的片段是否为正确的四轴飞行器程序。选手希望利用调试模式恢复加载在四轴飞行器中的程序。

你需要编写一个解决方案程序，与模拟四轴飞行器调试模式的评测程序进行交互，并最终恢复加载在四轴飞行器中的程序。

交互协议

这是一道交互题。

首先，输入一个整数 $n$ —— 四轴飞行器程序的指令数量（$2 \le n \le 50\,000$）。

对于每个测试点，评测程序固定了一个数字 $k$ —— 最大查询次数。保证 $k$ 次查询足以解决问题。该数字不会告知解决方案程序。不同子任务中 $k$ 的限制在评分标准表中给出。如果解决方案程序向评测程序发起的查询次数超过 $k$ 次，则该测试点将被判为“答案错误”。

要进行查询，解决方案程序必须输出一行格式为 ? l r 的字符串，其中 $l$ 和 $r$ 是指定四轴飞行器程序片段的正整数（$1 \le l \le r \le n$）。

作为对查询的响应，评测程序会输入一行字符串 Yes 或 No，具体取决于所查询的四轴飞行器程序片段是否为正确程序。

如果解决方案程序确定了问题的答案，则必须输出一行 ! c1c2...cn，其中字符 $c_i$ 指定四轴飞行器程序中的第 $i$ 条指令，且等于 ( 或 )。

在此之后，解决方案程序必须终止。

保证在每个测试点中，四轴飞行器内存中的程序是一个固定的正确程序，且不会根据解决方案程序发出的查询而改变。

样例

输入 1

4
Yes
No
Yes
Yes

输出 1

? 1 4
? 1 3
? 1 2
? 3 4
! ()()

输入 2

6
Yes
No
Yes

输出 2

? 3 4
? 1 2
? 2 5
! ((()))

说明

上述样例展示了解决方案程序与评测程序之间的“分步”交互过程。在实际测试中，不会输入额外的空行，也不需要输出空行。

在第一个样例中，$n=4$。由两条指令组成的唯一可能的正确程序是 ()，因此从第三次和第四次查询的结果可以推断出四轴飞行器内存中的程序是 ()()。因此，特别是对第二次查询的回答确实是 No，因为程序片段 ()( 不是一个正确的程序：如果四轴飞行器执行这三条指令，它将停留在地面上方一米处。

在第二个样例中，$n=6$，所进行的查询足以唯一确定四轴飞行器内存中的程序是 ((()))。

在题目给出的测试中，$k=150$，即允许进行不超过 150 次查询。

子任务