fork()==0世界线变动

您拥有一个整数 $k$，以及一个由字符 a 与字符 * 组成的长度为 $n$ 的字符串。

在这其中，每一个星号都必须替换成 $0\sim k$ 个字符 b，在所有的星号替换完成后，得到的字符串我们称为 BA-String。

请您求出给定字符串所转化出的字典序第 $x$ 小的 BA-String。

本题采用多组数据，数据组数为 $T$。

$1⩽T,n,k⩽2000$

$1⩽x⩽{10}^{18}$

给出$n$个数，定义一个数列是好的当且仅当$a_i\ne a_{i-1}$

你可以通过调整数的大小来把一个数列变成好的，将一个位置$i$上的数$+1$需要的花费是$b_i$，问：最小的花费

有$q$组询问，保证$\sum _{i=1}^q{n}_i\le 3\times {10}^5$，答案在$longlong$范围内

交互题，系统有两个整数 $(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\le 50,1\le a<m\le {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\le 5\times {10}^4$

第一行输出测试点总数 $T$。

之后每一行一个字符串 $s$ 表示替换掉部分字符后的合法括号序列。