我没有通过你的code详细了，但你似乎有环比R = p的范围 - 1;为r q - 1; - [R ++和这将是很好不会有这样做。

由于AI，我们要找出在给定的范围内尽可能多的最高位AI的逆尽可能喜的值。一切都是从0到2 ^ 15，所以不会有太多的比特担心。对于n = 1〜15可以根据其N最高位划分十一起来，所以把它分为2，4，8，16 .. 32768部。对于每一个部分保持一个列表在发现每个可能值的位置排序顺序，所以对于最高位，你将有两个列表，给处的位置的位模式为0 ......... .....和一个定案的位模式为1 ............对于每个三联，您可以使用二进制印章上的一个特定部分，以寻找是否有内任何位置的位置你的范围时，前n位中有你正在寻找的位模式。如果他们这样做，挺好的。如果没有，你将不得不接受的是，异或位置之一为0，稍微修改你找多一个最高位设置模式。

的设置成本是15线越过喜，这可能是低于它把你读它的时候。对于每一行，你可以做15二进制印章看到这顶n位值喜的比赛，和修改顶位你看看，如果你不能匹配特定位的模式。

我想，如果你通过问题codeA独立的子程序分开的问题，code中的I / O程序会更清晰。这也将使其更容易的问题，code一个版本比较与另一个，看看这是更快，如果他们都得到了相同的答案。

I came up with this question.

There is an encryption algorithm which uses bitwise XOR operations extensively. This encryption algorithm uses a sequence of non-negative integers x₁, x₂, ... x_n as key. To implement this algorithm efficiently, Xorq needs to find maximum value for (a xor x_j) for given integers a, p and q such that p <= j <= q. Help Xorq to implement this function.

Input

First line of input contains a single integer T (1<=T<=6). T test cases follow.

First line of each test case contains two integers N and Q separated by a single space (1 <= N <= 100,000; 1 <= Q <= 50,000). Next line contains N integers x₁, x₂, ... x_n separated by a single space (0 <= x_j < 215). Each of next Q lines describe a query which consists of three integers a_i, p_i and q_i (0 <= a_i < 215, 1<= p_i <= q_i <= N).

Output

For each query, print the maximum value for (a_i xor x_j) such that p_i <= j <= q_i in a single line.

Sample Input

1
15 8
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
10 6 10
1023 7 7
33 5 8
182 5 10
181 1 13
5 10 15
99 8 9
33 10 14

Sample Output

13
1016
41
191
191
15
107
47

Explanation

First Query (10 6 10): x6 xor 10 = 12,
    x7 xor 10 = 13, x8 xor 10 = 2, x9 xor 10 = 3, x10 xor 10 = 0,
    therefore answer for this query is 13.
Second Query (1023 7 7): x7 xor 1023 = 1016,
    therefore answer for this query is 1016.
Third Query (33 5 8): x5 xor 33 = 36, x6 xor 33 = 39,
    x7 xor 33 = 38, x8 xor 33 = 41, therefore answer for this query is 41.
Fourth Query (182 5 10): x5 xor 182 = 179,
    x6 xor 182 = 176, x7 xor 182 = 177, x8 xor 182 = 190,
    x9 xor 182 = 191, x10 xor 182 = 188,
    therefore answer for this query is 191.

I tried this by first making the numbers length(in binary) in the given range equal and then comparing 'a' bit by bit with the particular xj values.But it is time exceeding. Maximum time limit in java is 5sec.

I haven't gone through your code in detail, but you seem to have loops over the range of r = p - 1; r < q - 1; r++, and it would be nice not to have to do this.

Given ai, we want to find a value of xi in the given range with as many of its top bits the inverse of ai as possible. Everything is between 0 and 2^15, so there aren't many bits to worry about. For n = 1 to 15 you could divide the xi up according to its n highest bits, so dividing it into 2, 4, 8, 16.. 32768 portions. For each portion keep a list in sorted order of the positions where each possible value is found, so for the top bit you will have two lists, one giving the positions at which the bit pattern is 0.............. and one giving the position at which the bit pattern is 1............ For each triple, you can use binary chop on a particular portion to find if there are any positions within your range at which the top n bits have the bit pattern you are looking for. If they do, fine. If not you will have to accept that one of the xor positions is 0 and slightly modify the pattern you look for with one more top bit set.

The setup cost is 15 linear passes over the xi, which is probably less time than it takes you to read it in. For each line you could do 15 binary chops to see which values of xi match in the top n bits, and modify the pattern of top bits you look for if you can't match a particular bit.

I think your program would be clearer if you separated the I/O from the problem code by making the problem code a separate subroutine. This would also make it easier to compare one version of the problem code with another, to see which is faster and if they both get the same answer.