Baltic Olympiad in Informatics: 2016 Day 1, Problem 2

In the capital of Byteland, there is a fenced park whose area is a rectangle. The trees and the visitors in the park are represented as circles.

There are four entrances in the park, one in each corner (1 = bottom-left, 2 = bottom-right, 3 = top-right, 4 = top-left). The visitors can enter and exit the park only through the entrances.

Visitors can enter and exit the park when they touch both sides of a corner of the corresponding entrance. Visitors can move freely in the park, but they cannot overlap any of the trees or the fence.

Your task is to calculate for each visitor, given the entrance they will enter the park, through which entrances they can exit the park.

Note: Two objects touch if they have one common point. Two objects overlap if they have more than one common point.

Constraints

For all subtasks:

~4k < w, h \le 10^9~, where ~k~ is the radius of the largest visitor.

Subtask 1 [27%]

~1 \le n \le 2\,000~

~m = 1~

Subtask 2 [31%]

~1 \le n \le 200~

~1 \le m \le 10^5~

Subtask 3 [42%]

~1 \le n \le 2\,000~

~1 \le m \le 10^5~

Input Specification

The first input line contains two integers ~n~ and ~m~: the number of trees in the park and the number of visitors.

The second input line contains two integers ~w~ and ~h~: the width and the height of the park area. The bottom-left corner is ~(0, 0)~, and the top-right corner is ~(w, h)~.

After this, there are lines that describe the trees. Each line contains three integers ~x, y~ and ~r~: the center of the tree is ~(x, y)~ and its radius is ~r~. The trees do not overlap each other or the fence.

Finally, there are ~m~ lines that describe the visitors. Each line contains two integers ~r~ and ~e~: the radius of the visitor and the entrance they will enter the park.

In addition, no tree overlaps a square area of ~2k \times 2k~ in each corner, where ~k~ is the radius of the largest visitor.

Output Specification

You should output for each visitor a single line containing the entrances through which they can exit the park, in sorted order without spaces in between.

Sample Input

5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1

Sample Output

1234
2
14

Explanation for Sample

The following figure shows the entrance areas and possible routes for each visitor: