题目描述

Tom 把 $n$ 个小球装进了 $n$ 个袋子，第 $i$ 个袋子里有 $p_i$ 个小球（$1 \le i \le n$）。这些数 $p_1, p_2, \dots, p_n$ 恰好是 $1$ 到 $n$ 的一个排列，也就是说每个袋子里的小球数量互不相同。

33DAI 看不见袋子里的球。他只能向 Tom 提问：任选两个编号不同的袋子 $a, b$，Tom 会告诉他第 $a$ 个袋子里的小球是否严格少于第 $b$ 个袋子里的小球。

33DAI 一共最多只能问 $20000$ 次。问完之后，他必须把每个袋子里的小球数量全部报出来。请你帮他完成这件事，并且注意：问的次数要尽量少。

交互规则

本题没有输入文件，你通过与交互器对话来获取信息。你的程序需要从标准输入读入数据、向标准输出写数据。

第一步：从标准输入读入一个整数 $n$（$1 \le n \le 1000$），表示袋子的个数。

接下来的每一次操作，你向标准输出写一行，格式必须是下面两种之一：

• 1 a b：提问。其中 $a, b$ 是两个编号，必须满足 $1 \le a, b \le n$ 且 $a \ne b$。交互器会回答一行：
  • yes：表示 $p_a < p_b$；
  • no：表示 $p_a > p_b$（因为 $p$ 是排列，两个数一定不相等）。
• 2 q_1 q_2 \dots q_n：报告答案。这一行一共有 $n + 1$ 个整数，第一个是 $2$，后面跟着你的答案 $q_1, q_2, \dots, q_n$，其中 $q_i$ 是你认为的第 $i$ 个袋子里的小球数量，必须满足 $1 \le q_i \le n$。
  • 如果 $q_1, q_2, \dots, q_n$ 恰好等于 $p_1, p_2, \dots, p_n$，交互器会输出一行 win，本题该测试点通过；
  • 如果 $q$ 不是 $1$ 到 $n$ 的一个排列（有数字重复或超出范围），或者与 $p$ 不同，本题该测试点判为 Wrong Answer。

报告答案的那一次操作不计入提问次数。

每次输出一行后，必须立即刷新输出缓冲区，否则交互器会读到旧数据而判错。C++ 中的做法是：

printf("1 %d %d\n", a, b);
fflush(stdout);
// 用 cout 的话写 cout << "1 " << a << " " << b << endl;（endl 会刷新）或 cout.flush();

限制：提问次数不能超过 $20000$ 次，否则判为 Wrong Answer。

样例 1

下面是一次合法的交互过程（$n = 4$，隐藏的排列是 $p = [3, 4, 2, 1]$）。空行只是为了排版，实际输出中不要有空行。

交互器        你的程序
4
              1 1 2
yes
              1 2 3
yes
              2 3 4 2 1
win

样例解释

• 交互器给出 $n = 4$；
• 你问 1 1 2，交互器回答 yes，说明 $p_1 < p_2$；
• 你问 1 2 3，交互器回答 yes，说明 $p_2 < p_3$；
• 你报告 2 3 4 2 1，正好等于隐藏的 $p = [3, 4, 2, 1]$，交互器回答 win，本测试点通过。

注意上面这次交互只用了 $2$ 次提问，这远不是全部信息，只是恰好猜中了答案。

样例 2

见 order1.in 与 order1.ans。

其中 .in 就是本次交互开始时交互器给出的 $n$；.ans 是本测试点隐藏的排列 $p$，供你本地调试时查看，实际评测时你并看不到它。

样例 3

见 order2.in 与 order2.ans。

其中 .in 就是本次交互开始时交互器给出的 $n$；.ans 是本测试点隐藏的排列 $p$，供你本地调试时查看，实际评测时你并看不到它。

数据范围

对于所有测试数据，保证：

• $1 \le n \le 1000$；
• $p_1, p_2, \dots, p_n$ 是 $1$ 到 $n$ 的一个排列。