← 返回题目列表

AtCoder · awc0060_e

E. 循环密码

中文机器翻译题面 查看原题

分数: 466 分

问题陈述

高桥的公司有 N 端子编号自 1 to N.

终端 i (1 \leq i \leq N) 显示一位数字 D_i (之间 0 和 9 包括在内)并具有目的地终端号码 P_i (1 \leq P_i \leq N)已配置。

Takahashi从指定的起始终端开始,准确地重复以下操作 K 次。

  1. 记录当前终端显示的数字。
  2. 如果当前端子号是 i,移动到终端 P_i.

同一终端可能被多次访问。

让 d_1, d_2, \ldots, d_K 是按顺序记录的数字 K 操作。结果值 V 定义如下:

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

这是通过解释数字字符串得到的值 d_1 d_2 \ldots d_K 作为基数的非负整数 10 (允许使用前导零)。

当 K = 0 (不执行任何操作), V = 0.

你被给予 Q 查询。在 j- 第一个查询 (1 \leq j \leq Q), 起始终端号 S_j 以及一些操作 已指定 K_j 。求余数,当 V,从终端启动获得 S_j 并表演 K_j 运算,除以 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
  • 第一行包含终端数量 N, 查询次数 Q,和除数 M,用空格分隔。
  • 如下 N 行, i-第行包含数字 终端显示 D_i 显示在终端上 i 和目的地终端号码 P_i,用空格分隔。
  • 如下 Q 行, j-第行包含起始端子号 S_j 和操作次数 K_j,用空格分隔。

输出

输出 Q 行。

关于 j第行,输出当 V 除以 M 作为答案 j第一个查询。


示例输入 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