Separating Lines

You are given $n$ pairwise distinct points and $m$ lines on the plane.

A line divides the plane into two half-planes. Both of them are closed, which means the line itself belongs to each of the two half-planes. A line is called separating when each of the two half-planes it creates contains at least one of the given points.

For every given line, decide whether it is separating.

Because a point lying exactly on the line belongs to both half-planes, a line that passes through at least one of the points is always separating. In other words, a line fails to be separating only when every point lies strictly on the same side of it, with no point on the line.

The first line contains an integer $Z$ ($Z = 1$), the number of test cases. Each test case is given as follows.

The first line contains an integer $n$ ($1 \le n \le 100\,000$), the number of points. Each of the next $n$ lines contains two integers $x$ and $y$ ($1 \le x, y \le 10^9$), the coordinates of one point. All points are pairwise distinct.

The next line contains an integer $m$ ($1 \le m \le 100\,000$), the number of lines. Each of the next $m$ lines contains four integers $x_1$, $y_1$, $x_2$, $y_2$ ($1 \le x_1, y_1, x_2, y_2 \le 10^9$), the coordinates of two distinct points that the line passes through.

For each of the $m$ lines, print TAK (yes) if it is separating, or NIE (no) otherwise. Print each answer on its own line.