문제 설명
\(H \times W\)의 크기의 그라운드가 있다. 이 그라운드에는 보물이 숨겨져 있는데, 위에서부터 \(i\)행, 왼쪽에서부터 \(j\)열에 있는 칸 \(X_{i,j}\)에는 숨겨져 있는 보물의 수가 적혀져 있다.
보물 사냥꾼인 판다는 왼쪽 위\((A_i, B_j)\), 오른쪽 아래\((C_i, D_j)\)으로 표현되는 사각형 영역 \(Q\)개에 대한 정보를 얻었다.
이 영역은 보물이 묻혀있을 가능성이 높은 정보로 그 중 하나만 골라 채굴을 할 수 있다.
가장 많은 보물이 묻혀있는 영역의 번호를 찾아 판다에게 알려주자.
보물 사냥꾼인 판다는 왼쪽 위\((A_i, B_j)\), 오른쪽 아래\((C_i, D_j)\)으로 표현되는 사각형 영역 \(Q\)개에 대한 정보를 얻었다.
이 영역은 보물이 묻혀있을 가능성이 높은 정보로 그 중 하나만 골라 채굴을 할 수 있다.
가장 많은 보물이 묻혀있는 영역의 번호를 찾아 판다에게 알려주자.
입력 설명
\(H\) \(W\) \(Q\)
\(X_{1,1}\) \(X_{1,2}\) ... \(X_{1,W}\)
...
\(X_{H,1}\) \(X_{H,2}\) ... \(X_{H,W}\)
\(A_1\) \(B_1\) \(C_1\) \(D_1\)
...
\(A_Q\) \(B_Q\) \(C_Q\) \(D_Q\)
\(1 \le H,W \le 1,500\)
\(1 \le Q \le 100,000\)
\(0 \le X_{i,j} \le 9\)
\(1 \le A_i \le C_i \le H\)
\(1 \le B_i \le D_i \le W\)
\(X_{1,1}\) \(X_{1,2}\) ... \(X_{1,W}\)
...
\(X_{H,1}\) \(X_{H,2}\) ... \(X_{H,W}\)
\(A_1\) \(B_1\) \(C_1\) \(D_1\)
...
\(A_Q\) \(B_Q\) \(C_Q\) \(D_Q\)
\(1 \le H,W \le 1,500\)
\(1 \le Q \le 100,000\)
\(0 \le X_{i,j} \le 9\)
\(1 \le A_i \le C_i \le H\)
\(1 \le B_i \le D_i \le W\)
출력 설명
가장 많은 보물이 묻혀있는 영역의 번호를 출력한다. 첫번째 입력되는 영역의 번호는 \(1\) 이며 마지막 영역의 번호는 \(Q\)이다.
입력 예시 Copy
5 6 2
2 0 0 5 1 2
3 0 1 1 2 0
0 0 1 5 3 0
1 3 0 1 0 0
2 2 1 3 0 5
2 2 4 5
1 1 5 5
출력 예시 Copy
2