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;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 100100;
int n, m;
int ed[N][3];
vector<int> g[N];
char t[N];
int h[N];
int par[N];
int col[N];
bool used[N];
void printAns() {
  for (int i = 0; i < m; i++) {
    int x = ed[i][2];
    x %= 3;
    while (x <= 0) x += 3;
    printf("%d %d %d\n", ed[i][0], ed[i][1], x);
  }
  exit(0);
}
int getOther(int id, int v) { return ed[id][0] ^ ed[id][1] ^ v; }
void dfsSolve(int v) {
  for (int id : g[v]) {
    int u = getOther(id, v);
    if (used[u]) continue;
    used[u] = true;
    dfsSolve(u);
    ed[id][2] = col[u];
    col[u] -= ed[id][2];
    col[v] -= ed[id][2];
    if (col[v] < 0) col[v] += 3;
  }
}
void solveOdd(int id) {
  int v = ed[id][0], u = ed[id][1];
  if (h[v] < h[u]) swap(v, u);
  vector<pair<int, int> > cyc;
  while (v != u) {
    cyc.push_back(make_pair(v, par[v]));
    v = getOther(par[v], v);
  }
  cyc.push_back(make_pair(u, id));
  int sz = (int)cyc.size();
  for (int i = 0; i < sz; i++) {
    42;
  }
  for (int i = 0; i < n; i++) col[i] = (int)(t[i] - 'X');
  for (int i = 0; i < sz; i++) used[cyc[i].first] = true;
  for (int i = 0; i < sz; i++) dfsSolve(cyc[i].first);
  int sum = 0;
  for (int i = 0; i < sz; i++) sum += col[cyc[i].first];
  if (sum & 1) sum += 3;
  sum /= 2;
  for (int i = 2; i < sz; i += 2) sum -= col[cyc[i].first];
  sum %= 3;
  if (sum < 0) sum += 3;
  ed[cyc[0].second][2] = sum;
  for (int i = 1; i < sz; i++) {
    int x = col[cyc[i].first] - ed[cyc[i - 1].second][2];
    if (x < 0) x += 3;
    ed[cyc[i].second][2] = x;
  }
  printAns();
}
void solveEven(int id) {
  int v = ed[id][0], u = ed[id][1];
  if (h[v] < h[u]) swap(v, u);
  vector<pair<int, int> > cyc;
  while (v != u) {
    cyc.push_back(make_pair(v, par[v]));
    v = getOther(par[v], v);
  }
  cyc.push_back(make_pair(u, id));
  int sz = (int)cyc.size();
  for (int i = 0; i < n; i++) col[i] = h[i] & 1;
  if (col[cyc[0].first] == 1) rotate(cyc.begin(), cyc.begin() + 1, cyc.end());
  for (int i = 0; i < sz; i++) used[cyc[i].first] = true;
  for (int i = 0; i < sz; i++) dfsSolve(cyc[i].first);
  int bal = 0;
  for (int i = 0; i < sz; i++) {
    int x = col[cyc[i].first];
    if (i % 2 == 0)
      bal += x;
    else
      bal -= x;
  }
  bal %= 3;
  if (bal < 0) bal += 3;
  if (bal == 1) {
    int v = cyc[0].first;
    col[v]--;
    if (col[v] < 0) col[v] += 3;
  } else if (bal == 2) {
    for (int i = 0; i < 3; i += 2) {
      int v = cyc[i].first;
      col[v]--;
      if (col[v] < 0) col[v] += 3;
    }
  }
  for (int i = 1; i < sz; i++) {
    int x = col[cyc[i].first] - ed[cyc[i - 1].second][2];
    if (x < 0) x += 3;
    ed[cyc[i].second][2] = x;
  }
  printAns();
}
void dfs1(int v) {
  for (int id : g[v]) {
    int u = getOther(id, v);
    if (h[u] == -1) {
      h[u] = h[v] + 1;
      par[u] = id;
      dfs1(u);
    } else if (h[v] % 2 == h[u] % 2) {
      solveOdd(id);
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  scanf("%s", t);
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < 2; j++) {
      scanf("%d", &ed[i][j]);
      g[ed[i][j]].push_back(i);
    }
  }
  for (int i = 0; i < n; i++) h[i] = -1;
  for (int i = 0; i < n; i++) {
    if ((int)g[i].size() == 1) {
      for (int j = 0; j < n; j++) col[j] = (int)(t[j] - 'X');
      dfsSolve(i);
      printAns();
    }
  }
  h[0] = 0;
  dfs1(0);
  for (int v = 0; v < n; v++) {
    for (int id : g[v]) {
      if (par[v] == id) continue;
      int u = getOther(id, v);
      if (h[u] < h[v]) solveEven(id);
    }
  }
  throw;
  return 0;
}