Given a sequence of non-negative integers $a_0, a_1, \dots, a_{n-1}$ of length $n$ ($1 \le n \le 6 \times 10^5$), where $0 \le a_i < 2^{30}$.

There are $q$ queries ($1 \le q \le 10^6$).

For each query, you are given two integers $l$ and $r$ ($0 \le l \le r < n$). Find the number of pairs of integers $(x, y)$ such that:

• $l \le x \le y \le r$;
• $\forall i, j \in S : i \oplus j \in S$, where $S := \{a_k\}_{k=x}^y$.

Implementation Details

Due to the large amount of data, you do not need to handle input and output. Please complete the init(int, int, vector<int>) and solve(int, int) functions in the following program and submit it.

void init(int n, int q, vector<int> a) {
  // implement...
}

long long solve(int l, int r) {
  // implement...
}

You can obtain the sample interaction library in the provided files.

Examples

Input 1

5 10 2
0000000001000020000300004

Output 1

4834712607666044912

Input 2

20 100 16500242824326557842
0000500006000070000800000000010000200003000040000000001000020000300004000090000:0000;0000<0000=0000>

Output 2

5449866856465492064

Subtasks

Idea: Powerless, Solution: ccz181078 & noip & w33z, Code: w33z, Data: w33z

For $100\%$ of the data, $1 \le n \le 6 \times 10^5$, $1 \le q \le 10^6$, $0 \le a_i < 2^{30}$, and $0 \le l \le r < n$.