Overview

For each cell’s value \(A_{i,p}\), we precompute and convert it to \(f(A_{i,p})\).
For each query, we exploit the fact that reachable cells form a “contiguous interval” at each level, and efficiently compute the interval maximum for each level.

Analysis

Shape of Reachable Cells

Let the starting position be \((L, P)\).

There are \(3\) types of operations:

• Stay
• Move directly below
• Move diagonally down-right

Since “stay” does not change position, if we let \(m\) be the number of times we actually move down a level, the reached level is level \(L+m\).

We must perform exactly \(T\) operations, but we can use “stay” to adjust the number of operations.
Therefore, the number of downward moves \(m\) can take any value in:

\[ 0 \leq m \leq \min(T, N-L) \]

Also, among \(m\) downward moves, if \(k\) of them are diagonal (down-right), the position becomes:

\[ (L+m,\ P+k) \]

Since \(k\) satisfies:

\[ 0 \leq k \leq m \]

the reachable positions at level \(L+m\) form the contiguous interval:

\[ P, P+1, \ldots, P+m \]

In other words, for a query \((L, P, T)\), the reachable cells viewed level by level are:

• Level \(L\): \([P, P]\)
• Level \(L+1\): \([P, P+1]\)
• Level \(L+2\): \([P, P+2]\)
• \(\cdots\)
• Up to level \(\min(N, L+T)\)

For example, if \(L=3, P=2, T=2\), the reachable range is:

• Level \(3\): \([2,2]\)
• Level \(4\): \([2,3]\)
• Level \(5\): \([2,4]\)

Issues with the Naive Approach

Trying all possible operation sequences would result in up to \(3^T\) possibilities, which is far too slow.

Also, enumerating all reachable cells would require examining up to \(O(N^2)\) cells per query.
Since \(Q\) is large, this is also too slow.

However, the range to examine at each level is a contiguous interval.
Therefore, if we can efficiently compute “interval maximums” for each level, we can process each query in time proportional to the number of levels, i.e., \(O(N)\).

Since the constraint \(NQ \leq 10^7\) holds, \(O(N)\) per query is fast enough.

Computing \(f(V)\)

\(f(V)\) is the digit sum of the integer \(Y\) satisfying:

\[ 0 \leq Y \leq V \]

that maximizes the digit sum \(S(Y)\).

We cannot try all \(Y\).

Consider the decimal representation of \(V\).
To maximize the digit sum, it is optimal to decrease some digit by \(1\) and set all digits to its right to \(9\).

For example, if:

\[ V = 2503 \]

then the candidates to consider are:

• \(2503\) itself, digit sum \(2+5+0+3=10\)
• \(1999\), digit sum \(1+9+9+9=28\)
• \(2499\), digit sum \(2+4+9+9=24\)
• \(2502\), digit sum \(2+5+0+2=9\)

and this is sufficient.

In general, suppose some digit has value \(d>0\), the sum of digits to its left is \(\mathrm{pref}\), and there are \(r\) remaining digits to its right.
If we decrease that digit to \(d-1\) and set all right digits to \(9\), the digit sum becomes:

\[ \mathrm{pref} + (d-1) + 9r \]

By trying this for all digits and also including the digit sum of \(V\) itself as a candidate, we can compute \(f(V)\).

Since \(A_{i,p} \leq 10^{18}\), the number of digits is at most \(19\).
Therefore, \(f(A_{i,p})\) for each cell can be computed sufficiently fast.

Algorithm

First, convert each cell’s value to:

\[ B_{i,p} = f(A_{i,p}) \]

Then, build a Sparse Table for each level to efficiently compute interval maximums.

Preprocessing

For each level \(i\), consider the array:

\[ B_{i,1}, B_{i,2}, \ldots, B_{i,i} \]

We build a Sparse Table for this array.

In the Sparse Table,

\[ \mathrm{st}[k][p] \]

represents “the maximum value in the interval of length \(2^k\) starting at position \(p\).”

Then, the maximum of any interval \([l,r]\) can be found by letting:

