由于一些原因，本题空间限制由原题 $\mathtt{\text{4GB}}$ 改为 $\mathtt{\text{2GB}}$。

JOI 街是一条贯通东西的长街。我们将其抽象为一条数轴。

从现在起，将有 $N$ 个贵宾（VIP）来到 JOI 街并大逛特逛。VIP 们以 $1$ 到 $N$ 编号。VIP $i(1\le i\le N)$ 将会在时刻 $T_i$ 从坐标 $A_i$ 前往坐标 $B_i$。其速度是每单位时间 $1$ 单位长度。
如果 $A_i<B_i$，VIP $i$ 将会以不变的速度在正方向上移动。类似地，如果 $A_i>B_i$，VIP $i$ 将会以不变的速度在负方向上移动。

一个保镖的工作是在 JOI 街上巡逻并保护 VIP 们。为了保护一个 VIP，很有必要和 TA 一起逛一会街，同时保护 TA。当然，允许保镖在他们逛街逛到一半时才开始保护，或在他们逛街结束前就停止保护。开始和停止保护的时刻不必为一个整数。
特别地，尽管可能有多个 VIP 在同一坐标，保镖也最多只能保护一个 VIP。

保镖可以在 JOI 街上以每单位时间最多 $1$ 单位长度的速度随意走动。在他们停止保护一个 VIP 之后，可以去到另一个地方再开始保护另一个 VIP。如果一个保镖和 VIP $i$ 一起逛街，那么 VIP 将会对他们一起走过的距离的每单位长度给保镖 $C_i$ 元小费。这里保证 $C_i$ 是偶整数。

作为一个安保公司的员工，您正在计划 $Q$ 份保护 VIP 的方案。这些方案以 $1$ 到 $Q$ 编号。对于方案 $j(1\le j\le Q)$，一个保镖在时刻 $P_j$ 时从坐标 $X_j$ 开始工作。您的任务是分别最大化每个方案中的保镖能够得到的总小费。

请您编写一个程序对于给定的 VIP 和保镖的信息，计算每一个方案中保镖的最大总小费。

在此题的限制下，可以证明答案一定是个整数。

输入格式

第一行，两个整数 $N,Q$。

接下来 $N$ 行，每行四个整数 $T_i,A_i,B_i,C_i$。

接下来 $Q$ 行，每行两个整数 $P_j,X_j$。

输出格式

输出 $Q$ 行。第 $j(1\le j\le Q)$ 行应当包含一个整数表示方案 $j$ 中保镖能得到的最大总小费。

样例一

input

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

output

8
2

explanation

在方案 $1$ 中，一个保镖可以按照以下方式得到 $4+4=8$ 元。

1. 在时刻 $1$ 从坐标 $2$ 开始工作。
2. 在时刻 $1$ 到时刻 $2$ 间保护 VIP $1$。由于他们一起走过了 $1$ 单位长度，他得到 $4\times 1=4$ 元的小费。
3. 在时刻 $2$ 到时刻 $3$ 间留在坐标 $1$。
4. 在时刻 $3$ 到时刻 $5$ 间保护 VIP $2$。由于他们一起走过了 $2$ 单位长度，他得到 $2\times 2=4$ 元的小费。

由于这是最大值，所以第一行输出 $8$。

在方案 $2$ 中，一个保镖可以按照以下方式得到 $2$ 元。

1. 在时刻 $3$ 从坐标 $3$ 开始工作。
2. 在时刻 $3$ 到时刻 $4$ 间从坐标 $3$ 移动到坐标 $2$。
3. 在时刻 $4$ 到时刻 $5$ 间保护 VIP $2$。由于他们一起走过了 $1$ 单位长度，他得到 $2\times 1=2$ 元的小费。

由于这是最大值，所以第二行输出 $2$。

这组样例满足子任务 $1,3,4,5$ 的限制。

样例二

input

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

output

15
0

explanation

在方案 $1$ 中，一个保镖可以按照以下方式得到 $4+1+8+2=15$ 元。

1. 在时刻 $2$ 从坐标 $2$ 开始工作。
2. 在时刻 $2$ 到时刻 $2.5$ 间从坐标 $2$ 移动到坐标 $2.5$。
3. 在时刻 $2.5$ 到时刻 $3.5$ 间保护 VIP $2$。由于他们一起走过了 $1$ 单位长度，他得到 $4\times 1=4$ 元的小费。
4. 在时刻 $3.5$ 到时刻 $4$ 间保护 VIP $1$。由于他们一起走过了 $0.5$ 单位长度，他得到 $2\times 0.5=1$ 元的小费。
5. 在时刻 $4$ 到时刻 $6$ 间保护 VIP $3$。由于他们一起走过了 $2$ 单位长度，他得到 $4\times 2=8$ 元的小费。
6. 在时刻 $6$ 到时刻 $7$ 间保护 VIP $1$。由于他们一起走过了 $1$ 单位长度，他得到 $2\times 1=4$ 元的小费。

由于这是最大值，所以第一行输出 $15$。

在方案 $2$ 中，保镖在时刻 $6$ 从坐标 $3$ 开始工作。然而，TA 无法保护任何 VIP。因此最大总小费为 $0$ 元。因此第二行输出 $0$。

这组样例满足子任务 $1,3,4,5$ 的限制。

样例三

这组样例满足子任务 $1,3,4,5$ 的限制。

input

5 5
8 1 4 10
8 3 7 6
1 4 6 2
3 9 5 4
6 1 9 6
7 6
6 8
1 3
9 4
2 4

output

30
27
48
30
48

限制与约定

对于所有数据，满足

• $1\le N\le 2800$。
• $1\le Q\le 3000000$。
• $1\le T_i\le 1000000000(1\le i\le N)$。
• $1\le A_i\le 1000000000(1\le i\le N)$。
• $1\le B_i\le 1000000000(1\le i\le N)$。
• $1\le C_i\le 1000000000(1\le i\le N)$。
• $A_i\ne B_i(1\le i\le N)$。
• $1\le C_i\le 1000000000(1\le i\le N)$。
• $C_i$ 是偶整数 $(1\le i\le N)$。
• $1\le P_j\le 1000000000(1\le j\le Q)$。
• $1\le X_j\le 1000000000(1\le j\le Q)$。

各子任务分值及限制见下表：

祝大家一遍 AC，求不虐萌萌哒测评机！

时间限制：$\mathtt{\text{25s}}$

空间限制：$\mathtt{\text{2GB}}$

下载

样例数据下载