先考虑求 $m$。

直接考虑二分判断一个 $\mathrm{mid}$ 的合法性，考虑对于每个 $\mathrm{mid}$ 在 $[1,\mathrm{mid}]$ 中随机若干次，那么当 $\mathrm{mid} < \frac{1}{c} \times m$ 的时候，平均符号变化一次的步数会和其它情况比出现显著变化，其中 $c$ 是一个 $[1+\epsilon,+\infty)$ 的常数，这是因为其它情况我们可以近似看作在 $0 \sim (m-1)$ 中随机并且加上一些扰动。

我们钦定 $c \in [1+\epsilon,2)$。

然后我们先瞎编一个合法的全套做法再继续。我们现在求出了一个大约在 $\frac{1}{c} m$ 左右的数，然后尝试用同样的手段去求解精确的 $m$。考虑如何确定一个合理的上界？注意到我们每次给当前 $m$ 的上界 $+ \frac{c-1}{c} m$ 的话，在 $\bmod m$ 意义下，一定不会超过原来的数，且会小上不少。这意味着，如果我们加出来了第一个 $\ge m$ 的数，那么我们模拟若干次加上当前上界的操作，符号变化次数一定会跳变。那么我们可以锁定一个更小的候选区间。

注意到有一个很优秀的性质：候选区间的“跳变”只有一次，这意味着我们可以直接利用同样的手法，在确定出的区间内去二分出 $m$。

至此我们编出了一个求解 $m$ 的做法。

那么下一步编一下 $x$ 怎么算。我们维护 $x$ 的候选区间 $[L,R]$，不难发现在 $m$ 确定的情况下，我们一定可以通过恰当的选取 $r$ 使得加上 $r$ 后 $[L,R]$ 会根据符号的不同分成两半，这部分是简单的，只需要 $\log m$ 次询问。

现在如果我们随机的 check 内部运行 $c_1$ 个数，二分 $m$ 的 check 内部运行 $c_2$ 个数，那么总操作次数是 $c_1 \log m + c_2 (\log m + O(1)) + \log m$。

但是看起来，$c_2$ 可以比较小，因为确定的数观察跳变显然只需要 $O(1)$ 次就行了。尝试减小 $c_1$。

编出一个更有意义的做法，我们考虑随机 $c_1$ 个数，我们计算符号两次 $<$ 之间的最小间隔，如果连续两次都是 $<$，那么我们认为这是普通的情况，否则是有显著变化的情况。以这个为依据进行二分，期望答案会略大于 $\frac 1 2 n$，那么完全满足条件，但是这样实际测试 $c_1$ 大约需要随机 $50$ 组才能保证足够的正确率，无法接受。我们考虑这种情况的产生原因是询问 $\mathrm{mid}$ 之后，有小概率出现假阴性。感性理解一下，考虑如何减少假阴性，我们考虑把判断条件改成两个 $<$ 之间最多空一个。我们而分出这个以后，对应的 $m$ 大致落在 $[1.5p, 3p)$，直接利用上面的判断方法，就可以直接二分出 $m$，这里的 $c_1$ 取 $30$ 就完全够了。

大概最大询问次数在 $1,800$ 次左右，足以通过本题。