벽

JOI 사가 발매한 TV 게임 소프트웨어를 손에 넣었다. 꽤 잘 만든 게임이라 매일 즐겁게 플레이하고 있었다.

어느 날 게이머들 사이에서 '레이저'라고 부르는 스테이지가 나타났다. 이 스테이지는 매우 어려워서 뛰어난 게이머도 아주 낮은 확률로만 클리어할 수 있다고 한다. 여러 번 도전하던 끝에, 매우 빠른 판단을 내리면 클리어할 가능성이 있다는 것을 깨달았고, 프로그램으로 대응할 수 있지 않을까 생각했다.

레이저 스테이지의 무대에는 N개의 벽이 놓여 있다. 무대는 직사각형이며 $1 \times 1$ 크기의 정사각형 칸으로 나뉜다. 각 칸은 0 이상의 정수 $x, y$를 써서 $(x, y)$로 나타낸다. $(0, 0)$은 왼쪽 아래 모서리 칸이고, $(x, y)$는 $(0, 0)$에서 오른쪽으로 $x$칸, 위로 $y$칸 이동한 칸이다.

스테이지가 시작되면 적이 나타나 공격한다. 공격은 M번 순서대로 이루어진다. $j$번째 공격에서 적은 칸 $(P_j, N+1)$에서 칸 $(P_j, 0)$을 향해 레이저를 곧게 발사한다.

각 벽은 y좌표가 같은 연속된 칸들에 놓인다. 벽 $i$ ($1 \le i \le N$)는 가로 길이가 $B_i - A_i + 1$, 세로 길이가 1인 직사각형이다. 스테이지 시작 시 벽 $i$는 칸 $(A_i, i)$부터 칸 $(B_i, i)$까지를 차지한다. 첫 공격 직전과 공격 사이에 벽을 좌우로 몇 번이고 움직일 수 있다. 한 번의 이동으로 벽 하나를 오른쪽으로 1칸 또는 왼쪽으로 1칸 옮길 수 있다.

레이저는 벽에 부딪히면 위력이 약해진다. 모든 레이저가 모든 벽에 부딪히도록 벽을 움직여 레이저의 위력을 최소로 만들고자 한다. 이때 벽의 이동 횟수도 가능한 한 적어야 한다.

각 벽의 시작 위치와 적의 공격 위치가 주어진다. 모든 레이저가 모든 벽에 부딪히도록 벽을 움직일 때, 각 벽의 이동 횟수 최솟값을 구하라.

첫 줄에 정수 N과 M이 공백으로 구분되어 주어진다. 벽이 N개 있고, 적의 공격이 M번 이루어진다는 뜻이다.

이어지는 N줄의 i번째 줄 (1 ≤ i ≤ N)에는 정수 $A_i$와 $B_i$가 공백으로 구분되어 주어진다. 스테이지 시작 시 벽 i가 칸 $(A_i, i)$부터 칸 $(B_i, i)$까지에 놓여 있다는 뜻이다.

이어지는 M줄의 j번째 줄 (1 ≤ j ≤ M)에는 정수 $P_j$가 주어진다. j번째 공격에서 적이 칸 $(P_j, N+1)$에서 칸 $(P_j, 0)$을 향해 레이저를 쏜다는 뜻이다.

N줄을 출력하라. i번째 줄에는 벽 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$)