In a Cartesian coordinate system, we are given $n$ points. These $n$ points are considered reachable. If points $A$ and $B$ are reachable, then all points on the line segment $AB$ are also reachable.

Given $m$ circles, determine which circles satisfy the condition that every point inside the circle is reachable.

Input

The first line contains an integer $T$, representing the number of test cases.

For each test case:

The first line contains an integer $n$.

The next $n$ lines each contain two integers $x_i, y_i$, representing the coordinates of the points.

The next line contains an integer $m$.

The next $m$ lines each contain three integers $X_i, Y_i, R_i$, representing the circles.

Output

For each test case, output a single line containing a binary string of length $m$. A 0 indicates that there exists at least one unreachable point inside the circle, and a 1 indicates that all points inside the circle are reachable.

Examples

Input 1

1
8
1 10
1 -10
10 1
8 -5
-10 0
8 6
-4 8
-6 8
15
2 -1 3
8 -1 6
-7 -10 2
-10 -1 4
7 10 10
-1 -7 9
-5 0 5
-5 5 4
10 -7 4
-5 5 1
2 1 6
10 3 7
-2 0 3
-2 0 7
-9 -6 6

Output 1

100000000110100

Note

Idea: ccz181078, Solution: ccz181078, Code: ccz181078, Data: ccz181078

Example explanation:

The red points are the given points, the orange circles represent queries with an answer of 1, and the blue circles represent queries with an answer of 0.

$1\leq n,m\leq 5\times 10^5$, $1\leq R_i\leq 10^6$, $-10^6\leq x_i,y_i,X_i,Y_i\leq 10^6$, $\sum n\leq 5\times 10^5$, $\sum m\leq 5\times 10^5$.

It is guaranteed that the answer does not change if $R_i$ is changed by at most $1$.