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.
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 ~N~ lines, the ~j~th of which containing a single integer, the minimum possible penalty that the ~j~th student can achieve.
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.
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
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~.