题目背景

因为数据包过大，所以请在 此处 获取完整数据。

题目描述

在一条数轴上，有 $N$ 个人，他们都是书虫保镖公司的顾客，第 $i$ 个人会在第 $T_i$ 个时刻从第 $A_i$ 个位置移动到第 $B_i$ 个位置，他们的速度是每一个时刻一个单位长度。

如果一个保镖与一个顾客同时在一个位置上，就称保镖在保护这个顾客。设这个保镖从 $a$ 时刻开始保护一个顾客 $i$，从 $b$ 时刻停止保护，那么区间 $[a,b]$ 就称为这个顾客的保护时间，时刻 $a$ 称为保护开始时间，时刻 $b$ 称为保护停止时间。其中 $a$ 和 $b$ 不必是整数。特殊地，如果一个保镖与两个顾客同时在一个位置上，保镖只能保护一个顾客。

保镖可以在数轴上以最多每一个时刻一个单位长度最少静止不动的速度随意移动，当保镖停止保护一个顾客的时候，他可以到另一个位置上保护另一个顾客。如果一个保镖保护第 $i$ 个顾客一起走过的路径长度为 $L$，那么顾客 $i$ 将会以 $C_i$ 津巴布韦币每单位长度给这个保镖 $L \times C_i$ 津巴布韦币作为他的工资。

书虫作为书虫保镖公司的老板，他手里紧握着 $Q$ 份策划保护的方案，其中，第 $j$ 个方案，一个保镖从时刻 $P_j$ 开始从第 $X_j$ 个位置出发开始进行工作。

求对于每个方案，每个保镖获得的总工资数量最多是多少津巴布韦币。

输入格式

第一行两个整数 $N,Q$ 代表顾客数和策划保护的方案数。

接下来 $N$ 行每行四个整数 $T_i,A_i,B_i,C_i$ 描述一位顾客。

接下来 $Q$ 行每行两个整数 $P_j,X_j$ 描述一个策划保护的方案。

输出格式

$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

提示

样例 1 解释

• 保护方案 $1$ 中保镖可以按照下面的方式得到 $4+4=8$ 津巴布韦币：
  • 在时刻 $1$ 从 $2$ 位置开始行动。
  • 从时刻 $1$ 到时刻 $2$ 保护顾客 $1$，一起走过的路径长度为 $1$，得到 $4 \times 1=4$ 津巴布韦币。
  • 时刻 $2$ 到时刻 $3$ 停留在 $1$ 位置。
  • 从时刻 $3$ 到时刻 $5$ 保护顾客 $2$，一起走过的路径长度为 $2$，得到 $2 \times 2=4$ 津巴布韦币。
• 保护方案 $2$ 中保镖可以按照下面的方式得到 $2$ 津巴布韦币：
  • 在时刻 $3$ 从 $3$ 位置开始行动。
  • 时刻 $3$ 到时刻 $4$ 从 $3$ 位置移动到 $2$ 位置。
  • 从时刻 $4$ 到时刻 $5$ 保护顾客 $2$，一起走过的路径长度为 $1$，得到 $2 \times 1=2$ 津巴布韦币。

样例 2 解释

• 保护方案 $1$ 中保镖可以按照下面的方式得到 $4+1+8+2=15$ 津巴布韦币：
  • 在时刻 $2$ 从 $2$ 位置开始行动。
  • 时刻 $2$ 到时刻 $2.5$ 从 $2$ 位置移动到 $2.5$ 位置。
  • 从时刻 $2.5$ 到时刻 $3.5$ 保护顾客 $2$，一起走过的路径长度为 $1$，得到 $4 \times 1=4$ 津巴布韦币。
  • 从时刻 $3.5$ 到时刻 $4$ 保护顾客 $1$，一起走过的路径长度为 $0.5$，得到 $2 \times 0.5=1$ 津巴布韦币。
  • 从时刻 $4$ 到时刻 $6$ 保护顾客 $3$，一起走过的路径长度为 $2$，得到 $4 \times 2=8$ 津巴布韦币。
  • 从时刻 $6$ 到时刻 $7$ 保护顾客 $1$，一起走过的路径长度为 $1$，得到 $2 \times 1=2$ 津巴布韦币。
• 保护方案 $2$ 中保镖无论怎么走都得不到工资，只能得到 $0$ 津巴布韦币。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（6 pts）：$T_i,A_i,B_i,P_j,X_j \le 3000$。
• Subtask 2（7 pts）：$Q=1$。
• Subtask 3（15 pts）：$Q \le 3000$。
• Subtask 4（20 pts）：$Q \le 4 \times 10^4$。
• Subtask 5（52 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le N \le 2800$，$1 \le Q \le 3 \times 10^6$，$1 \le T_i,A_i,B_i,C_i \le 10^9$，$A_i \ne B_i$，$C_i$ 为偶数，$1 \le P_j,X_j \le 10^9$。

说明

翻译自 第２０回日本情報オリンピック　春季トレーニング合宿 Day3 B ボディーガード (Bodyguard) 的英文版本。