题目描述

题目译自 XXI Olimpiada Informatyczna — III etap Lampy słoneczne

Bajtazar 拥有一座宽敞美丽的花园，可夜幕降临时，他无法欣赏其魅力。于是，他决定安装太阳灯，让灯光点亮夜晚，延续花园的迷人风采。

Bajtazar 买的灯只照亮特定角度的区域，所有灯的照射角度相同，且必须朝同一方向安装。这些灯是太阳能的，夜间虽无阳光，但若被足够多的其他灯照亮，也会自动发光。当然，接通电源也能让灯亮起。

Bajtazar 在花园中装好灯，并确定了接通电源的顺序。为方便起见，灯按 $1$ 到 $n$ 编号，Bajtazar 在时刻 $i$ 给 $i$ 号灯通电。他想知道每盏灯何时亮起。请你编写程序，帮他解答这个问题。

输入格式

输入第一行包含一个整数 $n$ $(1 \leq n \leq 200000)$，表示 Bajtazar 购买的灯数。

第二行包含四个整数 $X_1, Y_1, X_2, Y_2$ $(-10^9 \leq X_i, Y_i \leq 10^9, (X_i, Y_i) \neq (0,0))$，定义每盏灯的照射区域。若某灯位于 $(x, y)$，其照射区域（含边界）由两条半直线围成的小角度区域决定，第 $i$ $(i=1,2)$ 条半直线从 $(x, y)$ 出发，经过 $(x + X_i, y + Y_i)$，且角度不为 180 度。

接下来的 $n$ 行描述灯的位置，第 $i$ 行包含两个整数 $x_i, y_i$ $(-10^9 \leq x_i, y_i \leq 10^9)$，表示 $i$ 号灯位于 $(x_i, y_i)$。保证无两灯同位。

最后一行包含 $n$ 个整数 $k_1, k_2, \ldots, k_n$ $(1 \leq k_i \leq n)$，表示 $i$ 号灯需被至少 $k_i$ 盏其他灯照亮才会发光。

输出格式

输出一行，包含 $n$ 个整数 $t_1, \ldots, 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

时刻 $1$，Bajtazar 给 $1$ 号灯通电，$3$ 号灯因被 $1$ 号灯照亮而亮起。时刻 $2$，给 $2$ 号灯通电，$4$ 号灯因被 $1, 2, 3$ 号灯照亮而亮起。$5$ 号灯在时刻 $5$ 通电后亮起。

附加样例

1. $n=7$，小型随机样例；
2. $n=6$，灯照射角度为 $0$ 度（Bajtazar 投资了激光灯）；
3. $n=160000$，灯排列成 $400 \times 400$ 网格，照射角度为 90 度，射线平行于坐标轴。

数据范围与提示

对于 $30\%$ 的数据，$n \leq 1000$。