#include<bits/stdc++.h> #define int long long using namespace std; int n,m,Q,k,p[500005],q[500005]; vector<int>e[500005]; void read(int &x){ x=0; char c=getchar(); while(!isdigit(c))c=getchar(); while(isdigit(c))x=x*10+c-'0',c=getchar(); } namespace k2{ void slv(){ while(Q--){ int l,r; read(l),read(r); int ans=0; for(int i=l;i<=r;i++){ for(int x:e[i]){ if(q[x]<=r&&q[x]>=l)ans++; } } printf("%lld\n",ans); } } } namespace k3{ namespace sub1{ int cnt[5005][5005],sum[5005][5005]; void slv(){ for(int i=1;i<=n;i++){ for(int x:e[i])for(int y:e[i])cnt[x][y]++; } for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+cnt[p[i]][p[j]]; // for(int i=1;i<=n;i++){ // for(int j=1;j<=n;j++)cout<<cnt[p[i]][p[j]]<<" "; // cout<<endl; // } // for(int i=1;i<=n;i++){ // for(int j=1;j<=n;j++)cout<<sum[i][j]<<" "; // cout<<endl; // } while(Q--){ int l,r; read(l),read(r); // cout<<sum[r][r]<<" "<<sum[r][l-1]<<" "<<sum[l-1][r]<<" "<<sum[l-1][l-1]<<endl; printf("%lld\n",sum[r][r]-sum[r][l-1]-sum[l-1][r]+sum[l-1][l-1]); } } } namespace sub2{ struct node{ int t,l,r; }; struct segtree{ node t[50000<<5]; int tot,rt[50005]; int cl(int p){ t[++tot]=t[p]; return tot; } #define ls(p) t[p].l #define rs(p) t[p].r #define mid (l+r>>1) int bd(int l,int r,int p){ p=++tot; if(l!=r){ ls(p)=bd(l,mid,ls(p)); rs(p)=bd(mid+1,r,rs(p)); } return p; } int upd(int l,int r,int id,int p){ p=cl(p); // cout<<l<<" "<<r<<" "<<id<<" "<<p<<endl; t[p].t++; if(l==r)return p; if(mid>=id)ls(p)=upd(l,mid,id,ls(p)); else rs(p)=upd(mid+1,r,id,rs(p)); return p; } int qu(int l,int r,int u,int v,int id){ if(l>=id)return t[u].t-t[v].t; int res=0; if(mid>=id)res+=qu(l,mid,ls(u),ls(v),id); res+=qu(mid+1,r,rs(u),rs(v),id); return res; } }A,M; int sum1[50005]; int prem[500005],prea[500005],lst[500005]; void slv(){ for(int i=1;i<=n;i++)sum1[i]=sum1[i-1]+e[p[i]].size(); for(int i=1;i<=n;i++){ if(lst[q[i]-2])prem[i]=lst[q[i]-2]; if(lst[q[i]+2])prea[i]=lst[q[i]+2]; lst[q[i]]=i; } A.rt[0]=A.bd(1,n,1); M.rt[0]=M.bd(1,n,1); for(int i=1;i<=n;i++){ if(prea[i]) A.rt[i]=A.upd(1,n,prea[i],A.rt[i-1]); else A.rt[i]=A.rt[i-1]; if(prem[i]) M.rt[i]=M.upd(1,n,prem[i],M.rt[i-1]); else M.rt[i]=M.rt[i-1]; } while(Q--){ int l,r; read(l),read(r); // cout<<l<<" "<<r<<endl; int ans=sum1[r]-sum1[l-1]; ans+=2*A.qu(1,n,A.rt[r],A.rt[l-1],l); ans+=2*M.qu(1,n,M.rt[r],M.rt[l-1],l); printf("%lld\n",ans); } } } void slv(){ // if(n<=5000&&m<=5000&&Q<=5000)sub1::slv(); // else sub2::slv(); } } signed main(){ read(n),read(m),read(Q),read(k); for(int i=1;i<=m;i++){ int u,v; read(u),read(v); e[u].push_back(v); e[v].push_back(u); } for(int i=1;i<=n;i++)read(p[i]),q[p[i]]=i; if(k==2)k2::slv(); else if(k==3)k3::slv(); return 0; }