JYY and his Mars expedition team have landed on the Martian town again and intend to teach machine learning to the Martians to improve their living efficiency. However, the Martians, with their limited intelligence, have expressed disbelief in computer science. To convince them, JYY's team retrieved their detailed historical data records and trained a prediction model that can accurately predict the life and death of Martians in the future.

Description

Currently, there are $n$ residents in the Martian town (numbered $1, 2, \dots, n$). The machine learning algorithm has predicted the life and death status of these residents over the next $T$ moments (numbered $1, 2, \dots, T$). Each prediction is in one of the following two forms:

• $0 \ t \ x \ y$: At time $t$, if $x$ is in a dead state, then at time $t+1$, $y$ is in a dead state. (Note: If $x$ is in a living state at time $t$, this prediction is also considered correct.)
• $1 \ t \ x \ y$: At time $t$, if $x$ is in a living state, then at time $t$, $y$ is in a dead state. (Note: If $x$ is in a dead state at time $t$, this prediction is also considered correct.)

(Note that this problem predicts the life/death status at a specific moment. If someone is alive at time $t$ and dead at time $t+1$, you can assume that an event occurred between time $t$ and $t+1$ that caused their death.)

Although JYY is very confident in the model he derived from big data, the Martians were shocked by these predictions, finding them unacceptable and viewing computer science as a terrifying cult that has disrupted their peaceful lives. To appease the Martians, JYY intends to deduce some facts from these predictions that are easier for the Martians to accept.

Specifically, JYY first assumes that all predictions about the life and death of the Martians are correct. Based on this, JYY wants to calculate for each resident $k$ how many other Martians could possibly be alive at time $T+1$ along with them. In other words, JYY wants to calculate for each Martian $k$:

$$\sum_{1 \le i \le n, i \neq k} Live(k, i)$$

where $Live(i, j) = 1$ indicates that Martians $i$ and $j$ can both be in a living state at time $T+1$, and $Live(i, j) = 0$ otherwise.

Note that Martians cannot be resurrected. A Martian might be dead at time $1$, and there may be deaths not covered by the predictions (Martians can die at any time, but at any moment, a Martian is observed to be either alive or dead). Finally, note that $Live$ is defined for each pair of Martians individually, so $Live(x, y) = 1$ and $Live(y, z) = 1$ does not imply $Live(x, z) = 1$.

Input

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

The next $m$ lines each represent a prediction. The first integer $c$ in each line indicates the type of prediction: $c = 0$: Read $t, x, y$ $c = 1$: Read $t, x, y$

The input data guarantees $1 \le t \le T$ and $1 \le x, y \le n$.

Output

Output $n$ integers separated by spaces, representing the answers.

Examples

Input 1

3 3 2
0 2 1 3
1 1 2 3

Output 1

2 1 1

Note 1

If Martian 2 is alive at time $T+1$, it means they were also alive at time $1$. Due to the second prediction, we observe that Martian 3 is in a dead state at time $1$, so Martians 2 and 3 cannot both be alive at time $T+1$, thus $Live(2, 3) = 0$.

Martian 1 can be alive at time $T+1$ with either of the other two. Note that when 1 and 3 are both alive, the first prediction is correct. Therefore, $Live(1, 2) = 1$ and $Live(1, 3) = 1$.

Examples 2

See predict/predict2.in and predict/predict2.ans in the contestant directory.

Subtasks