410477: GYM104025 C Combination

Aqua and Hiyori love combination.

Today, Aqua has a sequence $$$a$$$ with length of $$$n$$$, and she wants to combine the sequence. She can get all $$$x$$$ which satisfies that there exists $$$\lbrace c_1,c_2,\cdots,c_n\rbrace,c_i \in \mathbb{N}$$$, and $$$x=\sum_{i=1}^n c_ia_i$$$. Hiyori decides to test Aqua, so she will set $$$q$$$ queries.

In each query, Hiyori will give Aqua two integers $$$A,B$$$. According to the answer of the last query called $$$\mathrm{lastans}$$$, the present query has two parameters $$$l=\min(A\oplus \mathrm{lastans},B\oplus \mathrm{lastans})$$$, $$$r=\max(A\oplus \mathrm{lastans},B\oplus \mathrm{lastans})$$$. Initially, $$$\mathrm{lastans}=0$$$.

Here $$$\oplus$$$ denotes bitwise XOR (exclusive-or).

Aqua should answer that how many numbers in $$$[l,r]$$$ has she got. But she is stupid, could you help her?

The first line contains two integers $$$n,q\ (1\leq n,q\leq 10^6)$$$, indicating the length of the sequence $$$a$$$ and the number of queries.

The second line contains $$$n$$$ integers $$$a_1,a_2,\cdots,a_n\ (2\leq a_i\leq 10^9)$$$.

The next $$$q$$$ lines, each line contains two integers $$$A,B\ (0\leq A,B\leq 10^{18})$$$, indicating a query. It is guaranteed that $$$n\times \min_{i=1}^n a_i\leq 10^6$$$.

Print $$$q$$$ lines. The $$$i$$$-th line the contains answer for the $$$i$$$-th query.

2 3
7 4
1 6
1 5
1 2

1
2
1

5 3
6 7 8 9 3
0 5
0 6
0 5

2
1
1