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;
using ll=long long;
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

int n,m,a,b;
vector<int> d,ans;
vector<vector<pair<int,int>>> v;
vector<bool> vs,c;

void rec(int i,bool f=false){
    if(vs[i]) return;
    vs[i]=true;
    c[i]=f;
    for(auto&j:v[i]) if(ans[j.second]!=-1){
        rec(j.first,!f);
    }
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    istream& in(cin);
    ostream& out(cout);
    in>>n>>m;
    d.resize(n);v.resize(n);
    for(auto&i:d) in>>i;
    fr(i,m){
        in>>a>>b;
        --a,--b;
        v[a].emplace_back(b,i);
        v[b].emplace_back(a,i);
    }
    fr(i,n){
        sort(v[i].begin(),v[i].end(),[&](pair<int,int> x,pair<int,int> y){
            return d[x.first]<d[y.first];
        });
        if(d[i]<d[v[i][0].first]) return cout<<-1<<endl,0;
    }
    c.resize(n);
    ans.resize(m,-1);
    vector<int> vis(n,-1);
    fr(i,n){
        if(vis[i]==d[i]) continue;
        int j,e;
        tie(j,e)=v[i][0];
        vis[j]=ans[e]=d[i];
    }
    vs.resize(n);
    fr(i,n) rec(i);
    fr(i,n) cout<<(c[i]?"B":"W");
    cout<<endl;
    fr(i,m) cout<<(ans[i]==-1?1000000000:ans[i])<<endl;
}