26615번 - 다오의 행사 계획하기

문제

크레이지 아케이드의 버블힐에서는 매년 새해가 찾아오면 다오가 개최하는 행사가 열린다.

행사를 계획하려는 다오

이번 행사는 특별히도 $N \times M$의 미로 모양 행사장에서 진행한다. 행사장의 가장 왼쪽 위의 칸을 $(0,0)$이라 하고 가장 오른쪽 아래의 칸을 $(N-1, M-1)$이라 하면 임의의 두 칸을 잇는 경로는 정확히 1개 있음이 보장된다.

행사는 총 $T$일 간 개최되는데, 각 날짜에 진행하는 이벤트에 따라 오는 사람의 수는 달라질 수 있다. 이때 이벤트가 열리면 이를 위한 긴 대기줄이 만들어지면서 해당 구역에 사람이 증가하게 된다. 구체적으로 $i$번 이벤트가 $S_i$일부터 $E_i$일까지 열린다고 할 때, 해당 날 동안 $(a_i,b_i)$에서 $(c_i,d_i)$를 잇는 경로상에 사람이 $V_i$명 증가한다.

다오는 행사를 효율적으로 계획하기 위해 날마다 어느 정도로 사람이 많을지 알고 싶다. 이벤트가 총 $K$개 열릴 때, 각 날마다 행사에 올 사람의 총합을 구해보자.

입력

첫 줄에 $N, M, T$가 주어진다. $(N, M \ge 2, N \times M \le 10^5, 1 \le T \le 10^5)$

이후 $(N-1) \times M$ 행렬 $A$가 주어진다. $A_{i,j}$의 값이 1ドル$이면 $(i,j)$와 $(i+1,j)$사이에 벽이 있음을 의미하고 0ドル$이면 없음을 의미한다.

이후 $N \times (M-1)$ 행렬 $B$가 주어진다. $B_{i,j}$의 값이 1ドル$이면 $(i,j)$와 $(i,j+1)$사이에 벽이 있음을 의미하고 0ドル$이면 없음을 의미한다.

그 후 이벤트의 개수 $K$가 주어진다. $(1 \le K \le 10^5)$

이후 $K$줄에 걸쳐 $i$번 이벤트의 정보 $S_i, E_i, a_i, b_i, c_i, d_i, V_i$가 주어진다. $(1 \le S_i \le E_i \le T, 0 \le a_i, c_i \le N-1, 0 \le b_i, d_i \le M-1, 1 \le V_i \le 10^3)$

출력

$T$줄에 걸쳐 $i$번 줄에 $i$일에 오는 사람의 총합을 출력한다.

제한

힌트