Problem: This is an interactive problem.

The judge has a hidden rooted full binary tree with n leaves. A full binary tree is one where every node has either 0 or 2 children. The nodes with 0 children are called the leaves of the tree. Since this is a full binary tree, there are exactly 2n - 1 nodes in the tree. The leaves of the judge's tree has labels from 1 to n. You would like to reconstruct a tree that is isomorphic to the judge's tree. To do this, you can ask some questions.

A question consists of printing the label of three distinct leaves a1, a2, a3. Let the depth of a node be the shortest distance from the node to the root of the tree. Let LCA(a, b) denote the node with maximum depth that is a common ancestor of the nodes a and b.

Consider X = LCA(a1, a2), Y = LCA(a2, a3), Z = LCA(a3, a1). The judge will tell you which one of X, Y, Z has the maximum depth. Note, this pair is uniquely determined since the tree is a binary tree; there can't be any ties. 

More specifically, if X (or Y, Z respectively) maximizes the depth, the judge will respond with the string "X" (or "Y", "Z" respectively). 

You may only ask at most 10·n questions.

Input

The first line of input will contain a single integer n (3 ≤ n ≤ 1 000) — the number of leaves in the tree.

Output

To print the final answer, print out the string "-1" on its own line. Then, the next line should contain 2n - 1 integers. The i-th integer should be the parent of the i-th node, or -1, if it is the root.

Your answer will be judged correct if your output is isomorphic to the judge's tree. In particular, the labels of the leaves do not need to be labeled from 1 to n. Here, isomorphic means that there exists a permutation π such that node i is the parent of node j in the judge tree if and only node π(i) is the parent of node π(j) in your tree.

Interaction

To ask a question, print out three distinct integers a1, a2, a3. These integers should be between 1 and n, inclusive.

The judge will respond with a single character, either "X", "Y", "Z". 

If the string is "X" (or "Y", "Z" respectively), that means the pair (a1, a2) (or (a2, a3), (a3, a1) respectively) has the deepest LCA among the three pairs.

You may only ask a question at most 10·n times, otherwise, you will get Wrong Answer.

When you are ready to answer, print out a single integer "-1" on its own line. The next line should contain 2n - 1 integers. The i-th integer should be the parent of the i-th node, or -1, if it is the root. Do not forget to flush the final answer as well. Printing the answer does not count as asking a question.

You will get Wrong Answer verdict if 

  * Your question or answers are not in the format described in this statement. 
  * You ask strictly more than 10·n questions. 
  * Your question contains duplicate indices. 
  * Your final answer is not isomorphic to the judge tree. 



You will get Idleness Limit Exceeded if you don't print anything or if you forget to flush the output, including for the final answer (more info about flushing output below).

To flush you can use (just after printing an integer and end-of-line): 

  * fflush(stdout) in C++; 
  * System.out.flush() in Java; 
  * stdout.flush() in Python; 
  * flush(output) in Pascal; 
  * See the documentation for other languages. 



If at any moment your program reads -1 as an answer, it should immediately exit normally (for example, by calling exit(0)). You will get Wrong Answer in this case, it means that you made more queries than allowed, or made an invalid query. If you ignore this, you can get other verdicts since your program will continue to read from a closed stream.

Hacking To hack someone, use the following format 
    
    
      
    n  
    p_1 p_2 ... p_{2n-1}  
    

This denotes a tree where the parent of the i-th node is pi (pi = - 1 or n < pi ≤ 2n - 1). If pi is equal to -1, then node i is the root. This input must describe a valid full rooted binary tree.

Of course, contestant programs will not be able to see this input.

Example

Input

5
X
Z
Y
Y
X<span class="tex-font-style-tt"></span>


Output

1 4 2
1 2 4
2 4 1
2 3 5
2 4 3
-1
-1 1 1 2 2 3 3 6 6

Note

For the first sample, the judge has the hidden tree:

<image>

Here is a more readable format of the interaction: 

