Overview

The transitions from each terminal form a functional graph where “the next terminal is uniquely determined,” so we precompute “the position after \(2^b\) operations” and “the \(2^b\)-digit value obtained at that point (mod \(M\))” using doubling, and answer each query by efficiently composing them according to the binary representation of \(K\).

Analysis

In this problem, one operation consists of:

• Appending the digit of the current terminal
• Moving to the next terminal

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

---

The key observation is that “concatenation of digit sequences” can be expressed by the following formula.

If the value of a sequence of length \(a\) is \(X\) and the value of a sequence of length \(b\) is \(Y\), then the value of the concatenated sequence of length \(a+b\) is

\[ X \cdot 10^b + Y \]

(we just take mod \(M\) at the end).

In other words, if we can compose a “first-half block” and a “second-half block,” we can build blocks of sizes \(2^0, 2^1, 2^2, \dots\). This is exactly doubling (binary lifting).

---

Why the naive approach fails:

• Iterating \(K\) times per query → worst case \(10^{18}\) steps, impossible
• The number of queries is up to \(10^5\), so we need to reduce the cost per query to about \(O(\log K)\)

Therefore, for each terminal \(v\), we maintain:

• nxt[b][v]: the terminal reached after \(2^b\) moves from \(v\)
• val[b][v]: the \(2^b\)-digit value (mod \(M\)) obtained by performing \(2^b\) operations from \(v\)

Then each query can be answered by composing only the set bits of \(K\) in order.

Algorithm

1. Initialization (\(b=0\))

   • nxt[0][v] = P[v]
   • val[0][v] = D[v] mod M
     (One operation records one digit and moves once)

2. Precomputation of \(10^{2^b} \bmod M\)

   • pow10[0] = 10 mod M
   • pow10[b] = pow10[b-1]^2 mod M
     This gives pow10[b] = 10^{2^b} mod M.

3. Building the doubling transitions

   • A \(2^b\) block is the concatenation of two \(2^{b-1}\) blocks.
   • mid = nxt[b-1][v] (position after the first half)
   • nxt[b][v] = nxt[b-1][mid]
   • val[b][v] = val[b-1][v] * 10^{2^{b-1}} + val[b-1][mid] (mod M)

The implementation formula: $\( \text{val}[b][v] = (\text{val}[b-1][v] \cdot \text{pow10}[b-1] + \text{val}[b-1][\text{mid}]) \bmod M \)$

1. Processing each query
   • cur = S_j, ans = 0
   • Scanning the bits of \(K_j\) from the least significant bit, if bit \(b\) is set:
     • ans = ans * 10^{2^b} + val[b][cur] (mod M)
     • cur = nxt[b][cur]
   • Repeat until \(K_j = 0\).
   • When \(K_j = 0\), nothing is composed, so ans = 0 remains (as per the problem statement).

The order of “appending blocks to the end of ans” is important. Even though we process from the least significant bit, each time we “shift the current answer to the left and then append the new block,” so the digit order is correctly maintained.

Complexity

• Time complexity: \(O(N \log K_{\max} + Q \log K_{\max})\)
  where \(K_{\max} \le 10^{18}\), so \(\log K_{\max} \approx 60\).
• Space complexity: \(O(N \log K_{\max})\)

Implementation Notes

• Terminal numbers are 1-indexed in the input; convert to 0-indexed in the code.

• LOG=60 is sufficient (\(10^{18} < 2^{60}\)).

• pow10[b] is an array holding \(10^{2^b} \bmod M\). It is essential during composition.

• Even in Python, \(O((N+Q) \times 60)\) is fast enough.

• When \(M=1\), everything automatically becomes 0, which is correct.

  Source Code

import sys

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

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

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

    # nxt[b][v]: node after 2^b moves from v
    # val[b][v]: value of length 2^b digit string obtained from v, modulo M
    nxt = [[0] * N for _ in range(LOG)]
    val = [[0] * N for _ in range(LOG)]

    for v in range(N):
        nxt[0][v] = P[v]
        val[0][v] = D[v] % M

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

    for b in range(1, LOG):
        nb = nxt[b - 1]
        vb = val[b - 1]
        ncur = nxt[b]
        vcur = val[b]
        mul = pow10[b - 1]
        for v in range(N):
            mid = nb[v]
            ncur[v] = nb[mid]
            vcur[v] = (vb[v] * mul + vb[mid]) % M

    out = []
    for _ in range(Q):
        s, k = input().split()
        s = int(s) - 1
        k = int(k)

        cur = s
        ans = 0
        bit = 0
        while k:
            if k & 1:
                ans = (ans * pow10[bit] + val[bit][cur]) % M
                cur = nxt[bit][cur]
            k >>= 1
            bit += 1
        out.append(str(ans))

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

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.3-codex.