CF2037E Kachina's Favorite Binary String

这是一道交互题。 卡齐娜有一个长为 $n$ 的 01 串 $s$。她定义 $f(l,r)$ 为子段 $s_ls_{l+1}\cdots s_r$ 中等于 $\texttt{01}$ 的子序列的个数。子序列不要求连续；两个位置不同的子序列被认为是 **不同** 的，即便它们含有相同的字符序列。 你需要通过向卡齐娜提问来猜出 $s$。每次提问，你可以选择两个下标 $l,r(1\le l < r\le n)$，询问她 $f(l,r)$ 的值。你最多提问 $n$ 次。如果 $s$ 不可能在 $n$ 次询问内确定，输出 $\texttt{IMPOSSIBLE}$。

第一行一个整数 $t(1\le t\le 10^3)$ — 测试数据的组数。 每组测试数据一行一个整数 $n(2\le n\le 10^4)$ — 01 串 $s$ 的长度。 保证各组测试数据 $n$ 的总和不超过 $10^4$。

每次提问，按照以下格式输出一行（不含括号）： - $\texttt{? l r}(1\le l < r\le n)$ 测试程序会返回一个整数 $f(l,r)$。当你确定答案后，按照以下格式输出一行： - 如果 $s$ 无法确定，输出 $\texttt{"! IMPOSSIBLE"}$ - 否则输出 $\texttt{"! s"}$ 输出答案不算一次提问。

**第一个样例：** 第一次提问中，你询问卡齐娜 $f(1,5)$ 的值，她向输入流中返回 $4$。 第二次提问中，你询问卡齐娜 $f(2,4)$ 的值。因为在 $\texttt{100}$ 中没有等于 $\texttt{01}$ 的子序列，她向输入流中返回 $0$。 提问四次后，你输出正确答案 $\texttt{01001}$。 **第二个样例：** 第一次提问中，你询问卡齐娜 $f(1,2)$ 的值，她向输入流中返回 $0$。 注意到你除了 $\texttt{? 1 2}$ 提不出别的问题了，但 01 串 $\texttt{00}$ 和 $\texttt{11}$ 的答案都是 $0$，无法确定唯一答案，所以输出 $\texttt{IMPOSSIBLE}$。 样例仅用于展示交互格式，不代表正解方法。