D. Ковавансад дайралт хийсэн нь

хугацааны хязгаарлалт 4 секунд

санах ойн хязгаарлалт 70 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Мэдээж дэлхий дээр байгаа хамгийн ухаантай амьтан бол үхэр юм. Энэхүү дүгнэлтийг өөр нэгэн оюун ухаант иргэншилтэй харь гаригийнхан хийсэн юм.

Заримдаа үхэрнүүд ковавансд цуглардаг. Энэ нь ямар нэг шалтгаантай байдаг байх. Яг энэ үед үхрүүд идэвхгүй болж хариу үйлдэл үзүүлж чадахаа байдаг байна. Коваванс бол харь гаригийнханд үхэрнүүдийг олзлож авахад хамгийн тохиромжтой газар болж байгаа юм. Ингэхийн тулд ямартай ч үхэрнүүдийг нэг эгнээнд эгнүүлэн жагсаана.

Үхэрнүүдийг $1$-ээс $n$ хүртэл дугаарлая. Харь гаригийнхан Кованан дайралт - $(a, b)$ ашиглана : Эхлээд $a$ дугаартай үхэрийг, дараа нь $a + b$, дараа нь $a + 2*b$, гэх мэтчилэн олзлолт хийнэ. Олзлолтын үеэр үхэрнүүд шинээр дугаарлагддаггүй.

Харь гаригийнхан бүх үхрүүдийг сансрын хөлөгтөө багтааж байвал баярлана. Гэхдээ хөлгийн дотор зай нь маш хязгаарлагдмал. Тэгвэл тэд танид $p$ ширхэг $(a, b)$-олзлолтын мэдээлэл өгсөн ба олзлолт тус бүрийн хувьд олзлогдох үхрүүдийн жингийн нийлбэрийг тоооцоолуулахыг хүссэн юм. Олзлолт бүр харилцан хамааралгүй бөгөөд тооцоолол бүрд ямар нэгэн үнээ олзлогдохгүй.

Оролт

Эхний мөрд $n$ ($1 ≤ n ≤ 3*10^{5}$) бүхэл тоо - Коваванд байгаа үхрийн тоо.

Хоёрдугаар мөрөнд $n$ бүхэл тоо $w_{i}$, $i$-р тоо нь $i$-р үхрийн жин ($1 ≤ w_{i} ≤ 10^{9}$).

Гуравдугаар мөрөнд $p$ - $(a, b)$ - олзлолтын тооцооллын тоо ($1 ≤ p ≤ 3*10^{5}$).

Дараагийн $p$ мөрөнд харгалзан $a$ болон $b$ параметрүүд байна ($1 ≤ a, b ≤ n$).

Гаралт

Харгалзан бүх $(a, b)$ - олзлолтын хувьд нийт олзлогдох үхрүүдийн жингийн нийлбэрийг хэвлэ.

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d эсвэл cin, cout стриймийг ашиглана уу.

Орчуулсан: Б.Алтангэрэл

Жишээ тэстүүд

Оролт
3
1 2 3
2
1 1
1 2
Гаралт
6
4
Оролт
4
2 3 5 7
3
1 3
2 3
2 2
Гаралт
9
3
10
Сэтгэгдлүүдийг ачааллаж байна...