codeforces#P1732C1. Sheikh (Easy version)

    ID: 33242 远端评测题 4000ms 256MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>binary searchbitmasksgreedytwo pointers*1800

Sheikh (Easy version)

Description

This is the easy version of the problem. The only difference is that in this version q=1q = 1.

You are given an array of integers a1,a2,,ana_1, a_2, \ldots, a_n.

The cost of a subsegment of the array [l,r][l, r], 1lrn1 \leq l \leq r \leq n, is the value f(l,r)=sum(l,r)xor(l,r)f(l, r) = \operatorname{sum}(l, r) - \operatorname{xor}(l, r), where sum(l,r)=al+al+1++ar\operatorname{sum}(l, r) = a_l + a_{l+1} + \ldots + a_r, and xor(l,r)=alal+1ar\operatorname{xor}(l, r) = a_l \oplus a_{l+1} \oplus \ldots \oplus a_r (\oplus stands for bitwise XOR).

You will have q=1q = 1 query. Each query is given by a pair of numbers LiL_i, RiR_i, where 1LiRin1 \leq L_i \leq R_i \leq n. You need to find the subsegment [l,r][l, r], LilrRiL_i \leq l \leq r \leq R_i, with maximum value f(l,r)f(l, r). If there are several answers, then among them you need to find a subsegment with the minimum length, that is, the minimum value of rl+1r - l + 1.

Each test consists of multiple test cases. The first line contains an integer tt (1t1041 \leq t \leq 10^4) — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers nn and qq (1n1051 \leq n \leq 10^5, q=1q = 1) — the length of the array and the number of queries.

The second line of each test case contains nn integers a1,a2,,ana_1, a_2, \ldots, a_n (0ai1090 \leq a_i \leq 10^9) — array elements.

ii-th of the next qq lines of each test case contains two integers LiL_i and RiR_i (1LiRin1 \leq L_i \leq R_i \leq n) — the boundaries in which we need to find the segment.

It is guaranteed that the sum of nn over all test cases does not exceed 21052 \cdot 10^5.

It is guaranteed that L1=1L_1 = 1 and R1=nR_1 = n.

For each test case print qq pairs of numbers LilrRiL_i \leq l \leq r \leq R_i such that the value f(l,r)f(l, r) is maximum and among such the length rl+1r - l + 1 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 tt (1t1041 \leq t \leq 10^4) — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers nn and qq (1n1051 \leq n \leq 10^5, q=1q = 1) — the length of the array and the number of queries.

The second line of each test case contains nn integers a1,a2,,ana_1, a_2, \ldots, a_n (0ai1090 \leq a_i \leq 10^9) — array elements.

ii-th of the next qq lines of each test case contains two integers LiL_i and RiR_i (1LiRin1 \leq L_i \leq R_i \leq n) — the boundaries in which we need to find the segment.

It is guaranteed that the sum of nn over all test cases does not exceed 21052 \cdot 10^5.

It is guaranteed that L1=1L_1 = 1 and R1=nR_1 = n.

Output

For each test case print qq pairs of numbers LilrRiL_i \leq l \leq r \leq R_i such that the value f(l,r)f(l, r) is maximum and among such the length rl+1r - l + 1 is minimum. If there are several correct answers, print any of them.

输入数据 1

6
1 1
0
1 1
2 1
5 10
1 2
3 1
0 2 4
1 3
4 1
0 12 8 3
1 4
5 1
21 32 32 32 10
1 5
7 1
0 1 0 1 0 1 0
1 7

输出数据 1

1 1
1 1
1 1
2 3
2 3
2 4

Note

In the first test case, f(1,1)=00=0f(1, 1) = 0 - 0 = 0.

In the second test case, f(1,1)=55=0f(1, 1) = 5 - 5 = 0, f(2,2)=1010=0f(2, 2) = 10 - 10 = 0. Note that f(1,2)=(10+5)(105)=0f(1, 2) = (10 + 5) - (10 \oplus 5) = 0, but we need to find a subsegment with the minimum length among the maximum values of f(l,r)f(l, r). So, only segments [1,1][1, 1] and [2,2][2, 2] are the correct answers.

In the fourth test case, f(2,3)=(12+8)(128)=16f(2, 3) = (12 + 8) - (12 \oplus 8) = 16.

There are two correct answers in the fifth test case, since f(2,3)=f(3,4)f(2, 3) = f(3, 4) and their lengths are equal.