Walking Through Attractions

Little L visits a tourist spot along a main road. The main road is abstracted as a sequence \(a\) of length \(n\) and each element \(a_i\) is a triple \((l_i, r_i, v_i)\). There are two types of points:

• If \(r_i = -1\), it represents an attraction requiring ticket purchase. The ticket costs \(l_i\) tokens. If after paying for the ticket, his remaining tokens are positive (i.e. \(x - l_i > 0\)), then he can visit the attraction and gain \(v_i\) units of pleasure. Note that in this case, his tokens are reduced by \(l_i\).
• If \(r_i \neq -1\), it represents a gift distribution point. If his current tokens \(x\) satisfy \(l_i \le x \le r_i\), he can receive a gift and gain \(v_i\) units of pleasure. His tokens remain unchanged in this case.

Little L will walk along the road for \(m\) trips. For each trip, he is given a starting index \(L\) and an ending index \(R\) (1-indexed) as well as an initial token sum \(x\) (and his initial pleasure is 0). During a trip, he visits the points in order from \(L\) to \(R\), performing the following at each point \(i\):

• If \(a_i = (l_i, -1, v_i)\): If \(x - l_i > 0\), he pays \(l_i\) tokens (i.e. \(x = x - l_i\)) and his pleasure increases by \(v_i\).
• If \(a_i = (l_i, r_i, v_i)\) with \(r_i \neq -1\): If \(l_i \le x \le r_i\), he gains \(v_i\) units of pleasure.

Your task is to quickly compute the final pleasure value after each trip.

Note: The indices are 1-indexed.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of attractions and the number of trips, respectively.

The next \(n\) lines each contain three integers \(l_i\), \(r_i\) and \(v_i\), describing an attraction. If \(r_i = -1\), the attraction is a ticket-required point; otherwise it is a gift distribution point.

The next \(m\) lines each contain three integers \(L\), \(R\) and \(x\), representing a trip where Little L starts at index \(L\) and ends at index \(R\) with an initial token sum \(x\).

outputFormat

For each trip, output a single line with the final pleasure value accumulated after processing the attractions in order.

sample

2 1
3 -1 10
5 7 5
1 2 10

15