您拥有一个整数 $k$，以及一个由字符 a 与字符 * 组成的长度为 $n$ 的字符串。
在这其中，每一个星号都必须替换成 $0\sim k$ 个字符 b，在所有的星号替换完成后，得到的字符串我们称为 BA-String。
请您求出给定字符串所转化出的字典序第 $x$ 小的 BA-String。
本题采用多组数据，数据组数为 $T$。
$1\leqslant T,n,k\leqslant2000$
$1\leqslant x\leqslant10^{18}$
给出$n$个数，定义一个数列是好的当且仅当$a_{i}\ne a_{i-1}$
你可以通过调整数的大小来把一个数列变成好的，将一个位置$i$上的数$+1$需要的花费是$b_i$，问：最小的花费
有$q$组询问，保证$\sum_{i=1}^q n_i\le3\times10^5$，答案在$long\ long$范围内
交互题，系统有两个整数 $(a,b)$，你每次可以询问一组整数 $(c,d)$，系统会回答：
$1$ 如果 $a\oplus c>b\oplus d$
$0$ 如果 $a\oplus c=b\oplus d$
$-1$ 如果 $a\oplus c<b\oplus d$
其中操作 $a\oplus b$ 表示 $a$ 和 $b$ 按位异或
你需要在询问不超过 $62$ 次之后输出 $(a,b)$ 的值，保证 $0\le a, b < 2^{30}$。
输入格式：
请见“交互”
输出格式：
输出 ! a b 以输出答案，不要忘了在输出答案后清除缓冲区
输出 ? c d 以询问，$c$ 和 $d$ 都应该是小于 $2^{30}$ 的非负整数，不要忘了在输出每一次询问后清除缓冲区
你可以用下列操作来清除缓冲区：
C++：fflush(stdout)
Java：System.out.flush()
Python：stdout.flush()
Pascal：fflush(stdout)
对于其它语言请参考文档
求
$$\sum_{x=0}^{m-1} [\ \gcd(a, m) = \gcd(a + x, m)\ ]$$
多组测试数据, $T \leq 50,\ 1 \leq a < m \leq 10^{10}$
在一个 $[1,m]$ 的数轴上有 n 条线段，第 i 条覆盖了 $[l_i,r_i]$ 的区间，权值为 $w_i$ ，你的任务是从这些线段中选出若干条首尾相接线段覆盖整个数轴，使得这些线段权值极差最小化，输出这个极差
首尾相接的定义是，假设你有机会从同一条线段覆盖的任意两个点中移动，如果你可以从位置 1 出发，经过一些线段到达位置 m ，就称为这些线段首尾相接
一个人在一张有向图的 $1$ 号结点，他要去到 $n$ 结点。每条边 $(a_i,b_i)$ 有边权 $s_i$，表示走过这条边需要花 $s_i$ 元。这个人一开始有 $p$ 元，到了一个点 $u$，他可以进行若干次演出，每次演出收获 $w_u$ 元。问到达 $n$ 的最小演出次数，若无解输出 -1。
有个合法括号序列，部分字符被 ? 替换了，问是否存在唯一的一种填 ? 的方案，使得括号序列合法，即判断填 ? 使得括号序列合法的方案数是否等于1。存在唯一方案输出 YES，方案不唯一输出 NO
序列长度 $\sum n\le 2\times 10^5$，测试点数 $T\leq 5\times 10^4$
第一行输出测试点总数 $T$。
之后每一行一个字符串 $s$ 表示替换掉部分字符后的合法括号序列。