Перестановки 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).
Выходные данные
Для каждого Васиного вопроса выведите единственное число — ответ на Васин вопрос.