#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 mk make_pair const int MAXN=2000010,MAXM=10010010; 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;} int n,m,q,k,p[MAXN]; #define ui unsigned int 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 side2{int u,v; bool operator<(const side2&G)const{return u<G.u;} }s[MAXM]; int cnt; struct side{ int u,v,id,val; bool operator<(const side&G)const{return u<G.u;} }a[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); } void slv3(){ for(int i=1;i<=m;i++)add_side(s[i].u,s[i].v); for(int i=1;i<=n;i++)for(inx(i)){ for(inx2(i))s[++cnt]={v,v2}; } 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+cnt+1); sort(a+1,a+4*q+1); for(int i=1,j=1;i<=4*q;i++){ while(j<=cnt&&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]); } 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; }