在 Byteland 的首都，有一个围起来的矩形公园。公园里的树木和游客都被表示为圆。

公园有四个入口，每个角各一个（1 = 左下，2 = 右下，3 = 右上，4 = 左上）。游客只能通过入口进出公园。

当游客接触到相应入口的两个边时，他们就可以进出公园。游客可以在公园内自由移动，但不能与任何树木或围栏重叠。

你的任务是：对于每位游客，给定他们进入公园的入口，计算他们可以从哪些入口离开公园。

输入格式

第一行包含两个整数 $n$ 和 $m$：公园里的树木数量和游客数量。

第二行包含两个整数 $w$ 和 $h$：公园区域的宽度和高度。左下角坐标为 $(0, 0)$，右上角坐标为 $(w, h)$。

接下来有 $n$ 行，描述树木。每行包含三个整数 $x, y$ 和 $r$：树的中心为 $(x, y)$，半径为 $r$。树木之间以及树木与围栏之间互不重叠。

最后有 $m$ 行，描述游客。每行包含两个整数 $r$ 和 $e$：游客的半径以及他们进入公园的入口编号。

此外，在每个角 $2k \times 2k$ 的正方形区域内没有树木，其中 $k$ 是半径最大的游客的半径。

输出格式

对于每位游客，输出一行，包含他们可以离开公园的入口编号，按升序排列，中间没有空格。

说明

如果两个物体有一个公共点，则称它们接触。如果两个物体有超过一个公共点，则称它们重叠。

样例

输入 1

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

输出 1

1234
2
14

下图展示了入口区域以及每位游客可能的路线：

子任务

在所有子任务中，$4k < w, h \le 10^9$，其中 $k$ 是半径最大的游客的半径。

• 子任务 1（27 分）：$1 \le n \le 2000$，$m = 1$
• 子任务 2（31 分）：$1 \le n \le 200$，$1 \le m \le 10^5$
• 子任务 3（42 分）：$1 \le n \le 2000$，$1 \le m \le 10^5$