题目描述

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

输入格式

第 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

说明/提示

数据范围：

对于 30% 的数据：满足$n≤100，0≤q≤100$

对于 50% 的数据：满足$n≤5000，0≤q≤5000$

对于 100% 的数据：满足$1≤n,m,q≤10^5，0≤k≤10^4$