L. Empty Triangles
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given $$$n$$$ points on the plane. For some triangles, each spanning three of these points, determine if they are empty (that is, they do not contain any of the other given points).

Input

The first line of input contains the number of test cases $$$Z$$$ ($$$1 \leq Z \leq 400$$$). The descriptions of the test cases follow.

The first line of a test case contains two integers: the number of points $$$n$$$ ($$$3 \leq n \leq 5\,000$$$) and the number of queries $$$q$$$ ($$$1 \leq q \leq 4\,000\,000$$$).

The next $$$n$$$ lines contain the coordinates of points with two integers $$$x_i, y_i$$$ ($$$-10^9 \leq x_i, y_i \leq 10^9$$$). The points are pairwise distinct. No three points are collinear.

The final $$$q$$$ lines describe the queries, each containing three distinct numbers $$$a_j, b_j, c_j$$$ ($$$1 \leq a_j, b_j, c_j \leq n$$$) – the vertices of the $$$j$$$-th triangle.

The total number of points over all test cases does not exceed $$$5\,000$$$. The total number of queries over all test cases does not exceed $$$4\,000\,000$$$.

Output

For every query, print "YES" if the triangle is empty, "NO" if it contains other points.

Example
Input
1
9 4
0 0
4 -1
8 0
9 4
8 8
4 9
0 8
-1 4
3 1
1 3 5
3 5 7
2 4 6
2 6 8
Output
NO
YES
YES
NO