Maricica

„Iarăși ți-e gândul la Maricica?”

Maricica este o fată silitoare și extrem de frumoasă, însă, în ciuda efortului pe care aceasta îl depune la matematică, nu reușește să ia o notă bună. De curând profesorul de matematică de la clasă le-a predat un capitol nou, intitulat divizibilitate, mai precis, cel mai mic divizor comun al unor numere date, anterior predându-le suma numerelor și îi promite că poate da un test din ambele capitole pentru a-și schimba nota, dar aceasta este deja supraaglomerată cu învățatul la celelalte materii, spre exemplu română, așa că te roagă să o ajuți în rezolvarea testului. Dacă o ajuți aceasta te va răsplăti cu o sută de puncte.

Cerință

Testul are două exerciții:

1. Dându-se $N$ și $N$ numere naturale, se cere găsirea celui mai mare divizor comun al celor $N$ numere date.
2. Dându-se $N$, $Q$, apoi $N$ numere naturale $a_1, a_2, a_3, \dots, a_N$, și $Q$ întrebări de forma $[l, r]$ unde $1 \le l \le r \le N$, se cere găsirea suma numerelor $a_l$, $a_{l+1}$, $a_{l+2}$, $\dots$, $a_r$ pentru fiecare întrebare.

Date de intrare

Pe prima linie a fișierul de intrare se va afla $C$ reprezentând numărul exercițiului.

Dacă $C = 1$ atunci pe a doua linie se va afla un număr $N$ și pe cea de-a treia linie se vor afla $N$ numere naturale.

În cazul în care $C = 2$ atunci pe a doua linie se va afla un număr $N$, pe cea de-a treia linie se vor afla $N$ numere naturale urmat pe rândul următor de $Q$ ce simbolizează numărul de întrebări urmat de încă $Q$ rânduri de forma $[l,r]$ unde $1 \le l \le r \le N$.

Date de ieșire

Dacă $C = 1$ atunci pe prima linie a fișierului de ieșire se va afla un singur număr, cel mai mare divizor comun al celor $N$ numere date, iar dacă $C = 2$ atunci se vor afișa, pe rânduri diferite, răspunsul la cele $Q$ întrebări.

Restricții și precizări

• $1 \le N \le 100\ 000$
• $0 \le a_i \le 10^9$
• $1 \le Q \le 10\ 000$
• Prima cerință valorează $30$ de puncte.
• A doua cerință valorează $70$ de puncte.
• Pentru teste în valoare de $5$ puncte, $0 \le a_i \le 10^5$ și $C = 1$.
• Pentru teste în valoare de $20$ de puncte, $1 \le N \le 1\ 000$ și $C = 2$.
• Pentru teste în valoare de $70$ de puncte, $0 \le a_i \le 10^5$ și $C = 2$.

Exemplul 1

maricica.in

1
5
2 4 10 6 8

maricica.out

2

Exemplul 2

maricica.in

2
5
2 4 10 6 8
3
2 4
1 5
3 5

maricica.out

20
30
24