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;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXN = 100000;
const int MAXM = 100000;
int n, m;
char s[MAXN + 1];
int e[MAXM][2];
int ans[MAXM];
vector<pair<int, int>> adj[MAXN];
int par[MAXN], parid[MAXN], dep[MAXN];
bool intree[MAXM];
int sum[MAXN];
void dfs(int at) {
  for (int i = (0); i < (((int)(adj[at]).size())); ++i) {
    int to = adj[at][i].first, id = adj[at][i].second;
    if (par[to] != -2) continue;
    par[to] = at, parid[to] = id, dep[to] = dep[at] + 1;
    dfs(to);
  }
}
void dfs3(int at) {
  sum[at] = 0;
  for (int i = (0); i < (((int)(adj[at]).size())); ++i) {
    int to = adj[at][i].first, id = adj[at][i].second;
    if (par[to] != -2 || !intree[id]) continue;
    par[to] = at, parid[to] = id, dep[to] = dep[at] + 1;
    dfs3(to);
    sum[at] = (sum[at] + ans[id]) % 3;
  }
  if (parid[at] != -1) {
    int want = s[at] - 'X';
    ans[parid[at]] = (want + 3 - sum[at]) % 3;
    sum[at] = (sum[at] + ans[parid[at]]) % 3;
    assert(sum[at] == want);
  }
}
void dfs2(int at) {
  sum[at] = 0;
  for (int i = (0); i < (((int)(adj[at]).size())); ++i) {
    int to = adj[at][i].first, id = adj[at][i].second;
    if (par[to] != -2 || !intree[id]) continue;
    par[to] = at, parid[to] = id, dep[to] = dep[at] + 1;
    dfs2(to);
    sum[at] = (sum[at] + ans[id]) % 3;
  }
  if (parid[at] != -1) {
    int want = dep[at] % 2;
    ans[parid[at]] = (want + 3 - sum[at]) % 3;
    sum[at] = (sum[at] + ans[parid[at]]) % 3;
    assert(sum[at] == want);
  }
}
void solve() {
  for (int i = (0); i < (n); ++i) adj[i].clear();
  for (int i = (0); i < (m); ++i)
    for (int j = (0); j < (2); ++j)
      adj[e[i][j]].push_back(make_pair(e[i][1 - j], i));
  for (int i = (0); i < (n); ++i) par[i] = -2;
  par[0] = -1, parid[0] = -1, dep[0] = 0;
  dfs(0);
  for (int i = (0); i < (n); ++i) assert(par[i] != -2);
  for (int i = (0); i < (m); ++i) intree[i] = false;
  for (int i = (0); i < (n); ++i)
    if (par[i] != -1) intree[parid[i]] = true;
  vector<pair<int, int>> oddcyc;
  for (int i = (0); i < (m); ++i)
    if (!intree[i]) {
      int a = e[i][0], b = e[i][1];
      if (dep[a] % 2 != dep[b] % 2) continue;
      vector<int> apath, bpath;
      while (a != b)
        if (dep[a] >= dep[b])
          apath.push_back(a), a = par[a];
        else
          bpath.push_back(b), b = par[b];
      reverse(bpath.begin(), bpath.end());
      for (int j = (0); j < (((int)(apath).size())); ++j) {
        int x = apath[j];
        oddcyc.push_back(make_pair(x, parid[x]));
      }
      oddcyc.push_back(make_pair(a, -1));
      for (int j = (0); j < (((int)(bpath).size())); ++j) {
        int x = bpath[j];
        oddcyc.push_back(make_pair(x, parid[x]));
      }
      for (int j = (((int)(apath).size()) + 1); j < (((int)(oddcyc).size()));
           ++j)
        oddcyc[j - 1].second = oddcyc[j].second;
      oddcyc[((int)(oddcyc).size()) - 1].second = i;
      assert(((int)(oddcyc).size()) % 2 == 1);
      break;
    }
  if (((int)(oddcyc).size()) == 0) {
    int root = 0;
    for (int i = (0); i < (n); ++i) par[i] = -2;
    for (int i = (0); i < (m); ++i) ans[i] = 0;
    par[root] = -1, parid[root] = -1, dep[root] = 0;
    dfs2(root);
    if (sum[root] == 1) {
      for (int i = (0); i < (m); ++i)
        if (!intree[i] && (e[i][0] == root || e[i][1] == root)) {
          int oth = e[i][0] + e[i][1] - root;
          assert(dep[oth] % 2 == 1 && sum[oth] == 1);
          ans[i] = (ans[i] + 1) % 3;
          sum[root] = sum[oth] = 2;
        }
    }
  } else {
    int root = oddcyc[0].first;
    for (int i = (0); i < (n); ++i) par[i] = -2;
    for (int i = (0); i < (m); ++i) ans[i] = 0;
    par[root] = -1, parid[root] = -1, dep[root] = 0;
    dfs3(root);
    for (int i = (0); i < (n); ++i) assert(par[i] != -2);
    int wantroot = s[root] - 'X';
    int delta = (wantroot + 3 - sum[root]) % 3, x = 2 * delta % 3;
    for (int i = (0); i < (((int)(oddcyc).size())); ++i) {
      int id = oddcyc[i].second;
      ans[id] = (ans[id] + (i % 2 == 0 ? x : 3 - x)) % 3;
    }
    sum[root] = (sum[root] + 2 * x) % 3;
  }
  for (int i = (0); i < (m); ++i)
    if (ans[i] == 0) ans[i] = 3;
  vector<int> chk(n, 0);
  for (int at = (0); at < (n); ++at)
    for (int i = (0); i < (((int)(adj[at]).size())); ++i)
      chk[at] += ans[adj[at][i].second];
}
void run() {
  scanf("%d%d", &n, &m);
  scanf("%s", s);
  assert(strlen(s) == n);
  for (int i = (0); i < (m); ++i)
    for (int j = (0); j < (2); ++j) scanf("%d", &e[i][j]);
  solve();
  for (int i = (0); i < (m); ++i)
    printf("%d %d %d\n", e[i][0], e[i][1], ans[i]);
}
int main() {
  run();
  return 0;
}