Задача №114219. Бар у Мо 2
В баре у Мо дела идут по-прежнему прекрасно. Как известно, чтобы дела шли еще лучше, Мо озадачился вопросом разнообразия сортов пива, которые разливают в его баре. Для составления стратегического плана по улучшению списка сортов пива Мо должен получить ответы на ряд вопросов.
В данный момент у барной стойки сидят \(n\) посетителей и у каждого посетителя есть кружка с пивом одного из сортов. Мо пронумеровал посетителей слева направо числами от \(1\) до \(n\). После этого он пронумеровал сорта пива числами от \(1\) до \(m\). Далее Мо вспомнил число \(k\), которое было рекомендовано в гороскопе на эту неделю. Наконец, Мо составил список вопросов, ответы на которые помогут его бизнесу стать еще успешней. В каждом вопросе спрашивается следующее: каково количество сортов пива, которые можно встретить ровно \(k\) раз в кружках посетителей с номерами от \(l\) до \(r\) включительно.
Мо ответил на все вопросы, но вдруг заметил, что пока он отвечал на вопросы, некоторые посетители выпивали свое пиво и тут же заказывали новую кружку с пивом, возможно другого сорта.
Чтобы проверить правильно ли Мо ответил на все вопросы, напишите программу которая ответит на все вопросы, учитывая все заказы посетителей. Всего в сумме произошло \(q\) событий, каждое из которых либо смена кружки пива одним из посетителей или вопрос от Мо.
В первой строке даны четыре целых числа \(n\), \(m\), \(q\) и \(k\) (\(1 \le n, \ q \le 10^5\), \(1 \le m \le 10^6\), \(0 \le k \le 3\)).
Во второй строке даны \(n\) целых чисел \(1 \le a_1, \ldots, a_n \le m\) -- номера сортов пива у посетителей.
В следующих \(q\) строках заданы события. Каждое событие одного из двух типов:
\(1 \ l \ r\) -- вопрос от Мо (\(1 \le l \le r \le n\)).
\(2 \ i \ j\) -- \(i\)-й посетитель перешел на пиво сорта \(j\), (\(1 \le i \le n\), \(1 \le j \le m\)).
Для каждого запроса первого типа выведите в отдельной строке ответ на него.
5 5 3 2 1 2 2 1 5 1 1 5 2 3 3 1 1 5
2 1