\[ len = r-l+1 \]

and choosing:

\[ k = \lfloor \log_2 len \rfloor \]

to compute:

\[ \max(\mathrm{st}[k][l],\ \mathrm{st}[k][r-2^k+1]) \]

Query Processing

For a query \((L, P, T)\), if \(P > L\), the starting cell does not exist, so output NA.

Otherwise, the maximum reachable level is:

\[ R = \min(N, L+T) \]

For each level \(r\), the reachable positions are:

\[ [P,\ P+(r-L)] \]

We find the maximum of this interval using that level’s Sparse Table, and take the overall maximum across all levels to get the answer.

Specifically:

1. Set ans = 0
2. Iterate \(r\) from \(L\) to \(R\)
3. Retrieve the maximum of interval \([P, P+(r-L)]\)
4. Update ans
5. Output ans at the end

Complexity

• Time complexity: \(O(N^2 \log N + NQ)\)
  • Computing \(f(A_{i,p})\) for each cell has at most \(19\) digits, so \(O(N^2)\) overall
  • Building Sparse Tables for all levels totals \(O(N^2 \log N)\)
  • Each query takes at most \(O(N)\), totaling \(O(NQ)\) by the constraint
• Space complexity: \(O(N^2 \log N)\)
  • For storing the Sparse Tables for each level

Implementation Notes

• Although \(T\) can be as large as \(10^9\), since there are only \(N\) levels, we only need to examine up to level \(\min(N, L+T)\).

• If \(P > L\), the starting cell does not exist, so output NA without computation.

• The maximum value of \(f(A_{i,p})\) is \(162\).

  • The number at most \(10^{18}\) with the maximum digit sum is \(999999999999999999\), with digit sum \(9 \times 18 = 162\).
  • Therefore, in the code, values are stored in bytearray / bytes to save memory.

• If the answer reaches \(162\), it cannot get any larger, so we can terminate processing of that query early.

  Source Code

import sys


def max_digit_sum_token(bs):
    if bs[0] == 48:
        if len(bs) == 1:
            return 0
        bs = bs.lstrip(b'0')
        if not bs:
            return 0

    n = len(bs)
    pref = 0
    ans = 0
    rem = n - 1

    for c in bs:
        d = c - 48
        if d:
            cand = pref + d - 1 + 9 * rem
            if cand > ans:
                ans = cand
        pref += d
        rem -= 1

    if pref > ans:
        ans = pref
    return ans


def main():
    input = sys.stdin.buffer.readline

    N, Q = map(int, input().split())

    logs = [0] * (N + 2)
    for i in range(2, N + 2):
        logs[i] = logs[i >> 1] + 1

    powers = [1 << i for i in range(logs[N] + 1)]

    rmq = [None] * (N + 1)
    calc = max_digit_sum_token

    for i in range(1, N + 1):
        parts = input().split()
        row = bytearray(i + 1)

        for p, tok in enumerate(parts, 1):
            row[p] = calc(tok)

        prev = bytes(row)
        levels = [prev]
        length = 1

        while (length << 1) <= i:
            seg = length << 1
            limit = i - seg + 1
            new = bytearray(limit + 1)
            pr = prev
            h = length

            for p in range(1, limit + 1):
                a = pr[p]
                b = pr[p + h]
                new[p] = a if a >= b else b

            prev = bytes(new)
            levels.append(prev)
            length = seg

        rmq[i] = levels

    out = []
    append = out.append
    rows = rmq
    MAX_F = 162

    for _ in range(Q):
        L, P, T = map(int, input().split())

        if P > L:
            append("NA")
            continue

        if T < N - L:
            end = L + T
        else:
            end = N

        ans = 0
        length = 1
        p = P

        for r in range(L, end + 1):
            k = logs[length]
            seg = powers[k]
            arr = rows[r][k]

            v = arr[p]
            w = arr[p + length - seg]
            if w > v:
                v = w

            if v > ans:
                ans = v
                if ans == MAX_F:
                    break

            length += 1

        append(str(ans))

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.