benzi

Proprietarul unui renumit club de informatică din Slatina dorește să introducă niște brățări formate din mai multe culori (pe care el le consideră numere ı̂ntregi) pe care le va confecțona dintr-o fâșie de cauciuc multicoloră. Cum el a consumat prea mult lapte ı̂n urma ultimului eveniment organizat la Manuel Shaorma, vă roagă să-l ajutați cu confecționarea brățărilor.

Se consideră un șir $a$ cu $N$ elemente, indexat de la $1$. Vom numi o bandă o secvență maximală $[l, r]$ cu toate elementeleegale, adică $a_l = a_{l+1} = … = a_r$.

Asupra acestui șir se vor efectua două operații:

1. $1$ $L$ $R$ – Se cere să se afle numărul de benzi și lungimea maximă a unei benzi considerând doar elementele din intervalul $[L, R]$. Subsecvența considerată va fi privită ca fiind circulară, adică $a_l$ și $a_r$ vor fi considerați vecini.
2. $2$ $L$ $R$ $M$ $B1$ $B2 . . . BM$ – Elementele șirului de la $L$ la $R$ vor lua valori conform patternului $B$ de lungime $M$. Atunci când subsecvența pe care trebuie să o umplem este mai lung ca patternul, patternul se va repeta (ultima repetare nu va fi neapărat completă). Spre exemplu, $2$ $3$ $10$ $3$ $1$ $2$ $2$ ı̂nseamnă că valorile șirului de la $3$ la $10$ vor fi: $1$, $2$, $2$, $1$, $2$,
   $2$, $1$, $2$.

În total, se vor efectua $Q$ astfel de operații asupra lui $a$.

Cerință

Mai ı̂ntâi, se cere să aflați numărul de benzi și lungimea maximă a unei benzi pentru șirul inițial. Apoi, aflați răspunsul
pentru fiecare operație de tip $1$. La finalul tuturor operațiilor, se cere să se afișeze toate elementele șirului.

Date de intrare

Pe prima linie se află numerele $N$ și $Q$ cu semnificația din enunț. Apoi, pe a doua linie se află valorile inițiale ale șirului. Următoarele $Q$ linii conțin operațiile ce respectă formatul de mai sus.

Date de ieșire

Pe prima linie se va afișa răspunsul pentru șirul inițial, două numere reprezentând numărul de benzi și lungimea maximă a unei benzi. Apoi, se vor afișa numărul de benzi și lungimea maximă a unei benzi pentru fiecare operație de tip $1$. Pe
ultima linie se vor afișa elementele șirului după toate operațiile.

Restricții și precizări

• $1 \leq N \leq 250 000$
• $1 \leq Q \leq 100 000$
• Pentru fiecare operație vom avea $1 \leq L \leq R \leq N$ și $1 \leq M \leq N$
• $0 \leq$ Suma $M$-urilor pentru toate operațiile $\leq 250 000$
• $1 \leq a_i, B_i \leq 10^9$
• Pentru $7$ puncte: $N, Q \leq 5000$ pentru toate operațiile
• Pentru $9$ puncte: Operațiile sunt doar de tipul $1$
• Pentru $5$ puncte: Suma valorilor $R − L$ pentru toate operațiile de tip $2 \leq 200000$
• Pentru $10$ puncte: $M = 1$ pentru toate operațiile
• Pentru $11$ puncte: Suma $M$-urilor pentru toate operațiile $\leq 5000$
• Pentru $27$ de puncte: $N, Q \leq 75 000$ și suma $M$-urilor pentru toate operațiile $\leq 50 000$
• Pentru $31$ de puncte: Fără alte restricții

Exemple

Intrare

12 9
1 1 2 3 2 1 2 2 2 3 1 1
1 1 11
1 3 9
2 6 6 1 2
1 3 9
1 1 11
2 4 10 4 2 2 1 1
1 1 12
1 3 9
1 1 11

Ieșire

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

Explicație

Inițial avem 7 benzi: $11..11$, $2$, $3$, $2$, $1$, $222$, $3$, cu lungimeaa maximă 4.
Pentru prima operație avem tot 7 benzi ca mai sus, numai că prima va fi $11..1$ în loc de $11..11$, deci lungimea maximă este 3.
Pentru a doua operație avem 4 benzi: $22..22$, $3$, $2$, $1$, cu lungimeaa maximă 4.
După a treia operație șirul va deveni $1, 1, 2, 3, 2, 2, 2, 2, 2, 3, 1, 1$.
Pentru a patra operație avem 2 benzi: $2..22222$ și $3$, cu lungimea maximă 6.
Pentru a cincea operație avem 5 benzi: $11..11$, $2$, $3$, $22222$, $3$, cu lungimea maximă 5.