Задача – 103Г
Както знаете, най-интелигентните същества на планетата Земя са, разбира се, кравите. Марсиански извънземни, както и редица други интелигентни цивилизации от дълбокия космос, отдавна са стигнали до това заключение.
Понякога кравите се събират в коровани. Май е сезонно. Но точно по това време кравите стават пасивни и реагират слабо на външни стимули. Korowan е идеалната мишена за марсианска изследователска чиния, време е за мащабни отвличания или, както казват марсианците, грабежи. С прости думи, короуан е набор от крави, подредени в редица.
Ако изброим всички крави в korowan с естествени числа от 1 доn, тогава можем да формализираме популярен модел на отвличане, известен като (a,b) - грабеж на korowan: първо се отвлича крава с номерa, след това с числоa+b, след това с числоa+ 2·bи така нататък, докато броят на отвлечената крава стане по-голям отn. В хода на един обир кравите не се преномерират.
Извънземните биха се радвали да настанят всички крави на борда на своя гостоприемен кораб, но, за съжаление, размерът на товарното отделение е много, много ограничен. Изследователите, знаейки масата на всяка крава в фургона, съставихаpсценарии (a,b) - грабеж. Сега те искат да определят за всеки сценарий поотделно каква е общата маса на чистото говеждо месо, което ще попадне на борда на кораба. Всички сценарии са независими, кравите не се отвличат в процеса на извършване на изчисления.
Първият ред съдържа едно естествено числоn— броят на кравите във фургон ( 1 ≤n≤ 3 10 5 ).
Вторият ред съдържаnестествени числаwi, разделени с интервали, къдетоiе числотоопределя масата наi-тата крава в фургона ( 1 ≤wi≤ 10 9 ).
Третият ред съдържа едно естествено числоp— броят на (a,b)-сценарии за грабеж ( 1 ≤p≤ 3 10 5 ).
Всеки следващ ред съдържа параметритеaиbна следващия сценарий ( 1 ≤a,b≤n).
За всеки (a,b) сценарий на грабеж отпечатайте общата маса крави, които могат да бъдат откраднати в резултат на грабеж според този сценарий.
Моля, не използвайте спецификатора %lld за четене или запис на 64-битови числа в C++. Препоръчителните потоци са cin, cout или спецификаторът %I64d.