You have obtained a video game software released by JOI Corp. It is a well-made game, and you have been playing it every day with some enjoyment.

One day, a stage called "Laser" appeared among the gamers. It seems that this stage is extremely difficult, and it is said that even excellent gamers can clear it with only a very small probability. While challenging the stage many times, you realized that there is a possibility of clearing it by making very fast judgments, and you thought that you might be able to deal with it by creating a program.

The laser stage is set in a place where $N$ walls are placed. The stage is rectangular and is divided into $1 \times 1$ square cells. Each cell is represented by $(x, y)$ using integers $x, y \ge 0$. $(0, 0)$ is the cell at the bottom-left corner, and $(x, y)$ represents the cell $x$ cells to the right and $y$ cells up from $(0, 0)$.

When the stage begins, enemies appear and attack. $M$ attacks are performed in sequence. In the $j$-th attack, the enemy fires a laser straight from cell $(P_j, N+1)$ toward cell $(P_j, 0)$.

Each wall is placed on several consecutive cells with the same $y$-coordinate. Wall $i$ ($1 \le i \le N$) is a rectangle with a horizontal width of $B_i - A_i + 1$ and a vertical width of $1$. At the start of the stage, it occupies the cells from $(A_i, i)$ to $(B_i, i)$. You can move the walls horizontally as many times as you like, both before the enemy's first attack and between any two enemy attacks. In one move, you can move one wall one cell to the right or one cell to the left.

When a laser hits a wall, its power is weakened. You want to minimize the power of the laser by moving the walls so that the laser hits all the walls.

In this stage, you want to minimize the total number of wall movements.

Task

Given the initial positions of the walls and the positions of the enemy attacks, calculate the minimum number of movements for each wall to ensure that every laser hits every wall.

Input

Read the following data from standard input:

• The first line contains two space-separated integers $N$ and $M$. This indicates that there are $N$ walls in this stage and $M$ attacks will be performed.
• The $i$-th line of the following $N$ lines ($1 \le i \le N$) contains two space-separated integers $A_i$ and $B_i$. This indicates that at the start of the stage, wall $i$ is placed from cell $(A_i, i)$ to cell $(B_i, i)$.
• The $j$-th line of the following $M$ lines ($1 \le j \le M$) contains an integer $P_j$. This indicates that in the $j$-th attack, the enemy fires a laser straight from cell $(P_j, N+1)$ toward cell $(P_j, 0)$.

Output

Output $N$ lines to standard output. The $i$-th line ($1 \le i \le N$) should contain the minimum number of movements for wall $i$.

Constraints

All input data satisfies the following conditions:

• $1 \le N \le 200\,000$.
• $1 \le M \le 200\,000$.
• $0 \le A_i \le B_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $0 \le P_j \le 1\,000\,000\,000$ ($1 \le j \le M$).

Subtasks

Subtask 1 [10 points]

• $N = 1$ is satisfied.

Subtask 2 [45 points]

• $A_i = 0$ ($1 \le i \le N$) is satisfied.

Subtask 3 [45 points]

• There are no additional constraints.

Examples

Input 1

4 4
0 3
4 4
2 7
8 11
6
4
3
8

Output 1

5
10
1
7

Note

In this input, one way to minimize the number of wall movements is as follows:

• Before the 1st attack, move wall 1 to the right 3 times, move wall 2 to the right 2 times, do not move wall 3, and move wall 4 to the left 2 times.
• Before the 2nd attack, do not move wall 1, move wall 2 to the left 2 times, do not move wall 3, and move wall 4 to the left 2 times.
• Before the 3rd attack, do not move wall 1, move wall 2 to the left 1 time, do not move wall 3, and move wall 4 to the left 1 time.
• Before the 4th attack, move wall 1 to the right 2 times, move wall 2 to the right 5 times, move wall 3 to the right 1 time, and move wall 4 to the right 2 times.

In this way, wall 1 is moved 5 times, wall 2 is moved 10 times, wall 3 is moved 1 time, and wall 4 is moved 7 times.

Stage start

1st attack

2nd attack

3rd attack

4th attack

Input 2

7 11
12 39
22 23
5 38
6 47
10 43
0 50
18 46
38
19
15
1
12
29
29
0
6
40
6

Output 2

34
178
13
6
18
0
36