As a tradition, the Code Village holds an annual championship, named ICPC (Intelligence Championship for Platinum Coders) to search for its most outstanding genius. The participants take part in various contests to find out who is the potential genius. The competitions include Go, Reversi, Sudoku and even Paper-Scissor-Rock, and it is fascinating to see the unpredictable result. Well... At least a few years ago.

Everything changed when an AI robot came to the village - it seems weird, but as the name of the contest shows, anything related to `intelligence' can take part freely. The robot soon won all the competitions without difficulty, and remained the defending champion for years and years. Everyone considered it to be undefeatable. And this time, your task will be - as you have figured out - beat the robot!

You are not alone - you will have a teammate. To make the game more interesting, the organizing committee has slightly modified the rule and it will be a guessing game. The game process is as follows:

• The judges announce two positive integers  to the three players - you, your teammate, and the robot.
• The robot generates an integer sequence of length  - let's call it  - and selects a secret integer . Each element of  should fall in the range , that is, each  should be a non-negative integer and strictly less than . Then it submits  and  to the judges. (Note that in this problem all the sequences are -indexed.)
• You receive the sequence  and the number  from the judges, and your task is to tell the exact value of  to your teammate. To achieve that, you \textbf{must} select exactly \textbf{one} index , and set  to .
• Your teammate then receives the sequence , and has to figure out the hidden integer . Note that he doesn't have access to the original string generated by the robot; the only information he gets is the string that you write. He has only one chance to submit his answer, and if he succeeds, both of you win the game.
  \end{itemize}

Some typical settings may apply here. For example, the three of you all have unlimited and accurate memory, your team can discuss strategies before the game starts (of course NOT during the game), while the robot has the access to your strategy. You can also assume that the three of you will play optimally to achieve their goals: for you two the goal is definitely to win the game, while for the robot it will do its best to prevent your victory.

Let's take some examples. For , your team will definitely win by always answering . For , a solution that ensures your victory works like this: your friend always answer the value of , and when you enter the room you just check if  differs from : if so then choose , otherwise choose . It is clear to see that such strategy works perfectly. However, it can be proved that for  your team has no chance to win at all.

There are five hours left before the competition, and you decide to do some practice by writing a program to determine that for certain pair of , which side will win the game. You will have to answer  independent queries.