Hide

# Problem JJeopardised Journey

Little Red Riding Hood’s1 grandmother’s hut is already quite old. It needs to be torn down and will be replaced with a new hut. Naturally, she wants the hut to be as safe as possible – nothing could be worse than Little Red Riding Hood being eaten by the big bad wolf.

Grandmother wants to build her hut in one of the forest’s glades2. Little Red Riding Hood’s house – well, that of her parents – is also in a glade. Furthermore, the wolf is also always lurking in one of the glades. If Little Red Riding Hood walks from her home to Grandmother’s hut and passes by the wolf, she will surely be eaten. The wolf only changes its glade during the night, so whenever Little Red Riding Hood is walking through the forest, he will be located in an unknown but fixed glade. He will never be in the glade of Grandmother’s hut nor in the glade of Little Red Riding Hood’s house.

Grandmother considers a glade safe for her to build her new hut there if no matter in which glade the wolf sits, Little Red Riding Hood can always find a way from her home to Grandmother and back. Grandmother has asked you to determine which of the glades are safe for her to build her house in.

## Input

The input consists of:

• One line with two integers $g$ and $h$ ($2 \leq g \leq 2\, 000$, $0 \leq h \leq 2\, 000$), the number of glades and the number of hills. The glades are numbered from $1$ to $g$. Little Red Riding Hood’s house is always located in the $g$th glade.

• $g$ lines, where the $i$th line contains the two integers $x_ i$ and $y_ i$ ($-10^7 \leq x_ i,y_ i \leq 10^7$) giving the $i$th glade’s coordinates.

• $h$ lines, each with three integers $x$, $y$, and $r$ ($-10^7 \leq x,y \leq 10^7$, $0 < r \leq 10^7$) giving the centre and radius of one of the hills.

No two glades have the same coordinates, no two hills share a common point, and no glade is within or on the boundary of a hill.

## Output

Output the indices of all glades where it is safe for Grandmother to build her hut. These indices must be output in ascending order.

Sample Input 1 Sample Output 1
4 3
0 0
0 10
10 0
10 10
5 0 2
10 5 2
2 2 1

2

Sample Input 2 Sample Output 2
7 5
0 0
10 10
10 -10
20 0
30 10
30 -10
40 0
10 4 1
6 -3 3
14 -3 3
20 10 4
30 0 4

4 5 6


Footnotes

1. In German: Rotkäppchen
2. In German: Lichtung
CPU Time limit 8 seconds
Memory limit 1024 MB
Statistics Show