온라인 쇼핑

시간 제한1초메모리 제한128 MB

요약

행렬의 행과 열을 자유롭게 재배열해 가격을 행 우선으로 이어 붙인 문자열이 사전순으로 가장 작아지도록 만든다.

난이도: 보통10점 중 7점
유형: 완전 탐색, 정렬, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

온라인 쇼핑이 늘면서 여러 상점의 가격을 한눈에 비교해 주는 서비스가 인기를 끕니다. 이런 서비스는 특정 상품의 가장 싼 가격을 빠르게 보여 주기 위해, 가격표를 최대한 정돈된 형태로 배치하려고 합니다.

가격표가 하나 주어집니다. 이 표에는 상품마다 한 행씩 $a$ 개의 행이 있고, 온라인 상점마다 한 열씩 $b$ 개의 열이 있습니다. $i$ 번째 행 $j$ 번째 열의 칸은 상품 $i$ 의 상점 $j$ 에서의 가격입니다.

상품(행)의 순서와 상점(열)의 순서는 서로 독립적으로, 원하는 대로 바꿀 수 있습니다. 어떤 배치가 정해지면 표 문자열은 표를 행 단위로 읽어서 만듭니다. 즉 각 상품을 순서대로 보면서 그 상품의 모든 상점 가격을 순서대로 나열하고, 모든 값을 공백 하나로 구분합니다.

행과 열의 모든 배치 중에서 표 문자열이 가장 작은 것을 출력하세요. 두 표 문자열은 값 단위로 비교합니다. 두 문자열이 처음으로 달라지는 위치에서 가격(센트 단위 정수)이 더 작은 쪽이 더 작은 표 문자열입니다.

입력

첫 줄에 테스트 케이스의 개수 $n$ 이 주어집니다.

이어지는 $n$ 개의 줄에는 각각 하나의 테스트 케이스가 주어집니다. 한 줄은 두 정수 $a$ 와 $b$ ( $1 \le a, b \le 5$ )로 시작하며, 각각 상품의 수와 상점의 수입니다. 그 뒤에는 표의 처음 배치를 나타내는 표 문자열로서 $a \cdot b$ 개의 가격이 이어집니다. 즉 각 상품을 순서대로 보면서 그 상품의 상점별 가격 $b$ 개가 차례로 나옵니다. 각 가격 $p$ 는 센트 단위의 정수이며 $0 \le p \le 10^9$ 을 만족합니다.

출력

각 테스트 케이스마다 먼저 Scenario #i: 줄을 출력합니다. 여기서 $i$ 는 $1$ 부터 시작하는 테스트 케이스 번호입니다. 다음 줄에는 상품과 상점을 최적으로 재배치했을 때의 표 문자열을 출력합니다. 연속한 두 테스트 케이스 사이는 빈 줄로 구분합니다.

예제1

예제 1

입력

2
3 2 3999 5000 4000 4000 12999 9999
4 3 120 120 110 120 80 75 250 50 200 55 80 80

예상 출력

Scenario #1:
3999 5000 4000 4000 12999 9999

Scenario #2:
50 200 250 80 75 120 80 80 55 120 110 120