#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=1e6+5,M=N*4+5,K=1000+5,mod=1e9+7,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(28382);
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#ifdef LOCAL
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
	#else 
	#define gdb(...) void()
	#endif
}using namespace Debug;
int C,n,m,q,A[N],k;
vector<int> pt[N],G[N],S[N];
vector<pii> eg[N];
void con(int x,int y){G[x].push_back(y);G[y].push_back(x);}
namespace Tarjan{
	int dfn[N],low[N],dh,st[N],sh;
	void tarjan(int x,int La){
		dfn[x]=low[x]=++dh;st[++sh]=x;
		for(int i:S[x]) if(i^La){
			if(dfn[i]){low[x]=min(low[x],dfn[i]);continue;}
			tarjan(i,x);low[x]=min(low[x],low[i]);
			if(low[i]>=dfn[x]){
				++k;con(k,x);
				while(st[sh+1]^i) con(st[sh--],k);
			}
		}
	}
}
ll mx[N],f[N],g[N],sizf[N],sizg[N];
void dfs1(int x,int La){
	f[x]=0;sizf[x]=(x<=n);
	for(int i:G[x]) if(i^La) dfs1(i,x),sizf[x]+=sizf[i];
	if(x>n){
		int len=G[x].size();
		rotate(G[x].begin(),find(all(G[x]),La),G[x].end());
		ll w1=0,w2=0;
		for(int j=1;j<len;j++){
			int p=G[x][j];
			w1+=f[p]+j*sizf[p];
		}
		for(int j=1;j<len;j++){
			int p=G[x][len-j];
			w2+=f[p]+j*sizf[p];
		}
		// if(La==3) gdb(w1,w2,len,sizf[3],sizf[G[x][1]]);
		// gdb(x,w1,w2,f[2],f[4],len,G[x][0],G[x][1]);
		f[x]=max(w1,w2);
		f[La]+=f[x];
	}
}
void dfs2(int x,int La){
	if(x>n){
		rotate(G[x].begin(),find(all(G[x]),La),G[x].end());
		for(int i:G[x]) if(i^La) sizg[i]=sizg[x]+sizf[x]-sizf[i];
		int len=G[x].size();
		for(int i=1;i<len;i++){
			ll w1=0,w2=0;
			for(int j=1;j<len;j++){
				int p=G[x][(i+j)%len];
				if(p==La) w1+=g[x]+sizg[x]*j;
				else w1+=f[p]+sizf[p]*j;
			}
			for(int j=1;j<len;j++){
				int p=G[x][(i+len-j)%len];
				if(p==La) w2+=g[x]+sizg[x]*j;
				else w2+=f[p]+sizf[p]*j;
			}
			g[G[x][i]]=max(w1,w2);
		}
	}else{
		for(int i:G[x])if(i^La){
			sizg[i]=sizg[x]+sizf[x]-sizf[i];
			g[i]=g[x]+f[x]-f[i];
		}
	}
	for(int i:G[x]) if(i^La) dfs2(i,x);
}
void Solve(){
	scanf("%d%d%d%d",&C,&n,&m,&q);
	for(int i=1;i<=n;i++) scanf("%d",&A[i]),pt[A[i]].push_back(i);
	for(int i=1;i<=m;i++){
		int x,y;scanf("%d%d",&x,&y);
		eg[__gcd(A[x],A[y])].emplace_back(x,y);
	}
	for(int i=1;i<=1e6;i++){
		if(i<=10) gdb(i);
		vector<int> st;
		for(int j=i;j<=1e6;j+=i){
			for(int p:pt[j]) st.push_back(p);
			for(auto [a,b]:eg[j]) S[a].push_back(b),S[b].push_back(a);
		}
		k=n;
		for(int j:st){
			if(!Tarjan::dfn[j]){
				Tarjan::tarjan(j,0);
				dfs1(j,0);
				g[j]=0;sizg[j]=0;dfs2(j,0);
			}
			mx[i]=max(mx[i],f[j]+g[j]);
		} 
		// for(int j:st) dfs1(j,0),mx[i]=max(mx[i],f[j]),gdb(i,j,f[j]);

		for(int j=0;j<=st.size()+1;j++) Tarjan::st[j]=0;Tarjan::dh=Tarjan::sh=0;
		for(int j:st) Tarjan::dfn[j]=Tarjan::low[j]=0,S[j].clear(),G[j].clear();
		for(int j=n+1;j<=k;j++) S[j].clear(),G[j].clear();
		if(i<=10) gdb(mx[i]);
	}
	for(int i=1e6;i;i--) mx[i]=max(mx[i+1],mx[i]);
	while(q--){
		ll x;scanf("%lld",&x);
		int l=0,r=1e6+1,mid;
		while(l+1<r) mid=l+r>>1,(mx[mid]>=x?l:r)=mid;
		printf("%d\n",mx[l]<x?-1:l);
	}
}
int main(){
	int t=1;
	// scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}