Overview

Each terminal has exactly one “next terminal” to move to, so movement follows a single path.
Therefore, we precompute the “destination” and “the value of the digit string recorded along the way \(\bmod M\)” after \(2^b\) moves using doubling, and process each query efficiently.

Analysis

In this problem, starting from terminal \(S\) and performing exactly \(K\) operations, we obtain the digit string

\[ d_1d_2\cdots d_K \]

and we need to find the remainder when the integer value

\[ V=\sum_{t=1}^{K} d_t \cdot 10^{K-t} \]

is divided by \(M\).

Naive simulation is too slow

If we consider moving \(K\) times and recording digits for each query,
\(K\) can be up to \(10^{18}\), so this is far too slow.

Also, since each terminal has exactly one destination, the graph is a “functional graph (each vertex has out-degree 1).”
Even if we try to find cycles and handle them carefully, we need to deal with the value of digit strings concatenated as base-10 numbers, making the implementation quite complex.

Key observation: digit string concatenation can be composed while preserving mod

For example, suppose the digit string value from one segment is \(A\) with length \(L_A\),
and the digit string value from the next segment is \(B\) with length \(L_B\).

The value of the concatenated digit string is

\[ A \times 10^{L_B} + B \]

For example, concatenating "31" and "45" gives "3145", and

\[ 3145 = 31 \times 10^2 + 45 \]

In other words, if we know for each segment:

• The destination after traversing that segment
• The digit string value \(\bmod M\) for that segment

then we can compose the information for longer segments.

Doubling can be used

By precomputing “the result of \(2^b\) moves,”
we can answer queries by decomposing \(K\) into binary.

For each \(b\), we maintain:

• up[b][i] = the terminal reached after \(2^b\) moves starting from terminal \(i\)
• val[b][i] = the digit string value \(\bmod M\) recorded during \(2^b\) operations starting from terminal \(i\)

Constructing the transitions

\(2^b\) moves consist of two consecutive sequences of \(2^{b-1}\) moves.

Let \(A\) be the value from the first half and \(B\) from the second half. Since both halves have length \(2^{b-1}\):

\[ \text{val}[b][i] = \text{val}[b-1][i] \times 10^{2^{b-1}} + \text{val}[b-1][\text{mid}] \pmod M \]

Here, \(\text{mid}=\text{up}[b-1][i]\) is the terminal reached after completing the first half.

To use this formula, we also precompute

\[ 10^{2^b} \bmod M \]

Processing queries

We examine \(K\) in binary, and for each set bit, we append the corresponding segment of length \(2^b\) in order.

For example, if \(K=13=(1101)_2\), we concatenate segments of:

• \(1\) move
• \(4\) moves
• \(8\) moves

in this order, giving exactly 13 moves from the start.

Let res be the current answer and cur be the current terminal. When appending a segment of length \(2^b\):

\[ \text{res} = \text{res} \times 10^{2^b} + \text{val}[b][cur] \pmod M \]

Then cur moves to up[b][cur].

This processes each query in \(O(\log K)\).

Algorithm

1. Read each terminal’s digit \(D_i\) and destination \(P_i\).
2. If \(M=1\), any value \(\bmod 1\) is \(0\), so the answer to every query is \(0\).
3. Since \(K \le 10^{18} < 2^{60}\), precompute for \(b=0,\dots,59\).
4. Precompute pow10[b] = 10^{2^b} \bmod M.
   • pow10[0] = 10 mod M
   • pow10[b] = pow10[b-1]^2 mod M
5. Build the doubling arrays.
   • Base case:
     • up[0][i] = P_i
     • val[0][i] = D_i
   • Transition:
     • mid = up[b-1][i]
     • up[b][i] = up[b-1][mid]
     • val[b][i] = (val[b-1][i] * pow10[b-1] + val[b-1][mid]) mod M
6. For each query \((S, K)\):
   • cur = S, res = 0
   • Iterate over bits of \(K\) from the least significant bit; if bit \(b\) is set:
     • res = (res * pow10[b] + val[b][cur]) mod M
     • cur = up[b][cur]
   • Output the final res.
7. When \(K=0\), no updates occur and res=0 remains, which is correct.

Complexity

• Time complexity: \(O((N+Q)\log K_{\max}) = O((N+Q)\cdot 60)\)
• Space complexity: \(O(N\log K_{\max}) = O(N\cdot 60)\)

Implementation Notes

• Be careful about the direction of the concatenation formula.
  The digit string that appears first is shifted left by the number of digits in the latter string:

$\( \text{Concatenating } B \text{ after } A \Rightarrow A \times 10^{|B|} + B \)$

• Both in precomputation and query processing, the pattern is “multiply the previous value by \(10^{\text{length}}\) and then add.”
• In Python, holding large 2D arrays with regular list[int] can be tight on memory, so in this code, array('I') is used to save memory.
• \(B = 60\) is sufficient because

$\( 10^{18} < 2^{60} \)$

Source Code

import sys
from array import array

def main():
    input = sys.stdin.buffer.readline
    N, Q, M = map(int, input().split())

    if M == 1:
        for _ in range(N):
            input()
        out = ["0"] * Q
        for _ in range(Q):
            input()
        sys.stdout.write("\n".join(out))
        return

    D = array('I', [0]) * (N + 1)
    P = array('I', [0]) * (N + 1)

    for i in range(1, N + 1):
        d, p = map(int, input().split())
        D[i] = d
        P[i] = p

    B = 60  # since K <= 1e18 < 2^60

    pow10 = [0] * B
    pow10[0] = 10 % M
    for b in range(1, B):
        pow10[b] = (pow10[b - 1] * pow10[b - 1]) % M

    up = [P]
    val = [D]

    idx_range = range(1, N + 1)
    for b in range(1, B):
        prev_up = up[-1]
        prev_val = val[-1]
        cur_up = array('I', [0]) * (N + 1)
        cur_val = array('I', [0]) * (N + 1)
        mul = pow10[b - 1]

        for i in idx_range:
            mid = prev_up[i]
            cur_up[i] = prev_up[mid]
            cur_val[i] = (prev_val[i] * mul + prev_val[mid]) % M

        up.append(cur_up)
        val.append(cur_val)

    out = []
    up_local = up
    val_local = val
    pow10_local = pow10

    for _ in range(Q):
        s, k = map(int, input().split())
        cur = s
        res = 0
        b = 0
        while k:
            if k & 1:
                res = (res * pow10_local[b] + val_local[b][cur]) % M
                cur = up_local[b][cur]
            k >>= 1
            b += 1
        out.append(str(res))

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

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.