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

You are given an array of integers $a_1, a_2, \ldots, a_n$.

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

You will have $q = 1$ query. Each query is given by a pair of numbers $L_i$, $R_i$, where $1 \leq L_i \leq R_i \leq n$. You need to find the subsegment $[l, r]$, $L_i \leq l \leq r \leq R_i$, with maximum value $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 $r - l + 1$.


-----Input-----

Each test consists of multiple test cases. The first line contains an integer $t$ ($1 \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 $n$ and $q$ ($1 \leq n \leq 10^5$, $q = 1$) — the length of the array and the number of queries.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 10^9$) — array elements.

$i$-th of the next $q$ lines of each test case contains two integers $L_i$ and $R_i$ ($1 \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 $n$ over all test cases does not exceed $2 \cdot 10^5$.

It is guaranteed that $L_1 = 1$ and $R_1 = n$.


-----Output-----

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


-----Examples-----

Input
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
Output
1 1
1 1
1 1
2 3
2 3
2 4


-----Note-----

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

In the second test case, $f(1, 1) = 5 - 5 = 0$, $f(2, 2) = 10 - 10 = 0$. Note that $f(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)$. So, only segments $[1, 1]$ and $[2, 2]$ are the correct answers.

In the fourth test case, $f(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)$ and their lengths are equal.

Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Sorting

Amortized analysis

Greedy algorithms
Skill types: Bit manipulation

Sorting

Amortized analysis

Greedy algorithms

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	vals = list(map(int, input().split()))
	(L, R) = map(int, input().split())
	L -= 1
	R -= 1
	s = 0
	xr = 0
	for i in range(L, R + 1):
		s += vals[i]
		xr ^= vals[i]
	f = s - xr
	(l, r) = (L, L)
	(ml, mr) = (L, R)
	(curs, curxr) = (0, 0)
	while r <= R:
		curs += vals[r]
		curxr ^= vals[r]
		if curs - curxr == f:
			while l < r and curs - vals[l] - (curxr ^ vals[l]) == f:
				curs -= vals[l]
				curxr ^= vals[l]
				l += 1
			if mr - ml > r - l:
				(mr, ml) = (r, l)
		r += 1
	print(ml + 1, mr + 1)


import sys
import math

def solve():
	inp = sys.stdin.readline
	(n, q) = map(int, inp().split())
	a = list(map(int, inp().split()))
	p = [0] * (n + 1)
	x = [0] * (n + 1)
	for i in range(n):
		p[i + 1] = p[i] + a[i]
	for i in range(n):
		x[i + 1] = x[i] ^ a[i]

	def cost(l, r):
		return p[r] - p[l - 1] - (x[r] ^ x[l - 1])
	for i in range(q):
		(l, r) = map(int, inp().split())
		ans = cost(l, r)
		answ = (n + 10, -1, -1)
		rr = r
		for i in range(l, r + 1):
			rr = max(i, rr)
			while rr < n and cost(i, rr) < ans:
				rr += 1
			while rr - 1 >= i and cost(i, rr - 1) >= ans:
				rr -= 1
			if cost(i, rr) == ans:
				answ = min(answ, (rr - i, i, rr))
		print(answ[1], answ[2])

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


from math import *
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	(L, R) = map(int, input().split())
	pairs = dict()
	pref_s = [0]
	pref_x = pref_s[:]
	for i in range(n):
		pref_s.append(pref_s[-1] + a[i])
		pref_x.append(pref_x[-1] ^ a[i])
	(l, r) = (1, n)
	pred = pref_s[r] - pref_s[l - 1] - (pref_x[r] ^ pref_x[l - 1])
	l = r = 1
	for i in range(2, n + 1):
		r = i
		s = pref_s[r] - pref_s[l - 1] - (pref_x[r] ^ pref_x[l - 1])
		if pred == s:
			while l + 1 <= r and pref_s[r] - pref_s[l] - (pref_x[r] ^ pref_x[l]) >= s:
				s = pref_s[r] - pref_s[l - 1] - (pref_x[r] ^ pref_x[l - 1])
				l += 1
		pairs[l, r] = s
	l = r = 1
	ans = 0
	for key in pairs:
		if ans < pairs[key] or (ans == pairs[key] and r - l + 1 > key[1] - key[0] + 1):
			(l, r) = (key[0], key[1])
			ans = pairs[key]
	print(l, r)


def compute(prefixS, prefixXor, l, r):
	if l == 0:
		return prefixS[r] - prefixXor[r]
	return prefixS[r] - prefixS[l - 1] - (prefixXor[r] ^ prefixXor[l - 1])
t = int(input())
while t:
	(n, q) = list(map(int, input().split()))
	nums = list(map(int, input().split()))
	(l, r) = list(map(int, input().split()))
	l -= 1
	r -= 1
	prefixS = nums[:]
	prefixXor = nums[:]
	for i in range(1, n):
		prefixS[i] += prefixS[i - 1]
		prefixXor[i] ^= prefixXor[i - 1]
	maxSum = prefixS[n - 1] - prefixXor[n - 1]
	(start, end) = (1, n - 1)
	while start <= end:
		mid = (start + end) // 2
		(i, j) = (0, mid - 1)
		flag = 0
		while j < n:
			temp = compute(prefixS, prefixXor, i, j)
			if temp == maxSum:
				flag = 1
				break
			j += 1
			i += 1
		if flag:
			(l, r) = (i, j)
			end = mid - 1
		else:
			start = mid + 1
	print(l + 1, ' ', r + 1)
	t -= 1


import math
I = input
t = int(I())
while t > 0:
	t -= 1
	(n, q) = map(int, I().split())
	a = [*map(int, I().split())]
	psum = [0] * n
	pxor = [0] * n
	for i in range(0, n):
		psum[i] = (psum[i - 1] if i else 0) + a[i]
		pxor[i] = (pxor[i - 1] if i else 0) ^ a[i]
	(l, r) = map(int, I().split())
	mxval = 0
	ans = (0, 0)
	for i in range(n):
		l = i
		h = n - 1
		pps = 0 if not i else psum[i - 1]
		ppx = 0 if not i else pxor[i - 1]
		mx = psum[h] - pps - (pxor[h] ^ ppx)
		if mx < mxval:
			continue
		while l < h:
			m = l + (h - l) // 2
			f = psum[m] - pps - (pxor[m] ^ ppx)
			if f < mx:
				l = m + 1
			else:
				h = m
		if mx > mxval or h - i < ans[1] - ans[0]:
			mxval = mx
			ans = (i, h)
	print(ans[0] + 1, ans[1] + 1)


test = int(input())
for testtest in range(test):
	(n, q) = map(int, input().split())
	L = list(map(int, input().split()))
	(l, r) = map(int, input().split())
	s = 0
	x = 0
	S = [0] * n
	X = [0] * n
	for i in range(n):
		s += L[i]
		x ^= L[i]
		S[i] = s
		X[i] = x
	S += [0]
	X += [0]
	Ans = [0, n - 1]
	for i in range(0, n):
		a = i
		b = n - 1
		while a < b:
			c = (a + b) // 2
			if S[c] - S[i - 1] - (X[c] ^ X[i - 1]) == s - x:
				b = c
				continue
			else:
				a = c + 1
				continue
		if a - i < Ans[1] - Ans[0]:
			Ans = [i, a]
		if S[n - 1] - S[i] - (X[n - 1] ^ X[i]) != s - x:
			break
	print(Ans[0] + 1, Ans[1] + 1)