题目描述

你获得了 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$ 坐标相同的格子，形成一个宽度为 $B_i - A_i + 1$、高度为 1 的长方形。屏障 $i$（$1 \le i \le N$）在关卡开始时占据从格子 $(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$ 移动次数的最小值。

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

5
10
1
7

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

34
178
13
6
18
0
36

提示

样例 1 解释

对于该输入，一种使屏障移动次数最小的移动方式如下：

• 在第 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 次。

:::align{center}

图片来自于 LibreOJ。 :::

数据范围

所有输入数据满足以下条件：

• $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$）

子任务

子任务 1 [10 分]

• $N = 1$

子任务 2 [45 分]

• $A_i = 0$（$1 \le i \le N$）

子任务 3 [45 分]

无额外限制。

翻译由 Qwen3-235B 完成