Product of Ranges

2 secs 1024 MB
powell

Product of Ranges


問題


以上の整数 と、 以上の整数 個からなる数列 が与えられる。

個のクエリ に対して、以下の式により定義される で割ったあまりを求めよ。

制約



入力


入力は以下の形式で標準入力から与えられる。

N Q
A_1 A_2 ... A_N
l_1 r_1
l_2 r_2
...
l_N r_N

入力サイズが大きいため、Pythonでは入力に以下を指定してください。

出力


個のクエリについて、 行で出力せよ。


入力例1


5 3
1 2 3 4 5
1 3
2 4
1 5

出力例1


6
24
120

個目のクエリでは を出力します。
個目のクエリでは を出力します。
個目のクエリでは を出力します。


入力例2


8 3
31415 92653 58979 32384 62643 38327 95028 84197
1 3
2 7
1 8

出力例2


741501342
924207616
583067047

あまりを取ることを忘れないようにしてください。

Submit


Go (1.14)