Добыча нефти

면접 대비

시간 제한2초메모리 제한1024 MB

요약

n 곱하기 m 격자에서 네 모서리에 표시된 칸의 합이 정확히 S가 되는 축 평행 직사각형을 찾는다.

난이도: 보통10점 중 4점
유형: 누적 합, 행렬
정답자: 아직 제출이 없습니다

문제

Компания RectanGas занимается добычей нефти уже с незапяматных времен и является бесспорным лидером в своей области. Маркетологи считают, что она стала такой успешной благодаря бессменному исполнительному директору. На нем стоит остановиться поподробнее.

Дело в том, что исполнительный директор совсем не изучал геометрию в школе и до сих пор считает, что кроме прямоугольников других геометрических фигур не существует. Более того, он никак не может поверить, что стороны прямоугольников могут быть не параллельными осям координат. Поэтому все нефтяные вышки строятся следующим образом: директор на карте отмечает четыре точки так, чтобы они образовывали прямоугольник со сторонами, параллельными осям координат карты, и приказывает строить нефтяные вышки на участках, соответствующим отмеченным точкам на карте. Эти нефтяные вышки за короткий промежуток времени добывают всю нефть, расположенную на соответствующем участке.

Компания RectanGas почти выполнила свой план по добыче нефти на май 2010 года. Для этого ей осталось добыть ровно $S$ баррелей нефти. Заметим, что больше добывать нельзя, иначе компанию обвинят в монополии. Меньше добывать тоже нельзя, потому что исполнительный директор, будучи человеком пунктуальным, очень огорчится, что повлечет за собой увольнение сотрудников и всеобщую безработицу. Геологи, подробно изучив карту местности, определили количество залежей нефти на каждом участке и попросили Вас написать программу, определяющую координаты будущих нефтяных вышек с учетом всех требований.

입력

Первая строка содержит три числа: размеры карты местности $n$ и $m$ и план по добыче нефти $S$ ( $2 \le n, m \le 300$ ; $0 \le S \le 10^{7}$ ). Далее следуют $n$ строк по $m$ чисел $a\_{ij}$ --- количество залежей нефти на соответсвующем участке ( $0 \le a\_{ij} \le 10^{6}$ )

출력

В случае, если увольнения не миновать, выведите << $-1$ >> (без кавычек). В противном случае выведите четыре числа --- координаты левой верхней и правой нижней вышек соответственно. Если вариантов ответа несколько, то выведите любой из них.

힌트

Иллюстрация к первому примеру:

Сумма значений в угловых вышках равна $1 + 5 + 2 + 8 = 16$

예제2

예제 1
입력
```
3 3 16
1 3 5 
2 4 8
6 9 7
```
예상 출력
```
1 1 2 3
```
예제 2
입력
```
2 3 4
12 6 7
4 9 5
```
예상 출력
```
-1
```