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, \ldots, 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
\(\sum_{1 \leq i \leq n, i \neq k}{Live(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 \(i^{th}\) integer shall be the count of other Martians that may be alive alongside the \(i^{th}\) Martian over all \(T + 1\) moments.

Limits

\(1 \leq t \leq T \leq 10^6\).
\(1 \leq x, y \leq n \leq 50000\).
\(1 \leq m \leq 100000\).

Subtask #	Score	Constraints
1	10	\(T \leq 2\) \(n \leq 10\) \(m \leq 10\)
2	20	\(T \leq 100\) \(n \leq 100\) \(m \leq 200\)
3	10	\(n \leq 3000\) \(m \leq 6000\)
4	20	\(T \leq 40000\) \(n \leq 10000\) \(m \leq 20000\)
5	10	\(n \leq 30000\) \(m \leq 60000\)
6	10	\(n \leq 40000\) \(m \leq 80000\)
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\).