물고기 양식장

양식업자인 데이브는 바다 양식장에서 많은 물고기를 기르고 있다. 양식장은 물고기들이 같이 헤엄치며 길러지는 정사각형 영역들이 격자 모양으로 붙어있다.

양식장은 $N \times M$ 크기의 2차원 격자판으로 나타낼 수 있다. 위에서부터 $r$ 번째 행, 왼쪽에서부터 $c$ 번째 열에 있는 칸은 $(r, c)$로 나타낸다. 각 물고기는 각자에게 정해져 있는 직사각형 영역 안의 칸에서 길러질 수 있다. 만약, 어떤 물고기가 $[r_1, r_2] \times [c_1, c_2]$인 영역에서 길러진다면, $r_1 \le r \le r_2$와 $c_1 \le c \le c_2$를 만족하는 모든 $r$, $c$에 대해 $(r, c)$ 칸을 포함하는 영역에 물고기가 있을 수 있음을 의미한다.

시간은 $1$ 이상 $Q$ 이하의 정수로 나타난다. 시간 $t$에는 어떤 물고기가 들어오거나 나가는 사건이 발생한다.

길러지는 칸을 공유하는 임의의 두 물고기는 단위 시간마다 각각 한 개씩 해당 칸에 알을 낳는다. 예를 들어, 어떤 단위 시간에 한 물고기는 $[1, 5] \times [2, 4]$에 해당하는 영역에서 길러지고, 다른 물고기는 $[2, 4] \times [1, 5]$에 해당하는 영역에서 길러진다면, 겹치는 영역인 $[2, 4] \times [2, 4]$에 해당하는 영역에 알이 하나씩 생겨 두 물고기의 알을 각각 $9$ 개씩 얻게 된다.

물고기가 낳은 알은 데이브에게 바로 회수되기 때문에, 알이 부화하는 것은 신경 쓰지 않는다. 중요한 것은 물고기들이 낳은 알의 개수이다.

양식장의 크기 $N$과 $M$, 물고기의 수 $K$, 물고기의 출입 기록이 주어질 때, 각 물고기가 낳은 알의 개수를 구하는 프로그램을 작성하시오.

입력 형식

첫 줄에는 양식장의 크기를 나타내는 정수 $N$과 $M$, 물고기의 수를 나타내는 정수 $K$, 물고기의 양식장 출입 기록의 수를 나타내는 정수 $Q$가 공백으로 구분되어 주어진다. ($1 \le N, M \le 5\,000$; $1 \le K \le 100\,000$; $1 \le Q \le 200\,000$)

이어지는 $Q$ 줄의 각 줄에 출입 기록이 하나씩 주어진다. $Q$ 개의 줄 중 $i$ 번째 줄에 주어지는 출입 기록은 다음 둘 중 하나의 형식을 띤다.

• 1 k r1 c1 r2 c2 : 시간 $i$에 물고기 $k$가 $[r_1, r_2] \times [c_1, c_2]$에 해당하는 영역에 들어와 길러지기 시작한다는 뜻이다.
• 2 k r1 c1 r2 c2 : 시간 $i$에 물고기 $k$가 $[r_1, r_2] \times [c_1, c_2]$에 해당하는 영역에서 나간다는 뜻이다.

$1 \le k \le K$이며, $1 \le r1 \le r2 \le N$와 $1 \le c1 \le c2 \le M$를 항상 만족하도록 입력이 주어진다. 또한, 어떤 물고기가 동시에 여러 영역에서 길러지는 기록이 주어지거나, 들어가지 않은 영역에서 나가는 기록은 주어지지 않는다. 마지막으로, 들어간 영역에 대해 상응하는 나간 기록은 항상 존재한다.

출력 형식

$K$ 개의 줄에 걸쳐, $i$ 번째 줄에 물고기 $i$가 낳은 알의 개수를 출력한다.

예제 1

5 5 3 4
1 1 2 1 4 5
1 2 1 2 5 4
2 1 2 1 4 5
2 2 1 2 5 4

9
9
0

예제 2

5 5 3 6
1 1 2 1 4 5
1 2 1 2 5 4
1 3 1 1 5 5
2 1 2 1 4 5
2 2 1 2 5 4
2 3 1 1 5 5

33
48
45

예제 설명

예제 1에서,

• 시간 $1$에 물고기 $1$이 $[2, 4] \times [1, 5]$에 해당하는 영역에 들어와 길러지기 시작한다.
• 시간 $2$에 물고기 $2$가 $[1, 5] \times [2, 4]$에 해당하는 영역에 들어와 길러지기 시작한다.
  • 시간 $2$에서 시간 $3$으로 넘어가는 동안에 물고기 $1$과 물고기 $2$가 $[2, 4] \times [2, 4]$에 해당하는 영역을 공유하기 때문에 각 물고기는 알을 $9$ 개 낳는다.
• 시간 $3$에 물고기 $1$이 $[2, 4] \times [1, 5]$에 해당하는 영역에서 나간다.
• 시간 $4$에 물고기 $2$가 $[1, 5] \times [2, 4]$에 해당하는 영역에서 나간다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설