Byteotia 有 $n$ 座城市。目前，该国还没有高速公路。然而，Byteotia 政府计划在未来几年内逐步修建 $m$ 条高速公路。每条计划修建的高速公路都是双向的，且属于 $1$ 到 $d$ 中的某一种类型。

固定未来某个时间点。我们称一个有序城市对 $(a, b)$ 是“连通的”，如果 $a = b$，或者满足以下条件：对于所有类型 $t = 1, \dots, d$，仅使用类型为 $t$ 的高速公路，都能从 $a$ 到达 $b$。

给定计划修建高速公路的顺序。你的任务是计算对于所有 $k = 1, \dots, m$，在前 $k$ 条高速公路建成后，连通的城市对数量。

输入格式

第一行包含三个整数 $d, n, m$ ($1 \le d \le 200, 1 \le n \le 5000, 1 \le m \le 1\,000\,000$)，分别表示高速公路的类型数量、城市数量和计划修建的高速公路数量。

城市编号为 $1$ 到 $n$。接下来的 $m$ 行描述了计划修建的高速公路。第 $i$ 行包含三个整数 $a_i, b_i, k_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i, 1 \le k_i \le d$)，表示第 $i$ 条高速公路连接 $a_i$ 和 $b_i$，且类型为 $k_i$。

输出格式

输出共 $m$ 行。第 $k$ 行应包含一个整数，表示在前 $k$ 条高速公路建成后，连通的（有序）城市对的数量。

样例

输入 1

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

输出 1

4
4
6
6
6
6
6
8
8
16