D - 工場の生産量 解説 /

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

配点 : 400 点

問題文

高橋君は N 個の工場を管理しています。各工場 i（1 \leq i \leq N）には生産効率を表す正整数 P_i が設定されています。

N 個の工場全体の総合生産量は、すべての工場の生産効率の積 P_1 \times P_2 \times \cdots \times P_N を素数 M で割った余りで評価されます。

高橋君は Q 個のシミュレーションを行いたいと考えています。j 番目（1 \leq j \leq Q）のシミュレーションでは、工場 X_j の生産効率のみを非負整数 V_j に変更し、他の工場の生産効率は元のままとしたときの総合生産量を求めます。すなわち、

P_1 \times \cdots \times P_{X_j - 1} \times V_j \times P_{X_j + 1} \times \cdots \times P_N

を M で割った余りを求めてください。

各シミュレーションは独立です。あるシミュレーションでの変更は他のシミュレーションには影響せず、毎回元の生産効率 P_1, P_2, \ldots, P_N から出発します。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 2 \leq M \leq 10^9
  • M は素数
  • 1 \leq P_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq X_j \leq N (1 \leq j \leq Q)
  • 0 \leq V_j \leq 10^9 (1 \leq j \leq Q)
  • 入力はすべて整数

入力

N Q M
P_1 P_2 \ldots P_N
X_1 V_1
X_2 V_2
\vdots
X_Q V_Q
  • 1 行目には、工場の個数 N、シミュレーションの回数 Q、素数 M がスペース区切りで与えられる。
  • 2 行目には、各工場の初期生産効率 P_1, P_2, \ldots, P_N がスペース区切りで与えられる。
  • 続く Q 行のうち j 行目（1 \leq j \leq Q）には、変更対象の工場の番号 X_j と変更後の生産効率 V_j がスペース区切りで与えられる。

出力

Q 行出力せよ。j 行目（1 \leq j \leq Q）には、j 番目のシミュレーションに対する答え、すなわち工場 X_j の生産効率を V_j に置き換えたときの全工場の生産効率の積を M で割った余りを出力せよ。

入力例 1

3 4 7
2 3 4
1 5
2 0
3 6
2 3

出力例 1

4
0
1
3

入力例 2

4 5 5
1 5 2 3
2 4
1 7
3 10
4 0
2 5

出力例 2

4
0
0
0
0

入力例 3

10 10 17
3 8 17 5 21 1 34 9 2 11
3 4
7 6
1 0
5 100
10 17
2 19
8 8
4 12
6 13
9 51

出力例 3

0
0
0
0
0
0
0
0
0
0

入力例 4

30 25 998244353
123456789 987654321 111111111 222222222 333333333 444444444 555555555 666666666 777777777 888888888 999999999 998244353 1 2 3 4 5 6 7 8 9 10 314159265 271828182 161803398 42 1000000000 999999937 12345 54321
12 7
1 1000000000
30 0
27 998244353
13 123456789
20 876543210
5 5
18 18
22 22
24 314159265
2 1
11 999999999
14 0
25 271828182
28 999999937
3 333333333
7 777777777
16 4
26 42
29 12345
10 888888888
4 222222222
19 7
21 9
6 444444444

出力例 4

643945267
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

入力例 5

1 1 2
1000000000
1 0

出力例 5

0

Score : 400 pts

Problem Statement

Takahashi manages N factories. Each factory i (1 \leq i \leq N) has a positive integer P_i representing its production efficiency.

The total production of all N factories is evaluated as the product of the production efficiencies of all factories P_1 \times P_2 \times \cdots \times P_N taken modulo a prime number M.

Takahashi wants to perform Q simulations. In the j-th simulation (1 \leq j \leq Q), only the production efficiency of factory X_j is changed to a non-negative integer V_j, while the production efficiencies of all other factories remain unchanged. That is, find

P_1 \times \cdots \times P_{X_j - 1} \times V_j \times P_{X_j + 1} \times \cdots \times P_N

modulo M.

Each simulation is independent. Changes made in one simulation do not affect other simulations; each simulation starts from the original production efficiencies P_1, P_2, \ldots, P_N.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 2 \leq M \leq 10^9
  • M is a prime number
  • 1 \leq P_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq X_j \leq N (1 \leq j \leq Q)
  • 0 \leq V_j \leq 10^9 (1 \leq j \leq Q)
  • All inputs are integers

Input

N Q M
P_1 P_2 \ldots P_N
X_1 V_1
X_2 V_2
\vdots
X_Q V_Q
  • The first line contains the number of factories N, the number of simulations Q, and the prime number M, separated by spaces.
  • The second line contains the initial production efficiencies P_1, P_2, \ldots, P_N of each factory, separated by spaces.
  • The j-th line (1 \leq j \leq Q) of the following Q lines contains the index of the factory to be changed X_j and the new production efficiency V_j, separated by spaces.

Output

Output Q lines. The j-th line (1 \leq j \leq Q) should contain the answer to the j-th simulation, that is, the remainder when the product of all factories' production efficiencies, with factory X_j's efficiency replaced by V_j, is divided by M.

Sample Input 1

3 4 7
2 3 4
1 5
2 0
3 6
2 3

Sample Output 1

4
0
1
3

Sample Input 2

4 5 5
1 5 2 3
2 4
1 7
3 10
4 0
2 5

Sample Output 2

4
0
0
0
0

Sample Input 3

10 10 17
3 8 17 5 21 1 34 9 2 11
3 4
7 6
1 0
5 100
10 17
2 19
8 8
4 12
6 13
9 51

Sample Output 3

0
0
0
0
0
0
0
0
0
0

Sample Input 4

30 25 998244353
123456789 987654321 111111111 222222222 333333333 444444444 555555555 666666666 777777777 888888888 999999999 998244353 1 2 3 4 5 6 7 8 9 10 314159265 271828182 161803398 42 1000000000 999999937 12345 54321
12 7
1 1000000000
30 0
27 998244353
13 123456789
20 876543210
5 5
18 18
22 22
24 314159265
2 1
11 999999999
14 0
25 271828182
28 999999937
3 333333333
7 777777777
16 4
26 42
29 12345
10 888888888
4 222222222
19 7
21 9
6 444444444

Sample Output 4

643945267
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

Sample Input 5

1 1 2
1000000000
1 0

Sample Output 5

0