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;
template <typename T>
void read(T &x) {
  T flag = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') flag = -1;
  for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  x *= flag;
}
const int maxn = 100005;
struct e {
  int u, v, val;
} ans[maxn];
int n, m;
char s[maxn];
int col[maxn], f[maxn], val[maxn], d[maxn];
vector<pair<int, int>> vec[maxn], t[maxn];
bool vis[maxn];
int tmp[maxn];
int flag, End;
int pre[maxn], num[maxn];
void print(int x, int y, int z) { printf("%d %d %d\n", x, y, z); }
void dfs(int x, int fa, int id) {
  f[x] = fa;
  if (fa) t[x].push_back(make_pair(fa, id));
  for (int i = 0; i < (int)vec[x].size(); i++) {
    int y = vec[x][i].first;
    if (f[y] > 0 || y == flag) continue;
    t[x].push_back(make_pair(y, vec[x][i].second));
    dfs(y, x, vec[x][i].second);
  }
}
void get_ans(int x) {
  for (int i = 0; i < (int)t[x].size(); i++) {
    int y = t[x][i].first;
    if (y == f[x]) continue;
    get_ans(y);
    int m = col[y] - d[y];
    ans[t[x][i].second].val = m;
    d[y] = d[y] + m;
    d[x] = d[x] + m;
  }
}
void get_ans2(int x) {
  for (int i = 0; i < (int)t[x].size(); i++) {
    int y = t[x][i].first;
    if (y == f[x]) continue;
    get_ans2(y);
    int m = tmp[y] - d[y];
    ans[t[x][i].second].val = m;
    d[y] = d[y] + m;
    d[x] = d[x] + m;
  }
}
void check(int x) {
  for (int i = 0; i < (int)vec[x].size(); i++) {
    int y = vec[x][i].first;
    if (tmp[y] == -1)
      tmp[y] = tmp[x] ^ 1, check(y);
    else {
      if (tmp[y] == tmp[x]) {
        flag = x;
      }
    }
  }
}
void yyy(int x) {
  for (int i = 0; i < (int)vec[x].size(); i++) {
    int y = vec[x][i].first;
    if (tmp[y] != -1) continue;
    tmp[y] = tmp[x] ^ 1;
    yyy(y);
  }
}
int cnt[maxn];
void output() {
  for (int i = 1; i <= m; i++) {
    ans[i].val = (ans[i].val % 3 + 3) % 3;
    if (ans[i].val == 0) ans[i].val = 3;
    print(ans[i].u, ans[i].v, ans[i].val);
    cnt[ans[i].u] += ans[i].val;
    cnt[ans[i].v] += ans[i].val;
  }
}
void jjj(int x) {
  for (int i = 0; i < (int)vec[x].size(); i++) {
    int y = vec[x][i].first;
    if (tmp[y] == -1)
      tmp[y] = tmp[x] ^ 1, pre[y] = x, num[y] = vec[x][i].second, jjj(y);
    else {
      if (y == flag && tmp[x] == tmp[flag]) {
        End = x;
      }
    }
  }
}
void work() {
  tmp[1] = 0;
  check(1);
  if (flag) {
    dfs(flag, 0, 0);
    get_ans(flag);
    int m = (col[flag] - d[flag]);
    memset(tmp, -1, sizeof(tmp));
    tmp[flag] = 0;
    jjj(flag);
    for (int i = End; i != flag; i = pre[i]) {
      ans[num[i]].val += m;
      m = -m;
    }
    for (int i = 0; i < (int)vec[End].size(); i++) {
      if (vec[End][i].first == flag) ans[vec[End][i].second].val += m << 1;
    }
    output();
  } else {
    flag = 1;
    memset(tmp, -1, sizeof(tmp));
    tmp[1] = 0;
    yyy(flag);
    dfs(flag, 0, 0);
    get_ans2(flag);
    if ((d[1] % 3 + 3) % 3 == 1 && vec[1].size() > 1) {
      ans[vec[1][1].second].val++;
      ans[vec[1][2].second].val++;
    }
    output();
  }
}
int main() {
  memset(tmp, -1, sizeof(tmp));
  read(n);
  read(m);
  scanf("%s", s + 1);
  for (int i = 1; i <= n; i++) {
    col[i] = s[i] - 'X';
  }
  for (int i = 1; i <= m; i++) {
    int u, v;
    read(u);
    read(v);
    ans[i].u = u;
    ans[i].v = v;
    u++;
    v++;
    vec[u].push_back(make_pair(v, i));
    vec[v].push_back(make_pair(u, i));
  }
  for (int i = 1; i <= n; i++) reverse(vec[i].begin(), vec[i].end());
  work();
  return 0;
}