28335번 - 올림픽

문제

4년마다 열리는 올림픽에서는 순위에 따라 선수들에게 금, 은, 동메달을 수여한다. 따라서 선수들의 국적을 바탕으로 각 국가가 획득한 메달의 수를 셀 수 있다. 공식적으로는 이를 통해 각 국가의 순위를 가리는 방법이 없지만, 본질적으로 순위를 매기는 편이 더 재미있고 열기를 고취시킬 수 있기 때문에 순위를 매기는 방법들이 고안되었다. 이 문제에서는 널리 쓰이는 두 가지 방법을 생각해 본다.

• 국가 $x$의 등수는 (국가 $x$보다 좋은 성적을 거둔 국가의 수 + 1) 로 정의한다.
• 방법 1. 메달의 수를 종류에 관계 없이 세어 많은 국가가 적은 국가보다 좋은 성적이라 정의한다.
• 방법 2. 금메달이 많은 국가가 적은 국가보다 좋은 성적이라 정의한다. 단, 같을 경우는 은메달이 많은 국가를 좋은 성적으로 정의하며, 은메달도 같은 경우는 동메달이 많은 국가를 좋은 성적으로 정의한다.

$N$개의 국가가 경쟁 중이며, 앞으로 $K$개의 경기가 남았다. 앞선 경기는 반드시 그렇지 않았지만 남은 경기 모두는 금, 은, 동메달이 서로 다른 국가에 하나씩 주어지는 종목이다. 지금까지 그들이 획득한 메달의 수가 주어질 때, 앞으로 남은 $K$ 경기의 결과에 따른 최선의 등수를 두 방법 각각에 대해 구하는 프로그램을 작성하라.

입력

입력은 $T$개의 테스트 케이스로 구성된다. 입력의 첫 행에는 $T$가 주어진다.

각 테스트 케이스의 첫 행에는 두 정수 $N$ (3ドル ≤ N ≤ 100$), $K$ (0ドル ≤ K ≤ 1,000円$)가 공백으로 구분되어 주어진다. 다음 $N$ 행에 걸쳐 한 행에 하나씩 각 국가가 획득한 금, 은, 동메달의 수가 공백으로 구분되어 주어진다. 각 메달의 수는 1ドル,円 000$을 넘지 않는다.

출력

각 테스트 케이스에 대해 두 행에 나누어 입력에서 주어진 순서에 따라 각 국가의 방법 1에 따른 최선의 등수를 공백으로 구분하여 출력하고, 다음 행에 마찬가지로 방법 2에 따른 최선의 등수를 출력한다.

제한

힌트

• 첫 번째 테스트 케이스: 첫 번째 국가가 남은 경기에서 메달을 획득하지 못하더라도 다른 국가가 어떤 방법으로도 더 잘 할 수 없다.
• 두 번째 테스트 케이스: 방법 1에 의하면, 첫 번째 국가를 제외한 모든 국가는 적어도 공동 1위가 될 수 있다. 그러나 첫 번째 국가의 경우 세 국가 중 적어도 둘은 메달을 획득하므로 첫 번째 국가보다 앞설 수밖에 없다. 방법 2에 의하면 어느 국가도 자신이 금메달을 획득하고 나머지 국가들이 적당히 은, 동메달을 나누어 가지면 1위가 될 수 있다.