#include <bits/stdc++.h>
#define LL long long
using namespace std;
set<pair<int,int> > ed;
vector<int> e[1000000];
int t[1000000],disS[1000000],disT[1000000],n,m,k;
void dij(int s,int dis[1000000]){
	for(int i=1;i<=n;i++) dis[i]=-1;
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
	q.push({0,s});
	while(!q.empty()){
		pair<int,int> now=q.top();
		q.pop();
		int p=now.second;
		if(dis[p]!=-1) continue;
		dis[p]=now.first+t[p];
		for(auto it:e[p]){
			if(dis[it]==-1) q.push({dis[p],it});
		}
	}
}
bool fl1[1000000],fl2[1000000];
int col[1000000];
void fillOther(int lft1,int lft2){
	for(int i=1;i<=n;i++){
		if(col[i]==0){
			if(lft1){
				lft1--;
				col[i]=1;
			}
			else{
				lft2--;
				col[i]=2;
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++) cin>>t[i];
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dij(1,disS);
	dij(n,disT);
	for(auto it:e[1]){
		if(disT[it]+t[1]==disT[1]) fl1[it]=1;
	}
	for(int it:e[n]){
		if(disS[it]+t[n]==disS[n]) fl2[it]=1;
	}
	int lft1=k,lft2=n-k;
	fl1[1]=fl2[n]=1;
	if(fl1[n]){
		if(lft1<=1&&lft2<=1){
			cout<<"impossible\n";
			return 0;
		}
		if(lft1>1){
			col[1]=col[n]=1;
			lft1-=2;
		}
		else{
			col[1]=col[n]=2;
			lft2-=2;
		}
		fillOther(lft1,lft2);
		for(int i=1;i<=n;i++) cout<<"XNS"[col[i]];
		cout<<'\n';
		return 0;
	}
	if(!lft1||!lft2){
		fillOther(lft1,lft2);
		for(int i=1;i<=n;i++) cout<<"XNS"[col[i]];
		cout<<'\n';
		return 0;
	}
	int cnt1=0,cnt2=0;
	for(int i=1;i<=n;i++){
		if(fl1[i]&&!fl2[i]) cnt1++;
		if(!fl1[i]&&fl2[i]) cnt2++;
	}
	for(int i=1;i<=n;i++){
		if(fl1[i]&&fl2[i]) continue;
		if((fl1[i]&&cnt1<=cnt2)||(fl2[i]&&cnt1>cnt2)){
			if(k>=(n>>1)){
				col[i]=1;
				lft1--;
			}
			else{
				col[i]=2;
				lft2--;
			}
		}
	}
	fillOther(lft1,lft2);
	for(int i=1;i<=n;i++) cout<<"XNS"[col[i]];
	cout<<'\n';
	return 0;
}