Problem Description

You are given $d$ undirected graphs, each with $n$ vertices. Initially, there are no edges in any graph. Then there are $m$ operations. Each operation gives $a, b, k$, meaning that an undirected edge is added between vertex $a$ and vertex $b$ in the $k$-th graph. After each operation, you need to output the number of ordered pairs $(a, b)$ such that $1 \leq a, b \leq n$, and vertices $a$ and $b$ are connected in all $d$ graphs.

Input Format

The first line contains three integers $d, n, m$.

The next $m$ lines each contain three integers $a, b, k$.

Output Format

Output $m$ lines. Each line contains one integer, representing the required value.

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

4
4
6
6
6
6
6
8
8
16

Hint

For $100\%$ of the testdata, $1 \leq d \leq 200$, $1 \leq n \leq 5 \times 10^3$, $1 \leq m \leq 10^6$, $1 \leq a, b \leq n$, $1 \leq k \leq d$.

Translated by ChatGPT 5