Overview

This problem asks us to move between \(N\) terminals \(K\) times, and find the remainder when dividing by \(M\) the large integer formed by concatenating the digits recorded at each terminal. Since the number of operations \(K\) can be as large as \(10^{18}\), naive simulation is not feasible, and we need to use Binary Lifting (Doubling) for speedup.

Analysis

1. Understanding the Value Computation

Let the digits recorded over \(K\) operations be \(d_1, d_2, \ldots, d_K\). The resulting value \(V\) is expressed as: $\(V = d_1 \cdot 10^{K-1} + d_2 \cdot 10^{K-2} + \dots + d_K \cdot 10^0\)$

This formula becomes easier to understand when we think of it as appending a new digit \(d_{new}\) to the end. If the current value is \(V_{old}\) with length (number of digits) \(L\), then the new value \(V_{new}\) after concatenating a \(k\)-digit number \(V_{add}\) to the end is: $\(V_{new} = V_{old} \cdot 10^k + V_{add} \pmod M\)$

2. Why Naive Simulation Doesn’t Work

If we directly simulate \(K\) moves for each query, it takes \(O(K)\) time per query. Since \(K \leq 10^{18}\), this cannot finish within the time limit.

3. Speedup via Doubling

By precomputing “the destination after \(2^p\) moves” and “the value obtained during those moves,” we can process any \(K\) moves in \(O(\log K)\).

• next_node[p][i]: The terminal number reached after starting from terminal \(i\) and making \(2^p\) moves
• value[p][i]: The value obtained after starting from terminal \(i\) and making \(2^p\) moves (\(\pmod M\))

Given these, the state for p+1 can be computed by combining two copies of the state for p: - Destination: next_node[p+1][i] = next_node[p][next_node[p][i]] - Value: value[p+1][i] = (value[p][i] * 10^{2^p} + value[p][next_node[p][i]]) % M

Algorithm

1. Preprocessing (Building the Doubling Table)

   • For \(p=0\) (\(2^0=1\) move): next_node[0][i] = P_i, value[0][i] = D_i \pmod M.
   • For \(p=1, 2, \dots, \log_2(\max K)\), fill the table using the transition formulas above.
   • Simultaneously, precompute \(10^{2^p} \pmod M\).

2. Query Processing

   • For each query \((S_j, K_j)\), set the current value \(v = 0\) and the current terminal \(u = S_j\).
   • Decompose \(K_j\) in binary, and for each bit position \(p\) that is set, perform the following updates:
     • \(v = (v \cdot 10^{2^p} + \text{value}[p][u]) \pmod M\)
     • \(u = \text{next\_node}[p][u]\)
   • The final \(v\) is the answer.

Complexity

• Time Complexity: \(O((N + Q) \log (\max K))\)
  • Building the doubling table takes \(O(N \log K)\), and answering queries takes \(O(Q \log K)\).
• Space Complexity: \(O(N \log (\max K))\)
  • Memory is needed to store the doubling table.

Implementation Notes

• Memory Optimization: In Python, storing the table as a list of lists can consume a large amount of memory, so using array.array or looping over only the minimum necessary number of bits can be effective.

• Speedup: Precomputing \(10^{2^p} \pmod M\) using repeated squaring reduces per-query computation.

• 0-indexed: Since terminal numbers are given from \(1\) to \(N\), converting them to \(0\) through \(N-1\) in the implementation makes array access smoother. Also, be careful with the case \(K=0\) (the answer is \(0\)).

  Source Code

import sys
import array

def solve():
    # Read all input at once for speed
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    try:
        N = int(next(it))
        Q = int(next(it))
        M = int(next(it))
    except StopIteration:
        return
    
    # Store digits and next terminal destinations
    D = [0] * N
    P = [0] * N
    for i in range(N):
        try:
            D[i] = int(next(it))
            P[i] = int(next(it)) - 1 # Convert to 0-indexed
        except StopIteration:
            break
            
    # Store queries and find the maximum number of steps needed
    queries = []
    max_k = 0
    for _ in range(Q):
        try:
            s = int(next(it)) - 1 # Convert to 0-indexed
            k = int(next(it))
            queries.append((s, k))
            if k > max_k:
                max_k = k
        except StopIteration:
            break
    
    # Special case where all query steps are 0
    if max_k == 0:
        sys.stdout.write('\n'.join(['0'] * Q) + '\n')
        return

    # Calculate the number of bits needed for the maximum k
    num_bits = max_k.bit_length()
    
    # next_node[bit][i] stores the terminal reached after 2^bit steps from terminal i
    # value[bit][i] stores the value obtained after 2^bit steps from terminal i
    # We use array.array for memory efficiency
    next_node = [array.array('I', P)]
    value = [array.array('I', [d % M for d in D])]
    
    # pow10[bit] stores 10^(2^bit) % M
    pow10 = array.array('Q', [0] * num_bits)
    pow10[0] = 10 % M
    
    # Binary lifting precomputation: O(N log K)
    for bit in range(num_bits - 1):
        prev_next = next_node[bit]
        prev_value = value[bit]
        p10 = pow10[bit]
        
        pow10[bit + 1] = (p10 * p10) % M
        
        # next_node[bit+1][i] = next_node[bit][next_node[bit][i]]
        # value[bit+1][i] = (value[bit][i] * 10^(2^bit) + value[bit][next_node[bit][i]]) % M
        # Using list comprehensions for faster execution in Python
        next_node.append(array.array('I', [prev_next[mid] for mid in prev_next]))
        value.append(array.array('I', [(int(v) * p10 + prev_value[mid]) % M 
                                      for v, mid in zip(prev_value, prev_next)]))
        
    results = []
    # Process each query: O(Q log K)
    for s, k in queries:
        v = 0
        u = s
        bit = 0
        # Decompose k into powers of 2 and jump through the precomputed tables
        while k:
            if k & 1:
                # Update current value: shift existing value by 2^bit places and add new part
                v = (v * pow10[bit] + value[bit][u]) % M
                # Jump to the terminal reached after 2^bit steps
                u = next_node[bit][u]
            k >>= 1
            bit += 1
        results.append(v)
        
    # Output all results at once
    sys.stdout.write('\n'.join(map(str, results)) + '\n')

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-thinking.