### National Olympiad in Informatics, China, 2003

## Day 2, Problem 3 - ZPLHZ

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 ≤ `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}, `a`_{3}, … 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}, `a`_{3}, … 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 Format

The first line of input will contain 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 ≤`M`,`n`≤ 100, 1 ≤`k`≤ 1000), 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`and_{i}`y`(0 ≤_{i}`x`,_{i}`y`≤ 10000), describing the 2D coordinates of the_{i}`i`-th weapon. - The next
`n`lines each contains a pair of integers`u`and_{i}`v`(0 ≤_{i}`x`,_{i}`y`≤ 10000), describing the 2D coordinates of_{i}`i`-th (1 ≤`i`≤`n`) bomb.

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

### Output Format

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}, …,`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.

where `good` is our official solution for `x`, and `ans` is your solution. If your output is illegal, then your score for the test case will be 0.

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.

All Submissions

Best Solutions

**Point Value:** 25 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 64M

**Added:** May 18, 2014

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...