429. Робот-пылесос

Костя живёт в прямоугольной комнате размером $w \times h$ с четырьмя углами, пронумерованными от 1 до 4 (1 — внизу слева, 2 — внизу справа, 3 — вверху справа, 4 — вверху слева). Нижний левый угол имеет координаты (0, 0), а верхний правый угол — координаты ($w$, $h$).

Для уборки комнаты Костя хочет использовать робот-пылесос, который может перемещаться по комнате в любом направлении. Робот-пылесос можно представить в виде окружности.

В комнате, помимо четырёх углов, есть мебель, с которой роботу-пылесосу лучше не сталкиваться. Вся мебель в комнате Кости круглая, каждый объект можно представить окружностью с центром в точке $(x_i, y_i)$ и радиусом $r_i$. Гарантируется, что окружности мебели не пересекаются между собой и не пересекаются со стенами комнаты.

Для выбора робота-пылесоса Костя делает $m$ специальных расчётов. А именно: он подсчитывает, до каких углов сможет доехать, не врезавшись в мебель или стену, робот-пылесос радиусом $r$, если начнёт в углу с номером $s$. Помогите Косте.

Силой трения в задаче можно пренебречь (иначе говоря, все объекты в комнате могут касаться друг друга, но не могут иметь положительную площадь пересечения). Считается, что робот радиусом $r$ находится в углу, если он касается обеих стен угла одновременно.

Гарантируется, что любой пылесос в запросе находится ближе к углу, чем любая мебель, а также не пересекается с никакой мебелью.

Первая строка ввода содержит два целых числа $n$ и $m$ ($1 \le n \le 2\,000$, $1 \le m \le 100\,000$) — количество элементов мебели в комнате и количество расчётов Кости.

Вторая строка ввода содержит два целых числа $w$ и $h$ ($1 \le w, h \le 10^9$) — ширину и длину комнаты.

После этого вводится $n$ строк, которые описывают мебель. Каждая строка содержит три целых числа $x_i$, $y_i$ и $r_i$ ($0 \le x_i \le w, 0 \le y_i \le h, 1 \le r_i \le \min(w, h)$) и описывает соответствующую окружность — координаты центра и радиус.

Наконец, есть $m$ строк, которые описывают расчёты. Каждая строка содержит два целых числа $r$ и $s$ ($1 \le r \le \min(w, h), 1 \le s \le 4$) — радиус пылесоса и номер угла.

Вы должны вывести для каждого пылесоса одну строку, содержащую номера углов, до которых они могут добраться, в отсортированном порядке без пробелов между ними.

В первом тесте задана комната размером $6 \times 6$, в которой левая и правая половины разделены «стенкой» из трёх окружностей радиусом 1. Таким образом, пылесосы радиуса 1, начинающие в левой половине комнаты (углы 1, 4), не доедут до правой (углы 2, 3), и наоборот.

Во втором тесте по центру комнаты стоит один объект. Первый пылесос может объехать его вдоль стен комнаты, возможно касаясь стен или объекта в определенные моменты и посетить каждый угол. У второго пылесоса это не получится.