**QUESTION**

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. \n\nAll 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).\n\nNow Sonam ask queries in which she gives rank of the student (x) and you have to tell marks obtained by that student.\n\nNote: rank1 is better than rank2 and rank2 is better than rank3 and so on and the first interval starts from 1.\n\n\nInput:\nThe first line of input contains an integer T, denoting the no of test cases. Then T test cases follow. Each test case contains two space separated values N and Q denoting the no of groups and no of queries asked respectively. \n\nThe next line contains N group of two integers separated by space which shows lowest marks in group i ie l(i) and highest marks in group i ie r(i) such that if i < j then r(i) < l(j). The next lines contain Q space separated integers x, denoting rank of student.\n\n\nOutput:\nFor each query output marks obtain by student whose rank is x(1<=x<=10^18).\n\n\nConstraints:\n1<=T<=50\n1<=N<=10^5\n1<=Q<=10^5\n1<= l(i) < r(i) <=10^18\n1<=x<=10^18\n\n

**ANSWER**

```
#include<iostream>
using namespace std;
int main()
{
int T;
cin>>T;
for(int i=0;i<T;++i)
{
int N,Q;
cin>>N>>Q;
long long l[100000],r[100000];
int j;
for(j=0;j<N;++j)
{
cin>>l[j]>>r[j];
}
for(int q=0;q<Q;++q)
{
long long x;
cin>>x;
// cout<<endl<<x<<endl;
long long count=0;
for(int p=0;p<N;++p)
{
// cout<<x<<":"<<count<<endl;
if(count+r[p]-l[p]+1<x)
{
count+=r[p]-l[p]+1;
if(count<x && p==N-1)
{
long long d=x-count;
if(p!=N-1)
cout<<r[p]+d<<" ";
else
cout<<r[p]+d;
}
}
else
{
long long d=x-count;
if(p!=N-1)
cout<<l[p]+d-1<<" ";
else
cout<<l[p]+d-1;
break;
}
}
}
cout<<endl;
}
return 0;
}
```