#include<iostream>
#include<cstdio>
#include<vector>
#define N 400000
#define M 1000000
using namespace std;
long long read()
{
	char c=0;
	long long sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int gcd(int x,int y)
{
	if (!y) return x;
	return gcd(y,x%y);
}
struct reads
{
	int x,y;
};
struct rds
{
	int num,data;
};
rds st[N+1];
struct node
{
	int v,nxt;
};
node edge[M+1],edge2[M+1];
int C,n,m,q,len,len2,lengs,lg[M+1],head[N+1],head2[N+1],stk[N+1],top,sz[N+1],fa[N+1],dfn[N+1],low[N+1],lengz,a[N+1],s[N+1],tong[N+1],length,leng;
long long k,dp[N+1],maxn,ans[M+1],s2[N+1];
vector<reads>p[M+1];
bool vis[N+1];
void add(int x,int y)
{
	edge[++len]=(node){y,head[x]},head[x]=len;
	edge[++len]=(node){x,head[y]},head[y]=len;
	return;
}
void add2(int x,int y)
{
	edge2[++len2]=(node){y,head2[x]},head2[x]=len2;
	return;
}
bool ops;
int dque[N+1],tops;
void tarjan(int x)
{
	if (ops) dque[++tops]=x;
	dfn[x]=low[x]=++lengz,stk[++top]=x;
	for (int i=head[x];i>0;i=edge[i].nxt)
	{
		if (!dfn[edge[i].v])
		{
			tarjan(edge[i].v),low[x]=min(low[x],low[edge[i].v]);
			if (low[edge[i].v]>=dfn[x])
			{
				++lengs;
				while (stk[top]!=edge[i].v) add2(lengs,stk[top]),top--;
				add2(lengs,stk[top]),top--,add2(x,lengs);
			}
		}
		else low[x]=min(low[x],dfn[edge[i].v]);
	}
	return;
}
void dfs(int x)
{
	sz[x]=(x<=n);
	for (int i=head2[x];i>0;i=edge2[i].nxt) fa[edge2[i].v]=x,dfs(edge2[i].v),sz[x]+=sz[edge2[i].v];
	return;
}
void dfs2(int x)
{
	if (x<=n) maxn=max(maxn,dp[x]);
	for (int i=head2[x];i>0;i=edge2[i].nxt) dp[edge2[i].v]+=dp[x],dfs2(edge2[i].v);
	return;
}
int main()
{
	int x,y,ps;
	long long res,res2;
	for (int i=2;i<=M;++i) lg[i]=lg[i>>1]+1;
	C=read(),n=read(),m=read(),q=read();
	for (int i=1;i<=n;++i) a[i]=read();
	for (int i=1;i<=m;++i) x=read(),y=read(),p[gcd(a[x],a[y])].push_back((reads){x,y});
	for (int i=M;i>=1;--i)
	{
		length=lengz=0,lengs=n,len=len2=maxn=0;
		for (int j=i;j<=M;j+=i)
			for (int k=0;k<p[j].size();++k)
			{
				add(p[j][k].x,p[j][k].y);
				if (!vis[p[j][k].x]) vis[p[j][k].x]=1,tong[++length]=p[j][k].x;
				if (!vis[p[j][k].y]) vis[p[j][k].y]=1,tong[++length]=p[j][k].y;
			}
		if (length)
		{
			for (int j=1;j<=length;++j)
				if (!dfn[tong[j]])
				{
					top=0,ps=lengs,tarjan(tong[j]),dfs(tong[j]);
					for (int k=ps+1;k<=lengs;++k)
					{
						leng=0;
						for (int t=head2[k];t>0;t=edge2[t].nxt) st[++leng]=(rds){edge2[t].v,sz[edge2[t].v]};
						st[++leng]=(rds){fa[k],sz[tong[j]]-sz[k]};
						for (int t=1;t<=leng;++t) s[t]=s[t-1]+st[t].data,s2[t]=s2[t-1]+1ll*st[t].data*t;
						for (int t=1;t<=leng;++t)
						{
							res=1ll*t*s[t]+1ll*(leng+t)*(s[leng]-s[t])-s2[leng];
							res2=s2[leng]+1ll*(leng-t)*s[t-1]-1ll*t*(s[leng]-s[t-1]);
							if (st[t].num!=fa[k]) dp[st[t].num]+=max(res,res2);
							else dp[tong[j]]+=max(res,res2),dp[k]-=max(res,res2);
						}
					}
					dfs2(tong[j]);
				}
			ans[i]=maxn;
			for (int j=1;j<=length;++j) vis[tong[j]]=head[tong[j]]=head2[tong[j]]=dfn[tong[j]]=dp[tong[j]]=0;
			for (int j=n+1;j<=lengs;++j) vis[j]=head[j]=head2[j]=dfn[j]=dp[j]=0;
		}
	}
	for (int i=M-1;i>=1;--i) ans[i]=max(ans[i],ans[i+1]);
	for (int qt=1;qt<=q;++qt)
	{
		k=read();
		if (ans[1]<k) puts("-1");
		else
		{
			ps=1;
			for (int i=lg[M];i>=0;--i)
				if (ps+(1<<i)<=M&&ans[ps+(1<<i)]>=k)
					ps+=(1<<i);
			printf("%d\n",ps);
		}
	}
	return 0;
}