Calitate

$\text{Macarie}$ și-a propus ca în vacanță să facă cumpărături. În țara în care el locuiește, există $P$ bancnote cu valorile $B_1\leq B_2\leq\dots\leq B_P$, toate acestea fiind numere prime. $\text{Macarie}$ vrea să viziteze $N$ magazine, iar el a asociat fiecărui magazin $i$ valoarea $V_i$. Folosind aceste valori, se poate calcula calitatea unui produs cumpărat de la magazinul $i$ cu bancnota $j$ ca fiind indicele numărului prim $B_j$ în lista sortată crescător a factorilor primi ai numărului $V_i$. Dacă $B_j$ nu divide $V_i$, calitatea este $0$ (magazinul nu vinde produse la acest preț).
Acum $\text{Macarie}$ se întreabă "Dacă aș lua la mine bancotele cu indicii $bl, bl+1,\dots , br$ și aș vizita magazinele $l, l+1,\dots , r$, cumpărând câte un produs folosind fiecare bancnotă de la fiecare magazin, care este suma calităților produselor pe care le-aș cumpăra?".

Cerință

Se dau valorile celor $P$ bancnote din țara lui $\text{Macarie}$ și valorile asociate celor $N$ magazine pe care acesta propune să le viziteze. Determinați, pentru $Q$ întrebări de tipul $(l, r, bl, br)$, care este suma calităților produselor pe care le-ar cumpăra $\text{Macarie}$ dacă ar cumpăra câte un produs cu bancnota $j$ de la magazinul $i$, pentru fiecare $bl\leq j\leq br$ și $l\leq i\leq r$.

Date de intrare

Pe prima linie a fișierului de intrare calitate.in se vor găsi numerele întregi $P, N, Q$, cu semnificațiile din enunț. Pe a doua linie se vor găsi $P$ numere prime $B_1\leq B_2\leq\dots\leq B_P$ sortate în ordine crescătoare, valorile bancnotelor din țara lui $\text{Macarie}$. Pe a treia linie se vor găsi $N$ numere întregi $V_1, V_2,\dots , V_N$, valorile celor $N$ magazine pe care acesta le va vizita. Pe a patra linie se vor găsi numerele $l_1, r_1, bl_1, br_1$, reprezentând prima întrebare pusă de $\text{Macarie}$, și pe următoarele $4$ linii se găsesc, grupate câte $2$, numerele $X_l, Y_l, X_r, Y_r, X_{bl}, Y_{bl}, X_{br}, Y_{br}$.

$\textbf{Atenție!}$ Din cauza numărului mare de query-uri, acestea se vor genera după următoarele formule de recurență:

• $r_{i+1}=1+(X_r\cdot r_i + Y_r) \ \%\ N$
• $l_{i+1}=1+(X_l\cdot l_i + Y_l) \ \%\ r_{i+1}$
• $br_{i+1}=1+(X_{br}\cdot br_i + Y_{br}) \ \%\ P$
• $bl_{i+1}=1+(X_{bl}\cdot bl_i + Y_{bl}) \ \%\ br_{i+1}$

Date de ieșire

Fișierul de ieșire calitate.out va conține o linie pe care se vor găsi $Q$ numere întregi, al $i$-lea reprezentând răspunsul la a $i$-a întrebare a lui $\text{Macarie}$.

Restricții și precizări

• $1\leq P\leq 100$;
• $1\leq N\leq 100\ 000$;
• $1\leq Q\leq 1\ 000\ 000$;
• $1\leq B_j, V_i\leq 1\ 000\ 000$ pentru orice $1\leq j\leq P$ și orice $1\leq i\leq N$;
• $1\leq l_1\leq r_1\leq N$ și $1\leq bl_1\leq br_1\leq P$;
• $1\leq X_l, Y_l, X_r, Y_r, X_{bl}, Y_{bl}, X_{br}, Y_{br}\leq 1\ 000\ 000$;
• Se garantează că numerele $B_1, B_2,\dots , B_P$ sunt prime și sortate în ordine crescătoare.

Subtask-uri și punctare

Exemplul 1

calitate.in

4 6 4
2 3 5 7
8 15 49 35 30 70
1 6 1 1
1 1
2 5
6 3
3 4

calitate.out

3 14 2 17

Explicație

Listele factorilor primi ale valorilor magazinelor sunt:

• $8 - 2$
• $15 - 3, 5$
• $49 - 7$
• $35 - 5, 7$
• $30 - 2, 3, 5$
• $70 - 2, 5, 7$

Întrebările generate, împreună cu răspunsurile lor, sunt: