CF2119C A Good Problem

[Juggernaut. - Lost Dream feat.星名はる](https://www.youtube.com/watch?v=TCckJwjMGcc) 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](https://en.wikipedia.org/wiki/Bitwise_operation#AND) and $ \oplus $ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). 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 $ .

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} $ ).

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

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.