culori

Am o prietenă creatoare de modă. Pentru a-și realiza creațiile ea vopsește uneori materialele și mă roagă în prealabil să o ajut. Azi vrea să vopsească o pânză cu lungimea $N$ cm folosind $C$ nuanțe ale aceleiași culori, codificate de la $1$ la $C$. Fiecare cm de pânză fiind colorat cu aceeași nuanță pe toată lățimea, va ieși o pânză în dungi. Inițial eu simulez cu ajutorul calculatorului vopsirea materialului, prietena mea începe apoi să intervină: de la cm $A$ la cm $B$, trebuie modificată intensitatea culorii cu $X$ puncte (intensitatea poate crește sau poate scădea, obținându-se astfel o altă nuanță). După nenumărate modificări de acest tip, să spunem $M$ modificări, prietena mea va fi mulțumită și va trece la vopsirea efectivă a pânzei.

Cerinţă

Scrieţi un program care determină și afișează:

1. Lungimea maximă a unei bucăți de pânză de aceeași culoare după vopsirea inițială;
2. Cum va arăta pânza în urma modificărilor prietenei mele.

Date de intrare

Fișierul de intrare culori.in conține pe prima linie cerința ($1$ sau $2$). Linia următoare conține trei numere naturale $C \ N \ M$ separate prin câte un spațiu, reprezentând numărul de culori, lungimea în cm a pânzei, respectiv numărul de modificări efectuate de prietena mea; următoarea linie conține $N$ numere naturale separate prin câte un spațiu, $c_1 \ c_2 \ c_3 \dots c_N$ reprezentând culoarea fiecărui cm de pânză după vopsirea inițială, iar următoarele $M$ linii conțin fiecare câte $3$ numere: două numere naturale $A \ B$, separate printr-un spațiu, reprezentând $A$ - poziția la care începe și $B$ - poziția finală la care se termină modificarea intensității și, separat printr-un spațiu, un număr întreg $X$ reprezentând valoarea cu care se modifică intensitatea.

Date de ieşire

Fișierul de ieșire culori.out va conține o singură linie pe care va fi scris un număr natural determinat conform cerinței, dacă cerința este $1$ sau $N$ numere naturale determinate conform cerinței, dacă cerința este $2$.

Restricţii și precizări

• $0 < N < 10 \ 001$
• $0 < C < 1 \ 000 \ 001$
• $0 < M < 200 \ 001$
• în urma tuturor modificărilor nuanțele rămân în mulțimea $\{1, 2, \dots, C \}$
• se acordă $20$ puncte pentru cerința $1$, $70$ puncte pentru cerința $2$; $10$ puncte se acordă din oficiu

Exemplul 1

culori.in

1
3 8 2
1 1 2 2 2 2 3 3
2 5 1
5 8 -1

culori.out

4

Explicație

Cea mai lungă secvență de elemente egale este $2 \ 2 \ 2 \ 2$ și are $4$ elemente

Exemplul 2

culori.in

2
3 8 2
1 1 2 2 2 2 3 3
2 5 1
5 8 -1

culori.out

1 2 3 3 2 1 2 2 

Explicație

După prima modificare vectorul este: $1 \ 2 \ 3 \ 3 \ 3 \ 2 \ 3 \ 3$
După a doua modificare este: $1 \ 2 \ 3 \ 3 \ 2 \ 1 \ 2 \ 2$