Chef and Dancing Steps

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Majd Ajaj was one of the cochefs who got accepted in the new job. His job was simple, just taste the food, and provide reports about its quality. Pretty simple huh? he thought that too, until one day one of the other cochefs made a really spicy food, which made Majd's ears produce smoke like a train. The two of them got into a very bad fight that Chef decided to expel both of them.
When Majd tried to entreat Chef, he offered him a chance.
Chef gave Majd a catalog that contains N minidances D_{1}, D_{2}, ..., D_{N}, and an integer M. Chef will ask Majd Q queries. In each query Chef will give Majd two numbers L and R, and Majd has to calculate the following:
Consider the range [L, R] of minidances in the catalog, what is the smallest dance length that falls completely inside the range [L, R], and the logical XOR of its elements is no less than M?
A dance is defined as a consecutive segment of minidances. A dance that starts at minidance i, and ends at minidance j is defined as [i, j]. The length of a dance [i, j] is j  i + 1.
Although Majd is an exceptional taster, he is not that good at dancing. Could you please help him find the answer for each query? Or determine that it's impossible for some of them.
Input
The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains three space separated integers N, M and Q denoting the length of the array, the number given by Chef, and the number of queries respectively.
The second line of each test case contains N space separated integers D_{1}, D_{2}, ..., D_{N} denoting the minidances in the catalog.
Q lines follow. Each line contains two space separated integers L_{i} and R_{i} denoting the i^{th} query.
Output
For each test case print Q lines, where each line contains a single integer, denoting the answer to the corresponding query. If it's impossible for Majd to find a dance for the corresponding query, then simply print 1.
Constraints
 1 ≤ T ≤ 1000.
 1 ≤ N, Q ≤ 3*10^{5}.
 0 ≤ M ≤ 10^{9}.
 0 ≤ D_{i} ≤ 10^{9}.
 The sum of all N over all test cases doesn't exceed 3*10^{5}.
 The sum of all Q over all test cases doesn't exceed 3*10^{5}.
Example
Input: 2 3 7 2 1 2 4 1 3 2 3 3 3 3 1 2 3 1 2 1 3 2 2 Output: 3 1 2 1 1
Explanation
Example case 1: The test asks for the smallest dance whose value is greater than or equal to 7 .
The first query asks for the smallest dance which belongs to the interval [1, 3]. The possible dances are: { [1,1] [1,2] [1,3] [2,2] [2,3] [3,3]}, but only the dance [1, 3] is valid, whose value is 7.
For the second query, there is no valid dance that has a value greater than or equal to 7.
Example case 2: For the second query, the smallest valid dance is [3,3].
Author:  saeed_sryhini 
Tester:  kingofnumbers 
Tags  saeed_sryhini 
Date Added:  20102017 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 