Algosia 和 Bajtek 处于一种非常特殊的情况。他们每个人都有一个长度为 $n$ 的二进制字符串。他们希望尽快交换这些字符串。

困难在于，他们目前正在参加一场石头、剪刀、布锦标赛。这场比赛最近经历了一场技术革命。为了避免参赛者之间进行任何形式的交流，并完全专注于选手策略的随机性，组织者决定将参赛者完全隔离，并在他们之间设置一个计算机系统。每位参赛者声明自己的出招，只有在此之后才会揭晓该轮的结果。

石头、剪刀、布的比赛规则如下：

• 比赛由多轮组成。
• 在每一轮中，每位玩家从三个符号中选择一个：布 (P)、石头 (K) 或剪刀 (N)。
• 然后比较这些符号。如果玩家选择了相同的符号，则该轮平局，无人得分。否则，拥有更强符号的玩家获得 1 分（布胜过石头，石头胜过剪刀，剪刀胜过布）。
• 第一个比对手多出 2 分的玩家赢得比赛。
• 比赛持续进行，直到其中一名玩家赢得比赛。

Algosia 和 Bajtek 希望在比赛结束前互相了解对方的字符串。他们还希望进行的轮数尽可能少，以免耗尽观察者和观众的耐心。请编写一个程序来帮助他们。你必须解决 $t$ 个独立测试用例的问题。

交互

这是一个交互式任务。你的程序将运行两个副本——一个代表 Algosia，另一个代表 Bajtek。每次运行的输入第一行都会收到单词 Algosia 或 Bajtek，这决定了该程序副本代表哪个人。

两种情况下的输入格式完全相同。输入的第一行包含单词 Algosia 或 Bajtek。第二行包含两个数字 $n$ 和 $t$ ($1 \le n \le 5000, 1 \le t \le 5$)，分别表示 Algosia 和 Bajtek 想要互相发送的二进制字符串的长度以及测试用例的数量。随后进行 $t$ 次程序间的交互。

在每个测试用例的第一行，两个程序都将收到一个长度为 $n$ 的字符串，仅由字符 0 和 1 组成。读取各自的字符串后，Algosia 和 Bajtek 开始游戏。在每一轮中，玩家首先输出一行包含其出招的内容，用字符 $c \in \{P, K, N\}$ 表示，然后从输入中读取一行，其中包含以相同格式表示对方玩家出招的字符。单个测试用例中的最大轮数为 20000。超过此限制将导致“错误答案”判决。

要结束测试用例，必须输出一行包含字符 !（感叹号）、一个空格以及随后的长度为 $n$ 的字符串，该字符串仅由字符 0 和 1 组成。对于 Algosia，这应该是 Bajtek 的字符串，而对于 Bajtek，这应该是 Algosia 的字符串。输出结果后，程序应立即进入下一个测试用例（即读取包含要传递的字符串的行），或者如果这是最后一个测试用例，则结束运行。

输出答案后，必须清空输出缓冲区，例如通过调用 cout.flush() 或 fflush(stdout)。

样例

输入格式 1

Algosia
5 2
10010
P
K
P
! 00001
00010
P
K
! 10001

输出格式 1

P
K
P
P
! 00001
P
K
! 10001

说明

上述交互对应于第一个示例测试（名为 0a）。在所有其他测试中（包括第二个示例测试 0b），满足 $t = 5, n = 5000$。如果在一轮之后，任何玩家比对手多出 2 分，程序将立即结束并给出“错误答案”判决。两个程序同时启动。程序运行时间测量为从交互器开始到结束的实际时间。优势不会在测试用例之间传递。在每个测试用例开始时，两名玩家都从 0 分开始（无论前一个测试用例以什么结果结束）。

子任务

测试集由一组组成，最多可获得 10 分。设 $m$ 为单个测试中所有测试用例进行的总轮数最大值。给定测试的分数根据以下规则确定：

提交的最终得分为所有测试中的最低得分。

本地测试

为了方便本地测试，我们提供了一个交互器（pknsoc.cpp）。你可以使用以下命令运行它：

python3 pknrun.py [程序1] [程序2]

其中 [程序1] 和 [程序2] 是编译后的可执行文件。交互器将模拟两名玩家之间的通信，并根据上述规则验证游戏的合法性。

公平竞争原则

禁止通过游戏过程以外的任何方式在程序之间进行通信，例如通过一个程序延迟发送出招而另一个程序读取时钟。如果评审团发现程序之间存在非法通信尝试，则提交内容可能会被删除，在严重的情况下，可能会做出取消整个比赛资格的决定。