最近，一群当地农民开始在 EJOI-land 交易他们的奶酪产品。每位农民都有自己的一块奶酪，其价值为某个固定的成本。

在 EJOI-land，交易通过面值为 2 的幂（$1, 2, 4, 8, \dots$）的钞票进行。

有一天，市场开市了，每位农民都带来了他们制作的一些奶酪样品，打算互相交易。在一次交易中，两位农民可以交换各自的一块奶酪样品。由于不同农民的样品价格可能不同，两位农民可能会使用钞票来平衡交易，使得每位农民的奶酪价值与他们支付的金额之和相等。

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

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

更正式地说，对于每一笔交易，她在笔记本上记录了 $i$ 和 $j$（代表参与交易的农民编号），$A$（代表农民 $i$ 最初支付的金额），以及 $B$，其中： 若 $B = -1$，表示她记得交易的确切金额，意味着在初始支付后交易即完成。 否则，当她不记得交易的确切金额时，$B$ 代表用于支付剩余交易金额的最小面值钞票。

作为组织者的朋友，请你依次审核每一条观察记录。如果任何观察记录与现有的交易记录明显矛盾，则应忽略该记录。否则，将其视为有效并添加到交易记录中。

输入格式

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

接下来的 $M$ 行包含笔记本中的条目，每行包含 $i, j, A, B$，其中 $i$ 和 $j$ 代表农民的编号，$A$ 代表农民 $i$ 最初支付的金额，$B$ 代表用于平衡交易的最小面值钞票，若农民除了初始支付的金额外没有使用任何额外资金，则 $B = -1$。

输出格式

输出 $M$ 行，每一行对应输入中的一笔交易。如果交易有效，则该行包含 1，如果无效，则包含 0。

样例

输入 1

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
1
0
1
0
1
1
0

数据范围

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

子任务