Ви придбали відеогру, випущену компанією JOI. Це досить добре зроблена гра, і ви щодня грали в неї із задоволенням.

Одного дня з'явився рівень, який гравці називають «Лазер». Схоже, він надзвичайно складний, і навіть найкращі гравці проходять його лише з дуже малою ймовірністю. Після багатьох спроб ви помітили, що його можна пройти, ухвалюючи рішення дуже швидко, і подумали, що для цього можна написати програму.

Дія лазерного рівня відбувається на полі з $N$ захисними стінами. Поле прямокутне й поділене на квадратні клітинки розміром $1 \times 1$. Кожна клітинка позначається $(x, y)$, де $x, y$ — невід'ємні цілі числа. Клітинка $(0, 0)$ розташована в нижньому лівому куті, а $(x, y)$ — на $x$ клітинок праворуч і $y$ клітинок вище від $(0, 0)$.

На початку рівня з'являється ворог і починає атакувати. Послідовно відбуваються $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