多彩的行列

时间限制：2s
空间限制：1024MB

题目描述

有一个初始未涂色的 $H\times W$ 网格和编号 $1,\ldots,C$ 的颜色。每次操作把指定整行或整列全部覆盖成给定颜色。所有操作结束后，求每种颜色的格子数。

输入格式

第一行 $H,W,C,Q$。接下来 $Q$ 行，每行 $t_i,n_i,c_i$：$t_i=1$ 表示涂第 $n_i$ 行，$t_i=2$ 表示涂第 $n_i$ 列。

输出格式

一行输出 $C$ 个整数，依次表示每种颜色的最终格子数。

样例输入 1

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

样例输出 1

0 8 3 3 0 0

数据范围

对于所有数据，$2\le H,W\le10^9$，$1\le C,Q\le3\times10^5$。