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>
int n, m;
char s[100005];
int hd[100005], _hd = 1;
struct edge {
  int v, nxt;
} e[100005 << 1];
inline void addedge(int u, int v) {
  e[++_hd] = (edge){v, hd[u]};
  hd[u] = _hd;
}
int a[100005], b[100005], c[100005];
int ans[100005];
int x, y, z, f[100005];
bool vis[100005];
inline void dfs1(int u) {
  vis[u] = 1;
  for (int i = hd[u]; i; i = e[i].nxt) {
    int v = e[i].v;
    if (vis[v]) {
      if (c[u] == c[v]) x = u, y = v;
      continue;
    }
    c[v] = c[u] ^ 1;
    dfs1(v);
    a[u] += (ans[i >> 1] = c[v] - a[v]);
    a[v] = c[v];
  }
}
bool flg[100005];
inline void dfs2(int u) {
  flg[u] = 1;
  a[u] = 0;
  for (int i = hd[u]; i; i = e[i].nxt) {
    int v = e[i].v;
    if (u == x && v == y) {
      z = i;
      continue;
    }
    if (flg[v]) {
      ans[i >> 1] = 0;
      continue;
    }
    f[v] = i ^ 1;
    dfs2(v);
    a[u] += (ans[i >> 1] = b[v] - a[v]);
    a[v] = b[v];
  }
}
int main() {
  scanf("%d%d%s", &n, &m, s + 1);
  for (int i = 1; i <= n; i++) b[i] = s[i] - 'X';
  for (int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    addedge(++u, ++v);
    addedge(v, u);
  }
  for (int i = 1; i <= n; i++)
    if (!vis[i]) {
      x = 0;
      dfs1(i);
      if (x) {
        dfs2(x);
        int tmp = (b[x] - a[x]) << 1;
        ans[z >> 1] += tmp;
        for (; y != x; y = e[f[y]].v) ans[f[y] >> 1] += (tmp = -tmp);
      } else if ((a[i] % 3 + 3) % 3 == 1 && e[hd[i]].nxt)
        ans[hd[i] >> 1]++, ans[e[hd[i]].nxt >> 1]++;
    }
  for (int i = 1; i <= m; i++) {
    int tmp = (ans[i] % 3 + 3) % 3;
    printf("%d %d %d\n", e[i << 1].v - 1, e[i << 1 | 1].v - 1, tmp ? tmp : 3);
  }
}