볼링

지난 토요일에 Paul, Ivo, Nick은 볼링장에 갔다. 한 시간 동안 레인을 빌려 세 게임을 했다. 이렇게 가볍게 즐기는 경기에서 이들은 그저 이긴 게임 수를 세기로 했다. 가장 많이 이긴 사람이 최종 승자가 된다. (동점이라면 승자를 가릴 다른 방법을 찾아야 했을 것이다.)

이번에는 Paul이 두 게임, Nick이 한 게임을 이겨서 Paul이 승자가 되었다. Ivo는 자신의 점수가 그렇게 나쁘지 않다고 느꼈는데도 어떻게 세 게임을 모두 잃었는지 궁금했다. 그래서 전광판을 다시 보니 이러했다.

Paul이 실제로 두 게임을 이기고 Nick이 한 게임을 이겼지만, Ivo는 자신이 게임 순서를 112-98-73으로 바꿔서 했다면 두 게임을 이기고 Paul은 하나도 이기지 못했을 것이라고 지적했다.

Ivo의 지적은 언뜻 보기보다 터무니없지 않다. 볼링에서는 다른 선수와 무관하게 각 게임이 치러지며, 심리적인 영향 정도만 있을 뿐이다. 한 선수의 연속된 점수도 서로 거의 독립적이고 같은 분포를 따른다고 볼 수 있다.

Ivo는 지난 토요일에는 현명하게도 이 이야기를 삼켰지만, 나중에 자신의 '잠재적 승수' 개념을 성적을 재는 척도로 써 볼 생각을 하기 시작했다. 각 선수의 최소 승수도 알면 흥미롭겠다고 결론지었다. 또한 승수를 최대화하거나 최소화하려는 선수의 게임만 순열할 수 있게 하는 것이 아니라 다른 선수의 게임도 순열할 수 있게 하면 좋겠다고 생각했다. 마지막으로 Ivo는 선수가 언제 게임을 '이기는지'를 정확히 정의해야 했다. 선수는 자신의 점수가 다른 모든 선수의 점수보다 엄격히 클 때에만 그 게임을 이긴다.

Ivo는 각 선수 i에 대해 다음을 계산하는 프로그램을 작성해 달라고 요청한다.

• mi, 각 선수의 점수를 어떻게 순열하든 상관없이 선수 i가 이겼을 최소 게임 수
• Mi, 각 선수의 점수를 그 목적에 맞게 최적으로 순열했을 때 선수 i가 이겼을 수 있는 최대 게임 수

입력의 첫 줄에는 테스트 케이스의 수가 하나 주어진다. 각 테스트 케이스는 다음 형식이다.

• 선수 수와 게임 수를 나타내는 두 정수 P와 G가 공백 하나를 사이에 두고 주어지는 한 줄 (2 ≤ P ≤ 100, 2 ≤ G ≤ 1000).
• 선수마다 한 줄씩, 각 줄에 그 선수의 연속된 점수를 나타내는 G개의 정수가 공백 하나를 사이에 두고 주어진다.

각 점수는 0 이상 300 이하이다.

입력의 각 테스트 케이스마다 선수마다 한 줄씩, 모두 P개의 줄을 출력한다. i번째 줄에는 mi와 Mi를 공백 하나를 사이에 두고 출력한다.