Background

Announcement: Note that cases with $l_i > r_i$ may occur; in such cases, the operation is invalid.

Xiao L is keen on walking.

Problem Description

Xiao L arrives at a tourist attraction and wants to walk along the main road there.

There are several key points on the main road. He can model them as a sequence $a$ of length $n$. Each $a_i$ is a triple $(l_i, r_i, v_i)$, meaning:

• If $r_i = -1$, it represents a scenic spot that requires buying a ticket to enter. The ticket costs $l_i$ coins, and after the visit he will gain $v_i$ happiness.
• If $r_i \neq -1$, it represents a gift distribution point. If the total face value of the coins he holds is $x$ and satisfies $l_i \leq x \leq r_i$, he can claim one gift and will gain $v_i$ happiness.

He plans to walk along this main road $m$ times. Each time, he is given the starting point $l$ and the ending point $r$. At the beginning, the total face value of the coins he holds is $x$, and his initial happiness is $0$.

He will start from $l$ and pass through $i \in [l, r]$ from left to right. He will do the following:

• If $r_i = -1$, if he still has coins left after paying the current ticket fee, he will visit this scenic spot.
• If $r_i \neq -1$, if possible, he will claim one gift.

Please help him quickly compute his happiness after each walk ends.

Input Format

The first line contains two integers $n, m$.

The next $n$ lines: the $i$-th line contains three integers $l_i, r_i, v_i$.

The next $m$ lines: each line contains three integers $l, r, x$, describing one query.

Output Format

Output $m$ lines, each containing one integer, representing the happiness after the walk ends.

4 10
1 1 4
5 -1 4
1 9 19
8 -1 10
1 1 11
2 2 4
3 3 5
4 4 14
1 2 1
2 3 9
3 4 1
1 3 9
2 4 8
1 4 10

0
0
19
10
4
23
19
23
23
23

Hint

This problem uses bundled testdata.

• Subtask 1 (10 pts): $1 \leq n, m \leq 5 \times 10^3$.
• Subtask 2 (10 pts): $r_i \neq -1$.
• Subtask 3 (20 pts): $r_i = -1$.
• Subtask 4 (10 pts): $1 \leq n, m \leq 7.5 \times 10^4$, Property A.
• Subtask 5 (20 pts): $1 \leq n, m \leq 7.5 \times 10^4$.
• Subtask 6 (10 pts): The testdata is generated randomly within the constraints, Property B.
• Subtask 7 (20 pts): No special restrictions.

Property A: $1 \leq l_i \leq 7.5 \times 10^4$, $r_i = -1$ or $1 \leq r_i \leq 7.5 \times 10^4$, $1 \leq x \leq 7.5 \times 10^4$.

Property B: When $r_i = -1$, $1 \leq l_i \leq 2 \times 10^5$.

For $100\%$ of the testdata:

• $1 \leq n, m \leq 2 \times 10^5$.
• $1 \leq l_i \leq 10^9$, $r_i = -1$ or $1 \leq r_i \leq 10^9$.
• $1 \leq v_i \leq 10^9$.
• $1 \leq l \leq r \leq n$, $1 \leq x \leq 10^9$.

Translated by ChatGPT 5