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.

AT_arc130_b [ARC130B] Colorful Lines

题目描述

有一个$H×W$的方格。首先，方格里的格子都没有涂颜色。

你决定对这个格子涂上颜色。可以使用的颜色有$C$种，颜色分别表示为$1$,$2$,$…$,$C$。

有$Q$次上色。

第$i$个上色给出三个整数，分别为$T_{i}$，$N_{i}$，$C_{i}$。表示涂色如下：

• 当$T_{i}=1$时：将第$N_{i}$行的格子全部涂上颜色$C_{i}$。
• 当$T_{i}=2$时：将第$N_{i}$列的格子全部涂上颜色$C_{i}$。

如果用颜色$C$涂某个格子的话，该格子的颜色无论之前是什么颜色，总是会变成颜色$C$。

当所有涂色完成时，请求出用颜色分别为$1$,$2$,$…$,$C$的格子的个数。

输入格式

第一行有四个整数，分别为$H$,$W$,$C$,$Q$。

接下来有$Q$行，每行有三个整数分别为$T_{i}$，$N_{i}$，$C_{i}$。

输出格式

输出共一行，有$C$个数。

对于第$i$个数，表示颜色为$i$的格子的个数。

翻译:WAITER

输入输出样例 #1

输入 #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

输入 #2

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

输出 #2

0 5000000000 0