#pragma GCC optimize(3)

#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i=(a),i##_end=(b);i<=i##_end;++i)

#define For(i,a,b) for(int i=(a),i##_end=(b);i<i##_end;++i)

#define per(i,a,b) for(int i=(b),i##_st=(a);i>=i##_st;--i)

#define fi first

#define se second

#define pb push_back

#define mp make_pair

#define dbg(x) cerr<<#x" = "<<x<<endl

#define debug(...) fprintf(stderr, __VA_ARGS__)

#define Es(x,i) for(Edge*i=G[x];i;i=i->nxt)

typedef long long ll;

typedef pair<int,int> pii;

const int inf=~0u>>1,MOD=1e9+7;

char *TT,*mo,but[(1<<15)+2];

#define getchar() ((TT==mo&&(mo=((TT=but)+fread(but,1,1<<15,stdin)),TT==mo))?-1:*TT++)

inline int rd() {

    int x,c,f=1;while(!isdigit(c=getchar()))f=c!='-';x=c-'0';

    while(isdigit(c=getchar()))x=x*10+c-'0';return f?x:-x;

}

#define Q 64

const int N=100011,MX=30000/Q+2,Modx=131;

typedef unsigned long long ui;

#define lb _lb_

int fx[1<<16],fy[Modx];

inline int pcal(){

	For(i,1,1<<16)fx[i]=fx[i^(i&-i)]+1;

	ui t=1;

	fy[1]=0;

	For(i,1,Q)t<<=1,fy[t%Modx]=i;

}

inline int cal1(unsigned int i){

	//cout<<i<<" f "<<fx[i&((1<<16)-1)]+fx[i>>16]<<endl;

	return fx[i&((1<<16)-1)]+fx[i>>16];

}

inline int cal(ui i){

	unsigned int a=i>>32,b=i&(~0ull);

	return cal1(a)+cal1(b);

}

inline int lb(ui i){

	return fy[i%Modx];

}

struct bs{

	ui w[MX];

	bs (int _t=1){if(!_t)memset(w,0,sizeof w);}

	void Ci(){memset(w,0,sizeof w);}

	//inline uint&operator&(int i){return w[i];}

	void operator|=(const bs&b){

		For(i,0,MX)this->w[i]|=b.w[i];

	}

	bs operator|(const bs&b)const{

		static bs c;

		c.Ci();

		For(i,0,MX)c.w[i]=w[i]|b.w[i];

		return c;

	}

	inline void in(int i){

		int j=i>>6;i&=(63);

		w[j]|=(1ull<<i);

	}

	inline pii query(){

		static const ui I=~0ull;

		//cerr<<I<<endl;

		//int t=clock();

		int a=0,b;

		For(i,0,MX)if(w[i]!=I){

			ui t=w[i];int p=0;

			t=~t;

			t=t&-t;

			//while(t&1)t>>=1,++p;

			b=(i<<6)+lb(t);break;

		}

		For(i,0,MX)if(w[i]){

			a+=cal(w[i]);

			//cout<<i<<" "<<w[i]<<endl;

		}

		//dbg(clock()-t);

		return mp(a,b);

	}

	#undef Q

} b[(int)(1.8*N+1000)],*it=b;

struct Edge{int v;Edge*nxt;}pl[N<<1],*cur=pl,*G[N];

inline void ins(int u,int v){*cur=(Edge){v,G[u]},G[u]=cur++;}

int n,rt,a[N],m,bel[N],fa[N];

int L[N],tot;

int Top[N],dep[N],son[N],sz[N],q[N];

inline void dfs(int S){

	int h,t=1;q[h=0]=S;

	while(h<t){

		int x=q[h++];

		dep[x]=dep[fa[x]]+1,sz[x]=1;

		Es(x,i)if(i->v!=fa[x]){

			fa[q[t++]=i->v]=x;

		}

	}

	per(o,0,t-1){

		int x=q[o];

		Es(x,i)if(i->v!=fa[x]){

			sz[x]+=sz[i->v];

			if(sz[i->v]>sz[son[x]])son[x]=i->v;

		}

	}

	For(o,0,t){

		int x=q[o];

		Top[x]=(son[fa[x]]==x)?Top[fa[x]]:x;

	}

}

inline void dfs2(int S){

	For(o,0,n){

		int x=q[o];

		L[x]=tot;

		if(!bel[x])bel[x]=bel[fa[x]];

		else if(x!=rt){

			it->in(a[x]);

			int t=fa[x],y=bel[t],lst=-1;

			while(bel[t]==y){

				it->in(a[t]);

				lst=t,t=fa[t];

			}

			++tot,++it;

			while(t>0){

				*it=b[L[lst]]|*(it-1);

				++it,++tot;

				if((lst=bel[t])==-1)break;

				else t=fa[lst];

			}

			//R[x]=tot;

		}

	}

}

inline void Init(){

	rt=rand()%n+1;

	dfs(rt);

	rep(i,1,n){

		if(dep[i]%200==0)bel[i]=i;

	}

	bel[rt]=-1;

	dfs2(rt);

}

bs A;

inline int lca(int x,int y){

	while(Top[x]!=Top[y]){

		if(dep[Top[x]]<dep[Top[y]])swap(x,y);

		x=fa[Top[x]];

	}

	return dep[x]<dep[y]?x:y;

}

inline void query(int x,int y){

	//int t=clock();

	int l=lca(x,y);

	{

		//dbg(x),dbg(rt),dbg(l);

		while(bel[x]!=x&&x!=l)A.in(a[x]),x=fa[x];//dbg(x);

		if(bel[x]==x){

			int e=L[x],f=x,g=bel[fa[x]];

			while(g>0&&dep[g]>=dep[l])++e,f=g,g=bel[fa[g]];

			if(e>L[x])A|=b[e-1];//cout<<"fff\n";;

			while(f!=l)A.in(a[f]),f=fa[f];

		}

	}

		//cerr<<"OK1"<<endl;

	swap(x,y);

	{

		while(bel[x]!=x&&x!=l)A.in(a[x]),x=fa[x];

		if(bel[x]==x){

			int e=L[x],f=x,g=bel[fa[x]];

			while(g>0&&dep[g]>=dep[l])++e,f=g,g=bel[fa[g]];

			if(e>L[x])A|=b[e-1];//cout<<"fff\n";;

			while(f!=l)A.in(a[f]),f=fa[f];

		}

	}

	A.in(a[l]);

}

int main(){

#ifdef flukehn

	freopen("test.txt","r",stdin);

	freopen("out.txt","w",stdout);

#endif

	srand((unsigned long long)(new char));

	pcal();

	n=rd();int q=rd(),f=rd(),lst=0;

	rep(i,1,n)a[i]=rd();

	For(i,1,n){

		int x=rd(),y=rd();

		ins(x,y),ins(y,x);

	}

	Init();

//	dbg(clock());

//	if(n>=90000)return 0;

	while(q--){

		//cerr<<q<<endl;

		//int t=clock();

		A.Ci();

		int a=rd();

		while(a--){int x=rd()^(f?lst:0),y=rd()^(f?lst:0);query(x,y);}

		//cerr<<q<<endl;

		pii tmp=A.query();

		lst=tmp.fi+tmp.se;

		printf("%d %d\n",tmp.fi,tmp.se);

		//dbg(clock()-t);

		//cerr<<q<<endl;

	}

//	cerr<<clock()<<endl;

}