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) \neq (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, \dots, k_n$ ($1 \le k_i \le n$)，用空格分隔，表示如果第 $i$ 号灯被至少 $k_i$ 盏其他灯照亮，那么它也会开始发光。

在总分 $30\%$ 的测试中，满足 $n \le 1000$。

输出格式

你的程序应向标准输出打印一行，包含 $n$ 个整数 $t_1, \dots, t_n$，用空格分隔。数字 $t_i$ 应为第 $i$ 号灯开始发光的时间。

样例

输入格式 1

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

输出格式 1

1 2 1 2 5

说明

在时间 $1$，Byteasar 打开了第 $1$ 号灯。一旦第 $2$ 号灯被打开，第 $4$ 号灯就开始发光（因为它被第 $1, 2, 3$ 号灯照亮）。

样例评分测试

• 测试点 1：$n = 7$，一个小规模随机测试。
• 测试点 2：$n = 6$，灯照亮的角度为零（Byteasar 误买了激光灯）。
• 测试点 3：$n = 160\,000$，灯排列成 $400 \times 400$ 的网格，且照亮的角度为 $90$ 度，其边平行于笛卡尔坐标轴。