<image> The last line can also be 8 6 9 8 9 7 -1 6 7. 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(0.0) * 2.0;
const long double eps = 1e-10;
const int step[8][2] = {{-1, 0}, {0, 1}, {1, 0},  {0, -1},
                        {-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
template <class T>
inline T abs1(T a) {
  return a < 0 ? -a : a;
}
template <typename t, typename t1>
t min1(t a, t1 b) {
  return a < b ? a : b;
}
template <typename t, typename... arg>
t min1(t a, arg... arr) {
  return min1(a, min1(arr...));
}
template <typename t, typename t1>
t max1(t a, t1 b) {
  return a > b ? a : b;
}
template <typename t, typename... arg>
t max1(t a, arg... arr) {
  return max1(a, max1(arr...));
}
inline int jud(double a, double b) {
  if (abs(a) < eps && abs(b) < eps)
    return 0;
  else if (abs1(a - b) / max(abs1(a), abs1(b)) < eps)
    return 0;
  if (a < b) return -1;
  return 1;
}
template <typename t>
inline int jud(t a, t b) {
  if (a < b) return -1;
  if (a == b) return 0;
  return 1;
}
template <typename it, typename t1>
inline int find(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1) {
  if (na == 0) return 0;
  int be = 0, en = na - 1;
  if (*a <= *(a + na - 1)) {
    if (f_lb == 0)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != 1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != -1)
          en = mid;
        else
          be = mid + 1;
      }
    if (f_small && jud(*(a + be), val) == 1) be--;
    if (!f_small && jud(*(a + be), val) == -1) be++;
  } else {
    if (f_lb)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != -1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != 1)
          en = mid;
        else
          be = mid + 1;
      }
    if (!f_small && jud(*(a + be), val) == -1) be--;
    if (f_small && jud(*(a + be), val) == 1) be++;
  }
  return be;
}
template <class T>
inline T lowb(T num) {
  return num & (-num);
}
inline int bitnum(unsigned int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(unsigned long long nValue) {
  return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32);
}
inline int bitnum(long long nValue) {
  return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32);
}
inline int bitmaxl(unsigned int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(unsigned long long a) {
  int temp = a >> 32;
  if (temp) return 32 - __builtin_clz(temp) + 32;
  return bitmaxl(int(a));
}
inline int bitmaxl(long long a) {
  int temp = a >> 32;
  if (temp) return 32 - __builtin_clz(temp) + 32;
  return bitmaxl(int(a));
}
long long pow(long long n, long long m, long long mod = 0) {
  if (m < 0) return 0;
  long long ans = 1;
  long long k = n;
  while (m) {
    if (m & 1) {
      ans *= k;
      if (mod) ans %= mod;
    }
    k *= k;
    if (mod) k %= mod;
    m >>= 1;
  }
  return ans;
}
template <class t>
void output1(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) cerr << arr[i] << ' ';
  cerr << endl;
}
template <class t>
void output2(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) output1(arr[i]);
}
const int maxn = 2010;
int n, fa[maxn], deep[maxn];
int getfa(int a, int b) {
  if (deep[a] < deep[b]) swap(a, b);
  while (deep[a] > deep[b]) a = fa[a];
  while (a != b) {
    a = fa[a], b = fa[b];
  }
  return deep[a];
}
int get(int a, int b, int c) {
  printf("%d %d %d\n", a + 1, b + 1, c + 1);
  fflush(stdout);
  char str[2];
  scanf("%s", str);
  return str[0] - 'X';
}
struct node {
  node *son[2], *fa;
  int sz;
  node() {
    fa = son[0] = son[1] = NULL;
    sz = 0;
  }
} rn[maxn];
int lrn;
node *getoneleaf(node *rno) {
  if (rno->son[0])
    return getoneleaf(rno->son[0]);
  else if (rno->son[1])
    return getoneleaf(rno->son[1]);
  else
    return rno;
}
void pushup(node *a) {
  if (a == NULL) return;
  a->sz = 0;
  if (a->son[0]) a->sz += a->son[0]->sz;
  if (a->son[1]) a->sz += a->son[1]->sz;
  pushup(a->fa);
}
void del(node *a) {
  if (a == NULL) return;
  node *b = a->fa;
  if (!b) return;
  int cate = 0;
  if (a == b->son[1]) cate = 1;
  a->fa = NULL;
  b->son[cate] = NULL;
  pushup(b);
}
void add(node *a, node *b) {
  int cate = 0;
  a->fa = b;
  if (b == NULL) return;
  if (b->son[0]) cate = 1;
  b->son[cate] = a;
  pushup(b);
}
node *upd(int no, node *root) {
  if (root->sz == 1) {
    node *rroot = getoneleaf(root);
    node *rt = rroot->fa;
    del(rroot);
    add(rn + lrn, rt);
    add(rroot, rn + lrn);
    add(rn + no, rn + lrn);
    lrn++;
    while (root->fa) root = root->fa;
    return root;
  }
  node *leaf1 = getoneleaf(root), *pre = NULL, *rroot = leaf1;
  for (; rroot->sz * 2 <= root->sz; pre = rroot, rroot = rroot->fa)
    ;
  node *leaf2;
  int rc = 0;
  if (pre == rroot->son[0])
    leaf2 = getoneleaf(rroot->son[1]);
  else {
    leaf2 = getoneleaf(rroot->son[0]);
    rc = 1;
  }
  int cate = get(leaf1 - rn, leaf2 - rn, no);
  if (cate == 0) {
    node *leaf1fa = leaf1->fa;
    node *rt = rroot->fa;
    del(leaf1);
    del(rroot);
    add(leaf1, rt);
    if (rt)
      upd(no, root);
    else
      upd(no, leaf1);
    node *rleaf1fa = leaf1->fa;
    del(leaf1);
    add(rroot, rleaf1fa);
    add(leaf1, leaf1fa);
    while (root->fa) root = root->fa;
    return root;
  } else if (cate == 1) {
    node *rt = rroot->son[1 - rc];
    del(rt);
    node *temp = upd(no, rt);
    add(temp, rroot);
  } else {
    node *rt = rroot->son[rc];
    del(rt);
    node *temp = upd(no, rt);
    add(temp, rroot);
  }
  return root;
}
int main() {
  ios_base::sync_with_stdio(0);
  scanf("%d", &n);
  lrn = n + 1;
  for (int i = 0; i < n; i++) rn[i].sz = 1;
  add(rn, rn + n);
  add(rn + 1, rn + n);
  node *root = rn + n;
  for (int i = 2; i < n; i++) {
    root = upd(i, root);
  }
  printf("-1");
  for (int i = 0; i < 2 * n - 1; i++)
    printf(" %d", rn[i].fa ? int(rn[i].fa - rn) + 1 : -1);
  return 0;
}