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$