#include <bits/stdc++.h> using namespace std; #define endl "\n" #define int long long int n,m,q,k; int p[200300]; struct ask{int l,r,id;}A[200300]; int bel[200300]; const int SIZ=250; int deg[200300]; vector<int>g[200300],bgg[200300]; int w[200300]; int U[200300],V[200300]; inline bool cmp(ask A,ask B){ if(bel[A.l]==bel[B.l])return A.r<B.r; return bel[A.l]<bel[B.l]; } int ANS[200300]; int A2,A3,A4; int c[200300]; int ok[200300]; int cnt=0; int ac[200300]; inline void ins(int x){ x=p[x]; ok[x]=1; // cout<<A2<<endl; for(int y:g[x]){ // cout<<x<<" "<<y<<" "<<2*ok[y]<<endl; if(k==3){ A3+=1+2*c[y]; } else if(k==2) A2+=2*ok[y]; else if(g[y].size()<=1000){ for(int z:g[y]) if(deg[z]<=1000)A4+=2*c[z]; else A4+=2*c[z],ac[z]++; } else A4+=2*ac[y]; c[y]++; cnt++; } // cout<<"ins "<<x<<" "<<A2<<endl; } inline void del(int x){ x=p[x]; ok[x]=0; for(int y:g[x]){ c[y]--; if(k==3){ A3-=1+2*c[y]; } else if(k==2)A2-=2*ok[y]; else if(deg[y]<=1000){ for(int z:g[y]) if(deg[z]<=1000)A4-=2*c[z]; else ac[z]--,A4-=2*c[z]; } else A4-=2*ac[y]; cnt++; } // cout<<"del "<<x<<" "<<A2<<endl; } signed main(){ // ios::sync_with_stdio(0); // cin.tie(0);cout.tie(0); // freopen("path.in","r",stdin); // freopen("ex_travel2.in","r",stdin); // freopen("SS.out","w",stdout); scanf("%lld %lld %lld %lld",&n,&m,&q,&k); for(int i=1;i<=m;i++){ int u,v; scanf("%lld %lld",&u,&v); g[u].push_back(v); g[v].push_back(u); U[i]=u,V[i]=v; deg[u]++,deg[v]++; } for(int i=1;i<=n;i++)scanf("%lld",&p[i]); vector<int>BG; for(int i=1;i<=n;i++){ w[i]=deg[p[i]]+1; if(k==4){ for(int j:g[p[i]]) if(deg[j]<=1000)w[i]+=deg[j]; } if(deg[i]>1000)BG.push_back(i); } for(int i:BG) for(int j:g[i]) if(deg[j]>1000)bgg[i].push_back(j); int now=0; int nos=0; int mx=0; int sum=0; for(int i=1;i<=n;i++){ if(nos+w[i]>SIZ){ now++; mx=max(mx,nos); sum+=nos; nos=0; } nos+=w[i]; bel[i]=now; } cerr<<max(mx,nos)<<" "<<sum+nos<<endl; for(int i=1;i<=q;i++){ int l,r; scanf("%lld %lld",&l,&r); A[i]={l,r,i}; } sort(A+1,A+q+1,cmp); int l=1,r=0; const int MSK=(1ll<<32)-1; for(int i=1;i<=q;i++){ while(r<A[i].r)ins(++r); while(l>A[i].l)ins(--l); while(r>A[i].r)del(r--); while(l<A[i].l)del(l++); if(k==2)ANS[A[i].id]=A2&MSK; else if(k==3)ANS[A[i].id]=A3&MSK; else{ int s=A4&MSK; for(int x:BG) for(int y:bgg[x]) s=(s+c[x]*c[y])&MSK; ANS[A[i].id]=s; } } for(int i=1;i<=q;i++) printf("%lld\n",ANS[i]); cout.flush(); return 0; }