#1552 눈치게임

32  1 s   128 MB  

Description

ICU Programming Club RUN은 ICPC 시즌을 맞아, 대전 근교 장태산으로 엠티를 갔다. 밤이 되고 함께 술을 마시며 놀다가, 그들은 눈치 게임을 시작했다. 눈치게임은 다음과 같은 방식으로 진행한다.
- N명의 사람이 있다. 편의상 각 사람을  1...N 번 사람이라고 부른다.
- 이들은 서로 눈치를 보며 1부터 K까지 순서대로 숫자를 외친다. K는 N보다 작다
- 두 사람 이상이 동시에 같은 숫자를 외치면 그 사람들은 게임에 지게 된다. 
- 한 번 숫자를 외친 사람은 더 이상 다른 숫자를 외치지 않는다.
- K 까지 숫자를 외치는 동안 패자가 없으면, 숫자를 외치지 못한 나머지 사람들이 지게 된다. 
게임이 시작하면 1을 외칠 수 있고, 누군가 j를 외치면 그 순간부터 j+1을 외칠 수 있다. i번 사람은 숫자 j를 외칠 수 있는 순간부터 W(i,j) 시간만큼 기다리며 눈치를 본다. 그리고 그 시간동안 아무도 숫자를 외치지 않으면 j를 외친다.
N명이 각각 숫자에 대해서 기다리는 시간이 주어졌을 때 눈치게임에서 지는 사람은 누구인가?

Input

첫 줄에는 게임의 회수 T가 주어진다. (1 ≤ T ≤ 40 )
각 테스트 케이스의 첫 줄에는 정수 N과 K가 주어진다. (1 ≤ K < N ≤ 200)
다음 줄부터 N 줄에 걸쳐서 N x K 의 행렬이 주어진다.
i행의 j열에 있는 수는 W(i,j)를 나타낸다. (0 ≤ W(i,j) ≤ 60, 1 ≤ i ≤ N, 1 ≤ j ≤ K)

Output

각각의 게임에 대하여 지는 사람의 목록을 오름차순으로 한 줄에 출력한다.
각 사람은 한 칸의 공백으로 구분하도록 한다.

Sample Input

Sample Output

3
4 3
0 1 3
7 0 1
5 1 3
1 2 3
3 2
1 1
1 2
1 3
5 3
0 1 2
2 0 1
1 2 0
1 2 3
1 1 1
3 4 
1 2 3 
4 5