Zeroing a Subsegment

This is a grader-based problem.

For an array of positive integers $b$ of length $m$, we define $f(b)$ as follows:

• Let a variable $x$ be initially $0$.
• For one coin, you are allowed to increase the value of $x$ by $1$.
• For one coin, you are allowed to choose an element of the array $b_i$ ($1 \le i \le m$) and replace it with $(b_i \oplus x)$, where $\oplus$ denotes the bitwise exclusive OR operation.
• $f(b)$ is the minimum number of coins required to make all elements of the array $b$ simultaneously equal to zero.

The bitwise exclusive OR of non-negative integers $a$ and $b$ ($a \oplus b$) is a non-negative integer whose binary representation has a one at a certain position if and only if the binary representations of $a$ and $b$ have different values at that position. For example, $3_{10} \oplus 5_{10} = 0011_2 \oplus 0101_2 = 0110_2 = 6_{10}$.

You are given an array of positive integers $a$ of length $n$ and $q$ queries of the form $l, r$. For each query, you need to find $f([a_l, a_{l+1}, \dots, a_r])$.

Interaction

You need to implement the following functions:

void init(integer n, array of integers a)

• $n$ — an integer denoting the length of the array;
• $a$ — an array of integers of length $n$;
• this function does not return anything.

integer ask(integer l, integer r)

• $l$ — an integer denoting the left boundary of the query;
• $r$ — an integer denoting the right boundary of the query;
• this function returns an integer — $f([a_l, a_{l+1}, \dots, a_r])$.

array of integers askAll(integer q, array of integers l, array of integers r)

• $q$ — an integer denoting the number of queries;
• $l$ — an array of integers of length $q$; $l_i$ denotes the left boundary of the $i$-th query;
• $r$ — an array of integers of length $q$; $r_i$ denotes the right boundary of the $i$-th query;
• this function returns an array of integers; the $i$-th number must be equal to the answer for the $i$-th query.

Input

The first line contains three integers $n, q$, and $t$ ($1 \le n, q \le 2 \cdot 10^5$; $1 \le t \le 2$) — the number of elements, the number of queries, and the query format, respectively.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i < 2^{60}$) — the elements of array $a$.

The next $q$ lines each contain two integers $l$ and $r$ ($1 \le l \le r \le n$) — the parameters of the $i$-th query.

The function init will be called exactly once. If $t = 1$, the function askAll will be called exactly once with all queries. If $t = 2$, the function ask will be called exactly $q$ times.

Output

The grader will output $q$ integers on separate lines — the answers to the queries.

Subtasks

1. (3 points): $t = 1$, $a_i = a_1$ for $1 \le i \le n$;
2. (8 points): $t = 1$, $a_i \neq a_j$ for $i \neq j$;
3. (3 points): $t = 1$, $2^m + n \le a_i < 2^{m+1}$ for some natural number $m$;
4. (9 points): $t = 1$, $a_i \le a_{i+1}$ for $1 \le i < n$;
5. (10 points): $t = 1$, $n, q \le 1000$;
6. (11 points): $t = 1$, $l_i = 1$ and $r_i = i$ for $1 \le i \le q$;
7. (10 points): $t = 1$, $n, q \le 50000$;
8. (25 points): $t = 1$;
9. (9 points): $t = 2$, $n, q \le 10^5$;
10. (12 points): $t = 2$.

Examples

Input 1

7 6 1
5 4 3 5 7 7 7
1 4
4 7
3 7
1 7
2 6
1 1

Output 1

9
11
12
14
12
6

Input 2

7 6 2
5 4 3 5 7 7 7
1 4
4 7
3 7
1 7
2 6
1 1

Output 2

9
11
12
14
12
6