#include<bits/stdc++.h> // #include<atcoder/modint> // #include<atcoder/convolution> #define pb push_back #define eb emplace_back #define mp make_pair #define F first #define S second #define rs resize #define ft front() #define bk back() #define int long long #define vi vector<int> #define vvi vector<vector<int>> #define pii pair<int, int> #define vpii vector<pair<int, int>> #define vc vector<char> #define vb vector<bool> #define mii map<int,int> #define f0r(i,n) for(int i=0;i<n;i++) #define FOR(i,k,n) for(int i=k;i<n;i++) #define r0f(i,n) for(int i = n-1; i >= 0; i--) #define R0F(i,k,n) for(int i = n-1; i >= k; i--) #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define SUM(v) (accumulate(all(v), 0LL)) #define in(a) int a; cin>>a #define in2(a,b) int a,b; cin>>a>>b #define in3(a,b,c) int a,b,c; cin>>a>>b>>c #define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d #define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];} #define out(a) cout<<a<<'\n' #define out2(a,b) cout<<a<<' '<<b<<'\n' #define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n' #define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n' #define pout(a) cout<<a.first<<' '<<a.second<<'\n' #define vout(v) for(auto u : v){cout<<u<<' ';} cout<<endl #define dout(a) cout<<a<<' '<<#a<<endl #define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<endl #define YN(x); if(x){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';} #define yn(x); if(x){cout<<"Yes"<<'\n';}else{cout<<"No"<<'\n';} #define p2(x) (1LL << (x)) #define pct(x) (__builtin_popcountll((x))) #define ist(x,y) (((x) >> (y)) & 1) template<class T, class U> bool ckmin(T& a, const U& b) { return (T)b < a ? a = (T)b, 1 : 0; } template<class T, class U> bool ckmax(T& a, const U& b) { return a < (T)b ? a = (T)b, 1 : 0; } const int leg = 1e9 + 7; const int mod = 998244353; using namespace std; // using namespace atcoder; // using mint = modint998244353; // using mint = modint1000000007; const int mxn = 1e5 + 5; // mint fact[mxn], inv[mxn]; // mint C(int n, int r){return fact[n] * inv[n-r] * inv[r];} // mint snb(int n, int r){return C(n + r, n);} const int B = 1000, lg = 18; struct item{ int x, y, t; }; struct query{int l, r, t;}; struct segtree{ vpii tree; int n; segtree(int x){ n=x; tree.rs(2*n+5); } void update(int k, int x){ k+=n; tree[k]=mp(x,k-n); for(k/=2;k>=1;k/=2)tree[k]=min(tree[k*2],tree[k*2+1]); } int quer(int l, int r){ pii ret = mp(4e18,0); l+=n;r+=n; while(l<=r){ if(l%2==1)ckmin(ret,tree[l++]); if(r%2==0)ckmin(ret,tree[r--]); l/=2;r/=2; } return ret.S; } }; bool operator <(const query &a, const query &b){return a.r<b.r;} signed main(){ ios::sync_with_stdio(false); cin.tie(NULL); //ifstream cin(".in"); //ofstream cout(".out"); // fact[0]=1;FOR(i,1,mxn)fact[i]=fact[i-1]*i;inv[mxn-1]=fact[mxn-1].inv();r0f(i,mxn-1)inv[i]=inv[i+1]*(i+1); in2(n,T); vpii w[n-1]; vector<item>g[n-1]; int ptr = 0; f0r(i,n-1){ in(m); f0r(j,m){in2(a,b); w[i].eb(a,b);} sort(rall(w[i])); vpii tmp; for(auto [a,b] : w[i]){ if(tmp.empty() || tmp.back().S > b)tmp.eb(a,b); } reverse(all(tmp)); for(auto [a,b] : tmp){g[i].pb({a,b,ptr}); ptr++;} } int s = ptr; vvi ts(n-1); vpii nxt(s*2, mp(-1,0)), prev(s*2, mp(-1,0)); f0r(i,n-1)for(auto [x,y,t] : g[i]){ nxt[t] = mp(t+s, y-x); prev[t+s] = mp(t, y-x); ts[i].pb(t); } in(q); vector<query>quers; f0r(i,q){in2(l,r);l--;r--; quers.pb({l,r,i});} vector<vector<query>>small(n); vector<query>big; for(auto [l,r,t] : quers){ if(r-l+1 <= B)small[l].pb({l,r,t}); else big.pb({l,r,t}); } // f0r(i,n-1){ // for(auto [x,y,z] : g[i])out3(x,y,z); cout<<'\n'; // } // dout(s); f0r(i,n-2){ int p1 = 0, p2 = 0; while(p1 < g[i].size()){ int j = g[i][p1].t; if(g[i][p1].y > g[i+1].back().x){nxt[j+s] = mp(g[i+1][0].t, g[i+1][0].x - g[i][p1].y + T);} else{ while(g[i+1][p2].x < g[i][p1].y)p2++; nxt[j+s] = mp(g[i+1][p2].t, g[i+1][p2].x - g[i][p1].y); } p1++; } p1 = g[i].size() - 1, p2 = g[i+1].size() - 1; while(p2 >= 0){ int j = g[i+1][p2].t; if(g[i+1][p2].x < g[i][0].y){prev[j] = mp(g[i].back().t + s, g[i+1][p2].x - g[i].back().y + T);} else{ while(g[i][p1].y > g[i+1][p2].x)p1--; prev[j] = mp(g[i][p1].t + s, g[i+1][p2].x - g[i][p1].y); } p2--; } } vector<vpii>R(s*2, vpii(lg)), L(s*2, vpii(lg)); f0r(i,s*2)R[i][0]=nxt[i], L[i][0]=prev[i]; FOR(j,1,lg)f0r(i,s*2){ if(R[i][j-1].F==-1)R[i][j]=mp(-1,0); else if(R[R[i][j-1].F][j-1].F == -1)R[i][j]=mp(-1,0); else R[i][j]=mp(R[R[i][j-1].F][j-1].F, R[i][j-1].S + R[R[i][j-1].F][j-1].S); if(L[i][j-1].F==-1)L[i][j]=mp(-1,0); else if(L[L[i][j-1].F][j-1].F == -1)L[i][j]=mp(-1,0); else L[i][j]=mp(L[L[i][j-1].F][j-1].F, L[i][j-1].S + L[L[i][j-1].F][j-1].S); } // f0r(i,10)cout<<nxt[i].F<<' '; cout<<'\n'; vi ans(q); f0r(i,n){ if(small[i].empty())continue; sort(all(small[i])); vi ptr, dist; for(auto u : ts[i])ptr.pb(u), dist.pb(0); int jm = (small[i][0].r - small[i][0].l)*2-1; f0r(k,jm){f0r(j,ptr.size())dist[j]+=nxt[ptr[j]].S, ptr[j] = nxt[ptr[j]].F;} // vout(dist); ans[small[i][0].t] = *min_element(all(dist)); int pv = ans[small[i][0].t]; FOR(j,1,small[i].size()){ f0r(k,(small[i][j].r - small[i][j-1].r) * 2){ f0r(z,ptr.size())dist[z]+=nxt[ptr[z]].S, ptr[z]=nxt[ptr[z]].F; } if(small[i][j].r==small[i][j-1].r)ans[small[i][j].t]=pv; else ans[small[i][j].t]=*min_element(all(dist)), pv=ans[small[i][j].t]; //vout(dist); } } segtree S = segtree(n-1); f0r(i,n-1)S.update(i,g[i].size()); for(auto [l,r,t] : big){ int d = S.quer(l,r-1); int lef = (d-l)*2; vi ptr, dist; for(auto u : ts[d])ptr.pb(u), dist.pb(0); f0r(j, lg)if(ist(lef,j)){ f0r(i,ptr.size())dist[i]+=L[ptr[i]][j].S, ptr[i]=L[ptr[i]][j].F; } //vout(dist); vi p2, d2; for(auto u : ts[d])p2.pb(u), d2.pb(0); int rig = (r-d)*2-1; f0r(j, lg)if(ist(rig, j)){ f0r(i,ptr.size())d2[i]+=R[p2[i]][j].S, p2[i]=R[p2[i]][j].F; } f0r(i,ptr.size())d2[i]+=dist[i]; ans[t] = *min_element(all(d2)); } f0r(i,q)cout<<ans[i]<<'\n'; }