human
E: Taiyaki-Master and Eater

story

Tsuta is very good at making Taiyaki. Ebi-chan loves Taiyaki made by Tsuta-san. The two are happy to make and eat Taiyaki every week, but Tsuta-san's recent worries are that Ebi-chan, who is in the middle of eating, eats the food while making Taiyaki.

Mr. Tsuta, who decided to make Taiyaki at the school festival, is worried about sales if he is eaten by Ebi-chan as usual, so it would be nice if he could know the state of Taiyaki in the range he is paying attention to. thought. Let's help Tsuta-san so that the school festival will be successful.

problem

There is a rectangular taiyaki plate with vertical H and horizontal W, and it takes T minutes from setting the taiyaki to baking. This plate can bake up to HW Taiyaki at a time, at the i (1 \ leq i \ leq H) th place from the top and the j (1 \ leq j \ leq W) th place from the left. Taiyaki is represented by (i, j).

The following three types of events occur a total of Q times. In the initial state, Taiyaki is not set in any place.

* At time t, Tsuta-san sets one Taiyaki at (h, w). The taiyaki is baked in T minutes and can be eaten at time t + T. However, the Taiyaki is not set in the place where the Taiyaki is already set.
* At time t, Ebi-chan tries to pick up and eat the Taiyaki at (h, w). However, you can only eat taiyaki that has already been baked. After eating the pinch, the taiyaki disappears from that place (that is, the taiyaki is not set). Note that a pinch-eating event may occur where the taiyaki is not baked or is not.
* For Taiyaki in a rectangular area (including (h_1, w_1) and (h_2, w_2)) where the upper left is (h_1, w_1) and the lower right is (h_2, w_2), the following number is the time t At that point, Mr. Tsuta counts how many each is.
* Number of Taiyaki already baked
* Number of Taiyaki that have not been baked yet


Input format

H W T Q
t_1 c_1 h_ {11} w_ {11} (h_ {12} w_ {12})
t_2 c_2 h_ {21} w_ {21} (h_ {22} w_ {22})
...
t_Q c_Q h_ {Q1} w_ {Q1} (h_ {Q2} w_ {Q2})

All inputs are given as...
class ... Write me a the Python program you requested?
assistant
#Here is the Python program you requested.
 fenwick_tree_2d:
    def __init__(self, h, w):
        self.H = h
        self.W = w
        self.tree = [[0]*(w+1) for _ in range(h+1)]

    def init_array(self, A):
        for i in range(self.H):
            for j in range(self.W):
                self.add(i+1, j+1, A[i][j])

    def add(self, i, j, x):
        if i <= 0 or j <= 0:
            raise IndexError
        while i <= self.H:
            k = j
            while k <= self.W:
                self.tree[i][k] += x
                k += k & -k
            i += i & -i

    def sum_until(self, i, j):
        if i < 0 or j < 0:
            raise IndexError
        s = 0
        while i > 0:
            k = j
            while k > 0:
                s += self.tree[i][k]
                k -= k & -k
            i -= i & -i
        return s

    def sum_acc(self, h1, h2, w1, w2):
        """
        0 <= h1 < h2 <= H
        0 <= w1 < w2 <= W
        [h1,h2) * [w1,w2) の長方形区域の値の総和を返す
        """
        return self.sum_until(h2, w2) - self.sum_until(h2, w1) \
            - self.sum_until(h1, w2) + self.sum_until(h1, w1)

def main():
    import sys
    input = sys.stdin.buffer.readline
    from collections import deque
    H, W, T, Q = (int(i) for i in input().split())
    taikaki_set = fenwick_tree_2d(H, W)
    taikaki_baked = fenwick_tree_2d(H, W)

    Query_t = deque([])
    Query_h = deque([])
    Query_w = deque([])
    for _ in range(Q):
        t, c, *A = (int(i) for i in input().split())
        while Query_t and Query_t[0] <= t:
            Query_t.popleft()
            th = Query_h.popleft()
            tw = Query_w.popleft()
            taikaki_set.add(th, tw, -1)
            taikaki_baked.add(th, tw, 1)
        if c == 0:
            (h, w) = A
            taikaki_set.add(h, w, 1)
            Query_t.append(t+T)
            Query_h.append(h)
            Query_w.append(w)
        elif c == 1:
            (h, w) = A
            cur = taikaki_baked.sum_acc(h-1, h, w-1, w)
            if 0 < cur:
                taikaki_baked.add(h, w, -1)
       ...