#include <iostream> #include <bits/stdc++.h> #define ll long long using namespace std; const ll maxn = 2*1e5+5, INF = 4e18+9; struct normalize{ vector<ll> poi, pot; void add(ll x){ poi.push_back(x); } void start(){ sort(poi.begin(), poi.end()); if(poi.size() > 0) pot.push_back(poi[0]); for(int i = 1; i < (int)poi.size(); i++){ if(poi[i] != poi[i-1]){ pot.push_back(poi[i]); } } } int encode(ll x){ return lower_bound(pot.begin(), pot.end(), x) - pot.begin()+1; } }; // supports: point modify, range apply, range query, walk to find first/last with some precedent // you are to implement the 2 structs Tag and Info // for the walks, pass a lambda that takes in Info and return true iff the node with that Info will contain the desired element template<class Info, class Tag> struct LazySegmentTree { int n; vector<Info> info; vector<Tag> tag; LazySegmentTree() : n(0) {} LazySegmentTree(int n_, Info v_ = Info()) { init(n_, v_); } template<class T> LazySegmentTree(vector<T> init_) { init(init_); } void init(int n_, Info v_ = Info()) { init(vector<Info>(n_, v_)); } template<class T> void init(vector<T> init_) { n = init_.size(); info.assign(4 << __lg(n), Info()); tag.assign(4 << __lg(n), Tag()); function<void(int, int, int)> build = [&](int p, int l, int r) { if (r - l == 1) { info[p] = init_[l]; return; } int m = (l + r) / 2; build(2 * p, l, m); build(2 * p + 1, m, r); pull(p); }; build(1, 0, n); } void pull(int p) { info[p] = info[2 * p] + info[2 * p + 1]; } void apply(int p, const Tag &v) { info[p].apply(v); tag[p].apply(v); } void push(int p) { apply(2 * p, tag[p]); apply(2 * p + 1, tag[p]); tag[p] = Tag(); } void modify(int p, int l, int r, int x, const Info &v) { if (r - l == 1) { info[p] = v; return; } int m = (l + r) / 2; push(p); if (x < m) { modify(2 * p, l, m, x, v); } else { modify(2 * p + 1, m, r, x, v); } pull(p); } void modify(int p, const Info &v) { modify(1, 0, n, p, v); } Info rangeQuery(int p, int l, int r, int x, int y) { if (l >= y || r <= x) { return Info(); } if (l >= x && r <= y) { return info[p]; } int m = (l + r) / 2; push(p); return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y); } Info rangeQuery(int l, int r) { return rangeQuery(1, 0, n, l, r); } void rangeApply(int p, int l, int r, int x, int y, const Tag &v) { if (l >= y || r <= x) { return; } if (l >= x && r <= y) { apply(p, v); return; } int m = (l + r) / 2; push(p); rangeApply(2 * p, l, m, x, y, v); rangeApply(2 * p + 1, m, r, x, y, v); pull(p); } void rangeApply(int l, int r, const Tag &v) { return rangeApply(1, 0, n, l, r, v); } template<class F> int findFirst(int p, int l, int r, int x, int y, F &&pred) { if (l >= y || r <= x) { return -1; } if (l >= x && r <= y && !pred(info[p])) { return -1; } if (r - l == 1) { return l; } int m = (l + r) / 2; push(p); int res = findFirst(2 * p, l, m, x, y, pred); if (res == -1) { res = findFirst(2 * p + 1, m, r, x, y, pred); } return res; } template<class F> int findFirst(int l, int r, F &&pred) { return findFirst(1, 0, n, l, r, pred); } template<class F> int findLast(int p, int l, int r, int x, int y, F &&pred) { if (l >= y || r <= x) { return -1; } if (l >= x && r <= y && !pred(info[p])) { return -1; } if (r - l == 1) { return l; } int m = (l + r) / 2; push(p); int res = findLast(2 * p + 1, m, r, x, y, pred); if (res == -1) { res = findLast(2 * p, l, m, x, y, pred); } return res; } template<class F> int findLast(int l, int r, F &&pred) { return findLast(1, 0, n, l, r, pred); } }; struct Tag { void apply(const Tag &t) & { } }; struct Info { int mn = 1e9, id = -1; void apply(const Tag &t) & { } Info operator+(const Info &b) { Info a = *this; if(a.mn < b.mn) return a; return b; } }; void solve(){ int n, L; cin >> n >> L; vector<int> M(n+1); vector<vector<int>> a(n+1), b(n+1); for(int i = 1; i < n; i++){ cin >> M[i]; a[i].resize(M[i]+1); b[i].resize(M[i]+1); for(int j = 1; j <= M[i]; j++){ cin >> a[i][j] >> b[i][j]; } } M[n] = 1; //build the goddamn tree int N = 0; vector<vector<int>> tn(n+1); for(int i = 1; i <= n; i++){ if(i == 1){ tn[i].resize(M[i]+1); for(int j = 1; j <= M[i]; j++){ N++; tn[i][j] = N; } }else if(i < n){ tn[i].resize(M[i-1]+M[i]+1); for(int j = 1; j <= M[i-1]; j++){ N++; tn[i][j] = N; } for(int j = 1; j <= M[i]; j++){ N++; tn[i][j+M[i-1]] = N; } }else{ tn[i].resize(M[i-1]+1); for(int j = 1; j <= M[i-1]; j++){ N++; tn[i][j] = N; } } } vector<vector<pair<ll, ll>>> adj(N+1); vector<pair<ll, ll>> pa(N+1); auto add_edge = [&](int u, int v, int w) -> void{ adj[u].push_back({v, w}); pa[v] = {u, w}; //cout << u << " " << v << " " << w << "\n"; }; LazySegmentTree<Info, Tag> T(N+1); vector<int> sz(n+1); for(int i = 1; i <= n; i++){ if(i == 1){ for(int j = 1; j <= M[i]; j++){ int u = tn[i+1][j]; int v = tn[i][j]; int w = b[i][j] - a[i][j]; add_edge(u, v, w); } sz[i] = M[i]; }else if(i < n){ normalize norm; for(int j = 1; j <= M[i-1]; j++){ norm.add(b[i-1][j]); } for(int j = 1; j <= M[i]; j++){ norm.add(a[i][j]); } norm.start(); for(int j = 1; j <= M[i]; j++){ int u = tn[i+1][j]; int v = tn[i][j+M[i-1]]; int w = b[i][j] - a[i][j]; add_edge(u, v, w); } for(int j = 1; j <= M[i]; j++){ T.modify(norm.encode(a[i][j]), {b[i][j], j}); } for(int j = 1; j <= M[i-1]; j++){ int p = T.rangeQuery(norm.encode(b[i-1][j]), N+1).id; ll w; if(p == -1){ p = T.rangeQuery(1, N+1).id; w = b[i][p] + L - b[i-1][j]; }else{ w = b[i][p] - b[i-1][j]; } int u = tn[i+1][p]; int v = tn[i][j]; add_edge(u, v, w); } //reset DS for(int j = 1; j <= M[i]; j++){ T.modify(norm.encode(a[i][j]), Info()); } sz[i] = M[i-1] + M[i]; }else{ for(int j = 1; j <= M[i-1]; j++){ int u = tn[i][j]; add_edge(0, u, 0); } sz[i] = M[i-1]; } } auto chmin = [&](ll &a, ll b) -> void{ a = min(a, b); }; int B = 500; vector<vector<ll>> big(n+1); for(int i = 1; i <= n; i++){ if(sz[i] > B){ //3 for loops but O(n) trust me bro //constant factor is (?) big[i].resize(n+1, INF); big[i][i] = 0; vector<ll> d(N+1, INF); for(int it = 1; it <= sz[i]; it++){ int u = tn[i][it]; d[u] = 0; } for(int j = i+1; j <= n; j++){ for(int it = 1; it <= sz[j]; it++){ int u = tn[j][it]; for(auto e : adj[u]){ ll v = e.first, w = e.second; chmin(d[u], d[v]+w); chmin(big[i][j], d[u]); } } } } } int Q; cin >> Q; vector<ll> ans(Q+1, INF); vector<vector<pair<int ,int>>> q(n+1); for(int i = 1; i <= Q; i++){ int l, r; cin >> l >> r; if(sz[l] > B){ ans[i] = big[l][r]; continue; } q[n+1 - l].push_back({n+1 - r, i}); } vector<ll> d(N+1, 0); vector<int> st; auto dfs = [&](auto dfs, int u, int len) -> void{ for(auto it : q[len]){ int p = it.first, id = it.second; chmin(ans[id], d[u] - d[st[p]]); } st.push_back(u); for(auto it : adj[u]){ ll v = it.first, w = it.second; d[v] = d[u] + w; dfs(dfs, v, len+1); } st.pop_back(); }; dfs(dfs, 0, 0); for(int i = 1; i <= Q; i++){ cout << ans[i] << "\n"; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); solve(); }