XOR
Consider an array AAA with n elements . Each of its element is A[i]A[i]A[i] (1≤i≤n)(1 le i le n)(1≤i≤n) . Then gives two integers QQQ, KKK, and QQQ queries follow . Each query , give you LLL, RRR, you can get ZZZ by the following rules.
To get ZZZ , at first you need to choose some elements from A[L]A[L]A[L] to A[R]A[R]A[R] ,we call them A[i1],A[i2]…A[it]A[i_1],A[i_2]…A[i_t]A[i1],A[i2]…A[it] , Then you can get number Z=KZ = KZ=K or (A[i1]A[i_1]A[i1] xor A[i2]A[i_2]A[i2] … xor A[it]A[i_t]A[it]) .
Please calculate the maximum ZZZ for each query .
Input
Several test cases .
First line an integer TTT (1≤T≤10)(1 le T le 10)(1≤T≤10) . Indicates the number of test cases.Then TTT test cases follows . Each test case begins with three integer NNN, QQQ, KKK (1≤N≤10000, 1≤Q≤100000, 0≤K≤100000)(1 le N le 10000, 1 le Q le 100000 , 0 le K le 100000)(1≤N≤10000, 1≤Q≤100000, 0≤K≤100000) . The next line has NNN integers indicate A[1]A[1]A[1] to A[N]A[N]A[N] (0≤A[i]≤108)(0 le A[i] le 10^8)(0≤A[i]≤108). Then QQQ lines , each line two integer LLL, RRR (1≤L≤R≤N)(1 le L le R le N)(1≤L≤R≤N) .
Output
For each query , print the answer in a single line.
样例输入
1 5 3 0 1 2 3 4 5 1 3 2 4 3 5
样例输出
3 7 7
分析：线段树维护区间线性基；
或一个数可以预处理的时候直接把有1的那些位屏蔽掉；
现场做不出来，果然还是因为太菜了呢。。