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 machinelearning algorithms have made \(m\) predictions about these residents for \(T\) upcoming moments. Each prediction takes one of the following two forms:
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:
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.
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 
Sample Input 1  Sample Output 1 
3 3 2

2

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\).
Subtask  Score 

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