在本题中，你需要将一个包含 $N = 100$ 个不同整数的列表按严格递增顺序排序。你可以通过交换任意两个位置的内容（它们不需要相邻）来重新排列列表。遗憾的是，你无法直接读取这些内容。你可以通过查询区间的最小值来获取有关列表内容的信息。最小值查询会给出一段连续位置区间内的最小值所在的位置。例如，在列表 $[51, 33, 100, 11]$ 中，位置 $2$ 到 $4$（基于 $1$ 的索引）之间的最小值位于位置 $4$，而位置 $1$ 到 $3$ 之间的最小值位于位置 $2$。

关于区间最小值的查询在每个测试用例中都有硬币预算限制。较大的区间更便宜：查询位置 $i$ 和 $j$（对于 $i < j$）之间的最小值位置的代价为 $\lceil 10^8 / (j - i + 1) \rceil$ 枚硬币，其中 $\lceil x \rceil$ 是大于或等于 $x$ 的最小整数（即向上取整）。另一方面，交换操作不消耗任何硬币。

编写一个程序，使用任意次数的交换操作，并在每个测试用例中总共使用不超过 $6 \times 10^8$ 枚硬币的最小值查询来对整数列表进行排序。

输入格式

这是一个交互式问题。你应该确保已经阅读了我们 FAQ 中关于交互式问题的相关信息。

最初，评测系统会发送一行，包含两个整数 $T$ 和 $N$：分别为测试用例的数量和每个测试用例中需要排序的元素数量。评测系统在接收你的程序输入之前已经预设了初始列表，在与你的程序交互过程中，列表仅会因你请求的交换操作而改变。

然后，你必须处理 $T$ 个测试用例。每个测试用例包含一系列交换操作，以及最后一行表示你已完成操作。每次交换操作由你打印一行，评测系统打印一行作为响应。你的程序必须打印一行，包含以下选项之一：

• 一个大写字母 M 和两个整数 $i$ 和 $j$，其中 $i < j$，表示一次最小值查询。评测系统会返回一个整数，表示列表中位置 $i$ 到 $j$（包含边界，基于 $1$ 的索引）之间最小值所在的位置。
• 一个大写字母 S 和两个整数 $i$ 和 $j$，其中 $i < j$，表示一次交换操作。评测系统会交换位置 $i$ 和 $j$（基于 $1$ 的索引）处的两个元素，并返回 $1$。
• 一个大写字母 D，表示你已完成列表排序。评测系统会检查列表。如果列表已按严格递增顺序排序，则返回 $1$，否则返回 $-1$。

在评测系统对 D 返回 $1$ 后，如果是最后一个测试用例，它将结束；否则，它将立即等待你为下一个测试用例发送的第一条命令。在接收到评测系统对第 $T$ 个测试用例的响应后，你的程序必须结束，以免收到超时错误。

如果评测系统在任何时刻接收到格式错误的行或无效值（包括代价超过该测试用例剩余预算的最小值操作），评测系统将打印单个数字 $-1$。在评测系统因上述任何原因打印 $-1$ 后，它将不再输出任何内容。如果你的程序在收到 $-1$ 后继续等待评测系统，你的程序将超时，导致超时错误。请注意，你有责任让你的程序及时退出，以获得错误答案（Wrong Answer）判决，而不是超时错误。通常情况下，如果超过内存限制或程序出现运行时错误，你将收到相应的判决。

数据范围

时间限制：60 秒。 内存限制：1 GB。

测试集 1（可见判决）： $T = 100$。 $N = 100$。

样例

样例输入 1

2 4
4
2
1
4
1
3
1
3
2
1

样例输出 1

M 2 4
M 1 3
S 1 4
M 3 4
S 3 4
D
M 1 4
S 1 3
M 3 4
M 2 4
D

实现细节

你可以使用此测试工具在本地或我们的平台上进行测试。要在本地测试，你需要将该工具与你的代码并行运行；你可以使用我们的交互式运行器（interactive runner）来实现。有关更多信息，请阅读该文件中的注释，并查看 FAQ 中的交互式问题部分。

测试工具的说明包含在工具内部的注释中。我们鼓励你添加自己的测试用例。请注意，虽然测试工具旨在模拟评测系统，但它不是真正的评测系统，其行为可能有所不同。如果你的代码通过了测试工具但在真实评测中失败，请检查 FAQ 的编码部分，确保你使用的编译器与我们相同。

[下载测试工具]