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

Input	Output
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$.