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.