该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem Description

为什么出题人那么热衷于出和括号有关的题呢？

本题为交互题。

给定一个长度为 $2n$ 的正则括号序列 $s$。

系统暗中选定一个位置 $p$（$1 \le p \le 2n$），将该位置的字符翻转——`(` 变成 `)` 或 `)` 变成 `(`。翻转后的串记为 $t$。你不知道 $p$ 的值。

你可以向系统提出询问。每次询问需指定两个字符串 $s_1, s_2$ 和一个区间 $[l, r]$，格式如下：

系统会将 $s_1$、$t[l \ldots r]$、$s_2$ 顺次拼接，然后回答该拼接串是否为正则括号序列（`YES` 或 `NO`）。

你需要找出 $p$。每组数据至多进行 $15$ 次询问。

仅由 `(` 和 `)` 构成的字符串称为正则括号序列（balanced bracket sequence），当且仅当满足以下归纳定义：

$\quad$· 空串 $\varepsilon$ 是正则括号序列；

$\quad$· 若 $A$ 是正则括号序列，则 $\texttt{(} A \texttt{)}$ 也是正则括号序列；

$\quad$· 若 $A, B$ 都是正则括号序列，则 $AB$ 也是正则括号序列。

Input Format

第一行一个整数 $T$（$1 \le T \le 1000$），表示测试数据组数。

对于每组数据：

第一行一个整数 $n$（$2 \le n \le 5000$）。

第二行一个长度为 $2n$ 的字符串 $s$，保证 $s$ 是正则括号序列。

保证所有数据满足 $\sum n \le 5000$。

Output Format

每组数据中，你可以进行至多 $15$ 次询问。每次询问输出一行：

其中 $s_1, s_2$ 是仅由 `(` 和 `)` 组成的非空字符串，且 $1 \le |s_1|, |s_2| \le 2n$；$l, r$ 是下标，满足 $1 \le l \le r \le 2n$。四个部分以空格分隔。

系统收到询问后，回答一行 `YES` 或 `NO`。

当你确定答案后，输出：

表示被翻转的位置。此行不计入询问次数。

每组数据处理完毕后请立即进入下一组。若询问次数超过 $15$、询问格式有误或答案错误，系统将回答 $-1$；收到 $-1$ 后你必须立即终止程序。

你在每次输出查询语句换行后，可以使用如下代码刷新缓冲区：

C++ 使用 fflush(stdout)；

Java 使用 System.out.flush()；

Python 使用 stdout.flush()；

Pascal 使用 flush(output)；

其它语言请参考相关文档。

1
2
(())

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

Hint

$n = 2$，$s = \texttt{(())}$，系统翻转位置 $2$（`(` 变 `)`），得到 $t = \texttt{()))}$。

选手输出 | 系统应答 | 说明

:--- | :--- | :---

`? ( 1 2 )))` | `NO` | 拼接 $\texttt{(} + t[1, 2] + \texttt{)))} = \texttt{(()))}$ 不是正则括号序列，故 $p \in [1, 2]$

`? ((( 3 4 )` | `YES` | 拼接 $\texttt{(((} + t[3, 4] + \texttt{)} = \texttt{((()))}$ 是正则括号序列，故 $p \notin [3, 4]$

`! 2` | | 结合两次结果得 $p=2$