#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back typedef long long ll; typedef unsigned int uint; using namespace std; const int maxn=5e5+10; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,m,q,k,p[maxn],loc[maxn]; vector<int>E[maxn]; namespace sub1 { struct BIT { int t[maxn]; int lb(int x){return x&(-x);} void upd(int x,int v){for(;x<=n;x+=lb(x))t[x]+=v;} int qry(int x){int res=0;for(;x;x-=lb(x))res+=t[x];return res;} int g(int l,int r){return qry(r)-qry(l-1);} }T; vector<pair<pi,int> >A[maxn]; int res[maxn]; void slv(){ up(i,1,q){ int l=read(),r=read(); A[r].p_b(m_p(m_p(l,r),i)); A[l-1].p_b(m_p(m_p(l,r),-i)); } up(i,1,n){ for(int x:E[p[i]])T.upd(loc[x],1); for(auto it:A[i]){int v=T.g(it.p1.p1,it.p1.p2);if(it.p2>0)res[it.p2]+=v;else res[-it.p2]-=v;} } up(i,1,q)printf("%d\n",res[i]); } } namespace sub2 { int A[maxn]; int bel[maxn],t[maxn]; ll _res[maxn]; struct nd { int l,r,id; }d[maxn]; bool operator<(nd a,nd b){ if(bel[a.l]^bel[b.l])return bel[a.l]<bel[b.l]; return a.r<b.r; } ll res,sm[maxn]; void ins(int x){ res+=2*t[x]+1;t[x]++; }void del(int x){ t[x]--;res-=2*t[x]+1; } void slv(){ up(i,1,q)d[i].l=read(),d[i].r=read(),d[i].id=i; int len=sqrt(m*2); up(i,1,m*2)bel[i]=(i-1)/len+1;int e=0; up(i,1,n)for(int x:E[p[i]])A[++e]=x; up(i,1,n)sm[i]=sm[i-1]+(int)E[p[i]].size(); up(i,1,q)d[i].l=sm[d[i].l-1]+1,d[i].r=sm[d[i].r]; sort(d+1,d+q+1); int l=1,r=0; up(i,1,q){ while(l>d[i].l)ins(A[--l]); while(r<d[i].r)ins(A[++r]); while(l<d[i].l)del(A[l++]); while(r>d[i].r)del(A[r--]); _res[d[i].id]=res; }up(i,1,q)printf("%lld\n",_res[i]); } } void slv(){ n=read(),m=read(),q=read(),k=read(); up(i,1,m){ int x=read(),y=read(); E[x].p_b(y),E[y].p_b(x); } up(i,1,n)p[i]=read(),loc[p[i]]=i; if(k==2)sub1::slv(); if(k==3)sub2::slv(); } int main(){ //freopen("path.in","r",stdin); //freopen("path.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }