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>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
using namespace std;
using ll = long long;
using vi = vector<ll>;
using pi = pair<ll, ll>;
const int maxn = 2e5 + 33, mod = 1e9 + 7;
int n, m, d[maxn], col[maxn];
vector<vi> g;
vector<pi> e;
queue<int> q;
map<pi, int> cost;
pi minmax(pi a) {
	if(a.second<a.first) swap(a.second, a.first);
	return a;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		cin >> d[i];
	}
	g.resize(n+1);
	for(int f, t, i = 0; i < m; i++) {
		cin >> f >> t;
		g[f].pb(t);
		g[t].pb(f);
		e.pb({f, t});
		if(d[f]==d[t]&&(!col[f]||!col[t])) {
			if(!col[f])
				q.push(f);
			if(!col[t])
				q.push(t);
			if(col[t])
				col[f]=col[t]^3;
			else if(col[f])
				col[t]=col[f]^3;
			else
				col[t] = 1, col[f] = 2;
			cost[minmax({f, t})] = d[f];
		}
	}
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		for(auto i : g[u]) {
			if(col[i]||d[i]<d[u]) continue;
			col[i] = col[u];
			cost[minmax({u, i})] = d[i]-d[u];
			q.push(i);
		}
	}
	for(int i = 1; i <= n; i++) if(!col[i]) return cout << -1, 0;
	for(int i = 1; i <= n; i++) cout << ("BW"[col[i]-1]);
	cout << '\n';
	for(auto i : e) {
		if(!cost.count(minmax(i))) cout << "1000000000\n";
		else cout << cost[minmax(i)] << '\n';
	}
}