题目描述

题目译自 eJOI2024 Day1 T2. Cheese

最近，一群当地农民在 EJOI 国开始交易他们的奶酪产品。每个农民的奶酪都有固定的价格。

在 EJOI 国，交易是用面值为 $2$ 的幂的钞票进行的 $(1,2,4,8, \ldots)$。

有一天，开设了一个市场，每个农民带来了一些他们制作的奶酪样品，打算互相交换。在交换过程中，两位农民可以交换他们的奶酪样品。由于不同农民的奶酪样品价格可能不同，双方可以使用钞票来平衡交易，使每位农民的奶酪和添加的货币的总价值相等。

例如，考虑以下两位农民之间的交换：Victor 和 Sanda。如果 Sanda 的奶酪价格比 Victor 的低 $2$ 个单位，他们可以进行如下交换：首先 Sanda 给 Victor 一张 $8$ 单位的钞票，然后 Victor 给 Sanda 一张 $2$ 单位的钞票和一张 $4$ 单位的钞票。这次交换确保了交易的公平。

市场组织者观察了所有的交易，并将它们记录在笔记本中。由于交易太多，她难以完全记住每笔交易。有时，她记住了交易的确切金额；而有时，她只记得第一位农民支付的部分金额以及用于完成剩余交易的面值最小的钞票。

更正式地说，对于每笔交易，她在笔记本中记录了 $i$ 和 $j$，表示参与交易的农民的编号，$A$ 表示农民 $i$ 首先支付给 $j$ 的金额，其中 $B$ 表示：

• 当 $B=-1$ 时，她记住了交易的确切金额，表示在 $i$ 支付给 $j$ 后交易便已完成。
• 否则，当她不记得交易的确切金额时，$B$ 表示用于完成剩余交易的面值最小的钞票。

作为组织者的朋友，你需要逐一审查每个记录。如果任何记录明显与现有的交易记录相矛盾，应将其忽略。否则，将其视为有效并添加到交易记录中。

输入格式

输入的第一行包含两个整数 $N$ 和 $M$，分别表示农民的数量和市场上的交易数量。

接下来的 $M$ 行包含笔记本中的记录，每行包含 $i, j, A, B$，其中 $i$ 和 $j$ 表示参与交易的农民的编号，$A$ 表示农民 $i$ 首先支付的金额，$B$ 表示用于完成剩余交易的面值最小的钞票，若 $B=-1$，表示在初始支付后双方并没有使用额外的钞票。

输出格式

输出 $M$ 行，每行对应输入中的一笔交易。每行包含一个整数，$1$ 表示交易有效，$0$ 表示交易无效。

4 10
1 2 5 -1
1 2 5 16
2 3 0 4
2 1 1 2
1 3 0 8
1 3 1 8
2 3 16 8
3 2 12 -1
1 4 2 8
4 3 1 4

1
1
1
1
0
1
0
1
1
0

让我们考虑这些交易是如何进行的。

• $1, 2, 5, -1$ - 农民 $1$ 首先给农民 $2$ 支付了 $5$ 个单位的金额，这使得我们知道农民 $2$ 的奶酪比农民 $1$ 的奶酪贵 $5$ 个单位。我们认为这笔交易是有效的，并将其记录下来。
• $1, 2, 5, 16$ - 农民 $1$ 首先给农民 $2$ 支付了 $5$ 个单位的金额，他们使用 $16$ 作为支付剩余交易的最小钞票（这仍然符合农民 $2$ 的奶酪比农民 $1$ 的贵 $5$ 个单位的事实）。一种可能的情况是，在第一次支付 $5$ 个单位后，农民 $1$ 又给了一张 $16$ 单位的钞票，农民 $2$ 给了一张 $16$ 单位的钞票。因此，差额仍然是预期的 $5$ 个单位。
• $2, 3, 0, 4$ - 农民 $2$ 首先给农民 $3$ 支付了 $0$ 个单位的金额，他们使用面值至少为 $4$ 的钞票支付了剩余交易。我们认为这笔交易是有效的，因为我们尚未遇到任何矛盾。
• $2, 1, 1, 2$ - 农民 $2$ 首先给农民 $1$ 支付了 $1$ 个单位的金额，然后他们使用面值至少为 $2$ 的钞票支付了剩余交易。这笔交易仍然一致，因为农民 $1$ 可以给农民 $2$ 三张 $2$ 单位的钞票，总价值为 $6$，这符合农民 $1$ 的奶酪比农民 $2$ 的便宜 $5$ 个单位。
• $1, 3, 0, 8$ - 农民 $1$ 首先给农民 $3$ 支付了 $0$ 个单位的金额，然后他们使用面值至少为 $8$ 的钞票支付了剩余交易。这笔交易与之前的交易不一致，因此我们认为它无效，不再使用它。
• $1, 3, 1, 8$ - 农民 $1$ 首先给农民 $3$ 支付了 $1$ 个单位的金额，然后他们使用面值至少为 $8$ 的钞票支付了剩余交易。这笔交易实际上是有效的。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N, M \leq 5 \cdot 10^{5}$
• $1 \leq i, j \leq N, i \neq j$
• $0 \leq A \leq 2^{15}$
• $B=-1$ 或 $B=1,2,4,8, \ldots, 2^{14}, 2^{15}$

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$7$	$2 \leq N, M \leq 10$
$2$	$8$	$B=2$
$3$	$11$	$B=-1$
$4$	$19$	$3 \leq N \leq 10$
$5$	$38$	$B=1,2,4,8,16,32$
$6$	$17$	无附加限制