Tzovex is currently taking a course in real analysis. Unfortunately for him and his class, they are having trouble following the lectures and are now struggling with a particular homework assignment that is due in $D+1$ days. The homework assignment consists of $M$ questions, the $i$th of which has a value of $v_i$. Including himself, Tzovex's class consists of $N$ students, the $j$th of which having solved the first $a_j$ problems while being unable to solve the rest. However, the professor is willing to help out students in extra classes, each of which is dedicated to a single problem. In particular, help will be available for the $i$th problem between $l_i$ and $r_i$ (inclusive) days from today. The $j$th student only has time for one extra class, and he can only attend it if it happens in exactly $d_j$ days. The professor also has a unique way of grading assignments. Rather than giving the students marks, he instead gives them penalties. Going from the first to the last problem, the $k$th problem that a student did not solve will earn them $k$ times the value of the problem in penalties. Assuming that no student will solve any extra problems on their own, determine the minimum possible penalty that each of the $N$ students can achieve.

Input Specification

The first line contains three space-separated integers, $N$, $M$, and $D$.
$M$ lines follow, the $i$th of which contains three space separated integers, $v_i$, $l_i$, and $r_i$.
$N$ more lines follow, the $j$th of which contains two space separated integers, $a_j$ and $d_j$.

Output Specification

Output $N$ lines, the $j$th of which containing a single integer, the minimum possible penalty that the $j$th student can achieve.

Constraints

In all subtasks,
$1\le N,M,D\le 200000$
$1\le v_i\le {10}^6$
$0\le a_j\le M$
$1\le d_j,l_i,r_i\le D$
$l_i\le r_i$

Subtask 1 [5%]

$1\le N,M,D\le 300$

Subtask 2 [10%]

$1\le N,M,D\le 5000$

Subtask 3 [35%]

$l_i=1$ and $r_i=D$

Subtask 4 [50%]

No additional constraints.

Sample Input

5 4 5
5 3 5
2 1 3
3 2 4
7 4 5
0 4
1 3
2 5
3 2
4 1

Sample Output

18
16
3
7
0

Explanation for Sample Output

The optimal move for student $1$ is to attend the lecture for problem $4$ resulting in a penalty of $1(5)+2(2)+3(3)=18$.
The optimal move for student $2$ is to attend the lecture for problem $3$ resulting in a penalty of $1(2)+2(7)=16$.
The optimal move for student $3$ is to attend the lecture for problem $4$ resulting in a penalty of $1(3)=3$.
Student $4$ can't attend any useful lectures and so has a penalty of $1(7)=7$.
Student $5$ doesn't need any lectures and has a penalty of $0$.