P12358 [eJOI 2024] 奶酪交易 / Cheese

最近，一群农夫开始在 EJOI 大陆上售卖他们的奶酪。**每个农夫的奶酪都有固定的价格。** EJOI 大陆的零钱面额均为 $2$ 的幂，即 $1,2,4,8,\dots$ 等等。 一天，农夫们将自己的奶酪带到一个集市上售卖。在一次交易中，农夫们需要给出自己的零钱来购买对方的奶酪。例如 Sanda 的奶酪比 Victor 的便宜 $2$ 块钱，则一种可能的交易方式是二人交换奶酪，Sanda 给 Victor 一张 $8$ 块钱，Victor 给 Sanda 一张 $2$ 块和一张 $4$ 块。这样双方得到的就平衡了。 市场的负责人注意到了这些有趣的交易，于是他将其全部记录在本子上，具体而言，他是这么记录的： 对于每次交易，首先记录两位农民，分别是 $i$ 和 $j$，接下来两个数 $A$ 和 $B$，$A$ 表示 $i$ 最开始付的零钱数，而 $B$ 则表示： - 若 $B=-1$，那么没有找零，即 $j$ 不用给 $i$ 任何钱。 - 否则，$B$ 表示 $j$ 给 $i$ 找零的钱中，面值最小的一张的面值。 由于负责人有些粗心，有些可能记录错了。作为负责人的朋友，你需要帮助他找到哪些记录是与前面记录矛盾的。 **译者注：若你无法理解题面，请参考样例解释。**

第一行，两个正整数 $N$ 和 $M$，分别表示农夫数量和交易数量。 接下来 $M$ 行，每行四个整数 $i,j,A,B$，表示记录一次交易。

对于每次交易，如果这次交易记录与前面不矛盾，输出 `1`；否则输出 `0`。

**【样例解释】** 共有 $10$ 次交易： - 第一次：`1 2 5 -1`，$1$ 号农夫给了 $2$ 号农夫 $5$ 块，由于 $B=-1$，所以我们可以知道 $1$ 号奶酪比 $2$ 号奶酪便宜 $5$ 块，这显然没有矛盾。 - 第二次：`1 2 5 16`，$1$ 号农夫给了 $2$ 号农夫 $5$ 块，两人在找零过程中使用的最小面值是 $16$。有一种可能的情况是，找零时，$1$ 号给 $2$ 号了 $16$ 块，$2$ 号给 $1$ 号了 $16$ 块（是的，这是可能的！），这样就不与第一条记录矛盾。 - 第三次：`2 3 0 4`，$2$ 号农夫给了 $3$ 号 $0$ 块，他们在找零时使用最小面值是 $4$。因为目前还没有关于 $2$ 和 $3$ 的交易，所以这次显然不矛盾。 - 第四次：`2 1 1 2`，$2$ 号农夫给了 $1$ 号农夫 $1$ 块，他们找零最小面值为 $2$ 块。此时，可能是 $1$ 号给了 $2$ 号三张 $2$ 块，这样他们两个奶酪价格差仍然是 $5$ 块，也不矛盾。 - 第五次：`1 3 0 8`，这次不管如何都不能满足条件，因此矛盾。 剩下 $5$ 次交易，请选手自行模拟。 ---- **【数据范围】** **本题采用 $\text{Subtask}$ 捆绑测试。** |$\text{Subtask}$|分值|特殊性质| |:-:|:-:|:-:| |$1$|$7$|$2\le N,M\le10$| |$2$|$8$|$B=2$| |$3$|$11$|$B=-1$| |$4$|$19$|$3\le N\le10$| |$5$|$38$|$B=1,2,4,8,16,32$| |$6$|$17$|无| 对于 $100\%$ 的数据，$2\le N,M\le5\times10^5,1\le i,j \le N,i\not =j,0\le A\le2^{15},B=-1$ 或 $B=1,2,4,8,\dots,2^{14},2^{15}$。