CFCF2174E2.Game of Scientists (Version 2)

两个版本对 $k$ 和 $c$ 有不同的限制。解决其中一个版本不一定能解决另一个版本。你可能需要阅读两个版本。两个版本均不支持 Hack。

本题为交互题。

在奥斯曼帝国时期，许多科学家致力于科研。你决定研究他们的日常生活，偶然发现了当时流行的一种有趣游戏。其中一位科学家会想一个整数 $x$，满足 $1 \leq x \leq c$。另一位科学家需要猜出这个数。他能够指定一个进制 $2 \leq b \leq c$，系统会返回 $x$ 在 $b$ 进制下各位数字之和（如果 $x \geq b$），如果 $x < b$ 则返回 $-1$。

你已经写好了一个可以随机选数并应答的程序。现在你想和它对弈，并且需要在不超过 $k$ 次询问内猜出答案。

第一行包含三个整数 $t$、$k$、$c$（$1 \leq t \leq 10^4$，$\mathbf{k=3}$，$\mathbf{c=2\cdot10^9}$）。你需要在 $t$ 次游戏中，每次在 $1$ 到 $c$ 的范围内猜出某个隐藏的数。每一局最多可以进行 $k$ 次询问，所有局独立进行，顺序连续。

（省略，因原题未给具体输出格式）

在第一局中，隐藏的数为 $1000000_{10} = 100_{1000} = 11110100001001000000_2$。在这些进制下各位之和分别是 $1$、$1$ 和 $7$。

第二局中，隐藏数为 $1$。当你用 $b=2$ 查询时会返回 $-1$。

第三局中，隐藏数为 $42_{10} = 132_{5}$。