← 返回题目列表

Codeforces · 1935/A

A. MAC 娱乐

中文机器翻译题面 查看原题

恭喜您被大师援助中心录取!然而,你在课堂上非常无聊,厌倦了无所事事,所以你给自己想出了一个游戏。

给定一个字符串 $$$s$$$ 和一个偶数 $$$n$$$。您可以对其应用两种类型的操作:

1. 将反转字符串 $$$s$$$ 添加到字符串 $$$s$$$ 的末尾(例如,如果 $$$s = $$$ cpm,则在应用操作 $$$s = $$$ cpmmpc 后)。
2. 反转当前字符串$$$s$$$(例如,如果$$$s = $$$ cpm,则在应用操作$$$s = $$$ mpc 后)。

需要确定在精确应用$$$n$$$操作后可以获得的按字典顺序最小的$$$^{\dagger}$$$字符串。请注意,您可以按任意顺序应用不同类型的操作,但总共必须应用精确的 $$$n$$$ 操作。

$$$^{\dagger}$$$当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$:

- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中有一个字母比 $$$b$$$ 中的对应字母更早出现。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 500$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个偶数 $$$n$$$ ($$$2 \leq n \leq 10^9$$$) — 应用于字符串 $$$s$$$ 的操作数。

每个测试用例的第二行包含一个字符串 $$$s$$$ ($$$1 \leq |s| \leq 100$$$),由小写英文字母组成,即应用操作的字符串。

输出

对于每个测试用例,输出一行 - 在精确应用 $$$n$$$ 操作后可以获得的按字典顺序排列的最小字符串。

示例

输入 #1

5
4
cpm
2
grib
10
kupitimilablodarbuz
1000000000
capybara
6
abacaba

输出 #1

cpm
birggrib
kupitimilablodarbuz
arabypaccapybara
abacaba

注意

在第一个测试用例中,您可以应用第二种类型的操作(即反转字符串 $$$s$$$)$$$4$$$ 次。那么字符串 $$$s$$$ 将保持等于 cpm。

在第二个测试用例中,您可以执行以下操作:

- 应用第二种类型的操作,之后 $$$s$$$ 将等于 birg。
- 应用第一种类型的操作(即,将反转的字符串 $$$s$$$ 添加到字符串 $$$s$$$ 的末尾),之后 $$$s$$$ 将等于 birggrib。