Recently there have been some outbreaks of COVID in k of your n different towns numbered from 1 to n. All citizens, however, have obeyed the law of only moving up to 5km away from the centre of their town. The distance between two coordinates is calculated by using the box distance, if if we have coordinates (x_a, y_a) and (x_b, y_b) then the box distance between them is max(|x_a - x_b|, |y_a - y_b|).

Daniel Andrews (fictionally) would like to prioritise vaccinating some towns before others. To measure which towns should be vaccinated first, Premier Andrews will give each town a value, p_i which is the 'priority value' of the i-th town. p_i is calculated by counting the number of towns around a town that could have transferred the COVID virus via two people meeting, i.e. the number of towns at most 10km (5km + 5km) away (in box distance) from the i-th town that has had an outbreak. Towns which have had an outbreak will include themselves in their 'priority value' count.

Towns with the highest p_i value should be vaccinated first, if there is a tie, then the town with the smallest town number should be vaccinated first.

Output the towns in order of which will get vaccinated first.

Input

Your first line will contain two space separated integers n and k, representing the number of towns total and the number of towns which have an outbreak respectively.

Your next n lines will contain two space separated integer each, the i-th line will contain the x and y-coordinates for the i-th town.

Your next line will contain k space-separated integers, each of which represents the number of a town that has had an outbreak.

1 ≤ k ≤ n ≤ 10^5

0 ≤ x-coordinate, y-coordinate ≤ 10^9

Output

You should output n space-separated integers, the i-th of which should be the i-th town to get vaccinated (so the first integer will be the first town to get vaccinated, etc.).

Example

Input 1
3 1
0 11
0 10
0 0
3

Output 1
2 3 1

Input 2
4 2
0 11
9 0
0 1
11 11
1 2

Output 2
3 1 2 4