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;

template <class T>inline T updmax(T& a, T b) {return a = max(a, b);}
template <class T>inline T updmin(T& a, T b) {return a = min(a, b);}

struct edge{
	int from, to;
	edge(int from, int to):from(from), to(to){}
};
using node = vector<edge>;
using graph = vector<node>;
void addedge(graph &g, int from, int to, bool bidirectional = false){
	g[from].emplace_back(edge(from, to));
	if(bidirectional)g[to].emplace_back(edge(to, from));
}

class Solution {
public:
	void No(){
		cout << -1 << endl;
		return;
	}

	void solve() {
		int n, m;
		cin >> n >> m;
		vector<int> d(n);
		vector<pair<int,int>> di(n);
		for(int i=0; i<n; i++)cin >> d[i];
		for(int i=0; i < n; i++)di[i] = make_pair(d[i], i);
		sort(di.begin(), di.end());
		if(di[0].first != di[1].first)return No();
		vector<int> color(n, -1);
		map<pair<int, int>, int> etoi;
		graph g(n);
		for(int i=0; i < m; i++){
			int u, v;
			cin >> u >> v;
			u--, v--;
			etoi[make_pair(u, v)] = i;
			etoi[make_pair(v, u)] = i;
			addedge(g, u, v, true);
		}
		vector<int> w(m, 1000000000);
		for(int i=0; i < n; i++){
			int u = di[i].second;
			int x = di[i].first;
			if(color[u] != -1)continue;
			for(auto e:g[u]){
				if(color[e.to] != -1){
					color[u] = 1-color[e.to];
					w[etoi[make_pair(u, e.to)]] = x;
					break;
				}
				else if(d[u] == d[e.to]){
					color[u] = 0;
					color[e.to] = 1;
					w[etoi[make_pair(u, e.to)]] = x;
					break;					
				}
			}
			if(color[u] == -1)return No();
		}
		for(int i=0; i < n; i++){
			if(color[i])cout << "B";
			else cout << "W";
		}
		cout << "\n";
		for(int i=0; i<m; i++)cout << w[i] << " ";
		cout << "\n";
		
		return;
	};
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	Solution solution;
	solution.solve();
	return 0;
}