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

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

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

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

В наступних \(Q\) рядках по два цілих числа \(L\) та \(R\) - запити. (\(1 \le L < R \le N\)).

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

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

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

5 5 2 2
1 2 2 1 5
1 5
2 4

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

2
1