P11675 [USACO25JAN] Photo Op G

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$ 的值。

无

无

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