题目描述

一条高速铁路上运行着 $n$ 列 CR200J 型动车组列车，小烟想用视频跟拍它们达速运行的画面。

动车组列车达速运行时，速度为每单位时间 $1$ 单位长度。CR200J 的运行速度很低，因此小烟可以很容易地利用主角光环，使自己的最大移动速度也达到每单位时间 $1$ 单位长度。

当小烟与某列动车组位于同一位置时，小烟可以拍摄这列动车组。若在时刻 $x$ 到时刻 $y$ 之间，小烟始终与第 $i$ 列动车组位于同一位置，那么他会获得一段拍摄第 $i$ 列动车组、时长为 $y-x$ 的视频。

注意，小烟在同一时刻只能拍摄一列动车组。若同一位置有多列动车组，他可以任选其中一列拍摄。

小烟只会拍摄动车组达速运行的画面。第 $i$ 列动车组将在时刻 $t_i$ 到达位置 $a_i$ 并开始达速运行，运行到位置 $b_i$ 后开始减速。

拍摄不同动车组的视频具有不同价值。拍摄第 $i$ 列动车组、时长为 $L$ 的视频，其价值为

小烟给出 $Q$ 组拍摄方案。每组方案包含两个参数 $s_i,p_i$，表示在该方案中，小烟将在时刻 $s_i$ 从位置 $p_i$ 出发，以不超过每单位时间 $1$ 单位长度的速度任意移动，并在合适的时刻拍摄视频。

对于每组方案，求小烟最终能够获得的视频总价值的最大值。

输入格式

第一行包含三个正整数 $id,n,Q$，其中 $id$ 表示测试点编号。

接下来 $n$ 行，每行包含四个整数 $t_i,a_i,b_i,c_i$，描述第 $i$ 列动车组。

接下来 $Q$ 行，每行包含两个整数 $s_i,p_i$，描述一组拍摄方案。

输出格式

输出 $Q$ 行，每行一个整数，表示对应方案下能够获得的视频总价值的最大值。

样例 1

输入

2 3 3
1 1 2 2
2 2 4 4
4 3 1 4
1 1
1 3
3 2

输出

16
14
8

样例解释

在第一组方案中，可以通过以下移动方式获得总价值 $16$：

• 时刻 $1$ 到时刻 $2$，小烟从位置 $1$ 以最大速度移动到位置 $2$，同时拍摄列车 $1$，获得价值

  $$1\times 2=2.$$

• 时刻 $2$ 到时刻 $3.5$，小烟从位置 $2$ 以最大速度移动到位置 $3.5$，同时拍摄列车 $2$，获得价值

  $$1.5\times 4=6.$$

• 时刻 $3.5$ 到时刻 $4$，小烟从位置 $3.5$ 以最大速度移动到位置 $3$。

• 时刻 $4$ 到时刻 $6$，小烟从位置 $3$ 以最大速度移动到位置 $1$，同时拍摄列车 $3$，获得价值

  $$2\times 4=8.$$

样例 2

输入

3 5 10
50000 36567 27248 52952
43094 59596 74880 63976
63776 4406 8106 65492
96111 36387 91120 44526
54344 93509 32083 88150
2726 62525
58854 59168
95950 8812
28162 65839
99300 86657
50171 73475
32778 51869
12119 95241
77446 480
6710 37837

输出

6453725868
4741368043
0
6432663327
1246883841
5762322799
6432663327
6453725868
296228075
6432663327

该样例满足测试点 $3$ 的限制条件。

数据范围与子任务

对于全部测试数据：

并保证 $c_i$ 为偶数。

特殊性质如下：

• 性质 A： $t_i,a_i,b_i,s_i,p_i\le 3000$。

• 性质 B： 对于所有 $1\le i\le n$，所有 $a_i$ 相等，且所有 $b_i$ 相等。

• 性质 C： 对于所有 $1\le i\le n$，$c_i=2$。

• 性质 D： 对于所有 $1\le i<j\le n$，均有 $t_j\ge t_i$ 且 $a_j\ge b_i$。

• 性质 E： 对于每个 $1\le i\le Q$，一定存在 $j,k$，使得

  $$s_i+p_i=t_j+a_j, \qquad s_i-p_i=t_k-a_k.$$