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 rep(i, n) for (int i = 0; i < (n); i++)

template<class T>
using minheap = priority_queue<T, vector<T>, greater<T>>;

int main() {
  int N, M; cin >> N >> M;
  vector<int> D(N); rep(i, N) cin >> D[i];
  vector<int> U(M), V(M);
  vector<vector<int>> G(N);
  rep(i, M) {
    cin >> U[i] >> V[i]; U[i]--; V[i]--;
    G[U[i]].push_back(i);
    G[V[i]].push_back(i);
  }
  vector<set<int>> T(N);
  vector<bool> vis(N);
  vector<int> color(N, -1);
  constexpr int INF = 1e9;
  vector<int> ans(M, INF + 1);
  rep(i, N) {
    pair<int, int> mn(INF, INF);
    for (int k : G[i]) {
      int j = U[k] ^ V[k] ^ i;
      mn = min(mn, make_pair(D[j], k));
    }
    ans[mn.second] = D[i];
  }
  rep(i, N) if (color[i] == -1) {
    color[i] = 0;
    queue<int> q;
    q.push(i);
    while (not q.empty()) {
      int v = q.front(); q.pop();
      for (int j : G[v]) if (ans[j] <= INF) {
        int u = U[j] ^ V[j] ^ v;
        if (color[u] == -1) {
          color[u] = color[v] ^ 1;
          q.push(u); 
        }
      }
    }
  }
  rep(i, M) ans[i] = min(ans[i], INF);
  for (int ii = 0; ii < 2; ii++) {
    constexpr ll INFL = 1e18;
    vector<ll> dist(N, INFL);
    minheap<pair<ll, int>> heap;
    rep(i, N) if (color[i] == ii) {
      dist[i] = 0;
      heap.emplace(0, i);
    }
    while (not heap.empty()) {
      ll d;
      int u;
      tie(d, u) = heap.top(); heap.pop();
      if (d > dist[u]) continue;
      for (int i : G[u]) {
        int v = U[i] ^ V[i] ^ u;
        if (dist[v] > dist[u] + ans[i]) {
          dist[v] = dist[u] + ans[i];
          heap.emplace(dist[v], v);
        }
      }
    }
    rep(i, N) if (color[i] == 1 - ii and dist[i] != D[i]) {
      cout << -1 << endl;
      return 0;
    }
  }
  rep(i, N) cout << (color[i] ? 'B' : 'W');
  cout << endl;
  rep(i, M) {
    cout << ans[i] << '\n';
  }
}