Park

In the capital of Byteland there is a rectangular park surrounded by a fence. The trees and the visitors in the park are all drawn as circles.

The park has one entrance in each corner. Entrance 1 is the bottom left corner, entrance 2 is the bottom right corner, entrance 3 is the top right corner, and entrance 4 is the top left corner. A visitor can enter and leave the park only through an entrance.

A visitor enters or leaves through an entrance when the visitor touches both sides of that corner at the same time. Inside the park a visitor moves freely, but a visitor must never overlap a tree or the fence. Touching is not overlapping, so touching is allowed.

Every visitor comes in through a given entrance. For each visitor, determine the entrances that visitor can leave through.

The first line contains the number of trees in the park $n$ and the number of visitors $m$.

The second line contains the width $w$ and the height $h$ of the park. The bottom left corner of the park is $(0, 0)$ and the top right corner is $(w, h)$.

Each of the next $n$ lines contains three integers $x$, $y$ and $r$ describing a tree. The center of the tree is $(x, y)$ and its radius is $r$. The trees do not overlap each other and they do not overlap the fence.

Each of the last $m$ lines contains two integers $r$ and $c$ describing a visitor. $r$ is the radius of the visitor and $c$ is the entrance that visitor comes in through.

For each visitor print one line with the entrances that visitor can leave through, in increasing order and with no spaces in between. The entrance $c$ the visitor came in through is always part of the answer.

• $0 \le n \le 1000$
• $1 \le m \le 100000$
• $4k < w \le 10^9$ and $4k < h \le 10^9$, where $k$ is the radius of the largest visitor.
• The radius of a tree satisfies $1 \le r \le 10^9$.
• The radius of a visitor satisfies $1 \le r \le 10^9$ and the entrance number satisfies $1 \le c \le 4$.
• Every number in the input is an integer.

Two shapes touch if they have exactly one common point, and they overlap if they have two or more common points. So if the gap between two trees is exactly as wide as the diameter of a visitor, that visitor can pass between them while touching both. The same holds for a gap between a tree and the fence.

The figure below shows the entrance areas and the routes each visitor of the first example can take.