You have an array: a1, a2, , an and you must answer for some queries. For each query, you are given an interval [L, R] and two numbers p and K. Your goal is to find the Kth closest distance between p and aL, aL+1, ..., aR. The distance between p and ai is equal to |p - ai|. For example: A = {31, 2, 5, 45, 4 } and L = 2, R = 5, p = 3, K = 2. |p - a2| = 1, |p - a3| = 2, |p - a4| = 42, |p - a5| = 1. Sorted distance is {1, 1, 2, 42}. Thus, the 2nd closest distance is 1.
Input
The first line of the input contains an integer T (1 <= T <= 3) denoting the number of test cases. For each test case: 冘The first line contains two integers n and m (1 <= n, m <= 10^5) denoting the size of array and number of queries. The second line contains n space-separated integers a1, a2, ..., an (1 <= ai <= 10^6). Each value of array is unique. Each of the next m lines contains four integers L', R', p' and K'. From these 4 numbers, you must get a real query L, R, p, K like this: L = L' xor X, R = R' xor X, p = p' xor X, K = K' xor X, where X is just previous answer and at the beginning, X = 0. (1 <= L < R <= n, 1 <= p <= 10^6, 1 <= K <= 169, R - L + 1 >= K).
Output
For each query print a single line containing the Kth closest distance between p and aL, aL+1, ..., aR.