#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];uint t[maxn]; uint _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; } uint res; int 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("%u\n",_res[i]); } } namespace sub3 { int A[maxn]; int bel[maxn];uint t[maxn]; uint 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; } int sm[maxn]; struct node { int l,r,id,sgn; node(int _l,int _r,int _id,int _sgn){ l=_l,r=_r,id=_id,sgn=_sgn; }node(){} }; vector<node>g[maxn]; uint s[maxn]; vector<int>v; uint tg[maxn],tg2[maxn]; int lim; vector<int>G[maxn]; 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); lim=pow(m,3.0/4); up(i,1,n)if(E[i].size()>lim)v.p_b(i); up(i,1,n)for(int x:E[i])if(E[x].size()>lim)G[i].p_b(x); int l=1,r=0; up(i,1,q){ if(l>d[i].l)g[r].p_b(node(d[i].l,l-1,d[i].id,1)),l=d[i].l; if(r<d[i].r)g[l-1].p_b(node(r+1,d[i].r,d[i].id,-1)),r=d[i].r; if(l<d[i].l)g[r].p_b(node(l,d[i].l-1,d[i].id,-1)),l=d[i].l; if(r>d[i].r)g[l-1].p_b(node(d[i].r+1,r,d[i].id,1)),r=d[i].r; } up(i,1,m*2){ s[i]=s[i-1]; int u=A[i]; if(E[u].size()<=lim){ for(int x:E[u])s[i]+=tg[x]; }else s[i]+=tg2[i]; tg[u]+=(uint)1; for(int x:G[u])tg2[x]+=(uint)1; for(auto it:g[i]){ int l=it.l,r=it.r,id=it.id,sgn=it.sgn; up(j,l,r){ int id=A[j]; uint s=0; if(E[id].size()<=lim){ for(int x:E[id])s+=tg[x]; }else s=tg2[id]; res[it.id]+=s*it.sgn; } } }l=1,r=0; up(i,1,q){ if(l>d[i].l)res[d[i].id]-=s[l-1]-s[d[i].l-1],l=d[i].l; if(r<d[i].r)res[d[i].id]+=s[d[i].r]-s[r],r=d[i].r; if(l<d[i].l)res[d[i].id]+=s[d[i].l-1]-s[l-1],l=d[i].l; if(r>d[i].r)res[d[i].id]-=s[r]-s[d[i].r],r=d[i].r; } up(i,1,q)res[d[i].id]+=res[d[i-1].id]; up(i,1,q)printf("%u\n",res[i]*2u); } } 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(); if(k==4)sub3::slv(); } int main(){ //freopen("path.in","r",stdin); //freopen("path.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }