They declared Sonam as bewafa. Although she is not, believe me! She asked a number of queries to people regrading their position in a test. Now its your duty to remove her bewafa tag by answering simple queries. All the students who give test can score from 1 to 10^18. Lower the marks, better the rank. Now instead of directly telling the marks of student they have been assigned groups where marks are distributed in continuous intervals, you have been given l(i) lowest mark of interval i and r(i) highest marks in interval i. So marks distribution in that interval is given as l(i), l(i)+1, l(i)+2 . . . r(i).
Now Sonam ask queries in which she gives rank of the student (rank_{i}) and you have to tell marks obtained by that student. Simply, for each query output marks obtain by student whose rank is rank_{i}(1<=rank_{i}<=10^{18}).
Note: rank1 is better than rank2 and rank2 is better than rank3 and so on and the first interval starts from 1.
Example 1:
Input:
n=3, q=3
l[] = {1, 12, 22}
r[] = {10, 20, 30}
rank[] = {5, 15, 25}
Output:
5 16 27
Intervals are from 1 to 10, second
interval from 12 to 20 and third 22 to 30.
In this test case, from 1 to 10 , they
are given the ranks from 1 to 10 but
in the second interval, it is starting
from 12 , so we will have to give its rank
11 and so on like this.
Rank: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15......
Marks: 1 2 3 4 5 6 7 8 9 10 12 13 14 15 16.....
So 5th rank will score 5 marks,15th rank will
score 16 marks and 25th rank will score 27 marks.

Your Task:
You don't need to read input or print anything. Your task is to complete the function getTestMarks() which takes the array l[], r[], its size n and array rank[], StoreAnswer[], its size q as inputs and fill the StoreAnswer[] array. This array stores the answer of every query.
Expected Time Complexity: O(n. log(n))
Expected Auxiliary Space: O(n.q)
Constraints:
1<=n<=10^{5}
1<=q<=10^{5}
1<= l(i) < r(i) <=10^{18}
1<=rank_{i}<=10^{18}

见题面

见题面