#include<bits/stdc++.h> #define u32 unsigned int #define endl '\n' using namespace std; const int maxn=5e5+7; const int maxB=807; int n,m,q,K; int U[maxn]; int V[maxn]; vector<int> E[maxn]; int p[maxn]; int pos[maxn]; int d[maxn]; u32 ans[maxn]; struct QR{ int l,id; }; struct OP{ int x,dt; }; vector<OP> RG[maxn]; vector<QR> qq[maxn]; //block int B,Bc; int bel[maxn]; int L[maxn],R[maxn]; u32 Sum[maxB]; u32 a[maxn]; inline void Init(){ B=sqrt(n); for(int i=1;i<=n;i++)bel[i]=(i-1)/B+1; Bc=bel[n]; for(int i=1;i<=Bc;i++){ L[i]=R[i-1]+1; R[i]=i*B; } R[Bc]=n; } inline void Add(int p,int dt){ a[p]+=dt; Sum[bel[p]]+=dt; } inline u32 Qry(int x){ if(x==0)return 0; int BL=bel[x]; u32 ans=0; for(int i=1;i<BL;i++)ans+=Sum[i]; for(int i=L[BL];i<=x;i++)ans+=a[i]; return ans; } //BIT inline int lb(int x){ return x&(-x); } inline void TAdd(int x,int dt){ for(int i=x;i<=n;i+=lb(i))a[i]+=dt; } inline u32 TQry(int x){ u32 ans=0; for(int i=x;i;i-=lb(i))ans+=a[i]; return ans; } inline void Read(){ cin>>n>>m>>q>>K; for(int i=1;i<=m;i++){ cin>>U[i]>>V[i]; E[U[i]].push_back(V[i]); E[V[i]].push_back(U[i]); d[U[i]]++;d[V[i]]++; } for(int i=1;i<=n;i++){ cin>>p[i]; pos[p[i]]=i; } for(int i=1;i<=q;i++){ int l,r; cin>>l>>r; qq[r].push_back((QR){l,i}); } } inline void K2(){ Init(); for(int i=1;i<=m;i++){ int u=pos[U[i]],v=pos[V[i]]; RG[max(u,v)].push_back((OP){min(u,v),2}); } for(int i=1;i<=n;i++){ for(OP o:RG[i])TAdd(o.x,o.dt); for(QR qr:qq[i])ans[qr.id]+=(TQry(i)-TQry(qr.l-1)); } for(int i=1;i<=q;i++)cout<<ans[i]<<endl; return; } inline void K3(){ Init(); int SD=0; for(int i=1;i<=n;i++){ SD+=d[i]*d[i]; } if(SD>3e7)return; for(int i=1;i<=n;i++){ for(auto st:E[i]){ for(auto ed:E[i]){ int u=pos[st],v=pos[ed]; RG[max(u,v)].push_back((OP){min(u,v),1}); } } } for(int i=1;i<=n;i++){ for(OP o:RG[i])Add(o.x,o.dt); for(QR qr:qq[i])ans[qr.id]+=(Qry(i)-Qry(qr.l-1)); } for(int i=1;i<=q;i++)cout<<ans[i]<<endl; return; } signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); freopen("path.in","r",stdin); freopen("path.out","w",stdout); Read(); if(K==2){ K2(); cout.flush(); return 0; } if(K==3){ K3(); cout.flush(); return 0; } }