XOR Is Fun

adnan_toky Tough Duo, April 2022
Limits 2s, 1.0 GB

Efa hates numbers. But she loves the XOR operation. This time, you have to solve another problem for her.

You are given a sequence a1, a2, a3, , ana_1,~a_2,~a_3,~…,~a_n of nn integers and qq queries. In each query, you are given four integers ll, rr, kk and xx. Let ss be a kk length subsequence of the segment al, al+1, al+2, , ara_l,~a_{l+1},~a_{l+2},~…,~a_r. Print the maximum value of i=1ksix\sum\limits_{i=1}^{k} {s_i \oplus x} among all possible ss and the number of such subsequences that maximizes the value of i=1ksix\sum\limits_{i=1}^{k} {s_i \oplus x}. Since the number of subsequences can be large, print it modulo 109+710^9+7.

Here, \oplus denotes the bitwise XOR operation.

A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.

Input

The first line of input contains two space-separated integers nn and qq (1n,q105)(1 \leq n, q \leq 10^5) denoting the number of integers and the number of queries.

The next line contains nn space-separated integers a1, a2, a3, , ana_1, ~a_2, ~a_3,~…, ~a_n​ (1ai109)(1 \leq a_i \leq 10^9).

Following qq lines contain four integers each. llrr (1lrn)(1 \leq l \leq r \leq n), kk (1krl+1)(1 \leq k \leq r-l+1) and xx (1x109)(1 \leq x \leq 10^9).

Output

For each query, print two space-separated integers. The maximum value and the number of subsequences as described above.

Sample

InputOutput
5 3
2 1 2 4 3
1 3 2 7
1 3 2 5
1 5 3 5
11 2
14 1
20 1

In the first query, the sequence {2,1,2}\{2, 1, 2\} has three subsequences of length 22. {2,1}\{2, 1\}, {2,2}\{2, 2\} and {1,2}\{1, 2\}.

For the first subsequence: (27)+(17)=11(2 \oplus 7) + (1 \oplus 7) = 11.

For the second subsequence: (27)+(27)=10(2 \oplus 7) + (2 \oplus 7) = 10.

For the third subsequence: (17)+(27)=11(1\oplus 7) + (2 \oplus 7) = 11.

So, the maximum value of i=1ksix\sum\limits_{i=1}^{k} {s_i \oplus x} is 1111 and the number of such subsequences is 22.


Submit

Login to submit.

Statistics

50% Solution Ratio
rfpermenEarliest, 5M ago
MrBrionixFastest, 0.4s
adnan_tokyLightest, 530 MB
Soumya1Shortest, 2702B
Toph uses cookies. By continuing you agree to our Cookie Policy.