Country B has finally developed a new type of weapon after spending billions: the Zenith Protected Linked Hybrid Zone. Legend has it that this is a self-sustaining intelligent weapon system that never stops. However, reconnaissance by Country A has revealed that the system is actually composed of $M$ independent weapons, numbered $1, 2, \dots, M$. Initially, weapon $1$ is active, while all other weapons are in an invincible self-defense state. Subsequently, once weapon $i$ ($1 \le i < M$) is destroyed, weapon $i+1$ automatically switches from its invincible self-defense state to an active state after $1$ second. The expensive system is destroyed once weapon $M$ is destroyed.

To strike a decisive blow against Country B's scientists, the Minister of Defense of Country A plans to use the cheapest weapon—bombs—to destroy the system. After long and precise reconnaissance, scientists from Country A have obtained the planar coordinates of the $M$ weapons in the system, and have determined the planar coordinates of $n$ bombs and placed them. Each bomb has an explosion duration of $5$ minutes. During its detonation time, each bomb can instantly destroy any active Country B weapon whose planar distance from the bomb is no more than $k$. Similar to the system, bomb $a_1$ is detonated first for $5$ minutes, then bomb $a_2$ is detonated for $5$ minutes, then bomb $a_3$ is detonated, and so on, until the system is destroyed.

Clearly, different sequences $a_1, a_2, a_3, \dots$ yield different results in destroying the system. A good sequence can destroy the system using fewer bombs, while a bad sequence might fail to destroy the system even after using all available bombs. Now, you must determine an optimal sequence $a_1, a_2, a_3, \dots$ such that the system is destroyed during the detonation of bomb $a_x$, where $x$ should be as small as possible.

Input

The first line contains three integers: $M, n,$ and $k$ ($1 \le M, n \le 100, 1 \le k \le 1000$), representing that the system of Country B consists of $M$ weapons, Country A has $n$ bombs available, and the attack range of each bomb is $k$. The following $M$ lines each contain a pair of integers $x_i, y_i$ ($0 \le x_i, y_i \le 10000$), representing the planar coordinates of the $i$-th ($1 \le i \le M$) weapon. The next $n$ lines each contain a pair of integers $u_i, v_i$ ($0 \le u_i, v_i \le 10000$), representing the planar coordinates of the $i$-th ($1 \le i \le n$) bomb. The input data is guaranteed to be random and correct.

Output

The first line contains an integer $x$, representing the number of bombs actually used. The second line contains $x$ integers, representing $a_1, a_2, \dots, a_x$ in order. The input data is guaranteed to have a solution.

Examples

Input 1

4 3 6
0 6
6 6
6 0
0 0
1 5
0 3
1 1
0 0

Output 1

2
1 3

Input 2

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

Output 2

5
6 2 1 3 4

Subtasks

If your output is invalid, you will receive $0$ points. Otherwise, let $best$ be the known optimal solution and $ans$ be your answer. Your score depends on the difference $ans - best$:

Note that according to the calculation method above, your score for a single test case might exceed $10$. However, if your total score for this problem is calculated to be greater than $100$, it will be capped at $100$. Therefore, the maximum score for this problem is $100$.