Problem description


Inwentaryzacja
(B)
Limit pamięci: 256 MB
Limit czasu: 4.00 s

Jasio zarządza lokalnym sklepem. W sklepie jest N regałów ustawionych jeden obok drugiego. Na każdym regale leżą przedmioty jednego rodzaju, który oferuje sklep Jasia. Rodzaje przedmiotów ponumerowane są liczbami naturalnymi od 1 do N. Jasio co jakiś czas decyduje, żeby zmienić typ przedmiotów na niektórych regałach. Musi również co jakiś czas przeprowadzać inwentaryzację. Pojedyncza inwentaryzacja polega na sprawdzeniu liczby regałów w przedziale od l-tego do r-tego, które mają wystawione przedmioty o ustalonym rodzaju v. Jasio poprosił Cię o napisanie systemu, który pozwoli mu przyspieszyć proces inwentaryzacji.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N oraz Q, oznaczające odpowiednio liczbę regałów oraz liczbę zapytań Jasia. W drugim wierszu wejścia znajduje się N liczb naturalnych p1, …, pN oznaczające początkowe rodzaje przedmiotów na kolejnych regałach sklepu Jasia. W następnych Q wierszach następuje opis zapytań. i-ty opis rozpoczyna się od jednego znaku ti. Jeżeli ti = Z, to w tym samym wierszu następują dwie liczby naturalne zi, vi oznaczające, że Jasio zmienił rodzaj przedmiotów na zi-tym regale na vi. Jeżeli ti = I, to w tym samym wierszu następują trzy liczby naturalne vi, li, ri oznaczające, że Jasio chce przeprowadzić inwentaryzację regałów od li-tego do ri-tego włącznie dla przedmiotów o rodzaju vi.

Wyjście

Dla każdego zapytania typu I należy wypisać jedną liczbę naturalną odpowiadającą na dane pytanie Jasia.

Ograniczenia

1 ≤ N, Q ≤ 500 000, 1 ≤ vi, pi, zi ≤ N, 1 ≤ li ≤ ri ≤ N.

W testach wartych łącznie 20% punktów zachodzi dodatkowy warunek N, Q ≤ 2000.

W testach wartych łącznie 40% punktów zachodzi dodatkowy warunek ti = I dla każdego i.

Przykład

Wejście Wyjście
3 4
1 2 3 
I 1 1 3
Z 2 1
I 1 1 2
I 2 2 3
1
2
0