给定一串n个珠子，其中每一个珠子的颜色为a[i]，总共有k类颜色珠子标号从1到k。
初始给定一个参数T。询问再给定m个区间l[i]到r[i]，每次询问这个区间有多少颜色的珠子出现了恰好T次。
第一行四个整数n，m，k，T（1<=nmkT<=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次询问的答案。
对于30%的数据 nmk<=2000T<=n.
对于另外40%的数据 T=1，1<=nmk<=5*10^5.
对于所有数据，1<=nmkT<=5*10^5，1<=a[i]<=k1<=l[i]<=r[i]<=n.
注意：本题输入量较大，请使用较为快速的读入方式。