题目描述

给出四个非负整数 $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$ 中所有整数的二进制按位异或和。

如有多解，求出任何一个均可。如果无解，请指出。

输入格式

本题有多组测试数据。

第一行，一个正整数 $T$，表示数据组数。接下来，对于每组数据：

• 仅一行，四个非负整数 $l, r, k, x$。

输出格式

对于每组数据：

• 仅一行，一个整数，为你求出的 $n$；或当无解时输出 $-1$。

本题使用自定义校验器检验你的输出是否正确，故有解时你只需要求出任意一个满足条件的 $\bm n$。

样例

6
1 10 1 7
16 30 7 7
432327 42682357 114514 1
45445 473274 4741 280230
713243 34783411 114514 1919810
432754349 970503499 231891327 987305496

6
19
432327
-1
1919810
923498342

样例解释

对于第一组数据，取 $n = 6$，则 $1 \oplus 2 \oplus \cdots \oplus 6 = 7$，符合题意。可以证明，这是在 $[1, 10]$ 范围内唯一合法的解。

对于第二组数据，容易验证 $n = 19$ 是一组合法的解。此外，在 $[16, 30]$ 区间内，$n = 23$ 和 $n = 27$ 也合法，所以输出它们也正确。

数据范围

• 特殊性质 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$。