#include <bits/stdc++.h> using namespace std; #define endl "\n" #define int long long int n,m,q,k; int p[500300]; struct ask{int l,r,id;}A[500300]; int bel[500300]; const int SIZ=10000; int deg[500300]; vector<int>g[500300],bgg[500300]; int w[500300]; int U[500300],V[500300]; 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[500300]; int A2,A3,A4; int c[500300]; bool ok[500300]; int cnt=0; inline void ins(int x){ x=p[x]; ok[x]=1; for(int y:g[x]){ 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]) A4+=2*c[z]; } c[y]++; cnt++; } } 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(g[y].size()<=1000){ for(int z:g[y]) A4-=2*c[z]; } cnt++; } } signed main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); // freopen("ex_travel6.in","r",stdin); // freopen("path.in","r",stdin); // freopen("path.out","w",stdout); cin>>n>>m>>q>>k; for(int i=1;i<=m;i++){ int u,v; cin>>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++)cin>>p[i]; // cout<<k<<endl; if(k==2||k==3){ for(int i=1;i<=n;i++) w[i]=deg[p[i]]+1; int now=0; int nos=0; int mx=0; for(int i=1;i<=n;i++){ if(nos+w[i]>1*SIZ){ now++; mx=max(mx,nos); nos=0; } nos+=w[i]; bel[i]=now; } for(int i=1;i<=q;i++){ int l,r; cin>>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; if(k==3)ANS[A[i].id]=A3&MSK; } // cerr<<cnt<<endl; for(int i=1;i<=q;i++) cout<<ANS[i]<<endl; } else{ vector<int>BG; for(int i=1;i<=n;i++){ w[i]=deg[p[i]]+1; for(int j:g[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; for(int i=1;i<=n;i++){ if(nos+w[i]>1*SIZ){ now++; mx=max(mx,nos); nos=0; } nos+=w[i]; bel[i]=now; } for(int i=1;i<=q;i++){ int l,r; cin>>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; 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+2*c[x]*c[y])&MSK; ANS[A[i].id]=s; // for(int j=1;j<=m;j++) // ANS[A[i].id]=(ANS[A[i].id]+2*c[U[j]]*c[V[j]])&MSK; } } // cerr<<cnt<<endl; for(int i=1;i<=q;i++) cout<<ANS[i]<<endl; } cout.flush(); return 0; }