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