P9494 “SFCOI-3” Take a Walk

**Announcement: Note that cases with $l_i > r_i$ may occur; in such cases, the operation is invalid.** ------------ Xiao L is keen on walking.

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.

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 $m$ lines, each containing one integer, representing the happiness after the walk ends.

**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