Code Submission Evaluation System Login

BOI 2016, day 1

Start:2016-05-12 09:00:00
End:2016-05-12 14:00:00
 

Tasks | Scoreboard | Statistics


CSES - BOI 2016, day 1 - ParkCSES - Park

Park

Time limit:2.50 s
Memory limit:256 MB

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.

Input

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 $n$ 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

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.

Notes

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

Example

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


Output:
1234
2
14


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

Subtasks

In all subtasks $4k < w,h \le 10^9$ where $k$ is the radius of the largest visitor.

Subtask 1 (27 points)
Subtask 2 (31 points)
Subtask 3 (42 points)