• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• منبع: آزمون عملی دوره ۲۰ المپیاد کامپیوتر

به شما یک آرایه $A_1, A_2, ..., A_n$ داده شده است. مطلوب است محاسبه‌ی مقدار عبارت زیر به ازای تعدادی دوتایی $s$ و $k$ مختلف.

$$\sum_{i=0}^{\lfloor \frac{n-s}{k} \rfloor} A_{i \times k+s} = A_{s} + A_{s + k} + A_{s + 2k}+\dots$$

ورودی

در سطر اوّل ورودی عدد $n$ می‌آید.

در سطر دوم $n$ عدد می‌آید که عدد $i$ام برابر $A_i$ است.

در سطر سوم عدد $Q$ به تنهایی می‌آید که برابر تعداد دوتایی‌های $s$ و $k$ است که در ادامه داده خواهند شد.

در هر یک از $Q$ سطر بعد دو عدد خواهد آمد. عدد اوّل $s$ و عدد دوم $k$ است.

تمام اعداد آرایه، طبیعی و کم‌تر از $10^9$ هستند.

$$1 \leq n, Q \leq 100\ 000$$

خروجی

خروجی دارای $Q$ خط است. در $i$امین خط باید مقدار عبارت مذکور را به ازای درخواست $i$ام چاپ کنید.

زیرمسئله‌ها

مثال

ورودی نمونه

6
11 3 15 8 5 1
4
1 2
5 1
2 4
3 1

خروجی نمونه

31
6
4
29