阶_LCA

阶

一天，小灰在学习阶的求法时，在代码里写下了这样一句：

assert((a^b)%p==a%p);

调出来的小灰气急败坏，于是让你解决这个问题：$q$ 组询问 $a,p$，求最小的正整数 $b$ 使得 $(a\oplus b)\equiv a\pmod p$。

当然，善解人意的小灰不止会发牢骚，她还布置了额外的考验：对于 $type=1$ 的所有数据，每组询问你需要输出 $b_1,b_2$，表示在限定了 $a\oplus b_1\le a$ 和 $a\oplus b_2>a$ 的条件下，原问题的解，若不存在这样的 $b$，输出 $-1$。

如果你通过了小灰的额外考验，她就会在今年 $13$ 月 $14$ 日给你转 $1314$。

输入格式：第一行两个个整数 $type\in(0,1),q$，下面 $q$ 行每行两个整数 $a,p$。

$1\le q\le 10^5,3\le p\le 10^9+10,1\le a\le 10^{16}$，$p$ 是奇质数。

特殊性质1：保证 $a< p$。

（这是我出的一道题）

考虑异或的性质，$(a\oplus b)=a+kp$，则我们求 $b_1$ 就是求最小的 $a\oplus (a-kp)$，求 $b_2$ 就是求最小的 $a\oplus (a+kp)$。

首先考虑特殊性质 $a< p$，显然此时 $b_1$ 不存在。

考虑求 $b_2$，你发现 $k$ 如果太大了，导致 $a+kp$ 的最高位高于 $a+p$ 的最高位，那么由于 $a\oplus (a+kp)$ 的最高位已经不优，无需考虑此情况。

而剩下的只有 $O(1)$ 个 $k$，分别判断即可。

然后考虑正解，你发现加少量的 $p$ 有可能导致大量进位，此时可能再加一点是更优秀的，例如 $a$ 为二进制下的 $111111111$，$p$ 为 $3$，此时求 $b_2$ 就不能只加常数个 $p$。

考虑先 $a'\gets a+p$，然后从高往低位确定答案，若当前位目前为 $0$，且 $a$ 的这位是 $1$，且不断 $+p$ 可以在不影响高位的前提下加到该位为 $1$（这个可以利用除法计算），那么我们就加尽量少的 $p$ 到这个结果。

同理，求解 $b_1$ 时先 $a'\gets a-p$，从高往低计算，若当前位为 $1$，且 $a$ 的这位为 $0$，且不断 $-p$ 可以在不影响高位的前提下减到该位为 $0$，那么我们就减尽量少的 $p$ 到这个结果。

小惊喜：当 $type=0$ 时我们只需要求 $\min\{b_1,b_2\}$，此时我们感性理解会发现，如果加少量 $p$ 导致了大量进位产生了严重影响，那么减去少量的 $p$ 就不会导致这一点，枚举 $k\in[-5,5]\cap\mathbb Z\setminus\{0\}$，即可通过此部分。