You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在古希腊的神话中，有一位掌管刷墙的神。他面前有一面大小为 $n \times m$ 的白墙，他有 $k + 1$ 种颜料（白色为 0 号，其他颜色分别为 1 到 $k$）。神将进行 $q$ 次粉刷操作，每次使用宽度为 1 单位的刷子，染色后覆盖一整行或者一整列。现在给出他的所有操作，你能告诉他，除白色外，每种颜色的最后覆盖面积吗？

输入格式

第一行包含四个整数 $n, m, k, q$。

接下来 $q$ 行描述 $q$ 次粉刷操作。

每行包含三个正整数 $opt, u, c$：

• 当 $opt = 0$ 时，表示将第 $u$ 行刷成颜色 $c$。
• 当 $opt = 1$ 时，表示将第 $u$ 列刷成颜色 $c$。

输出格式

输出一行包含 $k$ 个整数，分别表示每种颜色的最终覆盖面积。

5 5 2 2
1 1 1
0 1 2

4 5

样例2

color2.in
color2.out

数据范围

• 30%: 满足 $n\leq100, 0\leq q\leq100$
• 50%: 满足 $n\leq5000, 0\leq q\leq5000$
• 100%: 满足 $n,m\leq10^5, q\leq 10^5, 0\leq k\leq10^4$