题目描述

密码学研究的是秘密通信的方法，这些方法将一条消息（明文）转换成一种伪装形式（密文），这样除了目标接收者之外，任何看到密文的人都无法弄清楚明文的内容。将明文转换为密文的过程是加密；将密文转换为明文的过程是解密。“扭曲（Twisting）”是一种简单的加密方法，它要求发送者和接收者都就一个秘密密钥$k$达成一致，$k$是一个正整数。

“扭曲”方法使用四个数组：plaintext（明文）和ciphertext（密文）是字符数组，plaincode（明文编码）和ciphercode（密文编码）是整数数组。所有数组的长度都是$n$，其中$n$是要加密的消息的长度。数组的索引从0开始，所以元素编号从0到$n - 1$。对于本题，所有消息将只包含小写字母、句号和下划线（表示空格）。

要加密的消息存储在plaintext中。给定密钥$k$，加密方法如下。首先，根据以下规则将plaintext中的字母转换为plaincode中的整数值编码：_ = 0，a = 1，b = 2，...，z = 26，. = 27。接下来，根据以下公式将plaincode中的每个编码转换为ciphercode中的加密编码：对于所有$i$，从0到$n - 1$，

ciphercode[i] = (plaincode[ki mod n] - i) mod 28

（这里$x \bmod y$是$x$除以$y$的正余数。例如，$3 \bmod 7 = 3$，$22 \bmod 8 = 6$，$-1 \bmod 28 = 27$。只要结果为负时加上$y$，你就可以使用C语言中的%运算符或Pascal语言中的mod运算符来计算。）最后，根据上述规则将ciphercode中的编码转换回ciphertext中的字母。最终经过“扭曲”的消息就在ciphertext中。使用密钥5对消息“cat”进行“扭曲”得到如下结果：

数组      0   1   2 
plaintext 'c' 'a' 't' 
plaincode  3   1   20 
ciphercode 3   19  27 
ciphertext 'c' 's' '.' 

你的任务是编写一个程序，能够对消息进行“解扭曲”，也就是说，给定密钥$k$，将密文转换回原始的明文。例如，给定密钥5和密文“cs.”，你的程序必须输出明文“cat”。

输入

输入包含一个或多个测试用例，随后是一行仅包含数字$0$的行，该数字表示文件结束。每个测试用例独占一行，由密钥$k$、一个空格以及一条经过“扭曲”的消息组成，消息包含至少$1$个且最多$70$个字符。密钥$k$将是一个不大于300的正整数。

输出

对于每个测试用例，在单独的一行上输出解扭曲后的消息。

注意：你可以假设对一条消息进行解扭曲总是会得到唯一的结果。（对于那些具备一些基础数论或抽象代数知识的人来说，当密钥$k$和消息长度$n$的最大公约数为1时就会是这种情况，所有测试用例都满足这一条件。）

输入示例

5 cs.
101 thqqxw.lui.qswer
3 b_ylxmhzjsys.virpbkr
0

输出示例

cat
this_is_a_secret
beware._dogs_barking

来源

1998年美国中北部地区竞赛