分数: 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 次。
- 记录当前终端显示的数字。
- 如果当前端子号是 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