Chef has two integer sequences $A_1, A_2, \ldots, A_N$ and $B_1, B_2, \ldots, B_M$. You should choose $N+M-1$ pairs, each in the form $(A_x, B_y)$, such that the sums $A_x + B_y$ are all pairwise distinct.
It is guaranteed that under the given constraints, a solution always exists. If there are multiple solutions, you may find any one.

-----Input-----
- The first line of the input contains two space-separated integers $N$ and $M$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.
- The third line contains $M$ space-separated integers $B_1, B_2, \ldots, B_M$.

-----Output-----
Print $N+M-1$ lines. Each of these lines should contain two space-separated integers $x$ and $y$ denoting that you chose a pair $(A_{x+1}, B_{y+1})$.

-----Constraints-----
- $1 \le N, M \le 2 \cdot 10^5$
- $|A_i| \le 10^9$ for each valid $i$
- $|B_i| \le 10^9$ for each valid $i$
- $A_1, A_2, \ldots, A_N$ are pairwise distinct
- $B_1, B_2, \ldots, B_M$ are pairwise distinct

-----Subtasks-----
Subtask #1 (25 points): $1 \le N, M \le 10^3$
Subtask #2 (75 points): original constraints

-----Example Input-----
3 2
10 1 100
4 3

-----Example Output-----
2 1
0 0
1 0
0 1

-----Explanation-----
The chosen pairs and their sums are:
- $A_3 + B_2 = 100+3 = 103$
- $A_1 + B_1 = 10+4 = 14$
- $A_2 + B_1 = 1+4 = 5$
- $A_1 + B_2 = 10+3 = 13$
Since all sums are distinct, this is a correct output.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
(n, m) = map(int, input().split())
arr1 = list(map(int, input().split()))
arr2 = list(map(int, input().split()))
max1 = arr1.index(max(arr1))
min2 = arr2.index(min(arr2))
arr = []
for i in range(m):
	arr.append([max1, i])
for i in range(n):
	if i != max1:
		arr.append([i, min2])
for i in arr:
	print(*i)


(N, M) = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
ans = []
mina = A.index(min(A))
maxb = B.index(max(B))
for i in range(M):
	ans.append('{} {}'.format(mina, i))
for i in range(N):
	if mina != i:
		ans.append('{} {}'.format(i, maxb))
for i in ans:
	print(i)


(N, M) = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
ans = []
seen = {}
flag = False
for i in range(N):
	for j in range(M):
		if len(ans) == N + M - 1:
			flag = True
			break
		x = A[i] + B[j]
		if x not in seen:
			ans.append('{} {}'.format(i, j))
			seen[x] = True
	if flag:
		break
for i in ans:
	print(i)


try:
	(n, m) = map(int, input().split())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	a = l1.index(min(l1))
	b = l2.index(max(l2))
	for i in range(m):
		print(a, i)
	for i in range(n):
		if a != i:
			print(i, b)
except:
	pass


try:
	(m, n) = map(int, input().split())
	arr_m = list(map(int, input().split()))
	arr_n = list(map(int, input().split()))
	Sum = 0
	s = set()
	for i in range(m):
		for j in range(n):
			if len(s) > m + n - 2:
				break
			Sum = arr_m[i] + arr_n[j]
			if Sum not in s:
				s.add(Sum)
				print(i, j)
except:
	pass


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
set_a = {}
set_b = {}
for (index, item) in enumerate(a):
	if item not in set_a:
		set_a[item] = index
for (index, item) in enumerate(b):
	if item not in set_b:
		set_b[item] = index
sums = {}
total = 0
done = False
for (value_a, index_a) in set_a.items():
	for (value_b, index_b) in set_b.items():
		if value_a + value_b not in sums:
			sums[value_a + value_b] = True
			total += 1
			print(index_a, index_b)
			if total == n + m - 1:
				done = True
				break
	if done:
		break


(n, m) = map(int, input().split())
an = [int(x) for x in input().split()]
am = [int(x) for x in input().split()]
r = n + m - 1
c = 0
man = an.index(max(an))
for i in range(m):
	print(man, i)
mam = am.index(min(am))
for j in range(n):
	if j == man:
		continue
	print(j, mam)


(n, m) = list(map(int, input().split()))
k = n + m - 1
l1 = list(map(int, input().split()))
l2 = list(map(int, input().split()))
d = []
c = 0
for i in range(n):
	for j in range(m):
		a = l1[i] + l2[j]
		if a not in d:
			d.append(a)
			print(i, j)
			c += 1
		if c == k:
			break
	if c == k:
		break


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
d = list(map(int, input().split()))
x = l.index(min(l))
y = d.index(max(d))
for i in range(n):
	if i == x:
		for j in range(m):
			print(i, j)
	else:
		print(i, y)


(n, z) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
mini = float('inf')
maxi = -float('inf')
maxi_ind = -1
mini_ind = -1
for i in range(n):
	if a[i] < mini:
		mini = a[i]
		mini_ind = i
for i in range(z):
	if b[i] > maxi:
		maxi = b[i]
		maxi_ind = i
for i in range(n):
	if i == mini_ind:
		for j in range(z):
			print(i, j)
	else:
		print(i, maxi_ind)


from itertools import count, islice
R = lambda : map(int, input().split())
Z = lambda : list(zip(R(), count()))
(n, m) = R()
(a, b) = (Z(), Z())
if n != 10:
	a = (min(a), max(a))
d = {x + y: (i, j) for (x, i) in a for (y, j) in b}
for p in islice(d.values(), n + m - 1):
	print(*p)


(n, m) = map(int, input().split())
l1 = list(map(int, input().split()))
l2 = list(map(int, input().split()))
a = [(l1[i], i) for i in range(n)]
b = [(l2[i], i) for i in range(m)]
a.sort(key=lambda x: x[0])
b.sort(key=lambda x: x[0])
for i in range(m):
	print(a[0][1], b[i][1])
for i in range(1, n):
	print(a[i][1], b[m - 1][1])


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
al = [(a[i], i) for i in range(n)]
bl = [(b[i], i) for i in range(m)]
al.sort(key=lambda x: x[0])
bl.sort(key=lambda x: x[0])
for i in range(m):
	print(al[0][1], bl[i][1])
for i in range(1, n):
	print(al[i][1], bl[m - 1][1])


(n, m) = map(int, input().split())
c = list(map(int, input().split()))
b = list(map(int, input().split()))
x = c.index(min(c))
y = b.index(max(b))
for i in range(m):
	print(x, i)
for i in range(n):
	if i != x:
		print(i, y)


f = lambda : map(int, input().split())
from itertools import *
(a, b) = f()
l = list(f())
m = list(f())
m_a = l.index(min(l))
m_b = m.index(max(m))
for i in range(b):
	print(m_a, i)
for i in range(a):
	if i != m_a:
		print(i, m_b)