← 返回题目列表

Codeforces · 1974/B

B. 对称编码

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

Polycarp 有一个字符串 $$$s$$$,由小写拉丁字母组成。他使用以下算法对该字符串进行编码:

- 首先,他构造一个新的辅助字符串 $$$r$$$,它由字符串 $$$s$$$ 中所有不同的字母组成,按字母顺序书写;
- 然后编码如下:字符串 $$$s$$$ 中的每个字符都被字符串 $$$r$$$ 中的对称字符替换(字符串 $$$r$$$ 的第一个字符将被最后一个字符替换,第二个字符将被倒数第二个字符替换,依此类推)。

例如,对字符串 $$$s$$$="codeforces" 进行编码如下:

- 字符串 $$$r$$$ 被获取为“cdefors”;
- 第一个字符 $$$s_1$$$='c' 被 's' 替换;
- 第二个字符 $$$s_2$$$='o' 被 'e' 替换;
- 第三个字符 $$$s_3$$$='d' 被 'r' 替换;
- ...
- 最后一个字符 $$$s_{10}$$$='s' 被替换为 'c'。

字符串 $$$r$$$ 以及 $$$s$$$="codeforces" 的替换。

因此,对字符串 $$$s$$$="codeforces" 进行编码的结果是字符串“serofedsoc”。

编写一个执行解码的程序——即从编码结果中恢复原始字符串$$$s$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 字符串 $$$b$$$ 的长度。

每个测试用例的第二行包含一个长度为$$$n$$$的字符串$$$b$$$,由小写拉丁字母组成——原始字符串$$$s$$$编码的结果。

保证测试中所有测试用例的$$$n$$$值之和不超过$$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出字符串$$$s$$$,从中获得编码结果$$$b$$$。

示例

输入 #1

5
10
serofedsoc
3
ttf
9
tlrhgmaoi
1
w
15
hnndledmnhlttin

输出 #1

codeforces
fft
algorithm
w
meetinthemiddle