시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
8 초 256 MB 2 2 2 100.000%

문제

There are $n$ cities in Byteotia. Nowadays, the country has no highways. However, the Byteotian government planned that in the subsequent years, a network of $m$ highways will be gradually built. Each of the planned highways will be bidirectional and will be of one of $d$ types, numbered $1$ through $d$.

Fix some point of time in the future. We say that an ordered pair of cities $(a,b)$ is well-connected if $a=b$ or the following condition holds:  for all types $t=1,\ldots,d$, one can travel from $a$ to $b$ using only highways of type $t$.

You are given the order in which the planned highways will be built. Your task is to compute, for all $k=1,\ldots,m$, the number of pairs of cities that will be well-connected after $k$ first highways are built.

입력

The first line of the input contains three integers $d$, $n$, $m$ ($1 \le d \le 200$, $1 \le n \le 5000$, $1 \le m \le 1\,000\,000$), denoting the number of types of highways, the number of cities and the number  of planned highways. The cities are numbered $1$ through $n$. The following $m$ lines describe the planned highways. The $i$-th of these lines contains three integers $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$), denoting that the $i$-th highway will run between $a_i$ and $b_i$ and will be of type $k_i$.

출력

You should output exactly $m$ lines. The $k$-th of these lines should contain a single integer -- the number of (ordered) pairs of cities that are well-connected after the first $k$ highways are built.

예제 입력 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