Problem: We have a connected undirected graph with N vertices and M edges. Edge i in this graph (1 \leq i \leq M) connects Vertex U_i and Vertex V_i bidirectionally. We are additionally given N integers D_1, D_2, ..., D_N.

Determine whether the conditions below can be satisfied by assigning a color - white or black - to each vertex and an integer weight between 1 and 10^9 (inclusive) to each edge in this graph. If the answer is yes, find one such assignment of colors and integers, too.

* There is at least one vertex assigned white and at least one vertex assigned black.
* For each vertex v (1 \leq v \leq N), the following holds.
* The minimum cost to travel from Vertex v to a vertex whose color assigned is different from that of Vertex v by traversing the edges is equal to D_v.



Here, the cost of traversing the edges is the sum of the weights of the edges traversed.

Constraints

* 2 \leq N \leq 100,000
* 1 \leq M \leq 200,000
* 1 \leq D_i \leq 10^9
* 1 \leq U_i, V_i \leq N
* The given graph is connected and has no self-loops or multiple edges.
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N M
D_1 D_2 ... D_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M


Output

If there is no assignment satisfying the conditions, print a single line containing `-1`.

If such an assignment exists, print one such assignment in the following format:


S
C_1
C_2
\vdots
C_M


Here,

* the first line should contain the string S of length N. Its i-th character (1 \leq i \leq N) should be `W` if Vertex i is assigned white and `B` if it is assigned black.
* The (i + 1)-th line (1 \leq i \leq M) should contain the integer weight C_i assigned to Edge i.

Examples

Input

5 5
3 4 3 5 7
1 2
1 3
3 2
4 2
4 5


Output

BWWBB
4
3
1
5
2


Input

5 7
1 2 3 4 5
1 2
1 3
1 4
2 3
2 5
3 5
4 5


Output

-1


Input

4 6
1 1 1 1
1 2
1 3
1 4
2 3
2 4
3 4


Output

BBBW
1
1
1
2
1
1

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=(a),_ed=(b);i<=_ed;++i)
#define DREP(i,a,b) for(int i=(a),_ed=(b);i>=_ed;--i)
typedef long long ll;
inline int read(){
    register int x=0,f=1;register char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
    while(isdigit(ch)){x=x*10+(ch^'0');ch=getchar();}
    return f?x:-x;
}

#define fail return puts("-1"),0;
const int N=1e5+5,inf=1e9;
const char ch[]="BW";
int n,m,d[N],num=1,head[N],w[N<<1],col[N],fa[N];
struct edge{int to,next,vis;} e[N<<2];
inline void add(int u,int v){
    e[++num]=(edge){v,head[u]},head[u]=num;
    e[++num]=(edge){u,head[v]},head[v]=num;
}

inline void dfs(int u){
    for(int i=head[u];i;i=e[i].next){
	int v=e[i].to;if(!e[i].vis||~col[v])continue;
	col[v]=1-col[u];dfs(v);
    }
}

int main(){
    //freopen("in.in","r",stdin);
    n=read(),m=read();
    REP(i,1,n)d[i]=read();
    REP(i,1,m)add(read(),read()),w[i]=inf;
    REP(u,1,n){
	if(!head[u])fail;
	int p=head[u];
	for(int i=e[p].next;i;i=e[i].next){
	    if(d[e[i].to]<d[e[p].to])p=i;
	    else if(d[e[i].to]==d[e[p].to]&&e[i].to<e[p].to)p=i;
	}
	if(d[e[p].to]>d[u])fail;
	e[p^1].vis=1;w[p>>1]=d[u];fa[u]=e[p].to;
    }
    memset(col,-1,sizeof col);
    REP(i,1,n)if(fa[fa[i]]==i&&!~col[i])col[i]=0,dfs(i);
    REP(i,1,n)putchar(ch[col[i]]);
    puts("");
    REP(i,1,m)printf("%d\n",w[i]);
    return 0;
}