Problem Description

It's time to start dash!!

As a LLer, Kris loves dashing and he wants everyone to enjoy the interest of dashing. Kris can dash towards someone and pick him up so that they will dash together, forming a ray. If Kris hits the wall after he picks someone up, they will both enjoy the interest of dashing. For some secret reason, the walls now form a convex hull and Kris can only start dashing form an arbitary point in a triangle outside the polygon. Now Kris wants you to calculate the area of points that he can enjoy dashing with.

Formally, there's a convex hull. You will be given $m$ queries. Each query will give you a triangle $A$ ( maybe degenerated ), which is strictly outside the polygon. You must answer the area of points which satisfy the condition:

1.The point is strictly outside the polygon.

2. There exists a point $P$ in the triangle, the ray from $P$ to this point intersects with the convex hull but the segment from $P$ to this point does not.

Input

This problem contains multiple test cases.

The first line contains an intger $T$ indicates the number of test cases.

For each test case, the frist line contains one intger $n$ ($3 \leq n \leq 10^5$) indicating the number of points in the convex hull.

The next $n$ lines each contains two integers $x_i,y_i$ ($0 \leq |x_i|,|y_i| \leq 10^6$) which means the coordinate of the $i_{th}$ point.

It's garanteed that the points will be given in the order to form the polygon and in counter-clockwise.

Then you will be given an integer $q$ ($1 \leq q \leq 10^5$) indicating the number of queries.

The next $q$ lines each contains six integers $x_1,y_1,x_2,y_2,x_3,y_3$ ($0 \leq |x|,|y| \leq 10^6$) which means the coordinates of the points of the triangle.

It's guaranteed that the sum of $n$ is no more than $6 \times 10^5$.

Output

For each query, print the answer $2 \times S$ in one line. $S$ indicates the area of points meets the condition.

It can be proved that $2 \times S$ is always an integer.

1
8
-1 2
-2 1
-2 -1
-1 -2
1 -2
2 -1
2 1
1 2
1
0 3 0 4 1 5

11