Problem description

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 p₁, …, p_N 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 t_i. Jeżeli t_i = Z, to w tym samym wierszu następują dwie liczby naturalne z_i, v_i oznaczające, że Jasio zmienił rodzaj przedmiotów na z_i-tym regale na v_i. Jeżeli t_i = I, to w tym samym wierszu następują trzy liczby naturalne v_i, l_i, r_i oznaczające, że Jasio chce przeprowadzić inwentaryzację regałów od l_i-tego do r_i-tego włącznie dla przedmiotów o rodzaju v_i.

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 ≤ v_i, p_i, z_i ≤ N, 1 ≤ l_i ≤ r_i ≤ N.

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

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

Przykład

3 4
1 2 3 
I 1 1 3
Z 2 1
I 1 1 2
I 2 2 3

1
2
0