집 짓기

뉴욕 중심가에서 온 몇몇 괴짜들은 현대 사회에 넌더리가 났고, 그곳을 떠나기로 결심했다. 이들은 멀리 떨어진 곳에 직사각형 모양의 땅 한 조각을 함께 샀고, 이제 그곳에 정착하려고 한다.

땅은 $N \times M$개의 칸으로 이루어져 있고, 각 칸에는 집을 많아야 하나 지을 수 있다. 각 칸에는 그 칸이 얼마나 살기 좋은지를 나타내는 $0$과 $100$ 사이의 값 $a\_{x,y}$가 있다.

괴짜들의 목표는 서로를 포함한 다른 모든 사람으로부터 최대한 멀어지는 것이다. 따라서 괴짜가 $(x,y)$번 칸에 집을 지을 때 느끼는 행복은 $a\_{x,y} \cdot d$이고, 여기서 $d$는 다른 사람까지의 최소 거리이다. 습관적으로 괴짜들은 이 거리를 잴 때 맨해튼 거리를 사용한다. 즉 $d$는 다른 모든 사람의 칸 $(x\_2, y\_2)$에 대한 $\min |x - x\_2| + |y - y\_2|$로 정의된다.

이제 괴짜들은 집을 최적으로 배치해 이들이 느끼는 행복의 합이 최대가 되도록 돕고 싶어 한다. 도와줄 수 있겠는가?

입력은 $10$개의 테스트 케이스로 이루어지며, 아래에 설명되어 있다.

첫째 줄에는 테스트 케이스의 번호를 나타내는 $T$ ($0 \le T \le 10$)가 주어진다 (샘플은 $0$). 둘째 줄에는 $N$, $M$, $K$ ($1 \le N, M \le 1\,000$, $2 \le K \le N \cdot M$)가 주어진다. 이는 땅 격자의 높이와 너비, 그리고 사람의 수이다. 다음 $N$개의 줄에는 각각 $M$개의 정수, 즉 값 $a\_{x,y}$ ($0 \le a\_{x,y} \le 100$)가 주어진다.

집의 위치를 $K$개의 줄에 걸쳐 출력한다. 각 줄에는 두 수가 있어야 한다. 먼저 집의 행 ( $1$과 $N$ 사이), 그 다음 열 ( $1$과 $M$ 사이)이다. 두 집은 같은 위치에 배치될 수 없다.

예제에서는 $2 \times 3$ 격자에 두 채의 집을 배치하려고 한다. 예제 풀이에서는 한 집을 왼쪽 아래 모서리에, 다른 집을 오른쪽 위 모서리에 둔다. 그러면 두 집 모두 다른 집까지의 최단 거리가 $2 + 1 = 3$이 되고, 행복의 합은 $3 \cdot 30 + 3 \cdot 50 = 240$이 된다.

만약 이 테스트 케이스가 실제 테스트 케이스였고 다른 참가자가 집을 왼쪽 위와 오른쪽 아래 모서리에 배치했다면 (더 높은 행복 $270$을 얻었을 것이다), 그 테스트 케이스는 $10 \cdot (240 / 270)^2 \approx 7.90$점을 받았을 것이다.