阅读题面
推歌：はぐ
场切了，来写个题解。
sub 1
随便怎么做都能过。比较简单的一种做法是直接放 \(M\) 个 \(1\)，然后枚举。
sub 2
发现需要用一次询问区分 \(1\sim 3\)，容易想到对 \(2\) 做大小比较。但是直接放一个 \(2\) 可能无法准确定位到新放进去的 \(2\)，怎么办呢？把 \(2\) 拆成两个 \(1\)，这样这两个 \(1\) 一定是排在最前面的，而 \(d\) 一定在最后面，就可以用一次询问解决了。
sub 3
发现 \(2^{29}<10^9<2^{30}\)，考虑对 \(2\) 的幂次做二分。比较好想的是使用 \(\{a\}=\{2^0\sim 2^{29}\}\)，但是该怎么使用是个问题。
注意到如果没有加入 \(d\)，那么总有 \(2^0+\dots+2^{i-1}+1=2^{i}\)，考虑询问 \(S_1=\{a_0,\dots,a_{i-1}\},S_2=\{a_i\}\)。讨论 \(d\) 会在什么位置加入：
- \(d\ge 2^i\)：返回小于。
- \(1<d<2^i-1\)：返回大于。
- \(d=1\) 或 \(d=2^i-1\)：返回等于。
于是可以做到每次询问如果返回大于则把 \(d\) 所在区间长度减半，返回等于则询问是否为 \(1\)（可以取 \(S_1=\{a_0\},S_2=\{a_1\}\)），返回小于则可以转换为普通二分。于是可以在 \(\log\) 次内求出 \(d\)。
sub 4
看到这个 \(7\) 感觉很神秘。对着这个东西拟合一下发现 \(3^7=2187\)，很优美啊！
于是考虑如何用一次询问将区间长度除以三，这个东西应该是一个类似三分状物。我们可以使用 \(1\sim W+200\) 内全部的数各出现一次的 \(\{a\}\)。设当前的区间为 \((L,R]\)，为了方便初始时可以取 \(L=0,R=3^7\)。
取出 \((L,R]\) 的三等分点 \(x=\frac{2L+R}{3},y=\frac{L+2R}{3}\) 并考虑询问 \(S_1=\{x,y\},S_2=\{x+y\}\)，发现对于 \(L<d<x,x\le d< y,y\le d\le R\) 返回的结果是不一样的。于是就可以做到三分。
但是有时候 \(x+y>W+200\)，怎么办呢？我们发现可以取 \(c=\frac{R-L}{3}\)，每次考虑询问 \(S_1=\{L+c,L+2c\},S_2=\{L+3c,L\}\)，可以达到一样的效果。于是这道题就做完了。