//#ifndef LOCAL
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using indexed_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int int64_t
#define vi vector
#define ss second
#define ff first
#define TESTCASES
#define all(x) (x).begin(), (x).end()
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 LCA{
vector<vector<int>> up;
vector<int> dep,dist;
int n, logn;
//LCA (){}
LCA (int _n){
init(_n);
}
LCA (vector<vector<pair<int,int>>> &g){
build(g);
}
void init(int _n){
n = _n;
logn = 32 - __builtin_clz(n);
up.assign(n, vector<int> (logn, 0));
dep.assign(n, 0);
dist.assign(n, 0);
}
void dfs( vector<vector<pair<int,int>>> &g, int a, int par){
for(auto [u,w] : g[a]){
if(u == par) continue;
dep[u] = dep[a] + 1;
dist[u] = dist[a] + w;
up[u][0] = a;
for(int i = 1; i < logn; i ++){
up[u][i] = up[up[u][i - 1]][i - 1];
}
dfs(g, u, a);
}
}
void build(vector<vector<pair<int,int>>> &g){
init((int)(g.size()));
dfs(g, 0, 0);
}
int getkth(int a, int k){
for(int i = 0; i < logn; i ++){
if(k & (1 << i)) a = up[a][i];
}
return a;
}
int lca(int a, int b){
if(dep[a] < dep[b]) swap(a,b);
a = getkth(a, dep[a] - dep[b]);
if(a == b) return a;
for(int i = logn - 1; i >= 0; i --){
if(up[a][i] != up[b][i]){
a = up[a][i]; b = up[b][i];
}
}
return up[a][0];
}
int dis(int a, int b){
return dist[a] + dist[b] - 2 * dist[lca(a,b)];
}
};
const int logn = 30;
vi<vi<pair<int,int>>> g;
vi<vi<int>> up;
vi<int> dist,dis;
void dfs(int i, int par){
for(auto [x,val]:g[i]){
if(x==par)continue;
up[x][0]=i;
dist[x]=dist[i]+1;
for(int j=1; j<logn; j++){
up[x][j]=up[up[x][j-1]][j-1];
}
dfs(x,i);
dis[i]=dis[x]+val;
}
}
void solution(){
int n,q;
cin >> n >> q;
g.assign(n+1,{});
up.assign(n+1,vi<int>(30,0));
dist.assign(n+1,0);
dis.assign(n+1,0);
vi<pair<int,int>> pr,vec;
LCA lc(n);
for(int i=1; i<=n; i++){
int u,v;
cin >> u >> v;
vec.push_back({u,v});
}
map<int,vi<int>> mp;
multiset<int> mst;
for(int i=n-1; i>=0; i--){
if(mst.size()==0){
g[0].push_back({i+1,vec[i].ss});
g[i+1].push_back({0,vec[i].ss});
}
else {
auto lo=mst.upper_bound(vec[i].ff);
if(lo==mst.end()){
g[0].push_back({i+1,vec[i].ss});
g[i+1].push_back({0,vec[i].ss});
}
else {
int ind=mp[*lo].back();
g[ind].push_back({i+1,vec[i].ss});
g[i+1].push_back({ind,vec[i].ss});
}
}
mst.insert(vec[i].ff);
mp[vec[i].ff].push_back(i+1);
}
lc.build(g);
dfs(0,-1);
while(q--){
int node, val;
cin >> node >> val;
int l=0,r=dist[node];
int ans=node;
while(l<r){
int mid=(l+r+1)/2;
int p=node,x=mid;
for(int i=20; i>=0; i--){
if(x>=(1<<i)){
p=up[p][i];
x-=(1<<i);
}
}
if(lc.dis(node,p)<val)l=mid,ans=p;
else r=mid-1;
}
cout << ans << '\n';
}
}
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;
}
