An Array and XOR

Execution time limit is 4 seconds

Runtime memory usage limit is 512 megabytes

Given an integer $m$ , an array $a$ of non-negative integers of length $n$ , and $q$ queries of the form $l_{i}$ , $r_{i}$ . All elements of array $a$ are less than $2^{m}$ .

Let us define the function $f_{i} (x) = min_{j \in [l_{i}, r_{i}]} (a_{j} \oplus x)$ , where $\oplus$ denotes the bitwise exclusive OR operation. For each query, you need to find the value $max_{x \in {0, 1, \dots, 2^{m} - 1}} f_{i} (x)$ .

Bitwise exclusive OR of non-negative integers $a$ and $b$ $(a \oplus b)$ equals a non-negative integer that has a 1 in a certain position in its binary representation if and only if the binary representations of $a$ and $b$ have different values in that position. For example, $3_{10} \oplus 5_{10} = 001 1_{2} \oplus 010 1_{2} = 011 0_{2} = 6_{10}$ .

Input

The first line contains three integers $n$ , $q$ , $m$ ( $1 \leq n \leq 1 0^{5}$ , $1 \leq q \leq 5 \cdot 1 0^{5}$ , $1 \leq m \leq 50$ ), representing the length of the array, the number of queries, and the limit on the elements of the array, respectively.

The second line contains $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ ( $0 \leq a_{i} < 2^{m}$ ), representing the elements of the array.

The following $q$ lines each contain two integers $l_{i}$ and $r_{i}$ ( $1 \leq l_{i} \leq r_{i} \leq n$ ), representing the parameters of the $i$ -th query.

Output

For each $i$ -th query, output a single integer on a separate line — the value of $max_{x \in {0, 1, \dots, 2^{m} - 1}} f_{i} (x)$ .

Examples

Input #1

Answer #1

Note

The first query.

$f_{1} (0) = min (1 \oplus 0, 3 \oplus 0, 2 \oplus 0, 7 \oplus 0, 1 \oplus 0) = min (1, 3, 2, 7, 1) = 1$

$f_{1} (1) = min (1 \oplus 1, 3 \oplus 1, 2 \oplus 1, 7 \oplus 1, 1 \oplus 1) = min (0, 2, 3, 6, 0) = 0$

$f_{1} (2) = min (1 \oplus 2, 3 \oplus 2, 2 \oplus 2, 7 \oplus 2, 1 \oplus 2) = min (3, 1, 0, 5, 3) = 0$

$f_{1} (3) = min (1 \oplus 3, 3 \oplus 3, 2 \oplus 3, 7 \oplus 3, 1 \oplus 3) = min (2, 0, 1, 4, 2) = 0$

$f_{1} (4) = min (1 \oplus 4, 3 \oplus 4, 2 \oplus 4, 7 \oplus 4, 1 \oplus 4) = min (5, 7, 6, 3, 5) = 3$

$f_{1} (5) = min (1 \oplus 5, 3 \oplus 5, 2 \oplus 5, 7 \oplus 5, 1 \oplus 5) = min (4, 6, 7, 2, 4) = 2$

$f_{1} (6) = min (1 \oplus 6, 3 \oplus 6, 2 \oplus 6, 7 \oplus 6, 1 \oplus 6) = min (7, 5, 4, 1, 7) = 1$

$f_{1} (7) = min (1 \oplus 7, 3 \oplus 7, 2 \oplus 7, 7 \oplus 7, 1 \oplus 7) = min (6, 4, 5, 0, 6) = 0$

The answer to this query is equal to $max_{x \in {0, 1, \dots, 2^{3} - 1}} f_{1} (x) = max (1, 0, 0, 0, 3, 2, 1, 0) = 3$ .

Scoring

( $4$ points): $n \leq 100$ , $q \leq 100$ , $m \leq 10$ ;
( $17$ points): $q = 1$ , $l_{1} = 1$ , $r_{1} = n$ ;
( $16$ points): $q \leq 2 \cdot 1 0^{5}$ ; $a_{i} \leq a_{i + 1}$ for $1 \leq i < n$ ;
( $17$ points): $n \leq 1 0^{4}$ , $q \leq 1 0^{4}$ ;
( $26$ points): $n \leq 5 \cdot 1 0^{4}$ , $m \leq 30$ ;
( $20$ points): no additional constraints.