题目描述

Byteasar 有一座宽敞而美丽的花园。

为了能够在黄昏后也能欣赏花园的美景，他在花园中安装了一些灯。

这些灯是定向的，即它们只能照亮某个特定的角度，且所有灯的照明角度相同。此外，Byteasar 将它们对齐，使它们都朝向同一个方向。

最后但同样重要的是，这些是太阳能灯——奇怪的是，它们配备了太阳能电池板却没有电池！你可能会认为这些电池板因此毫无用处，每盏灯在夜间仍需电力供应，但事实并非如此：一盏灯在受到足够数量的其他灯照射时，它自己也会发光。

如今，Byteasar 甚至已经想好了为这些灯通电的顺序，从而依次点亮它们。为简单起见，我们按此顺序将灯编号为 $1$ 到 $n$，即第 $i$ 号灯在时刻 $i$ 获得电力供应。对 Byteasar（当然也包括你！）来说，剩下的唯一任务就是弄清楚每盏灯究竟会在何时开始发光。请编写一个程序帮助 Byteasar 确定答案。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 200\,000$)，表示 Byteasar 安装的灯的数量。

第二行包含四个整数 $X_1, Y_1, X_2, Y_2$ ($-10^9 \le X_i, Y_i \le 10^9$, $(X_i, Y_i) \ne (0, 0)$)，以单个空格分隔，用于描述每盏灯的照明区域。

具体来说，如果有一盏灯位于点 $(x, y)$，那么它照亮的是从 $(x, y)$ 出发的两条射线所夹的较小角度内的区域（包括边界），其中第 $i$ ($i = 1, 2$) 条射线经过点 $(x + X_i, y + Y_i)$。该角度总是小于 180 度。

接下来 $n$ 行中的每一行描述一盏灯的位置：第 $i$ 行包含两个整数 $x_i, y_i$ ($-10^9 \le x_i, y_i \le 10^9$)，以单个空格分隔，表示第 $i$ 号灯位于点 $(x_i, y_i)$。数据保证没有两盏灯位于同一位置。

最后一行包含 $n$ 个整数 $k_1, k_2, \cdots, k_n$ ($1 \le k_i \le n$)，以单个空格分隔，其含义是：如果第 $i$ 号灯被至少 $k_i$ 盏其他灯照亮，那么它也会开始发光。

输出格式

输出一行，包含 $n$ 个整数 $t_1, t_2, \cdots, t_n$，以单个空格分隔。

$t_i$ 表示第 $i$ 号灯开始发光的时刻。

5
3 1 1 3
2 1
1 4
3 4
5 6
5 2
1 2 1 3 2

1 2 1 2 5

提示

共有 $n$ 盏灯。每盏灯具有相同的角度照明范围且朝向相同。第 $i$ 盏灯会在时刻 $i$ 通电，但如果它被至少 $k_i$ 盏其他灯照亮，则它会更早发光。请确定每盏灯实际发光的时刻。

由 DeepSeek-R1 翻译。