Problem J
Jeopardised Journey

Little Red Riding Hood’s¹ 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 glades². 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.

Little Red Riding Hood always walks from one glade to another. In order to avoid getting eaten by the wolf, she has to check whether the wolf is in the glade she currently wants to walk to. Luckily, she has a pair of binoculars. So whenever she is in one of the glades and wants to go to some other glade, she first uses her binoculars to check whether the wolf is in that other glade. If he is, she won’t go to that glade. The problem, however, is the following: The forest is not flat. Throughout the forest there are hills, and if a hill is in-between Little Red Riding Hood’s current glade and the next glade she wants to go to, she cannot use her binoculars to check whether the wolf is in that next glade. She will never go from her current glade to another glade if she cannot check that other glade with her binoculars. This includes both the glade of her own home and that of Grandmother’s hut (the wolf will never be there, but it is still important for her to check in order to feel comfortable). Each of the hills is a perfect circle and we assume that the glades are sufficiently small compared to the hills so that we consider them to be points. Even if the line-of-sight between two glades is only tangent to a hill, Little Red Riding Hood’s sight is blocked. No two hills intersect and no glade is within or on the boundary of a hill.

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.

Figure 1: The first sample input.

Figure 2: The second sample input.

4 3
0 0
0 10
10 0
10 10
5 0 2
10 5 2
2 2 1

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