codeforces#P1732C1. Sheikh (Easy version)
Sheikh (Easy version)
Description
This is the easy version of the problem. The only difference is that in this version .
You are given an array of integers .
The cost of a subsegment of the array , , is the value , where , and ( stands for bitwise XOR).
You will have query. Each query is given by a pair of numbers , , where . You need to find the subsegment , , with maximum value . If there are several answers, then among them you need to find a subsegment with the minimum length, that is, the minimum value of .
Each test consists of multiple test cases. The first line contains an integer () — the number of test cases. The description of test cases follows.
The first line of each test case contains two integers and (, ) — the length of the array and the number of queries.
The second line of each test case contains integers () — array elements.
-th of the next lines of each test case contains two integers and () — the boundaries in which we need to find the segment.
It is guaranteed that the sum of over all test cases does not exceed .
It is guaranteed that and .
For each test case print pairs of numbers such that the value is maximum and among such the length is minimum. If there are several correct answers, print any of them.
Input
Each test consists of multiple test cases. The first line contains an integer () — the number of test cases. The description of test cases follows.
The first line of each test case contains two integers and (, ) — the length of the array and the number of queries.
The second line of each test case contains integers () — array elements.
-th of the next lines of each test case contains two integers and () — the boundaries in which we need to find the segment.
It is guaranteed that the sum of over all test cases does not exceed .
It is guaranteed that and .
Output
For each test case print pairs of numbers such that the value is maximum and among such the length is minimum. If there are several correct answers, print any of them.
Note
In the first test case, .
In the second test case, , . Note that , but we need to find a subsegment with the minimum length among the maximum values of . So, only segments and are the correct answers.
In the fourth test case, .
There are two correct answers in the fifth test case, since and their lengths are equal.