T0933 清单

#include <bits/stdc++.h>
using namespace std;

/*
清单：询问 [l,r] 内选一个非空子集，占用之和 <= m，价值之和最大，并统计最优方案数。

分治 + 背包：
  把询问按 mid 分成三类：全在左、全在右、跨过 mid。
  跨 mid 的询问，用
      左边 [l..mid] 的「恰好占满 x」背包 L[x]（值 + 方案数）
      右边 [mid+1..r] 的「占用不超过 m-x」背包 R[m-x]（值 + 方案数）
  组合：答案 = max_x ( L[x] + R[m-x] )，
        方案数 = 对所有取到最大值的 x，把 L 的方案数乘 R 的方案数累加。
  左边从 mid 往左逐个加入物品，O(M) 一次背包；右边从 mid+1 往右同理。
  每个左端点只保存「恰好装满」的数组，每个右端点只保存「不超过」的数组，
  这样方案数不会重复计算（左边用恰好、右边用不超过）。
*/

const int MOD = 998244353;

int n, q;
long long val[20005];
int wt[20005];

struct Query {
    int l, r, m, id;
};

long long ansVal[100005];
long long ansCnt[100005];

void solve(int L, int R, const vector<Query> &qs) {
    if (qs.empty()) return;
    if (L == R) {
        for (const auto &qu : qs) {
            if (wt[L] <= qu.m) {
                ansVal[qu.id] = val[L];
                ansCnt[qu.id] = 1;
            } else {
                ansVal[qu.id] = 0;
                ansCnt[qu.id] = 0;
            }
        }
        return;
    }
    int mid = (L + R) >> 1;
    vector<Query> ql, qr, qc;
    for (const auto &qu : qs) {
        if (qu.r <= mid) ql.push_back(qu);
        else if (qu.l > mid) qr.push_back(qu);
        else qc.push_back(qu);
    }

    if (!qc.empty()) {
        int M = 0;
        for (const auto &qu : qc) M = max(M, qu.m);

        vector<int> rowL(mid - L + 1, -1), rowR(R - mid, -1);
        int nL = 0, nR = 0;
        for (const auto &qu : qc) {
            int i = qu.l - L;
            if (rowL[i] == -1) rowL[i] = nL++;
            int j = qu.r - (mid + 1);
            if (rowR[j] == -1) rowR[j] = nR++;
        }

        vector<vector<int>> lval(nL, vector<int>(M + 1, -1));
        vector<vector<int>> lcnt(nL, vector<int>(M + 1, 0));
        vector<vector<int>> rval(nR, vector<int>(M + 1, -1));
        vector<vector<int>> rcnt(nR, vector<int>(M + 1, 0));

        vector<int> dpv(M + 1, -1), dpc(M + 1, 0);
        dpv[0] = 0;
        dpc[0] = 1;
        for (int l = mid; l >= L; l--) {
            int w = wt[l];
            if (w <= M) {
                int v = (int)val[l];
                for (int x = M; x >= w; x--) {
                    if (dpv[x - w] < 0) continue;
                    int cand = dpv[x - w] + v;
                    if (cand > dpv[x]) {
                        dpv[x] = cand;
                        dpc[x] = dpc[x - w];
                    } else if (cand == dpv[x]) {
                        dpc[x] += dpc[x - w];
                        if (dpc[x] >= MOD) dpc[x] -= MOD;
                    }
                }
            }
            int i = l - L;
            if (rowL[i] != -1) {
                lval[rowL[i]] = dpv;
                lcnt[rowL[i]] = dpc;
            }
        }

        vector<int> dpv2(M + 1, -1), dpc2(M + 1, 0);
        vector<int> av(M + 1, 0), ac(M + 1, 0);
        dpv2[0] = 0;
        dpc2[0] = 1;
        for (int r = mid + 1; r <= R; r++) {
            int w = wt[r];
            if (w <= M) {
                int v = (int)val[r];
                for (int x = M; x >= w; x--) {
                    if (dpv2[x - w] < 0) continue;
                    int cand = dpv2[x - w] + v;
                    if (cand > dpv2[x]) {
                        dpv2[x] = cand;
                        dpc2[x] = dpc2[x - w];
                    } else if (cand == dpv2[x]) {
                        dpc2[x] += dpc2[x - w];
                        if (dpc2[x] >= MOD) dpc2[x] -= MOD;
                    }
                }
            }
            av[0] = dpv2[0];
            ac[0] = dpc2[0];
            for (int c = 1; c <= M; c++) {
                av[c] = av[c - 1];
                ac[c] = ac[c - 1];
                if (dpv2[c] > av[c]) {
                    av[c] = dpv2[c];
                    ac[c] = dpc2[c];
                } else if (dpv2[c] == av[c]) {
                    ac[c] += dpc2[c];
                    if (ac[c] >= MOD) ac[c] -= MOD;
                }
            }
            int j = r - (mid + 1);
            if (rowR[j] != -1) {
                rval[rowR[j]] = av;
                rcnt[rowR[j]] = ac;
            }
        }

        for (const auto &qu : qc) {
            const vector<int> &lv = lval[rowL[qu.l - L]];
            const vector<int> &lc = lcnt[rowL[qu.l - L]];
            const vector<int> &rv = rval[rowR[qu.r - (mid + 1)]];
            const vector<int> &rc = rcnt[rowR[qu.r - (mid + 1)]];
            long long best = -1, ways = 0;
            for (int x = 0; x <= qu.m; x++) {
                if (lv[x] < 0) continue;
                int tot = lv[x] + rv[qu.m - x];
                long long w = (long long)lc[x] * rc[qu.m - x] % MOD;
                if (tot > best) {
                    best = tot;
                    ways = w;
                } else if (tot == best) {
                    ways += w;
                    if (ways >= MOD) ways -= MOD;
                }
            }
            if (best <= 0) {
                ansVal[qu.id] = 0;
                ansCnt[qu.id] = 0;
            } else {
                ansVal[qu.id] = best;
                ansCnt[qu.id] = ways;
            }
        }
    }

    solve(L, mid, ql);
    solve(mid + 1, R, qr);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> val[i] >> wt[i];
    cin >> q;
    vector<Query> qs(q);
    for (int i = 0; i < q; i++) {
        cin >> qs[i].l >> qs[i].r >> qs[i].m;
        qs[i].id = i;
    }
    solve(1, n, qs);
    for (int i = 0; i < q; i++) cout << ansVal[i] << ' ' << ansCnt[i] << "\n";
    return 0;
}