P11798 【MX-X9-T2】『GROI-R3』XOR
题目描述
给出四个非负整数 $l, r, k, x$。你需要找到任意一个整数 $n$ 满足 $l \leq n \leq r$ 且 $\bigoplus\limits_{i=k}^n i = x$。其中，$\bigoplus\limits_{i=k}^n i$ 表示 $k \sim n$ 中所有整数的二进制按位异或和。
如有多解，求出任何一个均可。如果无解，请指出。
输入格式
无
输出格式
无
说明/提示
**【样例解释】**
对于第一组数据，取 $n = 6$，则 $1 \oplus 2 \oplus \cdots \oplus 6 = 7$，符合题意。可以证明，这是在 $[1, 10]$ 范围内唯一合法的解。
对于第二组数据，容易验证 $n = 19$ 是一组合法的解。此外，在 $[16, 30]$ 区间内，$n = 23$ 和 $n = 27$ 也合法，所以输出它们也正确。
**【数据范围】**
| 测试点编号 | $T \leq$ | $r \leq$ | 特殊性质 |
| :----------: | :----------: | :----------: | :----------: |
| $1\sim 4$ | $5000$ | $5000$ | |
| $5\sim 8$ | $10^5$ | $10^9$ | AB |
| $9\sim 14$ | $10^5$ | $10^9$ | A |
| $15\sim 20$ | $10^5$ | $10^9$ | |
- 特殊性质 A：保证 $k$ 为偶数。
- 特殊性质 B：保证 $x \leq 1$。
对于 $100\%$ 的数据，保证 $1 \leq T \leq 10^5$，$1 \leq k \leq l \leq r \leq 10^9$，$0 \leq x \leq 2\times 10^9$。