Вы приобрели видеоигру, выпущенную компанией JOI. Игра оказалась довольно хорошо сделанной, и вы каждый день играли в неё с удовольствием.

Однажды в игре появился уровень, который игроки называют «Лазер». По-видимому, он чрезвычайно сложен: даже выдающимся игрокам удаётся пройти его лишь с очень малой вероятностью. Многократно пытаясь пройти этот уровень, вы заметили, что успех возможен при очень быстром принятии решений, и решили, что с этим может справиться программа.

Действие лазерного уровня происходит на площадке, где расположены $N$ защитных стен. Площадка прямоугольная и разбита на квадратные клетки размером $1\times1$. Каждая клетка обозначается парой неотрицательных целых чисел $(x,y)$. Клетка $(0,0)$ находится в левом нижнем углу, а клетка $(x,y)$ — на $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$ атак.
• Строка $i$ ($1 \le i \le N$) из следующих $N$ строк содержит целые числа $A_i,B_i$, разделённые пробелом. Это означает, что в начале уровня стена $i$ занимает клетки от $(A_i,i)$ до $(B_i,i)$.
• Строка $j$ ($1 \le j \le M$) из следующих $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$ вправо $3$ раза, стену $2$ вправо $2$ раза, стену $3$ не перемещайте, а стену $4$ переместите влево $2$ раза.
• Перед второй атакой стену $1$ не перемещайте, стену $2$ переместите влево $2$ раза, стену $3$ не перемещайте, а стену $4$ переместите влево $2$ раза.
• Перед третьей атакой стену $1$ не перемещайте, стену $2$ переместите влево $1$ раз, стену $3$ не перемещайте, а стену $4$ переместите влево $1$ раз.
• Перед четвёртой атакой переместите стену $1$ вправо $2$ раза, стену $2$ вправо $5$ раз, стену $3$ вправо $1$ раз, а стену $4$ вправо $2$ раза.

При таком способе стена $1$ перемещается $5$ раз, стена $2$ — $10$ раз, стена $3$ — $1$ раз, а стена $4$ — $7$ раз.

Начало уровня → первая атака → вторая атака → третья атака → четвёртая атака.

Входные данные 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