题目描述

Farmer John 的农场充满了茂盛的植被，每头奶牛都想拥有一张这里的自然美景的照片。不幸的是，Bessie 还有其他地方要去，但她不想打扰任何摄影活动。

Bessie 目前站在 xy 平面上 $(X,0)$ 处，她想要前往 $(0,Y)$（$1\le X,Y\le 10^6$）。不幸的是，$N$（$1 \leq N \leq 3 \cdot 10^5$）头其他奶牛决定在 $x$ 轴上摆姿势。更具体地说，奶牛 $i$ 将位于 $(x_i,0)$，她的摄影师位于 $(0,y_i)$（$1 \leq x_i,y_i \leq 10^6$），准备拍摄她的照片。他们将在时刻 $s_i$（$1 \leq s_i < T$）开始摆姿势，并且他们会保持姿势很长时间（他们必须拍出完美的照片）。这里，$1\le T\le N+1$。

Bessie 知道每头奶牛的摄影安排，她将选择最短欧几里得距离到达目的地，而不穿越任何摄影师与其对应的奶牛之间的视线（她的路径将由一条或多条线段组成）。

如果 Bessie 在时刻 $t$ 出发，她将避开所有在时刻 $s_i \le t$ 开始摆姿势的摄影师-奶牛对的视线，此外令她到达最终目的地的距离为 $d_t$。求从 $0$ 到 $T-1$ 的每一个整数 $t$ 的 $\lfloor d_t\rfloor$ 的值。

输入格式

输入的第一行包含 $N$ 和 $T$，为在 $x$ 轴上摆姿势的奶牛数量及 Bessie 可以出发的时刻数量。

第二行包含 $X$ 和 $Y$，分别表示 Bessie 起始点的 $x$ 坐标以及目的地的 $y$ 坐标。

以下 $N$ 行包含 $s_i$，$x_i$ 和 $y_i$。输入保证所有的 $x_i$ 各不相同且与 $X$ 不同，所有的 $y_i$ 各不相同且与 $Y$ 不同。所有 $s_i$ 将按升序给出，即 $s_i \leq s_{i+1}$。

输出格式

输出 $T$ 行，第 $t$ 行（从 0 开始索引）包含 $\lfloor d_t\rfloor$。

4 5
6 7
1 7 5
2 4 4
3 1 6
4 2 9

9
9
9
10
12

2 3
10 7
1 2 10
1 9 1

12
16
16

5 6
8 9
1 3 5
1 4 1
3 10 7
4 9 2
5 6 6

12
12
12
12
14
14

提示

样例 2 解释：

对于 $t=0$ 答案为 $\lfloor \sqrt{149} \rfloor=12$。

对于 $t=1$ 答案为 $\lfloor 14+\sqrt 5\rfloor=16$。

样例 3 解释：

对于 $t=5$ 答案为 $\lfloor 1+\sqrt{9^2+7^2}+2\rfloor=14$。路径：$(8,0)\to (9,0)\to (0,7)\to (0,9)$。

• 测试点 $4\sim 6$：$N\le 100$。
• 测试点 $7\sim 9$：$N\le 3000$。
• 测试点 $10\sim 12$：$T\le 10$。
• 测试点 $13\sim 18$：没有额外限制。