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: interview

Starter code:

Solutions:
# cook your dish here
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)

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
        if(A[i]+B[j] not in seen):
            ans.append('{} {}'.format(i,j))
            seen[A[i]+B[j]] = True
    if(flag):
        break

for i in ans:
    print(i)

# cook your dish here
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

# cook your dish here
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())

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)

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=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()))

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 i!=a:
        print(i, b)

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

# cook your dish here
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

# cook your dish here
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)


# cook your dish here
# cook your dish here
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)


# cook your dish here
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)


# cook your dish here
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)

# cook your dish here
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)

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

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])

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)

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])