preciseforecast

Precise Forecast


JYY and his Mars expedition team have landed again in the Martian Town, and they intend to impart the knowledge of machine learning to the Martians, thereby improving Martian standards of living. But the Martians have limited intelligence, and have expressed disbelief in the principles of Computer Science. In order to convince the Martians, JYY's expedition found detailed historical records for Mars and trained a predictive model to accurately predict the future lives and deaths of Martians.

Currently, there are n residents in the Martian Town, indexed 1,2,,n. JYY's machine-learning algorithms have made m predictions about these residents for T upcoming moments. Each prediction takes one of the following two forms:

  • Entanglement: 0 t x y. If Martian x is no longer alive at moment t, then in moment t+1 Martian y will no longer be alive. (If Martian x is alive at moment t, this prediction is also considered correct.)
  • Inverted Fate: 1 t x y. At moment t, if Martian x is alive then Martian y is not alive. (If Martian x is not alive at moment t, this prediction is also considered correct.)
As explained, these predictions work on a set of discrete moments. If a Martian is alive in moment t but not in moment t+1, it is assumed that an event occurred between moments t and t+1 leading to their death.

Although JYY was very confident in this model he constructed with the power of Big Data, the Martians were shocked to see these predictions and decried Computer Science as a terrible cult set to destroy their ways of life. In order to appease the Martians, JYY intends to deduce some more palatable facts based on these predictions.

JYY now assumes that all predictions made by the model are correct. On this basis, JYY hopes to determine: For each town resident k, how many other residents can k possibly live through all T+1 moments with? In other words, for every Martian k, JYY wants to count
1in,ikLive(k,i)
where Live(i,j)=1 if there exists at least one scenario in which Martians i and j are alive in all T+1 moments, and Live(i,j)=0 otherwise.

Keep in mind that Martians cannot be resurrected, and a Martian may be deceased at moment 1. Finally, note that Live is calculated independently for each pair of Martians, so Live(x,y)=Live(y,z)=1 does not necessarily imply Live(x,z)=1.

Input format

The first line of input consists of three integers T, n and m.

m lines of input follow. Each line contains four integers representing a prediction, and will take one of the two described forms:

  • 0 t x y
  • 1 t x y

Output format

Output a single line containing n integers. The ith integer shall be the count of other Martians that may be alive alongside the ith Martian over all T+1 moments.

Limits

1tT106.
1x,yn50000.
1m100000.
Subtask # Score Constraints
1 10 T2
n10
m10
2 20 T100
n100
m200
3 10 n3000
m6000
4 20 T40000
n10000
m20000
5 10 n30000
m60000
6 10 n40000
m80000
7 20 No additional constraints

Samples

Sample Input 1 Sample Output 1
3 3 2
0 2 1 3
1 1 2 3
2
1
1

If Martian 2 lives to moment T+1, then he must have been alive at moment 1 and by the second prediction Martian 3 must be deceased by then. Hence, Martians 2 and 3 cannot both remain alive til moment T+1, and thus Live(2,3)=0.

There are no predictions precluding any other pairs of Martians from both living to moment T+1, so Live(1,2)=Live(1,3)=1.



Submitting to 'preciseforecast'


You're not logged in! Click here to login


Submitting to 'preciseforecast'


You're not logged in! Click here to login


Submitting .cpp to 'preciseforecast'


You're not logged in! Click here to login

Time Limit: 3 Seconds
Memory Limit: 1024MB
Your best score: 0
Source: LOJ #3101

Subtask Score
1 10
2 20
3 10
4 20
5 10
6 10
7 20