背景

试题来自 清华大学学生算法协会。

题目描述

在二维平面上有 $n$ 条线段。每条线段均以 $x$ 轴的非负半轴 上的一点为起点，以 $y$ 轴的非负半轴 上的一点为终点。换言之，其起点坐标为 $(x_i, 0)$，其中 $x_i \ge 0$，终点坐标为 $(0, y_i)$，其中 $y_i \ge 0$。

你需要回答 $q$ 个查询。每个查询会给出另一条线段，该线段起点在 $x$ 轴上，终点可以在平面的 第一象限或坐标轴的非负部分 上的任意位置。对于每条查询线段，请判断它是否与任何已有线段相交。端点处的相交也算作相交。

查询之间相互独立；也就是说，每次查询给出的线段不会保留到后续的查询中。

输入格式

输入包含多组测试用例。第一行包含一个整数 $T$ ($1 \le T \le 10^6$)，表示测试用例的数量。

对于每组测试用例，第一行包含两个整数 $n, q$ ($1 \le n, q \le 10^6$)，分别表示已有线段的数量和查询的数量。

接下来 $n$ 行，每行包含两个整数 $x_i, y_i$ ($0 \le x_i, y_i \le 10^9$)，描述一条以 $(x_i, 0)$ 为起点、以 $(0, y_i)$ 为终点的线段。

再接下来 $q$ 行，每行包含三个整数 $a_j, b_j, c_j$ ($0 \le a_j, b_j, c_j \le 10^9$)，描述一条查询线段，其起点为 $(a_j, 0)$，终点为 $(b_j, c_j)$。

保证所有测试用例的 $n$ 之和与 $q$ 之和分别不超过 $10^6$。

输出格式

对于每个查询，如果该查询线段与至少一条已有线段相交（包括端点处），则输出 YES，否则输出 NO。

1
3 5
6 6
2 6
6 2
10 4 4
10 3 3
0 1 1
0 2 2
5 2 1

NO
YES
NO
YES
NO

提示

翻译由 DeepSeek V4 Pro 完成