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 200\,000~
~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 5\,000~

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~.