Перестановки strike back
Вася виписав на дошці у якомусь порядку усі числа від 1 до N, кожне число рівно по одному разу. Іноді він витирає якесь число і записує на його місце інше. Кількість чисел, записаних Васею, виявилась досить великою, тому Вася не може окинути поглядом усі числа. Проте йому потрібно усе-таки уявляти цю послідовність, тому він написав програму, яка у довільний момент відповідає на питання — скільки серед чисел, які стоять на позиціях з x по y, по величині знаходяться у інтервалі від k до l.
Зробіть те ж саме.
Вхідні дані
У першому рядку знаходиться два натуральних числа — 1 ≤ N ≤ 100000 — кількість чисел, які виписав Вася і 1 ≤ M ≤ 100000 — сумарна кількість питань і змін зроблених Васею. У другому рядку задано N чисел — послідовність чисел, виписаних Васею. Далі у M рядках знаходяться описи питань. Кожен запит на зміну числа у деякій позиції починається зі слова SET і має вигляд SET a b (1 ≤ a ≤ N, 1 ≤ b ≤ N). Це означає, що Вася змінив число, записане у позиції a на число b. Кожне Васине запитання починається зі слова GET і має вигляд GET x y k l (1 ≤ x ≤ y ≤ N, 1 ≤ k ≤ l ≤ N).
Вихідні дані
Для кожного Васиного запитання виведіть єдине число — відповідь на Васине запитання.