Kujou Karen is a girl who loves reading.

In a novel she is currently reading, the story describes a conflict between two tribes. The first tribe has $n$ people, and the second tribe has $m$ people. The position of each person can be represented as a point $(x_i, y_i)$ on a two-dimensional plane.

In this book, people have a strong sense of territory. For any point on the plane, if it is contained (including the boundary) within a triangle formed by three people from the same tribe (which may degenerate into a line segment), then this point belongs to the territory of that tribe. If there exists a point that belongs to the territories of both tribes simultaneously, then the two tribes will go to war to compete for this point.

Years of war have burdened both tribes, so the chief of the second tribe has made a wise decision. He plans to choose a vector $(dx, dy)$ and have all members of his tribe move by this vector. That is, the coordinates of all people in the second tribe will become $(x_i + dx, y_i + dy)$.

He has now planned $q$ candidate migration schemes. He wants you to help him calculate, for each migration scheme, whether the two tribes will still go to war over territory after the migration is completed.

Input

The first line contains three integers $n, m, q$, representing the number of people in the two tribes and the number of candidate migration schemes, respectively.

The next $n$ lines each contain two integers $x_i, y_i$, representing the coordinates of the people in the first tribe.

The next $m$ lines each contain two integers $x_i, y_i$, representing the coordinates of the people in the second tribe.

The next $q$ lines each contain two integers $dx_i, dy_i$, representing a migration scheme.

Output

For each migration scheme, output a single integer on a new line: $0$ if no conflict occurs, and $1$ if a conflict occurs.

Examples

Input 1

4 4 3
0 0
1 0
0 1
1 1
-1 0
0 3
0 2
0 -1
0 0
2 3
0 -1

Output 1

1
0
1

Note

The figure below shows the private territories of the two tribes in the first scheme; the point $(0,0)$ belongs to both tribes, so a war occurs.

The figure below shows the private territories of the two tribes in the second scheme; no point belongs to both tribes, so no war occurs.

The figure below shows the private territories of the two tribes in the third scheme; the point $(0,0)$ belongs to both tribes, so a war occurs.

Constraints

• For 20% of the data, $n, m \le 5, q \le 500$.
• For 40% of the data, $n, m \le 50, q \le 500$.
• For 70% of the data, $n, m \le 10^4, q \le 500$.
• For 100% of the data, $n, m \le 10^5, q \le 10^5$.
• For 100% of the data, it is guaranteed that $-10^8 \le x_i, y_i, dx_i, dy_i \le 10^8$, and $n, m \ge 3$. All people's coordinates are distinct, and for each tribe, not all people are collinear.