# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# XOR Is Fun

By adnan_toky · 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 $a_1,~a_2,~a_3,~…,~a_n$ of $n$ integers and $q$ queries. In each query, you are given four integers $l$, $r$, $k$ and $x$. Let $s$ be a $k$ length subsequence of the segment $a_l,~a_{l+1},~a_{l+2},~…,~a_r$. Print the maximum value of $\sum\limits_{i=1}^{k} {s_i \oplus x}$ among all possible $s$ and the number of such subsequences that maximizes the value of $\sum\limits_{i=1}^{k} {s_i \oplus x}$. Since the number of subsequences can be large, print it modulo $10^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 $n$ and $q$ $(1 \leq n, q \leq 10^5)$ denoting the number of integers and the number of queries.

The next line contains $n$ space-separated integers $a_1, ~a_2, ~a_3,~…, ~a_n$​ $(1 \leq a_i \leq 10^9)$.

Following $q$ lines contain four integers each. $l$$r$ $(1 \leq l \leq r \leq n)$, $k$ $(1 \leq k \leq r-l+1)$ and $x$ $(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\}$ has three subsequences of length $2$. $\{2, 1\}$, $\{2, 2\}$ and $\{1, 2\}$.

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

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

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

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

### Statistics

44% Solution Ratio

rfpermenEarliest, 1M ago

MrBrionixFastest, 0.4s

Soumya1Shortest, 2702B