Optimal Bomb Sequence to Destroy the Zenith Protected Linked Hybrid Zone

B country has spent billions to develop a new weapon system called the Zenith Protected Linked Hybrid Zone. Contrary to legends of it being an ever‐active self‐propelling intelligent weapon, espionage by A country revealed that it is in fact composed of \(M\) independent weapons numbered \(1, 2, \ldots, M\). Initially, only weapon \(1\) is in attack mode while the others are in an invincible defensive state. Once weapon \(i\) (where \(1 \le i < M\)) is destroyed, weapon \(i+1\) will automatically switch from defense to attack mode after \(1\) second. When weapon \(M\) is eliminated, the entire expensive chain formation is destroyed.

To decisively embarrass the scientists of B country, the defense minister of A country has decided to use the cheapest of weapons – bombs – to destroy the formation. The scientists in A have precisely detected the planar coordinates of the \(M\) weapons and also have determined the coordinates of \(n\) bombs which have been planted. Each bomb, once triggered, explodes for \(5\) minutes (i.e. \(300\) seconds), and during this explosion every bomb can instantly destroy any B country weapon that is in attack mode and whose distance from the bomb is no more than \(k\) (i.e. within radius \(k\)).

Similar to the chain formation, the bombs are activated in sequence. First bomb \(a_1\) explodes for \(5\) minutes, then bomb \(a_2\) explodes for \(5\) minutes, followed by bomb \(a_3\), and so on until the formation is destroyed. Note that if a bomb is activated when the current active weapon is the \(i\)th one, it can destroy it immediately (if the bomb is within range). Then after \(1\) second, the \(i+1\)th weapon will become active and, if it is within range of the still-exploding bomb (and if the explosion window has not exceeded \(300\) seconds), the bomb can destroy it too. Thus, a single bomb can eliminate a contiguous block of weapons starting from the currently active weapon, but at most \(301\) weapons can be destroyed by one bomb (since the delay between consecutive weapon activations is \(1\) second and \(0 \le t \le 300\)).

Your task is to determine an optimal sequence of bombs \(a_1, a_2, a_3, \ldots\) (selecting bombs from the available \(n\) bombs, each used at most once) such that the entire chain formation is destroyed by the end of the explosion of bomb \(a_x\), where \(x\) is as small as possible. If it is impossible to destroy the formation using the bombs available, output -1.

inputFormat

The first line contains three integers \(M\), \(n\), and \(k\): the number of weapons, the number of bombs, and the maximum distance a bomb can affect.

The next \(M\) lines each contain two integers representing the \(x\) and \(y\) coordinates of the weapons \(1\) through \(M\) (in order).

The following \(n\) lines each contain two integers representing the \(x\) and \(y\) coordinates of the bombs. Bombs are numbered from \(1\) to \(n\) in the order of input.

outputFormat

If it is possible to destroy the chain formation, the first line should contain an integer \(x\), representing the number of bombs used in the optimal sequence. The second line should contain \(x\) space-separated integers denoting the indices of the bombs in the order they should be detonated.

If it is impossible, output a single line containing -1.

sample

3 3 5
0 0
3 4
10 10
0 0
3 4
10 10

2
1 3