Divop

Cerință

Divizorul magic $d(x)$ al unui număr natural nenul $x$ este egal cu:

$d(x) = \begin{cases} \text{cel mai mare divizor al lui x strict mai mic decât x}, & \text{dacă x>1} \\ 1, & \text{dacă x=1} \end{cases}$

De exemplu, $d(1)=1$, $d(3)=1$, $d(28)=14$ și $d(125)=25$.

Se dă un șir $a_1,a_2,\ldots,a_n$ pe care va trebui să efectuați $q$ operații de următorul tip:

• l r: Pentru fiecare $l \le i \le r$, $a_i$ va fi înclocuit cu $d(a_i)$.

Afișați șirul $a$ în urma celor $q$ operații.

Date de intrare

Pe prima linie a fișierului de intrare divop.in se vor afla două numere naturale $n$ și $q$ - lungimea șirului $a$, respectiv numărul de operații.

Pe a doua linie se vor afla $n$ numere $a_1,a_2,\ldots,a_n$ - elementele șirului $a$.

Pe fiecare din următoarele $q$ linii se vor afla câte două numere $l$ și $r$ - capetele operațiilor.

Date de ieșire

Fișierul de ieșire divop.out va conține $n$ numere, elementele șirului $a$ în urma efectuării celor $q$ operații.

Restricții și precizări

• $1 \le n,q \le 3 \cdot 10^5$;
• $1 \le a_i \le 10^7$;
• $1 \le l \le r \le n$;
• Pentru $10$ puncte, $n,q,a_i \le 300$;
• Pentru încă $10$ puncte, $n,q,a_i \le 1 \ 000$;
• Pentru încă $10$ puncte, $n,q,a_i \le 5 \ 000$;
• Pentru încă $10$ puncte, $n,q \le 5 \ 000$ și $a_i \le 10^5$;
• Pentru încă $10$ puncte, $n,q \le 5 \ 000$;
• Pentru încă $10$ puncte, $l=r$;
• Pentru încă $20$ de puncte, $n,a_i \le 10^5$;
• Pentru încă $10$ puncte, $a_i \le 10^5$;
• Pentru restul de $10$ puncte, nu se impun restricții suplimentare.

Exemplu

divop.in

9 4
16 9 7 20 4 1 5 12 30
1 9
4 4
8 9
1 1

divop.out

4 3 1 5 2 1 1 3 5

Explicație

După prima operație, șirul $a$ va deveni $[8,3,1,10,2,1,1,6,15]$.

După a doua operație, șirul $a$ va deveni $[8,3,1,5,2,1,1,6,15]$.

După a treia operație, șirul $a$ va deveni $[8,3,1,5,2,1,1,3,5]$.

După a patra operație, șirul $a$ va deveni $[4,3,1,5,2,1,1,3,5]$.