Є масив з \(N\) цілих чисел, кожне з яких може приймтаи значення від 1 до \(M\), а також задано число \(K\).
Необхідно відповісти на запити \(L\) \(R\) - скільки чисел на відрізку \(L..R\) зустрічаються рівно \(K\) раз.
Також зустрічаються запити зміни елемента.

Формат вхідних даних

В першому рядку чотири цілих числа \(N,M,Q,K\) (\(1 \le N,Q \le 10^5\), \(1 \le M \le 10^6\), \(0 \le K \le 3\) ).

В другому рядку \(N\) цілих чисел - відповідний масив.

В наступних \(Q\) рядках по три цілих числа - запити одного з двох видів:
\(1\) \(L\) \(R\) - знайти кількість чисел на відрізку \(L..R\) які зустрічаються рівно \(K\) раз. (\(1 \le L \le R \le N\))
\(2\) \(pos\) \(val\) - замінити число в позиції \(pos\) на значення \(val\) (\(1 \le pos \le N\) , \(1 \le val \le M\))

Формат вихідних даних

Для кожного запиту першого типу виведіть в окремому рядку відповідь - скільки чисел на відрізку \(L..R\) зустрічаються рівно \(K\) раз.

Приклад вхідних даних

5 5 3 2
1 2 2 1 5
1 1 5
2 3 3
1 1 5

Приклад вихідних даних

2
1