당신은 JOI 사에서 출시한 비디오 게임 소프트웨어를 손에 넣었습니다. 잘 만들어진 게임이어서 매일 즐겁게 플레이하고 있습니다.

어느 날, 게이머들 사이에서 "레이저"라고 불리는 스테이지가 화제가 되었습니다. 이 스테이지는 극도로 어려워서 뛰어난 게이머라도 클리어할 확률이 매우 낮다고 합니다. 여러 번 이 스테이지에 도전하던 중, 당신은 아주 빠른 판단을 내리면 클리어할 가능성이 있다는 것을 깨달았고, 프로그램을 작성하면 이에 대처할 수 있을지도 모른다고 생각했습니다.

레이저 스테이지는 $N$개의 벽이 놓여 있는 곳을 배경으로 합니다. 스테이지는 직사각형 모양이며 $1 \times 1$ 크기의 정사각형 칸들로 나누어져 있습니다. 각 칸은 정수 $x, y \ge 0$을 사용하여 $(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$인 직사각형입니다. 스테이지가 시작될 때 이 벽은 $(A_i, i)$부터 $(B_i, i)$까지의 칸들을 차지하고 있습니다. 당신은 적의 첫 번째 공격 전과 임의의 두 공격 사이에 벽들을 수평 방향으로 원하는 만큼 여러 번 이동시킬 수 있습니다. 한 번의 이동으로 하나의 벽을 오른쪽으로 한 칸 또는 왼쪽으로 한 칸 이동시킬 수 있습니다.

레이저가 벽에 부딪히면 그 위력이 약해집니다. 당신은 레이저가 모든 벽에 부딪히도록 벽들을 이동시켜 레이저의 위력을 최소화하고 싶습니다.

이 스테이지에서 당신은 벽의 총 이동 횟수를 최소화하고 싶습니다.

과제

벽들의 초기 위치와 적의 공격 위치들이 주어졌을 때, 모든 레이저가 모든 벽에 부딪히도록 하기 위한 각 벽의 최소 이동 횟수를 계산하시오.

입력

표준 입력으로부터 다음 데이터를 읽으시오:

• 첫 번째 줄에는 공백으로 구분된 두 정수 $N$과 $M$이 주어집니다. 이는 이 스테이지에 $N$개의 벽이 있고 $M$번의 공격이 수행됨을 나타냅니다.
• 다음 $N$개 줄의 $i$번째 줄 ($1 \le i \le N$)에는 공백으로 구분된 두 정수 $A_i$와 $B_i$가 주어집니다. 이는 스테이지가 시작될 때 벽 $i$가 칸 $(A_i, i)$부터 칸 $(B_i, i)$까지 놓여 있음을 나타냅니다.
• 다음 $M$개 줄의 $j$번째 줄 ($1 \le j \le M$)에는 정수 $P_j$가 주어집니다. 이는 $j$번째 공격에서 적이 칸 $(P_j, N+1)$에서 칸 $(P_j, 0)$을 향해 일직선으로 레이저를 발사함을 나타냅니다.

출력

표준 출력에 $N$개의 줄을 출력하시오. $i$번째 줄 ($1 \le i \le N$)에는 벽 $i$의 최소 이동 횟수를 출력해야 합니다.

제약 조건

모든 입력 데이터는 다음 조건을 만족합니다:

• $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$).

서브태스크

서브태스크 1 [10점]

• $N = 1$을 만족합니다.

서브태스크 2 [45점]

• $A_i = 0$ ($1 \le i \le N$)을 만족합니다.

서브태스크 3 [45점]

• 추가적인 제약 조건이 없습니다.

예제

입력 1

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

출력 1

5
10
1
7

노트

이 입력에서 벽의 이동 횟수를 최소화하는 한 가지 방법은 다음과 같습니다:

• 1번째 공격 전에, 벽 1을 오른쪽으로 3번 이동시키고, 벽 2를 오른쪽으로 2번 이동시키고, 벽 3은 이동시키지 않고, 벽 4를 왼쪽으로 2번 이동시킵니다.
• 2번째 공격 전에, 벽 1은 이동시키지 않고, 벽 2를 왼쪽으로 2번 이동시키고, 벽 3은 이동시키지 않고, 벽 4를 왼쪽으로 2번 이동시킵니다.
• 3번째 공격 전에, 벽 1은 이동시키지 않고, 벽 2를 왼쪽으로 1번 이동시키고, 벽 3은 이동시키지 않고, 벽 4를 왼쪽으로 1번 이동시킵니다.
• 4번째 공격 전에, 벽 1을 오른쪽으로 2번 이동시키고, 벽 2를 오른쪽으로 5번 이동시키고, 벽 3을 오른쪽으로 1번 이동시키고, 벽 4를 오른쪽으로 2번 이동시킵니다.

이렇게 하면 벽 1은 5번, 벽 2는 10번, 벽 3은 1번, 벽 4는 7번 이동하게 됩니다.

스테이지 시작

1번째 공격

2번째 공격

3번째 공격

4번째 공격

입력 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

출력 2

34
178
13
6
18
0
36