# Enter your code here. Read input from STDIN. Print output to STDOUT
t = int(raw_input())

while(t>0):
    zoo_num,anm_num = map(int,raw_input().split())
    c = [[0 for k in xrange(anm_num)] for j in xrange(3)] 
    k = [[0 for k in xrange(anm_num)] for j in xrange(3)] 
    c[0] = raw_input().split()
    for i in range(1,anm_num):
        c[i] = map(int,raw_input().split())
    
    
    for i in range(0,anm_num):
        k[i] =  [row[i] for row in c]
    k.sort(key=lambda x: x[2])
    for i in range(0,anm_num):
        c[i] =  [row[i] for row in k]
    A = [c[2][0]]
    T = {c[0][0]:c[2][0]}
    for i in range(1,anm_num):
        dict((k, v) for k, v in T.iteritems() if v>c[1][i])
        if(c[0][i] == 'D'):
            if 'E' not in T.keys():
                if 'C' not in T.keys():
                    T['D']=c[2][i]
                    ans = ans + 1
                    A.append(ans)
        if(c[0][i] == 'C'):
            if 'D' not in T.keys():
                if 'M' not in T.keys():
                    T['C']=c[2][i]
                    ans = ans + 1
                    A.append(ans)
                    
        if(c[0][i] == 'M'):
            if 'C' not in T.keys():
                if 'E' not in T.keys():
                    T['M']=c[2][i]
                    ans = ans + 1
                    A.append(ans)
        if(c[0][i] == 'E'):
            if 'D' not in T.keys():
                if 'M' not in T.keys():
                    T['E']=c[2][i]
                    ans = ans + 1
                    A.append(ans)
                    
                
    print A,T
    t = t-1