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 residents in the Martian Town, indexed . JYY's machine-learning algorithms have made predictions about these residents for upcoming moments. Each prediction takes one of the following two forms:
- Entanglement: . If Martian is no longer alive at moment , then in moment Martian will no longer be alive. (If Martian is alive at moment , this prediction is also considered correct.)
- Inverted Fate: . At moment , if Martian is alive then Martian is not alive. (If Martian is not alive at moment , this prediction is also considered correct.)
As explained, these predictions work on a set of discrete moments. If a Martian is alive in moment but not in moment , it is assumed that an event occurred between moments and 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 , how many other residents can possibly live through all moments with? In other words, for every Martian , JYY wants to count
where if there exists at least one scenario in which Martians and are alive in all moments, and otherwise.
Keep in mind that Martians cannot be resurrected, and a Martian may be deceased at moment . Finally, note that is calculated independently for each pair of Martians, so does not necessarily imply .
Input format
The first line of input consists of three integers , and .
lines of input follow. Each line contains four integers representing a prediction, and will take one of the two described forms:
Output format
Output a single line containing integers. The integer shall be the count of other Martians that may be alive alongside the Martian over all moments.
Limits
.
.
.
Subtask #
|
Score
|
Constraints
|
1 |
10 |
|
2 |
20 |
|
3 |
10 |
|
4 |
20 |
|
5 |
10 |
|
6 |
10 |
|
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 , 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 , and thus .
There are no predictions precluding any other pairs of Martians from both living to moment , so .