0719 - 魔女っ娘ヒナくるん -Magic.01

Magic.01 『Miracle and Hinacle!!』

---幻想郷。
呆れかえるほどの平和が人々を支配していた。
この日、幻想郷一の幸せ者、ヒナはいつものように花畑を散歩していた。

ヒナ
「平和ねぇ・・・
益ばっかり溜まっていって、こんなのでいいのかしら・・・」
？？？
「さて、始めましょうか。」

空が、薄緑に染まる。
空間が、歪む。
世界が溶け、
ノイズが走り、
美しく花々が散る。
まるで、奇跡でも起こったかのように。
そして---

ヒナ
「・・・今のは？」
？？？
「あら、こんなところにいると危険ですわよ。」
ヒナ
「・・・あなたは？」
？？？
「私はコティーヤ。
この世界を統べる者。
私は奇跡に愛された。
あなた、私と一緒に世界を支配するつもりはない？」
ヒナ
「そんなのお断りよ！！
私は、今の平和で過ごしていたいの！！
あなたは今、ここで私が止める！！」
コティーヤ
「・・・面白いわね。
止めれるものなら、やってご覧なさい！！」
ヒナ
「お望み通り！！
奇跡なんてもの、私の前では無意味だと教えてあげるわ！！」

問題

物語は、ここから動き出す。
幻想郷の少女、ヒナとコティーヤの戦い。
ヒナはいくつかの攻撃方法を持っている。
各攻撃には番号が振られており、
ヒナが攻撃を行う際には、
連続した番号の攻撃しか同時に行うことが出来ない。
ヒナは、コティーヤに何回か攻撃を行おうとしている。
ヒナの攻撃方法と、各攻撃方法のダメージ、
攻撃を行う回数と、その時に攻撃する攻撃方法が与えられるので、
各攻撃毎に、コティーヤにどれだけのダメージを与えられるかを出力せよ。

君が、この物語を導くのだ。

入出力形式

一行目に、ヒナの攻撃方法の数 N が与えられる。
二行目に、i番目の攻撃で与えることが出来るダメージ P_i が空白区切りで与えられる。
三行目に、ヒナが攻撃を見積もりたい回数 M が与えられる。
以下M行に渡って、選んだ攻撃方法の範囲 a_i と b_i が与えられるので、
この入力毎に敵に与えることが出来るダメージを一行に出力せよ。
出力の最後の改行を忘れないこと。

制約

• 1 ≦ N,M ≦ 100000
• 0 ≦ P_i ≦ 100

部分点

配点の 20% は、 N,M ≦ 100 を満たす。

入出力例

入力例一

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

出力例一

12
8
2

一つ目のデータでは、二番目から四番目までの攻撃によるダメージの和を求めるので、
4+3+5 = 12 である。
二つ目のデータでは、三番目から四番目までの攻撃によるダメージの和を求めるので、
3+5 = 8 である。
三つ目のデータでは、一番目から一番目までの攻撃によるダメージの和を求めるので、
2 = 2 である。

入力例二

6
100 200 100 100 14 75
3
4 5
1 5
5 6

出力例二

114
514
89