题目描述

给出四个非负整数 $l, r, k, x$。你需要找到任意一个整数 $n$ 满足 $l \le n \le r$ 且 $\bigoplus\limits_{i=k}^n i = x$。其中，$\bigoplus\limits_{i=k}^n i$ 表示 $k \sim n$ 中所有整数的二进制按位异或和。

如有多解，求出任何一个均可。如果无解，请输出 $-1$。

答案不唯一，评测使用 Special Judge 校验输出是否合法。

输入格式

本题有多组测试数据。

第一行，一个正整数 $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

提示

【数据范围】

对于 $100\%$ 的数据，保证 $1 \le T \le 10^5$，$1 \le k \le l \le r \le 10^9$，$0 \le x \le 2 \times 10^9$。