题目描述

题目译自 JOISC 2021 Day3 T2「ボディーガード / Bodyguard」

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$ 中保镖能得到的最大总小费。

数据范围

对于所有数据，满足

• $1 \le N \le 2\,800$。
• $1 \le Q \le 3\,000\,000$。
• $1 \le T_i \le 1\,000\,000\,000\ (1 \le i \le N)$。
• $1 \le A_i \le 1\,000\,000\,000\ (1 \le i \le N)$。
• $1 \le B_i \le 1\,000\,000\,000\ (1 \le i \le N)$。
• $1 \le C_i \le 1\,000\,000\,000\ (1 \le i \le N)$。
• $A_i \ne B_i\ (1 \le i \le N)$。
• $1 \le C_i \le 1\,000\,000\,000\ (1 \le i \le N)$。
• $C_i$ 是偶整数 $(1 \le i \le N)$。
• $1 \le P_j \le 1\,000\,000\,000\ (1 \le j \le Q)$。
• $1 \le X_j \le 1\,000\,000\,000\ (1 \le j \le Q)$。

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

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

8
2

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

15
0

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

30
27
48
30
48