题目背景

你得到了 JOI 公司发行的一款电视游戏软件。这是一款制作精良的游戏，你每天都玩得相当开心。

有一天，玩家之间出现了一个被称为“激光”的关卡。这个关卡似乎极其困难，即使是优秀的玩家，也只有极小的概率才能通关。在多次挑战这个关卡的过程中，你注意到，如果能够进行非常高速的判断，就有可能通关，于是你想到，也许可以通过编写程序来应对。

激光关卡的舞台上放置了 $N$ 个防壁。舞台是一个长方形，被划分为 $1 \times 1$ 的正方形格子。每个格子用非负整数 $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$ 的长方形，在关卡开始时占据从格子 $(A_i, i)$ 到格子 $(B_i, i)$ 的位置。你可以在敌人第一次攻击之前，以及敌人每两次攻击之间的任意时刻，多次将防壁向左右移动。一次移动可以将一个防壁向右移动 $1$ 格，或者向左移动 $1$ 格。

激光在碰到防壁时威力会减弱。通过移动防壁，使得所有激光都能依次碰到所有防壁，从而将激光的威力降到最小。

在这个关卡中，你希望尽量减少防壁的移动次数。

任务

给定关卡开始时各个防壁的位置，以及每一次敌人攻击的位置。在移动防壁使得所有激光都能碰到所有防壁的前提下，求每个防壁所需的最小移动次数。

输入格式

从标准输入中读入以下数据：

• 第一行包含两个整数 $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 次。

输入例 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