题目描述

最近，一群农夫开始在 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。

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

提示

【样例解释】

共有 $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}$ 捆绑测试。

对于 $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}$。