题目描述

我们有一个$H\times W$大小的网格。初始时，所有的方格都没有被涂色。

你需要对这些方格进行涂色。有$C$种可用的颜色，编号为$1, 2, \ldots, C$。

涂色的过程将由$Q$个查询给出。第$i$个查询包含整数$t_i, n_i, c_i$，表示以下动作。

• 如果$t_i = 1$：用颜色$c_i$涂色第$n_i$行的所有方格。
• 如果$t_i = 2$：用颜色$c_i$涂色第$n_i$列的所有方格。

将一个方格涂色为颜色$c$会使该方格的颜色变为$c$，无论它之前的状态如何。

在整个过程结束后，找到每种颜色$1, 2, \ldots, C$中被涂色的方格的数量。

约束条件

• $2\leq H\leq 10^9$
• $2\leq W\leq 10^9$
• $1\leq C\leq 3\times 10^5$
• $1\leq Q\leq 3\times 10^5$
• $t_i\in \{1,2\}$
• 如果$t_i = 1$，则$1\leq n_i\leq H$
• 如果$t_i = 2$，则$1\leq n_i\leq W$
• $1\leq c_i\leq C$

输入

输入以以下格式从标准输入给出：

$H$ $W$ $C$ $Q$ $t_1$ $n_1$ $c_1$ $\vdots$ $t_Q$ $n_Q$ $c_Q$

输出

打印一行，其中包含颜色$1, 2, \ldots, 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

过程如下改变了方格的颜色。这里，.表示一个未涂色的方格。

.....   66666   66666   64666   64626   22222
.....   .....   .....   .4...   .4.2.   .4.2.
.....   .....   33333   34333   34323   34323
.....   .....   .....   .4...   .4.2.   .4.2.

示例输入2

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

示例输出2

0 5000000000 0