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，保镖必须与该 VIP 同行一段时间。保镖可以在 VIP 行走过程中的任意时刻开始保护，也可以在 VIP 结束行走之前停止保护。开始或结束保护的时间不必是整数。然而，即使多位 VIP 处于同一坐标，保镖在同一时刻最多只能保护一位 VIP。

保镖可以在 JOI 大街上自由行走，速度不超过单位时间 $1$ 个单位距离。当保镖结束保护一位 VIP 后，可以移动到另一个地方并开始保护另一位 VIP。如果保镖与 VIP $i$ 同行，VIP 会根据保镖保护该 VIP 所行进的距离，给予保镖每单位距离 $C_i$ 日元的报酬。题目保证 $C_i$ 为偶数。

你所在的安全公司正在规划 $Q$ 个保护 VIP 的项目。项目编号从 $1$ 到 $Q$。对于项目 $j$ ($1 \le j \le Q$)，保镖在时间 $P_j$ 从坐标 $X_j$ 开始工作。你的任务是计算每个项目的最大总报酬。

编写一个程序，在给定 VIP 和项目信息的情况下，计算每个项目的最大总报酬。

在本题的约束条件下，可以证明每个项目的最大总报酬始终为整数。

输入格式

从标准输入读取以下数据。所有给定的值均为整数。

$N \ Q$ $T_1 \ A_1 \ B_1 \ C_1$ $\vdots$ $T_N \ A_N \ B_N \ C_N$ $P_1 \ X_1$ $\vdots$ $P_Q \ X_Q$

输出格式

输出 $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$)
• $A_i \neq 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$)

子任务

1. (6 分) $T_i \le 3\,000, A_i \le 3\,000, B_i \le 3\,000$ ($1 \le i \le N$)。$P_j \le 3\,000, X_j \le 3\,000$ ($1 \le j \le Q$)。
2. (7 分) $Q = 1$。
3. (15 分) $Q \le 3\,000$。
4. (20 分) $Q \le 40\,000$。
5. (52 分) 无附加约束。

样例

样例输入 1

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

样例输出 1

8
2

样例输入 2

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

样例输出 2

15
0

样例输入 3

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

样例输出 3

30
27
48
30
48