2119C.md (2517B)
1 Source: https://codeforces.com/problemset/problem/2119/C 2 3 C. A Good Problem 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 [Juggernaut. - Lost Dream feat.星名はる](https://www.youtube.com/watch?v=TCckJwjMGcc) 22 23 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: 24 25 * For every $1 \leq i \leq n$, $l \leq a_i \leq r$. 26 * $a_1 \, \& \, a_2 \, \& \, \ldots \, \& \, a_n = a_1 \oplus a_2 \oplus \ldots \oplus a_n$, where $\&$ denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND) and $\oplus$ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). 27 28 If no such array exists, output $-1$. Otherwise, since the entire array might be too large to output, output $a_k$ only. 29 30 $^{\text{∗}}$An array $a$ is lexicographically smaller than an array $b$ if and only if one of the following holds: 31 32 * $a$ is a prefix of $b$, but $a \ne b$; or 33 * in the first position where $a$ and $b$ differ, the array $a$ has a smaller element than the corresponding element in $b$. 34 35 Input 36 37 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. 38 39 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}$). 40 41 Output 42 43 For each test case, output $a_k$ or $-1$ if no array meets the conditions. 44 45 Example 46 47 Input 48 49 ``` 50 9 51 52 1 4 4 1 53 54 3 1 3 3 55 56 4 6 9 2 57 58 4 6 9 3 59 60 4 6 7 4 61 62 2 5 5 1 63 64 2 3 6 2 65 66 999999999999999999 1000000000000000000 1000000000000000000 999999999999999999 67 68 1000000000000000000 1 999999999999999999 1000000000000000000 69 ``` 70 71 Output 72 73 ``` 74 4 75 1 76 6 77 8 78 -1 79 -1 80 -1 81 1000000000000000000 82 2 83 ``` 84 85 Note 86 87 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. 88 89 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. 90 91 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. 92 93 In the fifth test case and the sixth test case, it can be proven that there is no array that meets the above requirements.