J. Island
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

For his next video, Mr. Beast has gathered $$$n$$$ contestants on his private planet Island, which, fittingly, is an ocean planet with a single large island. Each contestant is given two numbers $$$a_i$$$ and $$$b_i$$$, which are the beginning and end of a sequence of consecutive numbers that the contestant has to count, in order. For a prize of 1 trillion dollars, the contestants have to work together to ensure that each contestant counts their own numbers while maintaining a nondecreasing order between all the contestants' numbers.

Now, the contestants need your help to answer $$$q$$$ queries asking for the numbers that will be counted at various positions. In other words, each query asks for the number at a specific position in the sorted list containing all the sequences merged together.

Input

The first line of input contains $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 10^5$$$), the number of sequences and the number of queries, respectively.

The next $$$n$$$ lines each contain two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i \le b_i \le 10^9$$$), the beginning and end (inclusive) of the $$$i^\text{th}$$$ sequence of consecutive numbers, respectively.

The next line contains $$$q$$$ integers $$$x_1, x_2, ..., x_n$$$ ($$$1 \le x_i \le 10^{14}$$$), the position that each query asks about in the sorted list; each position is guaranteed to be valid.

Output

The output should be $$$q$$$ integers, each on a separate line, the number counted at each query's position.

Example
Input
3 9
1 3
2 4
3 5
1 2 3 4 5 6 7 8 9
Output
1
2
2
3
3
3
4
4
5
Note

The three given sequences are $$$1, 2, 3$$$; $$$2, 3, 4$$$; and $$$3, 4, 5$$$. When merged together and sorted, the result is $$$1, 2, 2, 3, 3, 3, 4, 4, 5$$$. The queries ask for every index in order, so the whole list is printed.