An Array and XOR#229

An Array and XOR

4 seconds

512 megabytes

Hard

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

Let us define the function $f_{i} (x) = min_{j \in [l_{i}, r_{i}]} (a_{j} \oplus x)$ 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)$ \max_{x \in \{0, 1, \ldots, 2^m-1\}} f_i(x).

Bitwise exclusive OR of non-negative integers $a$ and $b$ $(a \oplus 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}$ 3_{10} \oplus 5_{10} = 0011_{2} \oplus 0101_{2} = 0110_{2} = 6_{10}.

Input

The first line contains three integers $n$ , $q$ , $m$ ( $1 \leq n \leq 1 0^{5}$ 1 \le n \le 10^5, $1 \leq q \leq 5 \cdot 1 0^{5}$ 1 \le q \le 5 \cdot 10^5, $1 \leq m \leq 50$ 1 \le m \le 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}$ a_1, a_2, \ldots, a_n ( $0 \leq a_{i} < 2^{m}$ 0 \le a_i < 2^m), representing the elements of the array.

The following $q$ lines each contain two integers $l_{i}$ l_i and $r_{i}$ r_i ( $1 \leq l_{i} \leq r_{i} \leq n$ 1 \le l_i \le r_i \le 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)$ \max_{x \in \{0, 1, \ldots, 2^m-1\}} f_i(x).

Examples

Example 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(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(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(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(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(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(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(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$ 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$ \max_{x \in \{0, 1, \ldots, 2^3-1\}} f_1(x) = \max(1, 0, 0, 0, 3, 2, 1, 0) = 3.

Scoring

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