Description

Currently, there are $n$ residents in the Mars town (numbered $1,2,\ldots,n$). A machine learning algorithm predicts the life-or-death status of these residents over the next $T$ moments (numbered $1,2,\ldots,T$). Each prediction is one of the following two types:

• Brothers in Misfortune $0$ $t$ $x$ $y$: At moment $t$, if $x$ is dead, then at moment $t+1$, $y$ is dead. (Note that if $x$ is alive at moment $t$, this prediction is also considered correct.)

• Death God Arrives $1$ $t$ $x$ $y$: At moment $t$, if $x$ is alive, then at moment $t$, $y$ is dead. (Note that if $x$ is dead at moment $t$, this prediction is also considered correct.)

Note that this problem is predicting the life-or-death status at a specific moment. If someone is alive at moment $t$ and dead at moment $t+1$, you may assume that some event happened during the time interval from $t$ to $t+1$ that caused their death.

Although JYY is very confident in the model obtained from big data statistics, the Martians are shocked by these predictions and feel it is hard to accept such a setting. They even think computer science is a scary cult that has broken their peaceful life. To calm the Martians down, JYY plans to derive some facts from these prediction results that are easier for the Martians to accept.

Specifically, JYY first assumes that all predictions about the Martians' life and death are correct. Based on this, JYY wants to compute, for each resident $k$, how many Martians might be able to live together with him until moment $T+1$. In other words, for each Martian $k$, JYY wants to compute

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

where $\operatorname{Live}(i,j)=1$ means that Martians $i$ and $j$ may possibly both be alive at moment $T+1$; otherwise, $\operatorname{Live}(i,j)=0$.

Note that Martians cannot be resurrected. A Martian may already be dead at moment $1$, and there may also be deaths not covered by any prediction (a Martian can die at any time, but at any moment, a Martian's observed state is either alive or dead). Finally, note that $\operatorname{Live}$ is computed independently for each pair of Martians, so $\operatorname{Live}(x,y)=1$ and $\operatorname{Live}(y,z)=1$ does not imply $\operatorname{Live}(x,z)=1$.

Input Format

The first line contains three integers $T,n,m$. The next $m$ lines each describe a prophecy. The first integer $c$ of each prophecy indicates its type:

• $c=0$: then read $t,x,y$;

• $c=1$: then read $t,x,y$.

Output Format

Output $n$ numbers as the answers, separated by spaces.

3 3 2
0 2 1 3
1 1 2 3

2 1 1

Hint

Translated by ChatGPT 5