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보다 작게 만들 수는 없다.

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

실행시간은 2초를 초과할 수 없다. 부분 점수는 없다.

입력 형식

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

출력 형식

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

입력과 출력의 예

입력

4 5
3
3 1 7 6 3
3 4 2 8 2
8 6 4 2 4
3 5 1 2 1

출력

5
2 1 3
1 4

출처:koi 2007 koi 본선 고등 3 번