Efa hates numbers. But she loves the XOR operation. This time, you have to solve another problem for her.
You are given a sequence of integers and queries. In each query, you are given four integers , , and . Let be a length subsequence of the segment . Print the maximum value of among all possible and the number of such subsequences that maximizes the value of . Since the number of subsequences can be large, print it modulo .
Here, 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.
The first line of input contains two space-separated integers and denoting the number of integers and the number of queries.
The next line contains space-separated integers .
Following lines contain four integers each. , , and .
For each query, print two space-separated integers. The maximum value and the number of subsequences as described above.
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 has three subsequences of length . , and .
For the first subsequence: .
For the second subsequence: .
For the third subsequence: .
So, the maximum value of is and the number of such subsequences is .