M. Tower
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

We have $$$n$$$ towers on a horizontal road. The $$$i$$$-th tower is located at $$$a_i$$$ and has light intensity $$$p_i$$$ unit. However, the effect of this tower's light intensity decreases $$$1$$$ unit for each $$$1$$$ unit distance away. This means that for position $$$x$$$, the light intensity it received from the ith tower will be $$$$$$ \max(0,p_i -|a_i - x|) $$$$$$ For position $$$j$$$, the light intensity it receives is defined as the maximum light intensity of the light intensity from all the towers. Given the position of $$$m$$$ people on the same road, output the light intensity each of them receives.

Input

The first line contains two integers $$$n,m$$$ $$$(1\le n,m\le 2\times 10^5)$$$, representing the number of towers and the number of people.

The next $$$n$$$ lines each contain two integers $$$a_i,p_i$$$ $$$(1\le a_i,p_i\le 10^9)$$$, representing the position and intensity of the $$$i$$$-th tower.

The last line contains $$$m$$$ integers $$$b_1,b_2,\dots,b_m$$$ $$$(1\le b_i\le 10^9)$$$, representing the position of each person.

Output

On the $$$i$$$-th line, output the light intensity received by the $$$i$$$-th person.

Examples
Input
1 5
20 10
20 15 28 10 32
Output
10
5
2
0
0
Input
3 1
1 3
3 3
6 8
2
Output
4