题目描述

不知为何，Mitko 又一次掉进了一张矩形表格中。表格左下角格子的坐标是 (1, 1)。现在他位于坐标为 (X, 1) 的格子中心，当然，他现在最想做的事情就是逃出去。

已知有 M 个格子的中心是出口。

每过 1 秒，Mitko 可以移动到一个相邻格子的中心（即共享一条边的格子）。

遗憾的是，表格里有 N 面墙。每面墙由四个整数 sX、fX、Y 和 V 描述。这表示：对于所有满足 sX <= i <= fX 的整数 i，在坐标为 (i, Y) 的格子的上边有一面密度为 V 的墙。

如果 Mitko 所在格子的上边有一面墙，他仍然可以直接向上移动，但这次移动将花费 V 秒（即墙的密度），才能到达上方格子的中心。

现在 Mitko 想知道：从起始格子出发，到达每一个可能出口所需的最短时间分别是多少（每个出口都单独从起点出发计算）。

请编写程序 wall，帮助他得到这些答案。

输入格式

第一行包含一个正整数 X，表示起始格子的 X 坐标。
第二行包含两个整数 N 和 M，分别表示墙的数量和出口的数量。
接下来 N 行，每行包含四个整数 sX、fX、Y 和 V，描述一面墙。
接下来 M 行，每行包含两个整数 eX 和 eY，表示一个出口格子的坐标。

输出格式

输出 M 行，第 i 行输出一个整数，表示从起始格子到第 i 个出口的最短时间。
出口的编号按照输入顺序确定。

数据范围

已知：

• 不会有两面墙具有相同的 Y 坐标；
• 输入中出口格子可能重复出现；
• 设 max(X) 为所有墙和出口中出现的最大 X 坐标；
• 设 max(Y) 为所有墙和出口中出现的最大 Y 坐标。

则在所有子任务中：

• 2 <= sX <= fX
• 1 <= Y < 10^9
• 1 <= V < 10^9
• 2 <= eX
• 1 <= eY < 10^9

子任务与评分

对于每个子任务，只有当该子任务对应的所有测试全部通过时，才能获得该子任务的分数。

样例 1

输入 1

4
1 2
2 4 3 2
3 3
3 4

输出 1

3
5

样例 2

输入 2

4
1 2
2 4 3 100
3 3
3 4

输出 2

3
6

样例解释

图中 M 表示 Mitko 的起点，E1、E2 分别表示第 1、2 个出口，红色线段表示墙。

在第一个样例中，到 E1 的一种可行最短路径为：

(4, 1) -> (4, 2) -> (4, 3) -> (3, 3)

每次移动耗时都是 1 秒，因此总时间为 3 秒。

到 E2 的一种可行路径为：

(4, 1) -> (4, 2) -> (4, 3) -> (4, 4) -> (3, 4)

其中 (4, 3) -> (4, 4) 这一步要穿过一面密度为 2 的墙，因此耗时 2 秒。

在第二个样例中，到 E1 的最优路径不变；但到 E2 时，若穿墙会花费 100 秒，因此不再最优。一个可行路径为：

(4, 1) -> (4, 2) -> (4, 3) -> (5, 3) -> (5, 4) -> (4, 4) -> (3, 4)

注意，Mitko 始终是在一个格子的中心与另一个格子的中心之间移动。