题目描述

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 panelsbut 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 lightif a sufficient number of lamps illuminate it.

By now, Byteasar has even come up with an order he is going supply the lamps with electricity,thus turning them on.

For simplicity, we number the lamps from 1 to $n$ in this order, i.e., the lamp no. $i$ is supplied with electricity at time $i$. The only thing left for Byteasar (and you, of course!) is tofigure out when exactly each lamp will start emitting light. Help Byteasar by writing a programthat will determine the answer to this question.

给N盏灯，没盏灯能照到的角度范围是相同的，第i盏灯在第i秒或者被ki盏灯照到后都会亮起，问所有灯都在什么时刻亮起

输入格式

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

In the second line of input, there are 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 illuminatesthe area (together with its edge) within the smaller of the two angles formed by tworays 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.

The $n$ input lines that follow specify the locations of the lamps: 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, that indicate that the 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 of the input contains $n$ integers $k_1,k_2,\cdots,k_n$ ($1\le k_i\le n$), separated by single spaces, that signify that if the lamp no. i is in the area illuminated by at least $k_i$ other lamps, then it will start emitting light as well.

输出格式

Your program should print out to the standard output 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 the 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

提示

给N盏灯，没盏灯能照到的角度范围是相同的，第i盏灯在第i秒或者被ki盏灯照到后都会亮起，问所有灯都在什么时刻亮起