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>
const int N = 1e5 + 10;
inline int read() {
  int x = 0, f = 0;
  char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  return f ? -x : x;
}
int a[N], s[N], w[N], d[N], u[N], v[N];
std::vector<std::pair<int, int>> G[N];
int col[N], par[N], vis[N], flg, U, V;
inline void check(int u) {
  for (auto dat : G[u]) {
    int v = dat.first;
    if (col[v] == col[u]) return flg = 1, U = v, V = u, void();
    if (col[v] == -1) par[v] = u, col[v] = col[u] ^ 1, check(v);
    if (flg) return;
  }
}
inline void solve(int u) {
  vis[u] = 1;
  for (auto dat : G[u]) {
    int v = dat.first, i = dat.second;
    if (!vis[v]) solve(v), w[i] = ((col[v] - s[v]) % 3 + 3) % 3, s[u] += w[i];
  }
}
inline void Solve(int u) {
  vis[u] = 1;
  for (auto dat : G[u]) {
    int v = dat.first, i = dat.second;
    if (!vis[v]) Solve(v), w[i] = ((a[v] - s[v]) % 3 + 3) % 3, s[u] += w[i];
  }
}
std::pair<int, int> nex[N], pre[N];
int main() {
  int n = read(), m = read();
  for (int i = 1; i <= n; ++i) {
    char ch = getchar();
    while (ch != 'X' && ch != 'Y' && ch != 'Z') ch = getchar();
    a[i] = ch - 'X';
  }
  for (int i = 1; i <= m; ++i) {
    int u = read() + 1, v = read() + 1;
    G[u].emplace_back(v, i), ::u[i] = u;
    G[v].emplace_back(u, i), ::v[i] = v;
  }
  memset(col, -1, sizeof(col));
  col[1] = 0, check(1);
  if (flg) {
    int u = U, lst = V, v = par[V];
    std::vector<std::pair<int, int>> cir;
    for (; v != par[U]; lst = v, v = par[v]) {
      for (auto e : G[v])
        if (e.first == lst) nex[v] = e;
      for (auto e : G[lst])
        if (e.first == v) pre[lst] = e;
    }
    for (auto e : G[V])
      if (e.first == U) nex[V] = e;
    for (auto e : G[U])
      if (e.first == V) pre[U] = e;
    Solve(u);
    while (s[u] != a[u]) {
      int p1 = U, p2 = U, x = 1;
      while (nex[p1].first != p2) {
        w[nex[p1].second] += x, w[pre[p2].second] += x;
        p1 = nex[p1].first, p2 = pre[p2].first, x = -x;
      }
      w[nex[p1].second] += x;
      s[u] = (s[u] + 2) % 3;
    }
  } else {
    int rt = 0;
    for (int i = 1; i <= n; ++i)
      if (col[i] == 0) {
        rt = i;
        break;
      }
    solve(rt);
    int cnt = 0;
    if (s[rt] % 3 == 1 && G[rt].size() > 1)
      for (int i = 0; i < 2; ++i) w[G[rt][i].second]++, ++cnt;
  }
  for (int i = 1; i <= m; ++i) w[i] = (w[i] % 3 + 3) % 3;
  for (int i = 1; i <= m; ++i)
    printf("%d %d %d\n", u[i] - 1, v[i] - 1, w[i] ? w[i] : 3);
  return 0;
}