National Olympiad in Informatics, China, 2003

After spending ten billion dollars, country B has developed a new weapon - the Zenith Protected Linked Hybrid Zone (ZPLHZ). According to legend, the ZPLHZ is a type of spontaneously acting, intelligent weapon that is running nonstop. However, a spy from country A has discovered that the ZPLHZ actually consists of ~M~ independent weapons labeled from 1 to ~M~. Each weapon has two types of statuses: invincible defense mode and attack mode. Initially, weapon number 1 is used for attack, and all other weapons are set to invincible defense mode. Afterwards, if at any time the ~i~-th ~(1 \le i < M)~ independent weapon is destroyed, then 1 second after, the (~i+1~)-th weapon will automatically change from invincible defense mode to attack mode. When the ~M~-th weapon is destroyed, this incredibly expensive ZPLHZ weapon will be entirely destroyed.

To defeat country B, the commander of country A's military decides to use one of the cheapest weapons - bombs, to destroy the ZPLHZ. After a long period of sophisticated research and top-secret spying, country A's military strategists managed to acquire 2D coordinates of the ~M~ weapons that make up the ZPLHZ. Based on these, they have selected ~n~ points on which to plant special time bombs. These ~n~ points are labeled from 1 to ~n~. Each bomb has a radius of ~k~, and will continuously detonate for 5 minutes. Within these 5 minutes, each bomb can instantly destroy all the attack mode weapons from country B that is within a straight-line distance of no larger than ~k~ from the bomb. Similar to the ZPLHZ, bomb ~a_1~ will detonate for 5 minutes, then bomb ~a_2~ will detonate for 5 minutes, followed by bomb ~a_3~, and so forth until the ZPLHZ is destroyed. At the time of each detonation, the undetonated bombs at that time are buried underground, and thus will not be destroyed.

Clearly, it is vital to select the right values for ~a_1, a_2, \dots~ A good program can use the minimal number of bombs while also fully destroying the ZPLHZ. A bad program may use up all the bombs and still not destroy the ZPLHZ. Now, you must determine a sequence ~a_1, a_2, \dots~ so that during the detonation period of bomb ~a_x~, the ZPLHZ will be destroyed. Here, the value of ~x~ must be as small as possible.

Input Specification

The first line of input contains one integer ~T~, the number of test cases to follow. For each test case:

• The first line contains three integers ~M~, ~n~, and ~k~ ~(1 \le M,n \le 100, 1 \le k \le 1\,000)~, indicating that country B's ZPLHZ consists of ~M~ independent weapons, country A has ~n~ bombs at their disposal, and the radius of each bomb is ~k~.
• The next ~M~ lines each contains a pair of integers ~x_i~ and ~y_i~ ~(0 \le x_i, y_i \le 10\,000)~, describing the 2D coordinates of the ~i~-th weapon.
• The next ~n~ lines each contains a pair of integers ~u_i~ and ~v_i~ ~(0 \le u_i, v_i \le 10\,000)~, describing the 2D coordinates of ~i~-th ~(1 \le i \le n)~ bomb.

It is guaranteed that the input will always be valid and will always have a solution.

Output Specification

For each test case, there should be two lines:

• The first line should contain the integer ~x~, representing the number of bombs used.
• The second line should contain ~x~ integers, the values of ~a_1, a_2, \dots, a_x~.

Sample Input

2
4 3 6
0 6
6 6
6 0
0 0
1 5
0 3
1 1
10 10 45
41 67
34 0
69 24
78 58
62 64
5 45
81 27
61 91
95 42
27 36
91 4
2 53
92 82
21 16
18 95
47 26
71 38
69 12
67 99
35 94

Sample Output

2
1 3
5
6 2 1 3 4

Scoring

For each test case, if your output is valid, then you will be scored as follows.

$$\displaystyle score = \begin{cases} 18, & ans - good < -32 \\ 17, & -32 \le ans - good \le -16 \\ 15, & -15 \le ans - good \le -7 \\ 13, & -6 \le ans - good \le -4 \\ 12, & -3 \le ans - good \le -2 \\ 11, & ans - good = -1 \\ 10, & ans - good = 0 \\ 9, & ans - good = 1 \\ 8, & 2 \le ans - good \le 3 \\ 7, & 4 \le ans - good \le 6 \\ 5, & 7 \le ans - good \le 15 \\ 3, & 16 \le ans - good \le 32 \\ 2, & ans - good > 32 \end{cases}$$

where ~good~ is our official solution for ~x~, and ~ans~ is your solution. If your output is legal but does not destroy all the weapons, you will receive a score of ~0~ for that test case. If your output is illegal, you will receive a total score of ~0~ and a verdict of Wrong Answer.

Each test case is scored out of 10, and your total score will be the sum of your scores on each test case. However, a submission cannot score more than 100% of the points.

Problem translated to English by Alex.