Codeforces Round 932 (Div. 2) |
---|
Finished |
Congratulations, you have been accepted to the Master's Assistance Center! However, you were extremely bored in class and got tired of doing nothing, so you came up with a game for yourself.
You are given a string $$$s$$$ and an even integer $$$n$$$. There are two types of operations that you can apply to it:
It is required to determine the lexicographically smallest$$$^{\dagger}$$$ string that can be obtained after applying exactly $$$n$$$ operations. Note that you can apply operations of different types in any order, but you must apply exactly $$$n$$$ operations in total.
$$$^{\dagger}$$$A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 500$$$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single even integer $$$n$$$ ($$$2 \leq n \leq 10^9$$$) — the number of operations applied to the string $$$s$$$.
The second line of each test case contains a single string $$$s$$$ ($$$1 \leq |s| \leq 100$$$), consisting of lowercase English letters, — the string to which the operations are applied.
For each test case, output a single line — the lexicographically smallest string that can be obtained after applying exactly $$$n$$$ operations.
54cpm2grib10kupitimilablodarbuz1000000000capybara6abacaba
cpm birggrib kupitimilablodarbuz arabypaccapybara abacaba
In the first test case, you can apply the operation of the second type (i.e., reverse the string $$$s$$$) $$$4$$$ times. Then the string $$$s$$$ will remain equal to cpm.
In the second test case, you can do the following:
Name |
---|