//#ifndef LOCAL
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#endif
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define pb push_back
#define vi vector
#define vii vector<pair<int,int>>
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define ss second
#define ff first
#define TESTCASES
#define sz(x) int(x.size())
#define all(x) (x).begin(), (x).end()
#define seea(a,n) for(int i=0;i<n;i++){cin>>a[i];}
const int mod = 1E9+7;
const int MAXN=200000;
const int inf=1e18;
#ifndef khos
#define debug(...) 42
#endif
#define debug(args...) \
{ \
cout << "[" << #args << "]: "; \
my::debug::debug_out(args); \
cout << endl; \
}
namespace my::debug {
using std::cout;
template <typename T, typename = void>
struct is_container : std::false_type {};
template <typename T>
struct is_container<T, std::void_t<decltype(std::begin(std::declval<T>()))>>
: std::true_type {};
template <typename T>
constexpr bool is_container_v = is_container<T>::value;
template <typename Test, template <typename...> class Ref>
struct is_specialization : std::false_type {};
template <template <typename...> class Ref, typename... Args>
struct is_specialization<Ref<Args...>, Ref> : std::true_type {};
template <typename Test, template <typename...> class Ref>
constexpr bool is_specialization_v = is_specialization<Test, Ref>::value;
// https://stackoverflow.com/a/47563100
template <std::size_t N>
struct num {
static const constexpr auto value = N;
};
template <class F, std::size_t... Is>
void for_(F func, std::index_sequence<Is...>) {
(func(num<Is>{}), ...);
}
template <std::size_t N, typename F>
void for_(F func) {
for_(func, std::make_index_sequence<N>());
}
template <typename T>
constexpr auto is_coutable(int)
-> decltype(std::cout << std::declval<T>(), std::true_type{}) {
return std::true_type{};
}
template <typename T>
constexpr std::false_type is_coutable(...) {
return std::false_type{};
}
template <typename T>
constexpr bool is_coutable_v = decltype(is_coutable<T>(0))::value;
template <typename T>
void single_out(T x) {
if constexpr (std::is_same_v<T, std::string> | std::is_same_v<T, char*> ||
std::is_same_v<T, const char*>) {
cout << '"' << x << '"';
} else if constexpr (std::is_same_v<T, char>) {
cout << x;
} else if constexpr (std::is_integral_v<T> || std::is_floating_point_v<T> ||
std::is_enum_v<T> || std::is_pointer_v<T>) {
cout << x;
} else if constexpr (is_specialization_v<T, std::pair>) {
cout << "(";
single_out(x.first);
cout << ", ";
single_out(x.second);
cout << ")";
} else if constexpr (is_specialization_v<T, std::tuple>) {
cout << "(";
std::string sep = "";
for_<std::tuple_size_v<T>>([&](auto i) {
cout << exchange(sep, ", ");
single_out(std::get<i.value>(x));
});
cout << ")";
} else if constexpr (is_specialization_v<T, std::map> ||
is_specialization_v<T, std::unordered_map>) {
cout << "{";
std::string sep = "";
for (auto [k, v] : x) {
cout << exchange(sep, ", ");
single_out(k);
cout << ": ";
single_out(v);
}
cout << "}";
} else if constexpr (is_container_v<T>) {
if constexpr (is_specialization_v<T, std::vector>) {
cout << "[";
} else cout << "{";
std::string sep = "";
for (auto i : x) {
cout << exchange(sep, ", ");
single_out(i);
}
if constexpr (is_specialization_v<T, std::vector>) {
cout << "]";
} else cout << "}";
}
// types without iterator, f*** you, c++ comittee
else if constexpr (is_specialization_v<T, std::queue>) {
cout << "{";
std::string sep = "";
while (x.size()) {
cout << exchange(sep, ", ");
single_out(x.front());
x.pop();
}
cout << "}";
} else if constexpr (is_specialization_v<T, std::stack> ||
is_specialization_v<T, std::priority_queue>) {
std::vector<
std::remove_cv_t<std::remove_reference_t<decltype(x.top())>>>
v;
while (x.size()) {
v.push_back(x.top());
x.pop();
}
if constexpr (is_specialization_v<T, std::stack>)
std::reverse(v.begin(), v.end());
cout << "{";
std::string sep = "";
for (auto i : v) {
cout << exchange(sep, ", ");
single_out(i);
}
cout << "}";
}
// lastly, if the expression (cout << x) compiles, use it
else {
static_assert(is_coutable_v<T>, "The type given to debug() is not supported.");
cout << x;
}
}
template <typename T, typename... Rest>
void debug_out(T, Rest...);
void debug_out();
template <typename T, typename... Rest>
void debug_out(T x, Rest... rest) {
// single_out<std::remove_cv_t<std::decay_t<T>>>(x);
single_out<std::remove_cv_t<T>>(x);
if (sizeof...(rest) > 0) cout << ", ";
debug_out(rest...);
}
void debug_out() {
}
}; // namespace my::debug
struct segtree{
vi<int> tree;
int sz;
void init(int n){
sz=1;
while(sz<n)sz*=2;
tree.assign(2*sz-1,inf);
}
void update(int i,int v,int x,int lx,int rx){
if(rx-lx==1){
tree[x]=v;
return;
}
int m=(lx+rx)/2;
if(i<m)update(i,v,2*x+1,lx,m);
else update(i,v,2*x+2,m,rx);
tree[x]=min(tree[2*x+1],tree[2*x+2]);
}
void update(int i,int v){
return update(i,v,0,0,sz);
}
int sum(int l,int r,int x,int lx,int rx){
if(l>=rx || r<=lx)return inf;
if(l<=lx && rx<=r){
return tree[x];
}
int m=(lx+rx)/2;
int s1=sum(l,r,2*x+1,lx,m);
int s2=sum(l,r,2*x+2,m,rx);
return min(s1,s2);
}
int sum(int l,int r){
return sum(l,r,0,0,sz);
}
int find(int v, int r, int x, int lx, int rx){
if(lx>=r)return -1;
if(tree[x]>=v)return -1;
if(rx-lx==1)return lx;
int m=(lx+rx)/2;
int left=find(v,r,2*x+1,lx,m);
if(left!=-1)return left;
else return find(v,r,2*x+2,m,rx);
}
int find(int r, int v){
return find(v,r,0,0,sz);
}
};
void solution(){
int n,q;
cin >> n >> q;
segtree sgt;
sgt.init(n);
vi<pair<int,int>> vec(n);
for(int i=0; i<n; i++){
cin >> vec[i].ff >> vec[i].ss;
}
int cnt=0;
vi<vi<int>> g(n);
map<int,pair<int,int>> mp;
map<pair<int,int>,int> need;
for(int i=0; i<n; i++){
if(i==0){
mp[i]={cnt,0LL};
need[{cnt,0LL}]=i;
g[cnt].push_back(vec[i].ss);
sgt.update(cnt,vec[i].ff);
cnt++;
continue;
// st.insert({vec[i].ff,cnt++});
}
int p=sgt.find(cnt,vec[i].ff);
// debug(i,p);
// debug(sgt.sum(0,cnt));
if(p==-1){
// if(i==2)cout << vec[i].ff << endl;
mp[i]={cnt,0LL};
need[{cnt,0LL}]=i;
g[cnt].push_back(vec[i].ss);
sgt.update(cnt,vec[i].ff);
cnt++;
// st.insert({vec[i].ff,cnt++});
}
else {
int pp=p;
// if(i==1)cout << mp[p].ff << ' ' << g[pp].size() << endl;
mp[i]={p,g[p].size()};
need[{p,g[p].size()}]=i;
g[p].push_back(vec[i].ss);
// st.erase(st.begin());
// if(i==5)cout << sgt.sum(pp,pp+1) << ' ' << p << ' ' << pp << endl;
sgt.update(p,vec[i].ff);
// if(i==3)cout << sgt.sum(pp,pp+1) << ' ' << cnt << endl;
// st.insert({vec[i].ff,p.ss});
}
}
for(int i=0; i<n; i++){
for(int j=1; j<g[i].size(); j++){
g[i][j]+=g[i][j-1];
}
}
while(q--){
int ind,val;
cin >> ind >> val;
ind-=1;
int c=mp[ind].ff;
int cc=mp[ind].ss;
int var=(cc==0?0:g[c][cc-1]);
int lo=lower_bound(all(g[c]),var+val)-g[c].begin();
if(lo>=g[c].size())cout << 0 << '\n';
else {
cout << need[{c,lo}]+1 << '\n';
}
}
// debug(g[0]);
}
int32_t main(){
clock_t tStart = clock();
#ifdef khos
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int q = 1;
#ifdef TESTCASES
// cin >> q;
#endif
while(q--) {
solution();
cout << '\n';
}
cerr<<fixed<<setprecision(3)<<"\nTime Taken: "<<(double)(clock()- tStart)/CLOCKS_PER_SEC<<endl;
}
