Time Limit: 5000ms

Description

Some psychologists pointed out that, it's easier for people with similar IQ and EQ to play together.
For simplicity, they divede people into two main groups. Everyone belongs to only one group: GFS or ECQ.
Now you are one of the top data scientists, and want to use the kNN algorithm to predict a new man to be GFS or ECQ.
More explicitly, the kNN algorithm is described as follows:
First, calculate the euclidean distances using IQ and EQ as parameters between the new man and all other n people who already belong to one group.
Then, choose those people with the smallest k distances.
Finally, the new man will belong to the group with more people who are chosen at the last step.

Input

On the very first line, there's a number T, indicating the number of test cases.

Then T cases follows. In each case:
Line 1: three numbers n, q, k.
  n(10 <= n <= 10^5): total number of people who already belong to a group
  q(1 <= q <= n): number of queries
  k(1 <= k <= 9): the smallest k distances will be chosen

Line 2 - n+1: three numbers IQ, EQ, GRP, describing features of one person who already belongs to a group
  IQ(0 <= IQ <= 10^4): Intelligence Quotient of this person
  EQ(0 <= EQ <= 10^4): Emotional Quotient of this person
  GRP(GRP = 0 or 1): the group he/she belongs to

Line n+2 - n+1+q: two numbers IQ, EQ, describing features of one person w ho is going to be predicted
  IQ(0 <= IQ <= 10^4): Intelligence Quotient of this person
  EQ(0 <= EQ <= 10^4): Emotional Quotient of this person

We guarantee that k is always an odd number, and there are no same distances while computing.
Notice that IQ and EQ can be double numbers(It is recommended to use double in C/C++).

Output

For each query of a case, output one label(0 or 1) in a line, indicating the predicted group he/she belongs to.

Sample Input

1
5 2 3
0.0 0.0 0
0.0 3.0 0
1.0 0.0 1
3.0 0.0 1
1.0 2.0 0
2.0 0.0
1.0 1.0

Sample Output

1
0

Author

huangshenno1