Problem: Three planets X, Y and Z within the Alpha planetary system are inhabited with an advanced civilization. The spaceports of these planets are connected by interplanetary space shuttles. The flight scheduler should decide between 1, 2 and 3 return flights for every existing space shuttle connection. Since the residents of Alpha are strong opponents of the symmetry, there is a strict rule that any two of the spaceports connected by a shuttle must have a different number of flights. 

For every pair of connected spaceports, your goal is to propose a number 1, 2 or 3 for each shuttle flight, so that for every two connected spaceports the overall number of flights differs. 

You may assume that:

1) Every planet has at least one spaceport 

2) There exist only shuttle flights between spaceports of different planets 

3) For every two spaceports there is a series of shuttle flights enabling traveling between them

4) Spaceports are not connected by more than one shuttle

Input

The first row of the input is the integer number N (3 ≤ N ≤ 100 000), representing overall number of spaceports. The second row is the integer number M (2 ≤ M ≤ 100 000) representing number of shuttle flight connections. 

Third row contains N characters from the set \\{X, Y, Z\}. Letter on I^{th} position indicates on which planet is situated spaceport I. For example, "XYYXZZ" indicates that the spaceports 0 and 3 are located at planet X, spaceports 1 and 2 are located at Y, and spaceports 4 and 5 are at Z. 

Starting from the fourth row, every row contains two integer numbers separated by a whitespace. These numbers are natural numbers smaller than N and indicate the numbers of the spaceports that are connected. For example, "12\ 15" indicates that there is a shuttle flight between spaceports 12 and 15. 

Output

The same representation of shuttle flights in separate rows as in the input, but also containing a third number from the set \{1, 2, 3\} standing for the number of shuttle flights between these spaceports.

Example

Input


10
15
XXXXYYYZZZ
0 4
0 5
0 6
4 1
4 8
1 7
1 9
7 2
7 5
5 3
6 2
6 9
8 2
8 3
9 3


Output


0 4 2
0 5 2
0 6 2
4 1 1
4 8 1
1 7 2
1 9 3
7 2 2
7 5 1
5 3 1
6 2 1
6 9 1
8 2 3
8 3 1
9 3 1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int N, M;
int x[MAXN], y[MAXN];
vector<pair<int, int> > adj[MAXN], ch[MAXN];
char part[MAXN];
int label[MAXN];
int clr[MAXN];
int ans[MAXN];
void load() {
  scanf("%d%d%s", &N, &M, part);
  for (int i = 0; i < M; i++) {
    scanf("%d%d", x + i, y + i);
    adj[x[i]].push_back({y[i], i});
    adj[y[i]].push_back({x[i], i});
  }
}
pair<int, int> dfs(int x, int p, int c) {
  clr[x] = c;
  pair<int, int> res = {-1, -1};
  for (auto it : adj[x])
    if (clr[it.first] == -1) {
      ch[x].push_back(it);
      pair<int, int> tmp = dfs(it.first, x, c ^ 1);
      if (tmp.first != -1) res = tmp;
    } else if (clr[it.first] == clr[x])
      res = {x, it.second};
  return res;
}
void add(int &x, int y) {
  x += y;
  if (x >= 3)
    x -= 3;
  else if (x < 0)
    x += 3;
}
int calc(int x) {
  int curr = label[x];
  for (auto it : ch[x]) {
    int tmp = calc(it.first);
    ans[it.second] = tmp;
    add(curr, -tmp);
  }
  return curr;
}
void finish() {
  vector<int> sum(N, 0);
  for (int i = 0; i < M; i++) {
    if (!ans[i]) ans[i] = 3;
    printf("%d %d %d\n", x[i], y[i], ans[i]);
    sum[x[i]] += ans[i];
    sum[y[i]] += ans[i];
  }
  for (int i = 0; i < M; i++) assert(sum[x[i]] != sum[y[i]]);
  exit(0);
}
void bipartite() {
  vector<int> v[2];
  for (int i = 0; i < N; i++) v[clr[i]].push_back(i);
  int big = v[0].size() > v[1].size() ? 0 : 1;
  int sz = v[big].size();
  int twos = sz % 2 ? (sz - 3) / 2 : sz / 2;
  for (int i = 0; i < sz; i++) label[v[big][i]] = (i < twos) + 1;
  assert(!calc(0));
  finish();
}
void solve() {
  for (int i = 0; i < N; i++) label[i] = part[i] - 'X';
  memset(clr, -1, sizeof clr);
  pair<int, int> edge = dfs(0, -1, 0);
  if (edge.first == -1) bipartite();
  for (int i = 0; i < 3; i++) {
    ans[edge.second] = i;
    int u = edge.first;
    int v = x[edge.second] ^ y[edge.second] ^ u;
    add(label[u], -i);
    add(label[v], -i);
    if (!calc(0)) finish();
    add(label[u], i);
    add(label[v], i);
  }
  assert(false);
}
int main() {
  load();
  solve();
  return 0;
}