Walls

JOI released a TV game, and you got a copy. It is well made, and you have played it every day for fun.

One day, a stage nicknamed 'Laser' appeared among the gamers. It is extremely hard, and even excellent players clear it only with very low probability. After many attempts, you realized that a very fast decision might clear it, and you wondered whether a program could handle it.

The Laser stage is a field with N walls. The field is a rectangle divided into $1 \times 1$ square cells. Each cell is written as $(x, y)$ with integers $x, y \ge 0$. $(0, 0)$ is the bottom-left cell, and $(x, y)$ is the cell reached from $(0, 0)$ by moving $x$ cells right and $y$ cells up.

When the stage starts, an enemy appears and attacks. There are M attacks in order. In the $j$-th attack, the enemy fires a laser straight from cell $(P_j, N+1)$ down to cell $(P_j, 0)$.

Each wall lies on consecutive cells with the same y coordinate. Wall $i$ ($1 \le i \le N$) is a rectangle of width $B_i - A_i + 1$ and height 1. At the start, wall $i$ occupies the cells from $(A_i, i)$ to $(B_i, i)$. Before the first attack and between attacks, you may move the walls left or right any number of times. One move shifts one wall one cell to the right or one cell to the left.

A laser becomes weaker when it hits a wall. You want to minimize the laser power by moving the walls so that every laser hits every wall. You also want to make as few wall moves as possible.

The initial position of each wall and the position of each enemy attack are given. When every laser hits every wall, find the minimum number of moves for each wall.

The first line contains integers N and M, separated by a space. There are N walls, and the enemy attacks M times.

Each of the next N lines contains integers $A_i$ and $B_i$, separated by a space. At the start, wall $i$ is placed from cell $(A_i, i)$ to cell $(B_i, i)$.

Each of the next M lines contains an integer $P_j$. In the $j$-th attack, the enemy fires a laser from cell $(P_j, N+1)$ to cell $(P_j, 0)$.

Print N lines. On the $i$-th line, print the minimum number of moves for wall $i$.

$1 \le N \le 200000$

$1 \le M \le 200000$

$0 \le A_i \le B_i \le 1000000000$ ($1 \le i \le N$)

$0 \le P_j \le 1000000000$ ($1 \le j \le M$)