Description

The Three Fairies of Light Sunny Milk, Lunar Child, and Star Sapphire destroyed the ice fairy Cirno’s house to lure her into their prank plan. Of course, Cirno would not let it go. She found the Three Fairies to take revenge, in the form of a danmaku duel. On Normal difficulty, Star Sapphire does not appear in this duel, so only Sunny Milk and Lunar Child face off against Cirno.

In one spell card, the danmaku fired by Sunny Milk and Lunar Child almost fills the entire $100\times 100$ square battlefield, and can be exactly divided into two parts by a stationary, non-vertical straight line. The region above the line is Sunny Milk’s sunlight danmaku, and the region below the line is Lunar Child’s moonlight danmaku.

Cirno is the strongest fairy, but even she gets nervous in the face of dense danmaku from two fairies. Just as her motivation is about to run out, she realizes that if she can use two different strategies for the two kinds of danmaku, her chances of winning will greatly increase. Therefore, she wants to know what kind of danmaku will appear at some key positions.

Unfortunately, Cirno cannot determine where the separating line is. She only knows the current positions of every danmaku on the battlefield and whether each one is moonlight or sunlight. In rare cases (at most $0.1\%$), Cirno may misidentify the type of danmaku because they look so similar. What Cirno wants to know is: for positions where danmaku may appear next, if danmaku does appear, will it be moonlight or sunlight? Can you help her?

Input Format

The first line contains three positive integers $n, m, x$, denoting the number of danmaku currently on the field, the number of positions Cirno wants to query, and that $x$ is the index of the current test point.

The next $n$ lines each contain two real numbers $x,y$ and an integer $k$, separated by spaces. This means there is a danmaku of type $k$ at $(x,y)$. Here $k=1$ represents sunlight danmaku, and $k=-1$ represents moonlight danmaku.

The next $m$ lines each contain two real numbers $x,y$, representing positions where Cirno wants to know what type of danmaku would appear if danmaku appears there.

Output Format

Output $m$ lines, each containing one integer $1$ or $-1$, corresponding to the result for each query.

$1$ means sunlight danmaku, and $-1$ means moonlight danmaku.

4 4 0
3.000 4.000 1
3.000 3.000 -1
8.000 3.000 -1
8.000 4.000 1
100.000 100.000
0.000 0.000
3.141 5.926
0.618 1.618

1
-1
1
-1

Hint

[Sample explanation]

Note: This testdata is invalid due to being too small and lacking sufficient information to determine an accurate answer. It is only for understanding the problem statement and should not be used to test your program.

From the input, we observe that when $y=3$, they are all moonlight danmaku, and when $y=4$, they are all sunlight danmaku. We may guess that the separating line lies between $y=3 \sim y=4$.

Therefore, for the four queries, answer $1,-1,1,-1$ respectively.

[Constraints and notes]

• The area of a single danmaku can be considered $0$.

• If a query position lies exactly on the separating line, treat it as being below the line.

• This problem uses a Special Judge.

• For test point $1$:

$n=100000$, $m=100000$.

If the number of correctly answered queries in your output is at least $30\%$ of all queries, you will receive full score for this test point; otherwise, $0$ points.

• For test points $2 \sim 5$:

$n=1000$, $m=1000$.

If the number of correctly answered queries in your output is at least $60\%$ of all queries, you will receive full score for this test point; otherwise, $0$ points.

• For test points $6 \sim 7$:

$n=100000$, $m=100000$.

If the number of correctly answered queries in your output is at least $70\%$ of all queries, you will receive full score for this test point; otherwise, $0$ points.

• For test points $8 \sim 10$:

$n=100000$, $m=100000$.

If the number of correctly answered queries in your output is at least $80\%$ of all queries, you will receive full score for this test point; otherwise, $0$ points.

• For $100\%$ of the testdata:

$0.000 \le x,y \le 100.000$.

All input real numbers have exactly $3$ decimal places.

It is guaranteed that the input has a valid solution that can meet the required accuracy thresholds.

Time limit: for test points $2 \sim 5$, the limit is $1\ \mathrm{s}$; for the other test points, the limit is $2\ \mathrm{s}$.

Translated by ChatGPT 5