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ționa 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 $\textit{a}$ cu $\textit{N}$ elemente, indexat de la 1. Vom numi o $\textit{bandă}$ o secvență maximală $[l, r]$ cu toate elementele egale, adică $a_l=a_{l+1}=...=a_{r}$.

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

• $\text{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.
• $\text{2} \ L \ R \ M \ B_1 \ B_2 \ldots B_M$ - Elementele șirului de la $L$ la $R$ vor lua valori conform patternului $\textit{B}$ de lungime $\textit{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 $\textit{Q}$ astfel de operații asupra lui $\textit{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 $\textit{N}$ și $\textit{Q}$ cu semnificația din enunț.
Apoi, pe a doua linie se află valorile inițiale ale șirului.
Următoarele $\textit{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 200 \ 000$
• Pentru fiecare operație vom avea $1\le L \le R \le N$ și $1 \le M \le N$
• $0 \leq \text{ Suma \textit{M}-urilor pentru toate operațiile} \leq 250 \ 000$
• $1 \leq a_i, B_i \leq 10^9$

Subtask 1 (7 puncte)

• $N, Q \leq 5 \ 000$ pentru toate operațiile

Subtask 2 (9 puncte)

• Operațiile sunt doar de tipul 1

Subtask 3 (5 puncte)

• Suma valorilor $R - L$ pentru toate operațiile de tip 2 $\le 200 \ 000$

Subtask 4 (10 puncte)

• $M = 1$ pentru toate operațiile

Subtask 5 (11 puncte)

• $\text{ Suma \textit{M}-urilor pentru toate operațiile} \leq 5 \ 000$

Subtask 6 (27 puncte)

• $N, Q \le 75 \ 000 \text{ și suma \textit{M}-urilor pentru toate operațiile} \leq 50 \ 000$

Subtask 7 (31 puncte)

• Fără alte restricții

Exemplu

stdin

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

stdout

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ții

Inițial avem 7 benzi: $11..11$, $2$, $3$, $2$, $1$, $222$, $3$, cu lungimea 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 lungimea 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.