Problem Description

On a number line, there are $N$ individuals, all customers of the Bookworm Security Company. The $i$-th person will move from position $A_i$ to position $B_i$ at time $T_i$, with a speed of one unit per time unit.

A bodyguard is considered to be protecting a customer if they are at the same position at the same time. If a bodyguard starts protecting a customer $i$ at time $a$ and stops at time $b$, the interval $[a, b]$ is called the protection period for that customer, with time $a$ being the start time and time $b$ being the stop time. Note that $a$ and $b$ do not need to be integers. If a bodyguard is at the same position as two customers simultaneously, the bodyguard can only protect one of them.

The bodyguard can move freely on the number line at a speed of at most one unit per time unit or remain stationary. When a bodyguard stops protecting one customer, they can move to another position to protect another customer. If a bodyguard protects the $i$-th customer for a distance $L$, the customer will pay the bodyguard $L \times C_i$ Zimbabwean dollars as their salary.

Bookworm, the owner of the Bookworm Security Company, has $Q$ planned protection schemes. In the $j$-th scheme, a bodyguard starts working from position $X_j$ at time $P_j$.

Determine the maximum total salary in Zimbabwean dollars that each bodyguard can earn for each scheme.

Input Format

The first line contains two integers $N$ and $Q$, representing the number of customers and the number of planned protection schemes, respectively.

The next $N$ lines each contain four integers $T_i, A_i, B_i, C_i$, describing a customer.

The next $Q$ lines each contain two integers $P_j, X_j$, describing a planned protection scheme.

Output Format

Output $Q$ lines, each containing a single integer representing the maximum total salary in Zimbabwean dollars that a bodyguard can earn for each scheme.

Sample Input and Output

Input Sample #1

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

Output Sample #1

8
2

Input Sample #2

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

Output Sample #2

15
0

Input Sample #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

Output Sample #3

30
27
48
30
48

Notes/Hints

Sample 1 Explanation

• In scheme 1, the bodyguard can earn $4 + 4 = 8$ Zimbabwean dollars by:
• Starting at position 2 at time 1.
• Protecting customer 1 from time 1 to 2, covering a distance of 1, earning $4 \times 1 = 4$ Zimbabwean dollars.
• Staying at position 1 from time 2 to 3.
• Protecting customer 2 from time 3 to 5, covering a distance of 2, earning $2 \times 2 = 4$ Zimbabwean dollars.
• In scheme 2, the bodyguard can earn $2$ Zimbabwean dollars by:
• Starting at position 3 at time 3.
• Moving from position 3 to 2 from time 3 to 4.
• Protecting customer 2 from time 4 to 5, covering a distance of 1, earning $2 \times 1 = 2$ Zimbabwean dollars.

Sample 2 Explanation

• In scheme 1, the bodyguard can earn $4 + 1 + 8 + 2 = 15$ Zimbabwean dollars by:
• Starting at position 2 at time 2.
• Moving from position 2 to 2.5 from time 2 to 2.5.
• Protecting customer 2 from time 2.5 to 3.5, covering a distance of 1, earning $4 \times 1 = 4$ Zimbabwean dollars.
• Protecting customer 1 from time 3.5 to 4, covering a distance of 0.5, earning $2 \times 0.5 = 1$ Zimbabwean dollars.
• Protecting customer 3 from time 4 to 6, covering a distance of 2, earning $4 \times 2 = 8$ Zimbabwean dollars.
• Protecting customer 1 from time 6 to 7, covering a distance of 1, earning $2 \times 1 = 2$ Zimbabwean dollars.
• In scheme 2, the bodyguard cannot earn any salary, resulting in $0$ Zimbabwean dollars.

Data Constraints

This problem is bundled test.

• 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): No additional constraints.

For $100\%$ of the data, $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$ is an even number, $1 \le P_j, X_j \le 10^9$.

见题面 Input 部分

见题面 Output 部分