cheese — EJOI contest
Task type: batch | Time limit: 2 s | Memory limit: 256 MB | Difficulty: 18
Algorithms: number theory, modular arithmetic, graph theory, union-find

![](_page_0_Picture_0.jpeg)

# Cheese

Recently, a group of local farmers have begun trading their cheese products in EJOI-land. **Each farmer has their own cheese worth some certain fixed cost.**

In EJOI-land, exchanges are made with the help of banknotes that have face value powers of two $(1, 2, 4, 8,...)$.

One day, a market opens where each farmer brings some samples of the cheese they made, intending to trade it with one another. In an exchange, two farmers can trade one sample of their cheeses. Since the price of the samples from different farmers may differ, both farmers may use banknotes to balance the exchange, so that the combined value of each farmer's cheese and the money they add equals the other's.

For example, consider the following exchange between two farmers: Victor and Sanda. If Sanda's cheese is priced 2 units less than Victor's, they may have the following exchange: Sanda gives Victor an 8-unit banknote, Victor gives Sanda a 2-unit banknote and a 4-unit banknote. This exchange ensures that the exchange is balanced.

The market organizer observes all the exchanges and writes them down in her notebook. Since there are a lot of them, she struggles to remember each one completely. Sometimes, she remembers the exact amount of the exchange; other times, she only remembers a part of what the first farmer has given and the smallest banknote used to complete the rest of the exchange.

More formally, for each exchange, she wrote in her notebook $i$ and $j$ representing the indices of the farmers that were part of the exchange, $A$ representing the amount of money that farmer $i$ paid initially, and $B$ where:

*   $B = -1$ she remembers the exact amount of the exchange, meaning that after the initial payment the exchange is finalized
*   otherwise when she doesn't remember the exact amount of the trade, $B$ represents the value of the smallest banknote used to cover the **rest of the exchange**

As the organizer's friend, you're asked to review each observation in turn. If any observation clearly contradicts the existing exchange records, it should be ignored. Otherwise, regard it as valid and add it to the exchange records.

## Input

The first line of input contains two integers $N$ and $M$, representing the number of farmers and the number of exchanges at the market.

The following $M$ lines contain the entries in the notebook, each line containing $i$, $j$, $A$, $B$, where $i$ and $j$ represent the indices of the farmers, $A$ represents the amount of money that farmer $i$ paid initially, and $B$ represents the value of the smallest banknote used to balance the exchange, or $B = -1$, if the farmers didn't use any additional money aside from the initial amount paid.

## Output

Output $M$ lines each corresponding to an exchange from the input. Each line has to contain 1 if the exchange is valid or 0 if it invalid.

## Example

| Input       | Output |
| ----------- | ------ |
| 4 10        | 1      |
| 1 2 5 -1    | 1      |
| 1 2 5 16    | 1      |
| 2 3 0 4     | 1      |
| 2 1 1 2     | 0      |
| 1 3 0 8     | 1      |
| 1 3 1 8     | 0      |
| 2 3 16 8    | 1      |
| 3 2 12 -1   | 1      |
| 1 4 2 8     | 0      |
| 4 3 1 4     | 0      |

Let's consider how these exchanges take place.

*   1, 2, 5, -1 - Farmer 1 gives 5 units of money to farmer 2, which lets us know that the cheese of farmer 2 values 5 more than the one of farmer 1. We regard this exchange as valid, and write it down.
*   1, 2, 5, 16 - Farmer 1 gives 5 units of money to farmer 2, and they use 16 as the minimum banknote to cover the rest (which is still consistent with the fact that the cheese of the second farmer is 5 units more expensive than one of the first one). A possiblity might be that, after the first amount of 5 money, farmer 1 brings, he also gives a banknote of 16, and farmer 2 gives a single banknote of 16. Thus, the difference is 5 as it is expected.
*   2, 3, 0, 4 - Farmer 2 gives 0 units of money to farmer 3, and they use banknotes which are at least of size 4 to cover the rest. We consider the exchange as valid since we still did not get to any contradiction.
*   2, 1, 1, 2 - Farmer 2 gives 1 unit of money to farmer 1, and then they use banknotes of value at least 2. This exchange is yet again consistent, since 1 could give three banknotes of value 2 back to farmer 2, with a total worth of 6, which is consistent with the fact that the cheese of person 1 is worth 5 units less than the one of farmer 2.
*   1, 3, 0, 8 - Farmer 1 gives 0 units of money to farmer 3, and then they use banknotes of worth at least 8. This exchange is inconsistent with the previous exchanges, so we mark it as inconsistent and don't further use it.
*   1, 3, 1, 8 - Farmer 1 gives 1 units of money to farmer 3, and then they use banknotes of worth at least 8. This exchange is actually valid.

Note that the lack of descriptions for the last two exchanges provided is intentional, and not explaining the last four exchanges is yet again, intentional. The contestant should try to figure out the configurations themselves.

## Constraints and Scoring

*   $2 \le N, M \le 5 \cdot 10^5$
*   $1 \le i, j \le N, i \ne j$
*   $0 \le A < 2^{15}$
*   $B = -1$ or $B = 1, 2, 4, 8, \dots, 2^{14}, 2^{15}$

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group, you need to solve all test cases in the test group.

| Group | Score | Limits                              |
| ----- | ----- | ----------------------------------- |
| 1     | 7     | $2 \le N, M \le 10$                 |
| 2     | 8     | $B = 2$                             |
| 3     | 11    | $B = -1$                            |
| 4     | 19    | $3 \le N \le 10$                    |
| 5     | 38    | $B = 1, 2, 4, 8, 16 \text{ or } 32$ |
| 6     | 17    | No additional constraints.          |

Starter code: