C. A Good Problem
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Juggernaut. - Lost Dream feat.星名はる

You are given four positive integers $$$n, l, r, k$$$. You need to find the lexicographically smallest$$$^{\text{∗}}$$$ array $$$a$$$ of length $$$n$$$, consisting of integers, such that:

  • For every $$$1 \leq i \leq n$$$, $$$l \leq a_i \leq r$$$.
  • $$$a_1 \, \& \, a_2 \, \& \, \ldots \, \& \, a_n = a_1 \oplus a_2 \oplus \ldots \oplus a_n$$$, where $$$\&$$$ denotes the bitwise AND operation and $$$\oplus$$$ denotes the bitwise XOR operation.

If no such array exists, output $$$-1$$$. Otherwise, since the entire array might be too large to output, output $$$a_k$$$ only.

$$$^{\text{∗}}$$$An array $$$a$$$ is lexicographically smaller than an array $$$b$$$ if and only if one of the following holds:

  • $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$; or
  • in the first position where $$$a$$$ and $$$b$$$ differ, the array $$$a$$$ has a smaller element than the corresponding element in $$$b$$$.
Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

Each test case contains four positive integers $$$n,l,r,k$$$ ($$$1 \le k \le n \le 10^{18}$$$, $$$1 \le l \le r \le 10^{18}$$$).

Output

For each test case, output $$$a_k$$$ or $$$-1$$$ if no array meets the conditions.

Example
Input
9
1 4 4 1
3 1 3 3
4 6 9 2
4 6 9 3
4 6 7 4
2 5 5 1
2 3 6 2
999999999999999999 1000000000000000000 1000000000000000000 999999999999999999
1000000000000000000 1 999999999999999999 1000000000000000000
Output
4
1
6
8
-1
-1
-1
1000000000000000000
2
Note

In the first test case, the array $$$a = [4]$$$. It can be proven that there is no array that meets the above requirements and has a smaller lexicographic order.

In the second test case, the array $$$a= [1,1,1]$$$. It can be proven that there is no array that meets the above requirements and has a smaller lexicographic order.

In the third test case and the fourth test case, the array $$$a = [6,6,8,8]$$$. It can be proven that there is no array that meets the above requirements and has a smaller lexicographic order.

In the fifth test case and the sixth test case, it can be proven that there is no array that meets the above requirements.