该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

这是一道交互题。

国庆假期，江月诗去成都世界线玩耍了一下，发现了一个叫作“蒂娜换位思考”的游戏。

游戏中有 $n$ 个互不相同的方块，编号为 $1,2,\ldots,n$。工作人员提前确定了一个正确的排列 $p_{1},p_{2},\ldots,p_{n}$，并将它隐藏起来。这里，$p_{i}$ 表示正确排列中第 $i$ 个位置上的方块编号。 隐藏排列在交互开始前已经确定，在整个交互过程中不会改变。

最开始，江月诗将方块按照自然顺序 $(1,2,\ldots,n)$ 摆放。记当前排列为 $a_{1},a_{2},\ldots,a_{n}$，初始时 $a_{i}=i$。

每次操作，江月诗只能选择两个不同的位置，交换这两个位置上的方块。交换完成后， 工作人员会告诉她当前排列中有多少个位置上的方块是正确的，即返回

交换结果会保留。下一次交换作用于上一次交换后得到的当前排列。

请帮助江月诗确定隐藏排列。你最多可以进行 $10000$ 次交换询问，且选手程序向交互器 输出的总字节数不得超过 $99999$。

保证对于每个合法的隐藏排列，都存在同时满足上述两个限制的确定性策略。

输入格式

本题只有一组测试数据。

交互开始时，读入一个整数 $n$（$2\le n\le 100$），表示方块的数量。

初始当前排列为 $(1,2,\ldots,n)$。隐藏排列及初始排列的正确位置数不会直接提供给你的程序。

此后，每次合法的交换询问都会得到一个整数 $r$（$0\le r\le n$）， 表示完成这次交换之后，当前排列中位置正确的方块数量。

输出格式

本题只允许交换询问。

进行一次询问时，输出一行 S i j，其中 $1\le i<j\le n$。 命令中的字母 S 必须大写。

交互器会交换当前排列中的 $a_{i}$ 和 $a_{j}$，保留交换后的排列，并返回此时的正确位置数。 输出这条询问后，你应读入交互器返回的整数 $r$。

每条 S 命令都计为一次询问，询问总数不得超过 $10000$。 连续交换同一对位置两次会恢复到这两次交换之前的排列，但仍计为两次询问。

当你确定隐藏排列后，输出一行 ! p1 p2 ... pn，然后立即结束程序。 $p_{1},p_{2},\ldots,p_{n}$ 必须是 $1,2,\ldots,n$ 的一个排列。

! 只用于提交答案，不属于询问，不计入询问次数，但计入输出字节数。 最终提交只检查你输出的排列是否与隐藏排列相同。 即使某次询问返回了 $n$，你仍然必须使用 ! 提交最终答案。 提交最终答案后，无需继续读取反馈。

每条询问和最终答案都必须单独占一行，格式中的各项以空格分隔。 每次输出后都必须刷新输出缓冲区，否则可能被判超时。

在一次完整交互中，你的程序向交互器输出的总字节数不得超过 $99999$。 所有命令字符、数字、空格、换行符以及最终答案均计入这一限制。 该限制只统计选手程序向交互器输出的内容，不统计交互器返回的内容。

如果你的询问格式非法或询问次数超过限制，交互器会返回 $-1$。 读到 $-1$ 或遇到输入结束时，你应立即结束程序。 输出错误的最终答案、超过输出字节限制或违反其他交互规则，均无法通过本题。

3
1
3

S 1 2
S 2 3
! 2 3 1

样例解释

样例中的隐藏排列为 $(2,3,1)$。

样例输入列出交互器依次发送的内容，样例输出列出选手程序依次发送的内容。 两列内容是在实际运行中交替产生的，不表示交互器会预先给出全部反馈。

首先，交互器给出 $n=3$，当前排列为 $(1,2,3)$。

• 输出 S 1 2，交换当前排列的第 $1$、$2$ 个位置，得到 $(2,1,3)$。 只有第 $1$ 个位置正确，因此交互器返回 $1$。

• 输出 S 2 3，在当前排列 $(2,1,3)$ 上交换第 $2$、$3$ 个位置，得到 $(2,3,1)$。 三个位置全部正确，因此交互器返回 $3$。

• 最后输出 ! 2 3 1，提交正确答案并结束程序。

这个交互过程共使用了 $2$ 次交换询问，最后一行不计入询问次数。