Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.
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.
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 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 . |
44% Solution Ratio
rfpermenEarliest,
MrBrionixFastest, 0.4s
adnan_tokyLightest, 530 MB
Soumya1Shortest, 2702B
Login to submit
Let's solve the problem for the whole sequence instead of a given range. We can store each number i...