Cerința

Se dă un șir a de n numere naturale nenule strict mai mari decât 1, indexat de la 1. Asupra acestui șir se aplică 3 tipuri de operații:

• 1 st dr val – toate valorile a[i] cu i din intervalul [st, dr] devin egale cu val;
• 2 st dr – se cere să se afle câte elemente ale șirului a care au indicii aflați în intervalul [st, dr] sunt numere compuse(un număr natural este compus dacă are cel puțin 3 divizori);
• 3 st dr – se cere să se afișeze lungimea cele mai lungi secvențe de numere prime alcătuită exclusiv din elemente ale șirului care au indicii aflați în intervalul [st, dr](o secvență a unui șir este alcătuită din elemente aflate poziții consecutive).

Dându-se Q operații, să se raspundă în ordine la cele de tip 2 și 3.

Date de intrare

Fișierul de intrare numbers_tree.in conține pe prima linie numerele n și Q, reprezentând numărul de elemente ale șirului a, respectiv numărul de operații, pe a doua linie n numere naturale separate prin spații reprezentând elementele șirului inițial, iar pe următoarele Q linii sunt descrise operațiile.

Date de ieșire

Fișierul de ieșire numbers_tree.out va conține pe câte o linie răspunsurile la operațiile de tip 2 și 3 în ordinea în care acestea apar în fișierul de intrare.

Restricții și precizări

• 1 ≤ n, Q ≤ 100.000
• 2 ≤ a[i], val ≤ 1.000.000
• 1 ≤ st ≤ dr ≤ n

Exemplu:

numbers_tree.in

7 7
2 3 4 5 6 7 8
2 1 7
3 1 7
1 2 5 4
2 2 5
3 2 5
1 2 4 3
3 1 6

numbers_tree.out

3
2
4
0
4

Explicație

Pentru 2 1 7 răspunsul este 3, deoarece în șir există la momentul respectiv 3 numere compuse: 4 6 8
Pentru 3 1 7 răspunsul este 2, deoarece la momentul respectiv cea mai lungă secvență de numere prime din șir este 2 3.
Pentru 2 2 5 răspunsul este 4, elemenetele din acest interval(4 numere) au fost setate anterior la 4 care este număr compus. De asemenea, de aici se vede clar că răspunsul pentru 3 2 5 este 0 deoarece în acest interval de indici nu există elemente numere prime.
Pentru 3 1 6 răspunsul este 4, secevența de lungime maximă fiind 2 3 3 3.