Task Query on Supercomputer

In the management system of a supercomputer, each task is described by a triple \( (s_i, e_i, p_i) \), where \( s_i \) represents the start time and \( e_i \) represents the end time (both endpoints inclusive) of the task, and \( p_i \) is its priority. Note that multiple tasks may run concurrently at the same time.

The query system receives queries that ask: At a given second \( x_i \), among all the tasks running at that time, what is the sum of the priorities of the smallest \( k_i \) tasks (when sorted in increasing order of priority)? If \( k_i \) is greater than the total number of running tasks, then the answer is simply the sum of the priorities of all the running tasks.

All parameters are integers, and the time values lie in the range \( [1, n] \).

inputFormat

The first line contains three integers \( n \), \( m \), and \( q \), representing the maximum time, the number of tasks, and the number of queries, respectively.

The next \( m \) lines each contain three integers \( s_i \), \( e_i \), and \( p_i \), describing a task that starts at time \( s_i \), ends at time \( e_i \) (inclusive), and has priority \( p_i \).

The following \( q \) lines each contain two integers \( x_i \) and \( k_i \), representing a query at time \( x_i \) asking for the sum of the smallest \( k_i \) priorities among the tasks running at that moment.

outputFormat

For each query, output a single line containing the sum of the priorities according to the query specification.

sample

10 3 2
1 5 10
3 10 5
2 7 6
3 2
6 3

11
11