题目描述

In this problem, you need to sort a list of $N = 100$ distinct integers in strictly increasing order. You can rearrange the list by swapping the contents of any two positions (they do not need to be adjacent). Unfortunately, you cannot read those contents directly. You can access information about the list contents by querying the minimum of a range. The minimum query gives you the position of the minimum value over a range of consecutive positions. For example, in the list $[51, 33, 100, 11]$, the minimum over the range between positions 2 and 4, inclusive (1-based), is at position 4 and the minimum between positions 1 and 3 is at position 2.

Queries about the minimum within a range are limited by a coin budget per test case. Larger ranges are cheaper: asking about the position of the minimum between positions $i$ and $j$ (for $i < j$) costs $\lceil 10^8 / (j - i + 1) \rceil$ coins, where $\lceil x \rceil$ is the smallest integer greater than or equal to $x$ (that is, $x$ rounded up). Swap operations, on the other hand, do not cost any coins.

Write a program that sorts lists of integers using any number of swaps and at most $6 \times 10^8$ coins per test case distributed among any number of minimum queries.

Interactive Protocol

This is an interactive problem.

Initially, the judge will send you a single line containing two integers $\mathbf{T}$ and $\mathbf{N}$: the number of test cases and the number of elements to sort within each test case, respectively. The judge has the initial lists preset before it gets any input from your program, and the only changes done to them during the exchanges with your program are the swaps that you request.

Then, you must process $\mathbf{T}$ test cases. Each test case consists of a series of exchanges plus an additional line indicating you are done. Each exchange consists of you printing one line and the judge printing one line in response. Your program must print a single line containing one of these options:

• An uppercase $\mathbf{M}$ and two integers $i$ and $j$ with $i < j$ representing a minimum query. The judge responds with a single integer representing the position of the minimum value in the list within 1-based positions $i$ and $j$, inclusive.
• An uppercase $\mathbf{S}$ and two integers $i$ and $j$ with $i < j$ representing a swap operation. The judge swaps the two elements at 1-based positions $i$ and $j$ and responds with 1.
• An uppercase $\mathbf{D}$ representing that you are done sorting the list. The judge checks the list. It responds with 1 if the list is sorted in strictly increasing order and -1 if it is not.

After the judge responds 1 to a $\mathbf{D}$, it will finish if it was the last test case or it will immediately start waiting for your first command for the next test case. After receiving the judge's response for the $\mathbf{T}$-th case, your program must finish in order to not receive a Time Limit Exceeded error.

If the judge receives an invalidly formatted line or invalid values from your program at any moment, including a minimum operation whose cost would exceed your remaining budget for the test case, the judge will print a single number -1. After the judge prints -1 for any of the reasons explained above, it will not print any further output. If your program continues to wait for the judge after receiving a -1, your program will time out, resulting in a Time Limit Exceeded error. Notice that it is your responsibility to have your program exit in time to receive a Wrong Answer judgment instead of a Time Limit Exceeded error. As usual, if the memory limit is exceeded, or your program gets a runtime error, you will receive the appropriate judgment.

输入格式

See Interactive Protocol.

输出格式

See Interactive Protocol.

2 4

4

2

1

4

1

1

3

1

3

2

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

提示

You can use this testing tool to test locally or on our platform. To test locally, you will need to run the tool in parallel with your code; you can use our interactive runner for that.

Instructions for the testing tool are included in comments within the tool. We encourage you to add your own test cases. Please be advised that although the testing tool is intended to simulate the judging system, it is NOT the real judging system and might behave differently.

Limits

Test Set 1 (15 Pts, Visible Verdict)

• $\mathbf{T} = 100$.
• $\mathbf{N} = 100$.