This is a harder version of the problem. In this version, n ≤ 50 000.

There are n distinct points in three-dimensional space numbered from 1 to n. The i-th point has coordinates (x_i, y_i, z_i). The number of points n is even.

You'd like to remove all n points using a sequence of n/2 snaps. In one snap, you can remove any two points a and b that have not been removed yet and form a perfectly balanced pair. A pair of points a and b is perfectly balanced if no other point c (that has not been removed yet) lies within the axis-aligned minimum bounding box of points a and b.

Formally, point c lies within the axis-aligned minimum bounding box of points a and b if and only if min(x_a, x_b) ≤ x_c ≤ max(x_a, x_b), min(y_a, y_b) ≤ y_c ≤ max(y_a, y_b), and min(z_a, z_b) ≤ z_c ≤ max(z_a, z_b). Note that the bounding box might be degenerate. 

Find a way to remove all points in n/2 snaps.

Input

The first line contains a single integer n (2 ≤ n ≤ 50 000; n is even), denoting the number of points.

Each of the next n lines contains three integers x_i, y_i, z_i (-10^8 ≤ x_i, y_i, z_i ≤ 10^8), denoting the coordinates of the i-th point.

No two points coincide.

Output

Output n/2 pairs of integers a_i, b_i (1 ≤ a_i, b_i ≤ n), denoting the indices of points removed on snap i. Every integer between 1 and n, inclusive, must appear in your output exactly once.

We can show that it is always possible to remove all points. If there are many solutions, output any of them.

Examples

Input


6
3 1 0
0 3 0
2 2 0
1 0 0
1 3 0
0 1 0


Output


3 6
5 1
2 4


Input


8
0 1 1
1 0 1
1 1 0
1 1 1
2 2 2
3 2 2
2 3 2
2 2 3


Output


4 5
1 6
2 7
3 8

Note

In the first example, here is what points and their corresponding bounding boxes look like (drawn in two dimensions for simplicity, as all points lie on z = 0 plane). Note that order of removing matters: for example, points 5 and 1 don't form a perfectly balanced pair initially, but they do after point 3 is removed. 

<image>
from collections import defaultdict

def filterOut(ans,removed,mapp): # filters adjacent pairs in map values. same line
    # mapp is like {(x,y):[[z1,idx1],[z2,idx2],...]}
    for v in mapp.values():
        arr=list(v)
        n=len(arr)
        arr.sort() # sort by 0th index asc
        i=0
        while i+1<n:
            idx1,idx2=arr[i][1],arr[i+1][1]
            ans.append([idx1,idx2])
            removed[idx1]=removed[idx2]=True
            i+=2
    return

def filterOut2(ans,removed,mapp): # filters adjacent pairs in map values. same plane
    # mapp is like {x:[[y1,z1,idx1],[y2,z2,idx2],...]}
    for v in mapp.values():
        arr=list(v)
        n=len(arr)
        arr.sort() # sort by 0th index asc, then 1st index asc
        i=0
        while i+1<n:
            idx1,idx2=arr[i][2],arr[i+1][2]
            ans.append([idx1,idx2])
            removed[idx1]=removed[idx2]=True
            i+=2
    return
    

def main():
    
    n=int(input())
    coords=[] # [x,y,z,i]
    for i in range(1,n+1):
        x,y,z=readIntArr()
        coords.append([x,y,z,i])
    
    ans=[]
    removed=[False for _ in range(n+1)]
    
    # first identify points on the same lines
    # same (x,y)
    xyMap=defaultdict(lambda:[]) # {(x,y):[[z1,idx1],[z2,idx2],...]}
    for i in range(n):
        x,y,z,idx=coords[i]
        xyMap[(x,y)].append([z,idx])
    filterOut(ans,removed,xyMap)
    #update coords and n
    coords2=[]
    for i in range(n):
        if not removed[coords[i][3]]:
            coords2.append(coords[i])
    coords=coords2
    n=len(coords)
    
    # same (y,z)
    yzMap=defaultdict(lambda:[])
    for i in range(n):
        x,y,z,idx=coords[i]
        yzMap[(y,z)].append([x,idx])
    filterOut(ans,removed,yzMap)
    #update coords and n
    coords2=[]
    for i in range(n):
        if not removed[coords[i][3]]:
            coords2.append(coords[i])
    coords=coords2
    n=len(coords)
    
    # same (z,x)
    zxMap=defaultdict(lambda:[])
    for i in range(n):
        x,y,z,idx=coords[i]
        zxMap[(z,x)].append([y,idx])
    filterOut(ans,removed,zxMap)
    #update coords and n
    coords2=[]
    for i in range(n):
        if not removed[coords[i][3]]:
            coords2.append(coords[i])
    coords=coords2
    n=len(coords)
    
    
    # first identify points on the same planes
    # same x
    xMap=defaultdict(lambda:[]) # {x:[[y1,z1,idx1],[y2,z2,idx2],...]}
    for i in range(n):
        x,y,z,idx=coords[i]
        xMap[x].append([y,z,idx])
    filterOut2(ans,removed,xMap)
    #update coords and n
    coords2=[]
    for i in range(n):
        if not removed[coords[i][3]]:
            coords2.append(coords[i])
    coords=coords2
    n=len(coords)
    
    # same y
    yMap=defaultdict(lambda:[])
    for i in range(n):
        x,y,z,idx=coords[i]
        yMap[y].append([x,z,idx])
    filterOut2(ans,removed,yMap)
    #update coords and n
    coords2=[]
    for i in range(n):
        if not removed[coords[i][3]]:
            coords2.append(coords[i])
    coords=coords2
    n=len(coords)
    
    # same z
    zMap=defaultdict(lambda:[])
    for i in range(n):
        x,y,z,idx=coords[i]
        zMap[x].append([y,z,idx])
    filterOut2(ans,removed,zMap)
    #update coords and n
    coords2=[]
    for i in range(n):
        if not removed[coords[i][3]]:
            coords2.append(coords[i])
    coords=coords2
    n=len(coords)
    
    # remaining coordinates that don't share x,y,z
    coords.sort() # sort by x,y,z asc
    for i in range(0,n,2):
        ans.append([coords[i][3],coords[i+1][3]])
    multiLineArrayOfArraysPrint(ans)
    
    return

import sys
# input=sys.stdin.buffer.readline #FOR READING PURE INTEGER INPUTS (space separation ok)
input=lambda: sys.stdin.readline().rstrip("\r\n") #FOR READING STRING/TEXT INPUTS.
 
def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))
def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))
def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))
 
def readIntArr():
    return [int(x) for x in input().split()]
# def readFloatArr():
#     return [float(x) for x in input().split()]

def makeArr(defaultValFactory,dimensionArr): # eg. makeArr(lambda:0,[n,m])
    dv=defaultValFactory;da=dimensionArr
    if len(da)==1:return [dv() for _ in range(da[0])]
    else:return [makeArr(dv,da[1:]) for _ in range(da[0])]
 
def queryInteractive(i,j):
    print('? {} {}'.format(i,j))
    sys.stdout.flush()
    return int(input())
 
def answerInteractive(ans):
    print('! {}'.format(' '.join([str(x) for x in ans])))
    sys.stdout.flush()
 
inf=float('inf')
MOD=10**9+7
# MOD=998244353
 
 
for _abc in range(1):
    main()