Cerință
Divizorul magic d(x) al unui număr natural nenul x este egal cu:
d(x)={cel mai mare divizor al lui x strict mai mic decaˆt x,1,daca˘ x>1daca˘ x=1
De exemplu, d(1)=1, d(3)=1, d(28)=14 și d(125)=25.
Se dă un șir a1,a2,…,an pe care va trebui să efectuați q operații de următorul tip:
l r
: Pentru fiecare l≤i≤r, ai va fi înclocuit cu d(ai).
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 a1,a2,…,an - 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≤n,q≤3⋅105;
- 1≤ai≤107;
- 1≤l≤r≤n;
- Pentru 10 puncte, n,q,ai≤300;
- Pentru încă 10 puncte, n,q,ai≤1 000;
- Pentru încă 10 puncte, n,q,ai≤5 000;
- Pentru încă 10 puncte, n,q≤5 000 și ai≤105;
- Pentru încă 10 puncte, n,q≤5 000;
- Pentru încă 10 puncte, l=r;
- Pentru încă 20 de puncte, n,ai≤105;
- Pentru încă 10 puncte, ai≤105;
- 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].