题目描述

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

给定若干询问，每个询问指定一个轴对齐的矩形区域。问能否通过砍伐该区域内的三棵树（包括位于矩形边界上的树）得到三根三角形圆木？

输入格式

输入的第一行包含两个整数 $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_{\text{low}}$、$y_{\text{low}}$、$x_{\text{high}}$ 和 $y_{\text{high}}$（$1 \le x_{\text{low}} \le x_{\text{high}} \le 10^9$，$1 \le y_{\text{low}} \le y_{\text{high}} \le 10^9$），描述一个询问的轴对齐矩形区域。

输出格式

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

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

0
1
0
0
1

提示

翻译由 DeepSeek V3.2 完成