ma5termind-and-friends

Ma5termind has decided to give integer ratings ( either positive or negative )  to his friends. He has N friends which are numbered from 1 to N. But he is confused about how to distribute rating among his friends.
He formed M functions where i^th function consists of 3 integers L R and C. The i^th function denotes that he will give C rating to all his friends numbered from L to R.
We all know about ma5termind's love for queries. So, he decided to make Q queries where i^th query contains two integeres X and Y which denotes that he will implement all the functions numbered from X to Y (both inclusive).
Now ma5termind is curious about how much rating he has given to each of his friends in total. It should be noted that the final rating of any of his friend can be negative or positive.
Help ma5termind figure out this task.
Input:
Each input file will contain a T test case.
First line will contain two integres N and M denoting the number of friends and number of functions.
Next M lines contains three integers L R and C.
Next line will contain a integer Q.
Next Q lines will contain two integer X and Y each. 

Ouput:
Each test case will contain N space seperated integers.
Constraints:

1 ≤ T ≤ 5 
1 ≤ N and M ≤ 100000
1 ≤ L ≤ R ≤ N
-100000000 ≤ C ≤ 100000000
1 ≤ Q ≤ 100000
1 ≤ X ≤ Y ≤ M 

See sample I/O for more clarification.

Scoring:

subtask 1: 1 ≤ N, M, Q ≤ 1000 ( 28 pts )
subtask 2: 1 ≤ N, M, Q ≤ 10^5 ( 72 pts )

SAMPLE INPUT
1
5 4
1 2 3
1 3 2
2 4 1
1 4 4
3
1 2
2 3
2 4

SAMPLE OUTPUT
13 15 12 6 0

Source: hackerearth | Difficulty: EASY


Solutions: