你正在玩一个包含 $n$ 个房间、$m$ 个角色和一颗星星的电脑游戏。房间从左到右排列，编号依次为 1 到 $n$。角色编号为 1 到 $m$。在任何时候，每个角色都位于某个房间中，而星星要么位于某个房间里，要么被某个角色持有。游戏的目标是让角色 $m$ 持有星星。

你可以通过执行若干动作来玩游戏。每个动作都会消耗一定数量的 staracips（游戏中的货币单位），消耗量可能为零。在每次动作中，你选择一个角色 $x$（设该角色当前所在的房间为 $y$），并命令该角色执行以下任一操作：

• 移动到相邻的房间（$y - 1$ 或 $y + 1$），前提是该房间存在。如果角色 $x$ 持有星星，则该角色在移动后继续持有星星。此操作消耗 $s_x$ 个 staracips。已知 $s_1, s_2, \dots, s_m$ 的值。
• 捡起星星并持有它，前提是星星当前位于房间 $y$ 且未被任何角色持有。此操作消耗 0 个 staracips。
• 放下星星并释放它，前提是星星当前由角色 $x$ 持有。星星随后会落入房间 $y$。此操作消耗 0 个 staracips。

游戏包含 $q$ 个关卡，编号为 1 到 $q$。在所有关卡中，每个角色 $i$ 最初都位于房间 $r_i$，且角色 $m$ 必须持有星星才能赢得关卡。关卡之间的唯一区别在于，在每个关卡 $j$ 中，星星最初位于房间 $l_j$。

对于每个关卡，你需要计算赢得该关卡所需消耗的 staracips 总数的最小值。注意，你不需要最小化动作次数。

输入格式

输入的第一行包含三个整数 $n$、$m$ 和 $q$（$1 \le n \le 10^9$；$1 \le m \le 100\,000$；$1 \le q \le 100\,000$）。接下来的 $m$ 行中，第 $i$ 行包含两个整数 $r_i$ 和 $s_i$（$1 \le r_i \le n$；$1 \le s_i \le 10^9$）。接下来的 $q$ 行中，第 $j$ 行包含一个整数 $l_j$（$1 \le l_j \le n$）。

输出格式

对于每个关卡，按顺序输出赢得该关卡所需消耗的 staracips 总数的最小值。

样例

输入 1

6 5 4
1 7
3 2
2 3
5 3
2 5
1
2
5
6

输出 1

5
0
8
14

说明 1

你可以通过以下操作花费 5 个 staracips 赢得第一关：

1. 角色 5 从房间 2 移动到房间 1。此操作花费 5 个 staracips。
2. 角色 5 捡起星星。

你可以通过以下操作花费 0 个 staracips 赢得第二关：

1. 角色 5 捡起星星。

你可以通过以下操作花费 8 个 staracips 赢得第三关：

1. 角色 4 捡起星星。
2. 角色 4 从房间 5 移动到房间 4。此操作花费 3 个 staracips。
3. 角色 4 从房间 4 移动到房间 3。此操作花费 3 个 staracips。
4. 角色 4 放下星星。
5. 角色 2 捡起星星。
6. 角色 2 从房间 3 移动到房间 2。此操作花费 2 个 staracips。
7. 角色 2 放下星星。
8. 角色 5 捡起星星。

你可以通过以下操作花费 14 个 staracips 赢得第四关：

1. 角色 2 从房间 3 移动到房间 4，再到房间 5，最后到房间 6。这些操作总共花费 $3 \times 2 = 6$ 个 staracips。
2. 角色 2 捡起星星。
3. 角色 2 从房间 6 移动到房间 5，再到房间 4，再到房间 3，最后到房间 2。这些操作总共花费 $4 \times 2 = 8$ 个 staracips。
4. 角色 2 放下星星。
5. 角色 5 捡起星星。