数の切り取り



問題文

今ここに10進数字列 a がある。 a の区間を10進数で数値として見ることを考える。
例えば a = "0123456789"とすると、

  • 区間[1, 4)の数値は123である。
  • 区間[0, 8)の数値は1234567である(leading zeroは許可される)。

整数 m と、クエリが Q 個与えられる。 各クエリでは li, ri が与えられる。
各クエリに対して、 a の区間[ li, ri )を10進数で数値としてみたものを m で割った余りを出力せよ。


入力

入力は以下の形式で与えられる:
a
Q m
l0 r0
l1 r1
:
lQ-1 rQ-1
  • 1行目に、'0'から'9'の数字からなる文字列 a (1 ≦ a の長さ ≦ 1000000) が与えられる。
  • 2行目に、クエリの数を表す整数 Q (0 ≦ Q ≦ 1000000) と、クエリで剰余を取る数を表す整数 m (2 ≦ m ≦ 1000000007) が与えられる。
  • 続く Q 行は各クエリの入力を表している。 このうちの (i + 1)行目 (0 ≦ iQ) にはクエリ i の区間を表す2つの整数 li, ri (0 < liria の長さ) が空白区切りで書かれている。

出力

  • Q 行、各クエリ i ごとに、a の区間[ li, ri )を数値としてみたものを m で割った余りを出力せよ。

入力例0

0123456789
3 10000000
1 4
0 8
1 10

出力例0

123
1234567
3456789
  • a の区間[1, 4)は"123"であって、それを 10000000 で割った余りも123である。
  • a の区間[0, 8)は"01234567"である。文字列にリーディングゼロがあってもそれを無視することに注意せよ。
  • a の区間[1, 10)は"123456789"である。これを 10000000 で割った余りは 3456789 になる。

入力のダウンロードと提出

入力をダウンロード
大きな入力ファイルのダウンロードはサーバーに負荷をかけるので、1回だけにしてください。

テストケース
No. 設定得点 自分の状態 投稿日時
合計 150
0 25
1 25
2 100

テストケースごとの出力にそれぞれ"[testcase].out"(例: 0.out, 7.out, 12.out)という名前にしてください。 一部のテストケースみで提出することもできます。 ファイルは(windowsの場合選択画面でCtrl+クリックをすれば)複数選択できるはずです。

この問題のジャッジ: ローカルでパースされてハッシュが送られます。 出力文字列は空白・改行で区切られます。 その際の余分な空白・改行は無視されます。