给定一串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.
注意:本题输入量较大,请使用较为快速的读入方式.