【题目描述】

给定一串n个珠子，其中每一个珠子的颜色为a[i]，总共有k类颜色珠子标号从1到k。

初始给定一个参数T。询问再给定m个区间l[i]到r[i]，每次询问这个区间有多少颜色的珠子出现了恰好T次。

【输入格式】

第一行四个整数n，m，k，T（1<=n,m,k,T<=5*10^5）。

第二行n个整数，第i个整数为a[i]，表示对应珠子的颜色(1<=a[i]<=k)。

接下来m行，每行两个整数l[i]和r[i],表示询问的区间(1<=l[i]<=r[i]<=n)。

【输出格式】

输出m行，每行一个整数，第i行表示第i次询问的答案。

【样例输入】

10 5 5 1
1 5 3 4 2 4 1 2 3 5 
1 10
3 6 
2 8
5 7
6 10

【样例输出】

0
2
3
3
5

【数据范围】

对于30%的数据 n,m,k<=2000,T<=n.

对于另外40%的数据 T=1，1<=n,m,k<=5*10^5.

对于所有数据，1<=n,m,k,T<=5*10^5，1<=a[i]<=k,1<=l[i]<=r[i]<=n.

注意：本题输入量较大，请使用较为快速的读入方式。