#include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #include <bits/stdc++.h> using namespace std; #define int long long #define pll pair<long long, long long> #define mp make_pair #define pb push_back #define f first #define s second #define endl '\n' #define ld long double #define sz(x) static_cast<int>((x).size()) #define i5 tuple<int,int,int,int,int> #define all(x) x.begin(), x.end() #define iiii tuple<int, int,int,int> #define ld long double #define lol pair<pll,pll> #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> struct node { int s, e, m; lol v; node *l, *r; lol combine(lol a, lol b){ return mp(min(a.f, b.f), max(a.s, b.s)); } node (int S, int E, vector<pll> & V){ s=S, e=E, m=(s+e)/2; if(s!=e){ l=new node(s, m, V); r=new node(m+1, e, V); v=combine(l->v, r->v); } else { v.f.f=V[s].f; v.f.s=s; v.s.f=V[s].s; v.s.s=s; } //printf("segment %lld to %lld, {%lld %lld} {%lld %lld}\n", s,e,v.f.f,v.f.s,v.s.f,v.s.s); } lol qry(int S,int E){ if((S==s and E==e) or s==e){ return v; } if(E<=m)return l->qry(S,E); if(S>m)return r->qry(S,E); return combine(l->qry(S,m),r->qry(m+1,E)); } } *root; signed main(){ int n,k,m;cin>>n>>k>>m; vector<pll> v(n+1); for(int i=0;i<=n;i++)v[i]=make_pair(i,i); vector<tuple<int,int,int,int>> ed; vector<vector<pll>> st(n+1), en(n+1); for(int i=0;i<m;i++){ int a, b;cin>>a>>b; int l=min(a, b), r=max(a, b), ul, ur; if(a < b) ul=a, ur=min(r, a+k-1); else ul=max(l, a-k+1), ur=a; ed.pb(make_tuple(ul, ur, l, r)); //printf("ul %lld ur %lld, l %lld r %lld\n", ul, ur, l, r); st[ul].pb(mp(i, (a<b))); en[ur].pb(mp(i, (a<b))); } // sweep to calculate the extent of reach of each index. array<multiset<int>, 2> ms; for(int i=1;i<=n;i++){ for(auto [ind, t] : st[i]){ int l=(t==0 ? get<2>(ed[ind]): get<3>(ed[ind])); ms[t].insert(l); } v[i].f = min(i, (ms[0].empty() ? n : *ms[0].begin())); v[i].s = max(i, (ms[1].empty() ? 0 : *prev(ms[1].end()))); for(auto [ind,t] : en[i]){ int l=(t==0 ? get<2>(ed[ind]): get<3>(ed[ind])); ms[t].erase(ms[t].find(l)); } } //for(int i=1;i<=n;i++){printf("i %lld, l %lld, r %lld\n", i, v[i].f, v[i].s); } root=new node(1, n, v); // calculate the mn, mnindex, mx mxindex of each guy by segment tree vector<pair<int,int>> to(n+1, {0,0}); vector<vector<pll>> up(n+1, vector<pll>(20)); for (int i=1;i<=n;i++){ auto [mn, mx]=root->qry(v[i].f, v[i].s); up[i][0].f=mn.s, up[i][0].s=mx.s; //printf("up[%lld][0].f is %lld and [1].s is %lld\n", i, up[i][0].f, up[i][0].s); } // do twok decomp on each guy auto merge=[&](int a, int b, int p)->pll{ pll ret={-1, -1}; if(v[up[a][p].f].f <= v[up[b][p].f].f){ ret.f=up[a][p].f; } else { ret.f=up[b][p].f; } if(v[up[a][p].s].s >= v[up[b][p].s].s){ ret.s=up[a][p].s; } else { ret.s=up[b][p].s ; } return ret; }; for (int j=1;j<20;j++){ for(int i=1;i<=n;i++){ // two guys are up[i][j-1].f up[i][j-1].s up[i][j]=merge(up[i][j-1].f, up[i][j-1].s, j-1); } } // binary lift to find cost for each query. int q;cin>>q; while(q--){ int s, t, cost=1;cin>>s>>t; if(v[s].f <= t and t <= v[s].s){ cout<<cost<<'\n'; continue; } pll cur={s, s}; for(int j=19;j>=0;j--){ pll temp=merge(cur.f, cur.s, j); //printf("cur %lld %lld j is %lld, temp is %lld %lld\n", cur.f, cur.s, j, temp.f, temp.s); if(v[temp.f].f <= t and v[temp.s].s >= t) continue; cur=temp; cost += (1<<j); //printf("cur %lld %lld j is %lld, temp is %lld %lld\n", cur.f, cur.s, j, temp.f, temp.s); } if(cost < n) cout<<cost+1<<'\n'; else cout<<-1<<'\n'; } }