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.

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.