当地的森林里有很多树！每棵树都位于整数坐标处，并具有一个整数高度。砍倒任何一棵树都会得到一根长度等于其高度的圆木。你想要通过砍倒三棵树来获得三根可以构成三角形的圆木（即这三根圆木能构成一个非退化三角形）。

给定一系列查询，每个查询指定一个轴对齐的矩形区域，请问你是否可以通过砍倒该区域内的三棵树（可能包括边界上的树）来获得三根可以构成非退化三角形的圆木？

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 10^5$)，其中 $n$ 是树的数量，$q$ 是查询的数量。

接下来的 $n$ 行，每行包含三个整数 $x, y$ 和 $h$ ($1 \le x, y, h \le 10^9$)，描述了一棵位于坐标 $(x, y)$ 且高度为 $h$ 的树。所有树的位置各不相同。

接下来的 $q$ 行，每行包含四个整数 $x_{low}, y_{low}, x_{high}$ 和 $y_{high}$ ($1 \le x_{low} \le x_{high} \le 10^9, 1 \le y_{low} \le y_{high} \le 10^9$)，描述了一个用于查询的轴对齐矩形区域。

输出格式

输出 $q$ 行。每行包含一个整数，即对应查询的答案。如果查询区域内存在三棵树可以构成一个非退化三角形，则输出 $1$，否则输出 $0$。请按输入顺序输出查询结果。

样例

样例输入 1

9 5
1 3 3
2 3 1
3 3 4
1 2 1
2 2 5
3 2 9
1 1 2
2 1 6
3 1 5
1 1 1 2
1 1 2 2
1 1 1 3
1 2 3 2
1 1 3 3

样例输出 1

0
1
0
0
1