You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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$：没有额外限制。