Mars Survival Prediction

In Mars Town there are n residents (numbered 1,2,…,n). A machine learning algorithm has predicted the state (alive or dead) of these residents at T discrete time instants (numbered 1,2,…,T). Each prediction is one of the following two types:

• Brothers in Misfortune: a prediction in the form 0 t x y means: at time t, if resident x is dead then resident y will be dead at time t+1. (Note: if x is alive at time t, then this prediction is considered correct.)
• The Grim Reaper Arrives: a prediction in the form 1 t x y means: at time t, if resident x is alive then resident y must be dead at time t. (Note: if x is dead at time t, then this prediction is considered correct.)

Martians cannot be resurrected, so a resident must be alive in all times up to the final moment in order to be considered surviving. In particular, to be alive at time T+1, a resident must be alive at every time from 1 to T+1. When choosing a scenario (an assignment of alive/dead states to each resident at every time) we assume that the predictions are all correct. This means that when possible, the states may be chosen arbitrarily so as to maximize survival, provided that all predictions are satisfied.

For any two different residents i and j, we define $$ \operatorname{Live}(i,j)=\begin{cases}1,&\text{if it is possible for both i and j to be alive at time } T+1,\\0,&\text{otherwise.}\end{cases} $$

JYY wants to compute for each resident k the number of other Martians who may possibly survive together with resident k until time T+1, i.e. for each k</em} compute

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

Observation: When a resident is required to be dead by a prediction of the form 1 t x y (The Grim Reaper Arrives), if we wish for both x and y to survive until time T+1, then the prediction would be violated because both would be alive at time t. In contrast, predictions of the form 0 t x y (Brothers in Misfortune) do not force any death as long as resident x is kept alive. Therefore, for two residents i and j to possibly survive together until time T+1, there must be no prediction of type 1 in either direction (i.e. neither 1 t i j nor 1 t j i appears for any t).

Your task is to compute for each resident the number of other residents that can possibly be alive at time T+1 together with him/her, under the assumption that all predictions hold.

## inputFormat

The first line contains three integers n, T and m (1 ≤ n, T ≤ 10⁵, 0 ≤ m ≤ 10⁵), denoting the number of residents, the number of time instants, and the number of predictions, respectively.

Each of the following m lines contains four integers: a t x y, where a is either 0 or 1. If a = 0, then the line represents a "Brothers in Misfortune" prediction (0 t x y); if a = 1, then it represents a "Grim Reaper Arrives" prediction (1 t x y). It is guaranteed that 1 ≤ t ≤ T and 1 ≤ x, y ≤ n.

## outputFormat

Output a single line containing n integers. The k-th integer should be the number of other residents that can possibly survive until time T+1 together with resident k.

## sample

3 3 2
1 1 1 2
0 2 2 3

1 1 2

$$