Informatica Online Judge

  어부를 낚는 사람 #2 [2234 / 08BA]

Time Limit(Test case) : 999(ms)
Number of users who solved : 12   Total Tried : 13


The Champion of this Problem (C++) : gs17044 - ms / 846byte
My Best Submission (C++) : N/A

[34th 정원준]
Writer ID : [gs16103]

Background

옛날 옛날 아주 먼 옛날, 요정이 하나 있었어요. 어느 날 요정이 준호에게 가서 말했어요.

“어부를 낚아라”
“네”



준호는 이제 어부를 낚으려고 해요. 어부들은 N*M격자에 각각 $a_{ij}$명씩 있어요. 어부를 낚기 위해서는 낚시도구 “2B|!2B”가 필요해요. 이 도구를 이용하면 (1, 1)부터 (x, y)까지의 직사각형 안에 있는 모든 어부를 한 번에 낚을 수 있어요. 참 대단하죠? 어부를 최대한 많이 낚으려면 (1, 1)부터 (N, M)까지 모두 낚으면 돼요.

그런데 준호는 마음이 너무 착한 나머지 어부를 k명보다 많이 낚는 것은 나쁜 행동이라 하지 않기로 했어요. 따라서 준호는 k이하의 어부를 낚으면서도 최대한 많이 낚을 수 있게 되는 (x, y)를 고를 거예요.

이를 괘씸하게 생각한 요정은 격자에 있는 어부들의 수를 막 바꿔버리기로 했어요. 그럼 준호는 어떻게 어부들을 낚아야 할지 몰라서 당황하겠죠? 쌤통이에요.

준호가 당황하지 않게 어부를 낚는 오른쪽 아래 좌표 (x, y)를 구하여라.

Input

첫 줄에 격자의 크기를 나타내는 정수 N, M(1 <= N, M <= 500) 과 질문의 수를 나타내는 정수 Q(1 <= Q <= 500) 가 공백을 사이에 두고 주어진다.

두 번째 줄부터 N+1번째 줄까지 각각 M개의 정수 $a_{ij}$ (0 <= $a_{ij}$ <= 1,000,000) 가 입력된다.

N+2번째 줄부터 Q개의 줄에 각각 질문이 주어진다.

1 x y c : $a_{xy}$의 값을 c (0 <= c <= 1,000,000)로 바꾼다.
2 k : k (0 <= k <= N*M*1,000,000)이하의 어부를 낚으면서 가장 많이 낚게 되는 좌표 의 x, y값을 공백을 사이에 두고 출력한다. 답이 여러 개 있다면 아래쪽, 같은 행에 있다면 오른쪽에 있는 좌표를 출력한다. 주어진 조건을 만족하는 좌표가 없으면 -1을 출력한다. 모든 출력 뒤에는 줄바꿈이 들어간다.


[Sub-Task Info]
#1 : N = 1
#2 : 1 <= N,M,Q <= 30
#3 : 1 <= N,M,Q <= 80
#4 : 1 <= N,M,Q <= 300
#5 : 추가 제약 조건이 없다.

Output

모든 2번째 질문에 대하여 답을 출력한다. 2번째 질문은 적어도 하나 주어진다.

IO Example

입력
3 4 6
0 1 0 0
1 1 0 1
1 0 2 1
2 4
2 8
2 3
1 1 3 1
2 4
2 8

출력
3 2
3 4
2 3
3 2
3 3

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]