Overview

Instead of using the values \(A_{i,p}\) of each cell directly, we first transform them to \(f(A_{i,p})=\max_{0\le Y\le A_{i,p}}S(Y)\), and then for each query, the problem becomes efficiently finding the maximum value within the “reachable triangular region.”
By building a per-row RMQ (Sparse Table), we can process queries efficiently.

Analysis

The difficulty of this problem mainly lies in two aspects:

1. How to compute \(f(V)\) efficiently
2. How to efficiently obtain the maximum value over all reachable cells for each query

---

1. Computing \(f(V)\)

The definition is \(f(V)=\max_{0\le Y\le V}S(Y)\).
Brute-force searching from \(Y=0\) to \(V\) is impossible (\(V\) can be up to \(10^{18}\)).

Here we use a well-known digit-DP-like observation.
It suffices to only consider candidates of the following form:

• \(Y=V\) (as is)
• A number where some digit is decreased by 1, and all digits to its right are set to 9

Example: If \(V=5273\), the candidates are - 5273 (digit sum 17) - 4999 (22) - 5199 (24) - 5269 (22) and so on.
The maximum among these gives \(f(V)\).

In implementation, we convert to a string, use a precomputed prefix sum, compute the digit sum of each candidate in \(O(1)\), and the overall complexity is \(O(\text{number of digits})\).

---

2. Reachable Region for Queries

From the starting position \((L,P)\), in one move you can:

• Stay on the same row (remain)
• Move to the same column one row below
• Move to the adjacent right column one row below

So, when you are \(r\) rows below (i.e., row \(i=L+r\)), the column range is
\([P,\;P+r]\).
Also, you can go down at most \(N-L\) rows, so the rows you actually examine are \(i\in[L,\;\min(N,L+T)]\).

Thus, the query can be reformulated as:
For each row \(i\), take the maximum over the interval \([P,\;P+(i-L)]\), then take the maximum across all such rows.

---

Why a Naive Solution Is Too Slow

If we scan all cells in the reachable region for each query, the worst case becomes triangle-sized, which is too heavy.
Since \(Q\) can be up to \(10^5\), this is far too slow.

Therefore, to speed up the “per-row interval maximum,” we build a Sparse Table for each row.
This allows retrieving the maximum of any interval in \(O(1)\).
Each query only needs to iterate over rows from top to bottom, so processing takes \(O(\text{number of reachable rows})\) per query.
Since the constraint guarantees \(NQ\le 10^7\), this approach is fast enough.

Algorithm

1. For each input \(A_{i,p}\), compute and store \(B_{i,p}=f(A_{i,p})\).
2. For each row \(i\) (of length \(i\)), build a Sparse Table.
   • st[i][k][p] = maximum value in row \(i\) over the interval \([p,\;p+2^k-1]\)
3. Process each query \((L,P,T)\):
   • If \(P>L\), the starting cell does not exist, so output NA
   • Otherwise:
     • maxRow = L + min(T, N-L)
     • For each row \(i=L..maxRow\), retrieve the maximum over interval \([P,\;P+(i-L)]\) using RMQ
     • Output the overall maximum as the answer

Complexity

• Time complexity:
  
  • Preprocessing (\(f\) computation): \(O(N^2 \cdot D)\) (\(D\) is the number of digits, at most 19, which can be treated as a constant)
    
  • Sparse Table construction: \(\sum_{i=1}^N O(i\log i)=O(N^2\log N)\)
    
  • Query processing: \(\sum O(\min(N-L_j, T_j)+1)\), worst-case evaluation \(O(NQ)\) (at most \(\le 10^7\) by constraint)
• Space complexity: \(O(N^2\log N)\) (Sparse Tables per row)

Implementation Notes

• When P > L, immediately output NA.

• maxRow is capped at L + min(T, N-L) (since T can be large, use long long).

• When retrieving the interval maximum, for length len=r-l+1, use k=floor(log2(len)) and compute
  max(st[k][l], st[k][r-2^k+1]).

• In \(f(V)\), don’t forget to try all digits with the “decrease a digit by 1 and set all digits to the right to 9” candidates.
  Even if the leading digit becomes 0, there is no issue in terms of digit sum calculation.

  Source Code

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

static inline int digit_sum_u64(unsigned long long x) {
    int s = 0;
    while (x > 0) {
        s += int(x % 10);
        x /= 10;
    }
    return s;
}

static inline int f_max_digit_sum(unsigned long long V) {
    // f(V) = max_{0<=Y<=V} S(Y)
    // Candidates:
    // 1) Y = V
    // 2) For each position, reduce that digit by 1 and set all lower digits to 9.
    string s = to_string(V);
    int n = (int)s.size();

    vector<int> pref(n + 1, 0);
    for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + (s[i] - '0');

    int ans = pref[n]; // S(V)
    for (int i = 0; i < n; i++) {
        int d = s[i] - '0';
        if (d == 0) continue;
        int cand = pref[i] + (d - 1) + 9 * (n - i - 1);
        if (cand > ans) ans = cand;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    vector<vector<int>> B(N + 1);
    for (int i = 1; i <= N; i++) {
        B[i].resize(i + 1);
        for (int p = 1; p <= i; p++) {
            unsigned long long a;
            cin >> a;
            B[i][p] = f_max_digit_sum(a);
        }
    }

    // dpL[L][r][p]: row = L+r, max over columns [p, p+r]
    // Size O(N^3/2) with N<=1000 => about 167M ints max, but we store by L only needed.
    // Since NQ<=1e7, O(N^3) preprocessing is too much.
    // For each L, build sparse table over each row segment lengths via DP in O((N-L+1)^2).
    // Total O(N^3/3) still heavy. Instead use per-query O(N) with NQ<=1e7 acceptable.
    // Query: reachable rows i in [L, min(N, L+T)], and at row i columns in [P, P+(i-L)].
    // Need max over triangular region. We'll process row-wise with RMQ per row O(1).

    int K = 0;
    while ((1 << (K + 1)) <= N) K++;
    vector<int> lg(N + 1);
    for (int i = 2; i <= N; i++) lg[i] = lg[i >> 1] + 1;

    // Sparse table per row
    vector<vector<vector<int>>> st(N + 1);
    for (int i = 1; i <= N; i++) {
        int m = i;
        int kmax = lg[m] + 1;
        st[i].assign(kmax, vector<int>(m + 1, 0));
        for (int p = 1; p <= m; p++) st[i][0][p] = B[i][p];
        for (int k = 1; k < kmax; k++) {
            int len = 1 << k;
            int half = len >> 1;
            for (int p = 1; p + len - 1 <= m; p++) {
                st[i][k][p] = max(st[i][k - 1][p], st[i][k - 1][p + half]);
            }
        }
    }

    auto range_max_row = [&](int row, int l, int r) -> int {
        int len = r - l + 1;
        int k = lg[len];
        return max(st[row][k][l], st[row][k][r - (1 << k) + 1]);
    };

    for (int qi = 0; qi < Q; qi++) {
        int L, P;
        long long T;
        cin >> L >> P >> T;

        if (P > L) {
            cout << "NA\n";
            continue;
        }

        int maxRow = L + (int)min<long long>(T, N - L);
        int ans = 0;

        for (int i = L; i <= maxRow; i++) {
            int r = i - L;
            int left = P;
            int right = P + r; // <= i because P<=L
            ans = max(ans, range_max_row(i, left, right));
        }

        cout << ans << '\n';
    }

    return 0;
}

---

This editorial was generated by gpt-5.3-codex.