În clasa lui Ionuț sunt N elevi numerotați cu numere naturale de la 1 la N așezați în ordinea din catalog. Fiecare elev i (1 ≤ i ≤ N ) are ceea ce se numește un coeficient de popularitate \(A_i\) , un număr natural nenul. Fiecare elev din clasă are un grup de simpatizanți. Grupul de simpatizanți ai elevului i, notat cu \(G_i\) este reprezentat de cea mai lungă secvență de elevi din șirul dat în catalog, care îl conține pe elevul i, astfel încât coeficientul de popularitate al fiecărui elev j din secvență, \(A_j\) , să fie divizor al lui \(A_i\) . Lungimea secvenței, deci numărul elevilor din grupul de simpatizanți ai lui i, se notează cu \(|G_𝑖|\). Evident, elevul i face parte din propriul său grup de simpatizanți. Dacă elevul i face parte din grupul de simpatizanți ai elevului j, atunci nu este neapărat necesar ca și j să facă parte din grupul de simpatizanți ai elevului i.

După ore, unii elevi își invită la cofetărie grupul de simpatizanți, pentru câte o înghețată. Pentru un grup de simpatizanți \(G_i\) , elevul i merge și îi cere vânzătoarei exact \(|G_i|\) înghețate, dar vânzătoarea are o fire năstrușnică și îi spune că este disponibil doar un anumit număr de arome k, mereu cel mult egal cu numărul de înghețate cerute (\(1 ≤ 𝑘 ≤ |G_𝑖|\)). Elevii, creativi, calculează numărul de moduri în care se poate cumpăra înghețată pentru grup, astfel încât să achiziționeze fiecare sortiment cel puțin o dată; pentru grupul \(G_i\) , acest număr se notează cu \(v_i(k)\).

Cerința

1. Determinați numărul de ordine din catalog al elevului care are cel mai numeros grup de simpatizanți. Se garantează că există un singur astfel de elev.
2. Lui Ionuț îi place foarte mult să analizeze vânzările magazinelor de înghețată și vă lansează Q întrebări de tipul: (i, st, dr) (cu \(1 ≤ i ≤ N\) și \(1 ≤ st ≤ dr ≤ |G_i|\)); pentru fiecare determinați valoarea expresiei: \(v_i(st) + v_i(st + 1) + \cdots + v_i(dr)\); cum valoarea poate fi foarte mare, luați în considerare restul împărțirii ei la \(10^9 + 7\).

Date de intrare

Fișierul de intrare inghetata.in conține pe prima linie un număr natural C, care indică cerința ce trebuie rezolvată (C=1 sau C=2), pe a doua linie numărul N, reprezentând numărul de elevi din clasa lui Ionuț, iar pe următoarea linie se găsesc N numere naturale \(A_1\), \(A_2\), . . . , \(A_N\) , reprezentând coeficienții de popularitate ai colegilor lui Ionuț. Dacă C=2, în continuarea datelor precizate, începând cu următoarea linie, fișierul conține Q, numărul de întrebări, iar pe următoarele Q linii câte 3 numere naturale i st dr cu semnificația din enunț. Numerele de pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire

Dacă C=1, atunci fișierul de ieșire inghetata.out va conține, pe o singură linie numărul determinat la cerința 1.
Dacă C=2, atunci fișierul de ieșire inghetata.out va conține cele Q valori determinate la cerința 2, fiecare număr pe câte o linie a fișierului în ordinea întrebărilor corespunzătoare.

Restricții și precizări

• 1 ≤ N ≤ 200 000;
• \(1 ≤ 𝐴_𝑖 ≤ 10^9\) pentru orice i = 1, ..., N ;
• 1 ≤ Q ≤ 200 000;
• 0 ≤ dr − st ≤ 60 pentru fiecare din cele Q întrebări.
• Datorită dimensiunilor mari, nu au fost adăugate toate testele folosite în concurs.

Subtaskuri

1. pentru 60 de puncte: C = 1 și 1 ≤ N ≤ 1 000
2. pentru 4 puncte: C = 2 și 1 ≤ N ≤ 500 și 1 ≤ Q ≤ 500
3. pentru 4 puncte: C = 2 și 1 ≤ N ≤ 2 000 și 1 ≤ Q ≤ 2 000 și st = dr pentru fiecare dintre cele Q întrebări
4. pentru 3 puncte: C = 2 și \(A_1 = A_2 = … = A_N\)
5. pentru 9 puncte: C = 2 și \(A_i\) este putere a lui 2 pentru orice i = 1, 2, ... , N
6. pentru 3 puncte: C = 2 și \(1 ≤ st ≤ dr ≤ min(2, |G_i|)\) pentru fiecare din cele Q întrebări
7. pentru 4 puncte: C = 2 și \(max(1, |G_i| − 1) ≤ st ≤ dr ≤ |G_i|\) pentru fiecare din cele Q întrebări
8. pentru 13 puncte: C = 2

Exemplul 1

inghetata.in

1
5
1 9 3 3 1

inghetata.out

2

Exemplul 2

inghetata.in

2
10
1 2 2 4 4 8 8 3 1 3
2
10 1 2
4 3 3

inghetata.out

3
6

Explicație

Pentru primul exemplu, C=1, deci se rezolvă prima cerință. \(G_1=\left\{1\right\}\) (în stânga nu mai sunt elevi, iar în dreapta 9 nu este divizor al lui 1), \(G_2=\left\{1,2,3,4,5\right\}\) (toate numerele din șir sunt divizori ai lui 9, deci grupul de simpatizanți ai lui 2 este format din toți elevii), \(G_3=\{3,4,5\}\)(în stânga, 9 nu este divizor al lui 3, iar în dreapta 3 și 1 sunt divizori ai lui 3), \(G_4=\{3,4,5\}\)(în stânga, 3 este divizor al lui 3, dar 9 nu este divizor al lui 3, iar în dreapta 1 este divizor al lui 3), \(G_5=\{5\}\) (în stânga 3 nu este divizor al lui 1, iar în dreapta nu mai sunt elevi) . Așadar numărul de ordine al elevului cu cel mai numeros grup de simpatizanți este 2.

Pentru al doilea exemplu, C=2, deci se rezolvă a doua cerință. Pentru prima întrebare \(G_{10} = \left\{8, 9, 10\right\}\) și se calculează \(v_{10}(1) + v_{10}(2)\). Dacă vânzătoarea le spune că la magazin se vinde o singură aromă (k = 1), atunci este un singur mod de a face cumpărături, anume aceeași aromă pentru toate înghețatele achiziționate. Dacă se vând două arome (k = 2), de exemplu ciocolată și vanilie, atunci sunt două posibilități: prima variantă cu una de ciocolată și două de vanilie și a doua variantă cu două de ciocolată și una de vanilie. Deci \(v_{10}(1) = 1\), \(v_{10}(2) = 2\) și \(v_{10}(1) + v_{10}(2) = 3\). Pentru a doua întrebare \(D_4 = \left\{1, 2, 3, 4, 5\right\}\). Dacă vânzătoarea le spune că se vând trei arome (k = 3), de exemplu ciocolată, vanilie și mentă, sunt 6 posibilități, deci \(v_4(3) = 6\):

1. una de ciocolată, una de vanilie, trei de mentă;
2. una de ciocolată, două de vanilie, două de mentă;
3. una de ciocolată, trei de vanilie, una de mentă;
4. două de ciocolată, una de vanilie, două de mentă;
5. două de ciocolată, două de vanilie, una de mentă;
6. trei de ciocolată, una de vanilie, una de mentă.