D. Dynamic Connectivity Across Graphs
time limit per test
7 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

There are $$$k$$$ undirected graphs $$$G_1,G_2,\dots,G_k$$$. They share the vertex set $$$\{1,2,\dots,n\}$$$, and initially none of them has an edge.

Process $$$q$$$ operations in order. An operation $$$i,u,v$$$ adds an undirected edge between distinct vertices $$$u$$$ and $$$v$$$ in $$$G_i$$$. The same edge may be added more than once, and $$$u$$$ and $$$v$$$ may already be connected in $$$G_i$$$.

After every operation, determine the number of unordered pairs of distinct vertices $$$\{x,y\}$$$ such that $$$x$$$ and $$$y$$$ belong to the same connected component in every one of the $$$k$$$ graphs.

Input

The first line contains an integer $$$T$$$ ($$$1\le T\le 10^4$$$), the number of test cases.

For each test case:

  • The first line contains three integers $$$n,k,q$$$ ($$$1\le n\le 5\times 10^5$$$, $$$1\le k\le 5\times 10^5$$$, $$$0\le q\le 5\times 10^5$$$), the number of vertices, graphs, and operations.
  • Each of the next $$$q$$$ lines contains three integers $$$i,u,v$$$ ($$$1\le i\le k$$$, $$$1\le u\le n$$$, $$$1\le v\le n$$$, $$$u\ne v$$$), describing one operation.

It is guaranteed that the sum of $$$q$$$ over all test cases does not exceed $$$5\times 10^5$$$.

Output

For each test case, print $$$q$$$ lines. The $$$j$$$-th line must contain one integer: the required number of unordered pairs immediately after the $$$j$$$-th operation. If $$$q=0$$$, print no lines for that test case.

Example
Input
2
3 2 4
1 1 2
2 1 2
1 2 3
2 2 3
4 1 3
1 1 2
1 3 4
1 2 3
Output
0
1
1
3
1
2
6
Note

In the first test case, vertices $$$1$$$ and $$$2$$$ become connected in both graphs after the second operation. After the fourth operation, all three pairs of vertices are connected in both graphs.

The second test case has only one graph, so the answer is the number of vertex pairs within its connected components.