You have an array of integers between and . Initially, you do not know exactly the value of any element of the array, but you know that the length of the array is . Also, you are given segments of the array , where is the left bound of the segment, is the right bound of the segment, is the sum of the segment. Then You are given queries . For every query, you need to print the sum of elements of the array on interval, if it is impossible to print .
Input
- First line will contain , number of testcases.
- In first line of testcase you are given , .
- In next lines of testcase you are given information about array , , .
- in next lines of testcase you are given queries in form , .
Output
-For each query, you need to print the answer in a single line.
Constraints
-
-
-
-
It is guaranteed that the sum of overall test cases does not exceed
It is guaranteed that the sum of overall test cases does not exceed
It is guaranteed that the sum of overall test cases does not exceed
the sum for segment , is and sum for segment , is . So the sum for first query , is .
sum for segment , is given it is .
sum for segment , is unknown since can be any number from to