Algosia and Bajtek find themselves in a very unusual situation. Each of them possesses their own binary string of length $n$. They would like to exchange these strings as quickly as possible.

The matter is complicated by the fact that they are currently at a rock, paper, scissors championship. This competition has recently undergone a technological revolution. To avoid any attempts at communication between participants and to focus entirely on the randomness of the players' strategies, the organizers decided to completely isolate the participants from each other and place a computer system between them. Each participant declares their move, and only then are the results of the round revealed.

The rules of a rock, paper, scissors match are as follows:

• The match consists of rounds.
• During a single round, each player chooses one of three symbols: paper, rock, or scissors.
• Then, these symbols are compared. If the players chose the same symbol, the round ends in a draw and no one scores a point. Otherwise, the person with the stronger symbol scores 1 point (paper beats rock, rock beats scissors, and scissors beats paper).
• The player who is the first to have 2 more points than their opponent wins the match.
• Rounds continue until one of the players wins the match.

Algosia and Bajtek want to learn each other's strings before the end of the match. They also want to play as few rounds as possible so as not to exhaust the patience of the observers and fans. Write a program that will help them. You must solve this problem for $t$ independent test cases.

Interaction

This is an interactive problem. Your program will be executed in two copies – one for Algosia and one for Bajtek. Each execution will receive the word Algosia or Bajtek in the first line of input, which determines which person's actions this copy of the program is responsible for.

The input format is identical in both cases. The first line of input contains the word Algosia or Bajtek. The second line contains two numbers $n$ and $t$ ($1 \le n \le 5000, 1 \le t \le 5$), specifying the length of the binary strings that Algosia and Bajtek want to send to each other and the number of test cases, respectively. Then, the interaction between the programs takes place $t$ times.

In the first line of each test case, both programs will receive a string of length $n$, consisting only of the characters 0 and 1. After reading their strings, Algosia and Bajtek begin the game. During a single round, the player first prints a line containing their move, specified by a single character $c \in \{P, K, N\}$, and then reads from the input a line containing the character specifying the second player's move in the same format. The maximum number of rounds played in a single test case is 20000. Exceeding this limit will result in a "wrong answer" verdict.

To end a test case, you must print a line containing the character ! (exclamation mark), a space, and the following string of length $n$ consisting only of the characters 0 and 1. For Algosia, this should be Bajtek's string, and for Bajtek, Algosia's string. After printing the result, the program should immediately proceed to the next test case (i.e., read the line containing the string to be passed) or terminate if it was the last test case.

After printing the answer, you must flush the output buffer, for example by calling cout.flush() or fflush(stdout).

Examples

Input 1

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

Output 1

P
K
P
P
! 00001
P
K
! 10001

Note

The example above shows the interaction for the first sample test (named 0a). In all other tests (including the second sample test 0b), $t=5$ and $n=5000$.

Notes

• The interaction described above corresponds to the first sample test (named 0a).
• In all other tests (including the second sample test 0b), $t = 5, n = 5000$.
• If after a round one of the players has 2 more points than their opponent, the program terminates immediately with a "wrong answer" verdict.
• Both programs start at the same time. The execution time is measured as the real time from the start to the end of the interactor.
• Advantages do not carry over between test cases. At the beginning of each test case, both players start with 0 points (regardless of the result of the previous test case).

Scoring

The test set consists of one group, for which you can get a maximum of 10 points. Let $m$ be the maximum number of rounds played across all test cases of a single test. The score for a given test is determined according to the following rules:

The final score for the submission is the minimum score across all tests.

Local Testing

The interactor pknsoc.cpp is available in the Files section. It is identical to the interactor used for checking submissions on SIO2. It should be run with the command:

python3 pknrun.py [solution] < [test] > [result]

where the files pknsoc.cpp and oi.h must be in the same folder. The format in which the interactor accepts input is described in the comments of the pknsoc.cpp file.

Fair Play Rules

Communication between programs in any way other than through the game flow, e.g., by sending a move with a delay by one program and reading the clock by the other, is prohibited. If the Jury detects an attempt at unauthorized communication between programs, the submission may be removed, and in extreme cases, a decision may be made to disqualify the participant from the entire competition.