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$$
the sum for segment $$[1$$, $$2]$$ is $$3$$ and sum for segment $$[3$$, $$3]$$ is $$2$$. So the sum for first query $$[1$$, $$3]$$ is $$5$$.
sum for segment $$[1$$, $$2]$$ is given it is $$3$$.
sum for segment $$[1$$, $$2]$$ is unknown since $$a_1$$ can be any number from $$0$$ to $$3$$
