2544번 - 격자판 스페셜 저지

N개의 행과 M개의 열로 구성된 격자판의 각 칸에 숫자들이 들어있다. 정수 K (K ≥ 2)가 주어진다. K는 N보다 작고, M보다도 작다. 격자판에서 R개의 행과 C개의 열을 R + C = K가 만족하도록 선택하고, 선택된 행과 열을 제외한 나머지 칸에 있는 숫자들 가운데 가장 큰 숫자가 최소가 되도록 하려고 한다. N = 4, M = 5인 경우의 격자판의 예가 다음 그림과 같이 주어졌다고 하자.

위의 예에서 K = 3인 경우, 1행, 3행과 4열을 선택하면 다음 그림과 같이 선택된 행과 열을 제외한 나머지 칸에 있는 숫자들 가운데 제일 큰 숫자는 5이다.

3행, 3열과 4열을 선택하여도 선택된 행과 열을 제외한 나머지 칸 가운데 제일 큰 숫자는 5이다. 그러나 달리 선택하여 나머지 칸에 있는 숫자들이 모두 5보다 작게 만들 수는 없다.

숫자들이 들어있는 격자판과 선택할 수 있는 행의 개수와 열의 개수의 합이 주어졌을 때, 선택한 행과 열을 제외한 나머지 칸에 있는 숫자들 가운데 가장 큰 숫자가 최소가 되도록 행과 열을 선택하기 위한 프로그램을 작성하시오.

첫 줄에는 격자판의 크기를 나타내는 정수 N과 M이 주어진다. N과 M은 3 이상이며, 300 이하인 정수이다. 둘째 줄에는 선택할 수 있는 행과 열의 개수의 합 K (K < N, K < M)가 주어진다. 셋째 줄부터 격자판에 들어있는 양의 정수들이 한 줄에 한 행씩 1행부터 차례대로 주어진다. 격자판에 들어있는 각 숫자는 1 이상 500,000 이하의 정수이다. 같은 줄에 입력되는 각 정수들 사이에는 한 개의 공백이 있다.

첫 번째 줄에 R + C = K를 만족하는 R개의 행과 C개의 열을 선택하여, 선택된 행과 열을 제외한 나머지 칸에 있는 숫자들 가운데 가장 큰 숫자의 최솟값을 출력한다. 둘째 줄에는 선택한 행의 개수와 이어서 행 번호를 오름차순으로 출력한다. 셋째 줄에는 선택한 열의 개수와 이어서 열 번호를 오름차순으로 출력한다. 행의 개수나 열의 개수가 0인 경우에는 해당하는 줄에 0만 출력한다. 같은 줄에 출력되는 각 정수들 사이에는 한 개의 공백을 둔다.

조건을 만족하는 답이 여러 개인 경우에는 그 중에서 하나만 출력하면 된다.