在互联网上与朋友聊天时，我们总是会被各种聊天群中的海量消息所困扰，这令人十分烦恼。这些消息中绝大多数对我们来说其实并不重要，但如果我们屏蔽了这些群组，又可能会错过一些重要的通知。我们从所有在线聊天群中收到了多少条消息？从来没有人认真研究过这个问题。

作为信息学院的一名助理研究员，你需要调查我们每天收到的在线消息数量。我们已经抽样了 $n$ 个群组和 $m$ 名学生。每个群组包含 $m$ 名学生中的一个子集，该子集可能是空的。此外，群组成员是不断变化的；旧成员可能会退出，新成员可能会加入聊天群。成员可以在群组中发送消息；该消息会广播给当前在同一群组中的所有其他成员。

现在我们已经收集了这些聊天群的日志。日志是一系列事件，可能是学生加入群组、退出群组或在群组中发送消息。你的任务是计算每名学生收到的消息总数。

输入格式

输入的第一行包含三个整数 $n, m, s$ ($1 \le n \le 100\,000, 1 \le m \le 200\,000, 1 \le s \le 1\,000\,000$)，分别表示群组数量、学生数量和日志中的事件数量。

接下来的 $s$ 行按时间顺序给出了日志中的事件。每行包含三个整数 $t, x, y$ ($t \in \{1, 2, 3\}, 1 \le x \le m, 1 \le y \le n$)，指定了一个事件，该事件属于以下三类之一：

• 如果 $t = 1$，表示第 $x$ 号学生加入了第 $y$ 号群组。保证该学生之前不在该群组中。
• 如果 $t = 2$，表示第 $x$ 号学生退出了第 $y$ 号群组。保证该学生当前在该群组中。
• 如果 $t = 3$，表示第 $x$ 号学生在第 $y$ 号群组中发送了一条消息。保证该学生此时在该群组中。

最初，所有群组均为空。

输出格式

输出 $m$ 行。第 $i$ 行包含一个整数，表示第 $i$ 号学生收到的消息总数。

样例

输入 1

3 3 10
1 3 2
1 3 1
1 1 2
1 2 1
3 1 2
2 3 1
3 3 2
3 2 1
3 3 2
3 2 1

输出 1

2
0
1

输入 2

2 5 10
1 1 2
3 1 2
2 1 2
1 3 2
1 1 2
3 1 2
3 3 2
1 4 2
3 3 2
1 5 1

输出 2

2
0
1
1
0