E - 巡回パスワード 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 466 点

問題文

高橋君の会社には、1 から N までの番号が付いた N 台の端末があります。

端末 i（1 \leq i \leq N）には 1 桁の数字 D_i（0 以上 9 以下）が表示されており、移動先の端末番号 P_i（1 \leq P_i \leq N）が設定されています。

高橋君は、指定された開始端末から出発し、次の操作をちょうど K 回繰り返します。

  1. 現在いる端末に表示された数字を記録する。
  2. 現在いる端末の番号が i であるとき、端末 P_i へ移動する。

同じ端末を複数回訪問することもあります。

K 回の操作で順に記録された数字を d_1, d_2, \ldots, d_K とすると、得られる値 V は次のように定まります。

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

これは、数字列 d_1 d_2 \ldots d_K を 10 進表記の非負整数とみなした値です（先頭が 0 であってもよい）。

K = 0 のとき（操作を一度も行わないとき）は V = 0 です。

Q 個の問い合わせが与えられます。j 番目（1 \leq j \leq Q）の問い合わせでは、開始端末の番号 S_j と操作回数 K_j が指定されます。端末 S_j から出発して操作を K_j 回行ったときに得られる V を M で割った余りを求めてください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • N + Q \leq 1.5 \times 10^5
  • 1 \leq M \leq 10^9
  • 0 \leq D_i \leq 9
  • 1 \leq P_i \leq N
  • 1 \leq S_j \leq N
  • 0 \leq K_j \leq 10^{18}
  • 入力はすべて整数である。

入力

N Q M
D_1 P_1
D_2 P_2
\vdots
D_N P_N
S_1 K_1
S_2 K_2
\vdots
S_Q K_Q
  • 1 行目には、端末の台数 N、問い合わせの個数 Q、割る数 M がスペース区切りで与えられる。
  • 続く N 行のうち i 行目には、端末 i に表示された数字 D_i と移動先の端末番号 P_i がスペース区切りで与えられる。
  • 続く Q 行のうち j 行目には、開始端末の番号 S_j と操作回数 K_j がスペース区切りで与えられる。

出力

Q 行出力せよ。

j 行目には、j 番目の問い合わせに対する答えとして、V を M で割った余りを出力せよ。

入力例 1

4 4 1000
1 2
2 3
3 4
4 2
1 3
2 5
4 4
3 0

出力例 1

123
423
234
0

入力例 2

3 5 13
0 2
5 2
9 1
1 1
1 3
3 2
2 4
3 0

出力例 2

0
3
12
4
0

入力例 3

9 8 257
6 2
2 3
0 4
7 2
5 3
1 5
9 8
3 9
4 7
1 4
1 10
6 6
5 0
7 5
8 12
9 1
3 100

出力例 3

39
58
118
0
202
176
4
110

入力例 4

20 12 999999937
8 2
1 3
4 4
1 5
5 6
9 4
2 3
6 7
0 8
3 11
7 12
8 13
2 14
4 12
9 16
5 17
0 18
1 19
3 20
6 18
1 6
1 25
9 10
10 4
10 123456789012345678
15 5
15 1000000000000000000
4 0
12 11
20 7
8 13
17 2

出力例 4

814159
175840913
624159159
3782
327335048
95013
215912785
0
482487648
6136136
591984774
1

入力例 5

1 4 1
7 1
1 0
1 1
1 10
1 1000000000000000000

出力例 5

0
0
0
0

Score : 466 pts

Problem Statement

Takahashi's company has N terminals numbered from 1 to N.

Terminal i (1 \leq i \leq N) displays a single digit D_i (between 0 and 9 inclusive) and has a destination terminal number P_i (1 \leq P_i \leq N) configured.

Takahashi starts from a specified starting terminal and repeats the following operation exactly K times.

  1. Record the digit displayed on the current terminal.
  2. If the current terminal number is i, move to terminal P_i.

The same terminal may be visited multiple times.

Let d_1, d_2, \ldots, d_K be the digits recorded in order over the K operations. The resulting value V is defined as follows:

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

This is the value obtained by interpreting the digit string d_1 d_2 \ldots d_K as a non-negative integer in base 10 (leading zeros are allowed).

When K = 0 (no operations are performed), V = 0.

You are given Q queries. In the j-th query (1 \leq j \leq Q), a starting terminal number S_j and a number of operations K_j are specified. Find the remainder when V, obtained by starting from terminal S_j and performing K_j operations, is divided by M.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • N + Q \leq 1.5 \times 10^5
  • 1 \leq M \leq 10^9
  • 0 \leq D_i \leq 9
  • 1 \leq P_i \leq N
  • 1 \leq S_j \leq N
  • 0 \leq K_j \leq 10^{18}
  • All input values are integers.

Input

N Q M
D_1 P_1
D_2 P_2
\vdots
D_N P_N
S_1 K_1
S_2 K_2
\vdots
S_Q K_Q
  • The first line contains the number of terminals N, the number of queries Q, and the divisor M, separated by spaces.
  • In the following N lines, the i-th line contains the digit D_i displayed on terminal i and the destination terminal number P_i, separated by a space.
  • In the following Q lines, the j-th line contains the starting terminal number S_j and the number of operations K_j, separated by a space.

Output

Output Q lines.

On the j-th line, output the remainder when V is divided by M as the answer to the j-th query.

Sample Input 1

4 4 1000
1 2
2 3
3 4
4 2
1 3
2 5
4 4
3 0

Sample Output 1

123
423
234
0

Sample Input 2

3 5 13
0 2
5 2
9 1
1 1
1 3
3 2
2 4
3 0

Sample Output 2

0
3
12
4
0

Sample Input 3

9 8 257
6 2
2 3
0 4
7 2
5 3
1 5
9 8
3 9
4 7
1 4
1 10
6 6
5 0
7 5
8 12
9 1
3 100

Sample Output 3

39
58
118
0
202
176
4
110

Sample Input 4

20 12 999999937
8 2
1 3
4 4
1 5
5 6
9 4
2 3
6 7
0 8
3 11
7 12
8 13
2 14
4 12
9 16
5 17
0 18
1 19
3 20
6 18
1 6
1 25
9 10
10 4
10 123456789012345678
15 5
15 1000000000000000000
4 0
12 11
20 7
8 13
17 2

Sample Output 4

814159
175840913
624159159
3782
327335048
95013
215912785
0
482487648
6136136
591984774
1

Sample Input 5

1 4 1
7 1
1 0
1 1
1 10
1 1000000000000000000

Sample Output 5

0
0
0
0