Problem Description

Consider an array $A$ with $n$ elements. Each of its elements is $A[i]$ ($1 \le i \le n$). Then two integers $Q$, $K$ are given, and $Q$ queries follow. For each query, you are given $L$, $R$. You can get $Z$ by the following rules.

To get $Z$, at first you need to choose some elements from $A[L]$ to $A[R]$, we call them $A[i_1], A[i_2], \dots, A[i_t]$. Then you can get number $Z = K$ or $(A[i_1] \text{ xor } A[i_2] \text{ xor } \dots \text{ xor } A[i_t])$.

Please calculate the maximum $Z$ for each query.

Input Format

Several test cases.

First line an integer $T$ ($1 \le T \le 10$). Indicates the number of test cases. Then $T$ test cases follow. Each test case begins with three integers $N$, $Q$, $K$ ($1 \le N \le 10000,\ 1 \le Q \le 100000,\ 0 \le K \le 100000$). The next line has $N$ integers indicating $A[1]$ to $A[N]$ ($0 \le A[i] \le 10^8$). Then $Q$ lines follow, each line contains two integers $L$, $R$ ($1 \le L \le R \le N$).

Output Format

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