#include<bits/stdc++.h> using namespace std; #define pii pair<int,int> #define fr first #define sc second #define inx(u) int I=h[(u)],v=edge[I].v;I;I=edge[I].nx,v=edge[I].v #define inx2(u) int I2=h[(u)],v2=edge[I2].v;I2;I2=edge[I2].nx,v2=edge[I2].v #define ui unsigned int #define mk make_pair int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} const int MAXN=2000010,B=2; int n,m,q,k,p[MAXN]; ui as[MAXN]; struct Edge{int v,nx;}edge[MAXN<<1];int h[MAXN],CNT;void add_side(int u,int v){edge[++CNT]={v,h[u]};h[u]=CNT;edge[++CNT]={u,h[v]};h[v]=CNT;} struct side{ int u,v,id,val; bool operator<(const side&G)const{return u<G.u;} }a[MAXN],s[MAXN]; struct treearray{ int C[MAXN]; int lb(int x){return x&(-x);} void upd(int x,int y){for(int i=x;i<=n;i+=lb(i))C[i]+=y;} int qry(int x){int res=0;for(int i=x;i>=1;i-=lb(i))res+=C[i];return res;} }T; void slv2(){ for(int i=1;i<=q;i++){ int l=read(),r=read(); a[i]={l-1,l-1,i,1}; a[i+q]={r,r,i,1}; a[i+2*q]={l-1,r,i,-1}; a[i+3*q]={r,l-1,i,-1}; } sort(s+1,s+m+1); sort(a+1,a+4*q+1); for(int i=1,j=1;i<=4*q;i++){ while(j<=m&&s[j].u<=a[i].u)T.upd(s[j].v,1),j++; as[a[i].id]+=a[i].val*T.qry(a[i].v); } for(int i=1;i<=q;i++)printf("%u\n",as[i]*2); } int bel[MAXN]; struct ques{ int l,r,id; bool operator<(const ques&G)const{ return bel[l]!=bel[G.l]?l<G.l:bel[l]&1?r<G.r:r>G.r; } }qs[MAXN]; int e[MAXN],Lw[MAXN],Rw[MAXN]; ui sm[MAXN],Res; void add(int x){ Res+=sm[x]; sm[x]++; Res+=sm[x]; } void del(int x){ Res-=sm[x]; sm[x]--; Res-=sm[x]; } ui qry(){ return Res; } void slv3(){k=0; for(int i=1;i<=m<<1;i++)bel[i]=(i-1)/B+1; for(int i=1;i<=m;i++)add_side(s[i].u,s[i].v); for(int i=1;i<=n;i++){ Lw[i]=k+1; for(inx(i))e[++k]=v; Rw[i]=k; } for(int i=1;i<=q;i++){ int l=read(),r=read(); qs[i].l=Lw[l],qs[i].r=Rw[r],qs[i].id=i; } sort(qs+1,qs+q+1); int l=1,r=0; for(int i=1;i<=q;i++){ int L=qs[i].l,R=qs[i].r; while(l>L)add(e[--l]); while(r<R)add(e[++r]); while(l<L)del(e[l++]); while(r>R)del(e[r--]); as[qs[i].id]=qry(); } for(int i=1;i<=q;i++)printf("%u\n",as[i]); } void slv(){ n=read(),m=read(),q=read(),k=read(); for(int i=1;i<=m;i++)s[i].u=read(),s[i].v=read(); for(int i=1;i<=n;i++)p[read()]=i; for(int i=1;i<=m;i++)s[i].u=p[s[i].u],s[i].v=p[s[i].v];//,cout<<s[i].u<<" "<<s[i].v<<endl; if(k==2)slv2(); if(k==3)slv3(); } signed main(){ slv(); return 0; }