Description

Byteasar has a large and pretty garden.

As he would like to be able to appreciate its beauty even after dusk, he installed lamps across the garden.

The lamps are directional, i.e., they illuminate only a certain angle, common to them all. Moreover, Byteasar has aligned them so that they all face the same direction.

Last but not least, these are solar lamps, i.e., they come with solar panels but no batteries, strangely enough! You might think the panels are thus useless, and each lamp will require electricity at night, but not quite: a lamp will produce light if a sufficient number of lamps illuminate it.

By now, Byteasar has even come up with an order in which he is going to supply the lamps with electricity, thus turning them on. For simplicity, we number the lamps from 1 to $n$ in this order, i.e., lamp no. $i$ is supplied with electricity at time $i$. The only thing left for Byteasar (and you, of course!) is to figure out when exactly each lamp will start emitting light. Help Byteasar by writing a program that determines the answer to this question.

Input Format

The first line contains a single integer $n$ ($1 \le n \le 200\,000$): the number of lamps Byteasar installed.

The second line contains four integers $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)$), separated by single spaces, that describe the area illuminated by every lamp.

Namely, if there is a lamp located at the point $(x, y)$, then it illuminates the area (together with its edge) within the smaller of the two angles formed by two rays that both originate at $(x, y)$ such that the $i$-th (for $i = 1, 2$) ray passes through $(x + X_i, y + Y_i)$. This angle is always smaller than 180 degrees.

Each of the next $n$ lines specifies the location of a lamp: the $i$-th such line contains two integers $x_i, y_i$ ($-10^9 \le x_i, y_i \le 10^9$), separated by a single space, indicating that lamp no. $i$ is located at the point $(x_i, y_i)$. You may assume that no two lamps share their location.

The last line contains $n$ integers $k_1, k_2, \cdots, k_n$ ($1 \le k_i \le n$), separated by single spaces, signifying that if lamp no. $i$ is in the area illuminated by at least $k_i$ other lamps, then it will start emitting light as well.

Output Format

Print a single line with $n$ integers $t_1, t_2, \cdots, t_n$, separated by single spaces.

The number $t_i$ should be the time when lamp no. $i$ starts producing light.

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

Hint

There are $n$ lamps. Each lamp has the same angular illumination range and faces the same direction. Lamp $i$ lights up at time $i$, or earlier if it is illuminated by at least $k_i$ other lamps. Determine the time when each lamp lights up.

Translated by ChatGPT 5