题目描述

There are $n$ segments on a $2D$ plane. Each segment starts on the non-negative part of the $x$-axis and ends on the non-negative part of the $y$-axis. In other words, its starting point has coordinates $(x_i, 0)$ with $x_i \ge 0$, and its ending point has coordinates $(0, y_i)$ with $y_i \ge 0$.

You are given $q$ queries. In each query, a segment is specified whose starting point lies on the $x$-axis, and whose ending point can be anywhere in the first quadrant or the non-negative parts of the axes of the plane. For each query segment, determine whether it intersects with any of the existing segments. Intersections at endpoints are counted.

Queries are independent of each other; that is, the segment given in each query will not be kept in the remaining queries.

输入格式

The input contains multiple testcases. The first line of the input contains an integer $T$ ($1 \le T \le 10^6$), the number of testcases.

For each test case, the first line contains two integers $n, q$ ($1 \le n, q \le 10^6$), the number of existing segments and the number of queries.

Each of the next $n$ lines contains two integers $x_i, y_i$ ($0 \le x_i, y_i \le 10^9$), describing a segment that starts at $(x_i, 0)$ and ends at $(0, y_i)$.

Then, each of the following $q$ lines contains three integers $a_j, b_j, c_j$ ($0 \le a_j, b_j, c_j \le 10^9$), describing a query segment that starts at $(a_j, 0)$ and ends at $(b_j, c_j)$.

It’s guaranteed that the sum of $n$ and the sum of $q$ over all testcases does not exceed $10^6$, respectively.

输出格式

For each query, print YES if the query segment intersects (including at endpoints) with at least one of the existing segments, and NO otherwise.

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