You have an array $$a$$ of integers between $$0$$ and $$10^6$$. Initially, you do not know exactly the value of any element of the array, but you know that the length of the array is $$n$$. Also, you are given $$m$$ segments of the array $$l$$ $$r$$ $$x$$, where $$l$$ is the left bound of the segment, $$r$$ is the right bound of the segment, $$x$$ is the sum of the segment. Then You are given $$q$$ queries $$ql$$ $$qr$$. For every query, you need to print the sum of elements of the array $$a$$ on $$[ql, qr]$$ interval, if it is impossible to print $$-1$$.

 

Input

 

- First line will contain $$T$$, number of testcases. 

- In first line of testcase you are given $$n$$, $$m$$ $$q$$.

- In next $$m$$ lines of testcase you are given information about array $$l$$, $$r$$, $$x$$.

- in next $$q$$ lines of testcase you are given queries in form $$ql$$, $$qr$$.

 

Output

 

-For each query, you need to print the answer in a single line.

 

Constraints

- $$1 \leq T \leq 200$$

- $$2 \leq n, m, q \leq 2*10^5$$

- $$1 \leq l, r, ql, qr \leq n$$

- $$0 \leq x \leq 10^6$$

It is guaranteed that the sum of $$n$$ overall test cases does not exceed $$2*10^5$$

It is guaranteed that the sum of $$m$$ overall test cases does not exceed $$2*10^5$$

It is guaranteed that the sum of $$q$$ overall test cases does not exceed $$2*10^5$$