在古希腊的神话中，有一位掌管刷墙的神。他面前有一面大小为 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 个整数，分别表示每种颜色的最终覆盖面积。

数据范围

 - 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^3