#1657. 「USACO 2025.1 Gold」Photo Op

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

Bessie 目前站在 xy 平面上 处，她想要前往 （）。不幸的是，（）头其他奶牛决定在 轴上摆姿势。更具体地说，奶牛 将位于 ，她的摄影师位于 （），准备拍摄她的照片。他们将在时刻 （）开始摆姿势，并且他们会保持姿势很长时间（他们必须拍出完美的照片）。这里，。

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

如果 Bessie 在时刻 出发，她将需要避开所有在时刻 开始摆姿势的摄影师-奶牛对的视线，此外令她到达最终目的地的距离为 。求从 到 的每一个整数 的 的值。

注 1：Bessie 可以从摄影师或者奶牛的位置经过，这样不算穿越视线。

注 2：如果 Bessie 在时刻 出发，她需要避开的是所有满足 的摄影师-奶牛对的视线，不需要考虑 的摄影师-奶牛对。

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

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

以下 行包含 ， 和 。输入保证所有的 各不相同且与 不同，所有的 各不相同且与 不同。所有 将按升序给出，即 。

输出 行，第 行（从 0 开始索引）包含 。

输入 #1

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

输出 #1

9
9
9
10
12

输入 #2

2 3
10 7
1 2 10
1 9 1

输出 #2

12
16
16

输入 #3

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

输出 #3

12
12
12
12
14
14

样例 2 解释：

对于 答案为 。

对于 答案为 。

样例 3 解释：

对于 答案为 。路径：。

• 测试点 ：。
• 测试点 ：。
• 测试点 ：。
• 测试点 ：没有额外限制。