CF1974B Symmetric Encoding

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$。

由 ChatGPT 4.1 翻译