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 int;
using ull = unsigned long long int;
using P = pair<int, int>;
using P3 = pair<int,P>;
using PP = pair<P ,P>;
constexpr ll MOD = ll(1e9+7);
constexpr int IINF = INT_MAX;
constexpr ll LLINF = LLONG_MAX;
constexpr int MAX_N = int(1e6) + 5;
constexpr double EPS = 1e-8;
constexpr int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define SORTR(v) sort((v).rbegin(), (v).rend())
#define ALL(v) (v).begin(), (v).end()

int n, m;
vector<ll> d, len, color;
vector<P> ord;
vector<vector<P> > g;
vector<bool> used;

int main(){
    cin >> n >> m;
    d.resize(n);
    g.resize(n);
    used.resize(n);
    color.resize(n,-1);
    len.resize(m);
    for(int i=0;i<n;i++){
        cin >> d[i];
        ord.push_back(P(d[i],i));
    }
    for(int i=0;i<m;i++){
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].push_back(P(v,i));
        g[v].push_back(P(u,i));
    }
    SORT(ord);
    bool ok = true;
    for(int i=0;i<n;i++){
        int idx = ord[i].second;
        if(used[idx]) continue;
        for(auto &e : g[idx]){
            int v = e.first;
            if(d[v] <= d[idx]){
                len[e.second] = d[idx];
                if(used[v]){
                    color[idx] = color[v]^1;
                }else{
                    color[idx] = 0;
                    color[v] = 1;
                    used[v] = true;
                }
                used[idx] = true;
                break;
            }
        }
        if(!used[idx]) ok = false;
    }
    if(ok){
        for(int i=0;i<n;i++){
            cout << (color[i]==0 ? 'W' : 'B');
        }
        cout << endl;
        for(int i=0;i<m;i++){
            cout << (len[i]>0 ? len[i] : int(1e9)) << endl;
        }
    }else{
        cout << -1 << endl;
    }
    return 0;
}