Hats on and off P72822

There is a line of people on a row. Every one has a hat, which he can be wearing (on) or not (off). Let us use those people to play a game for two players, A and B. First, decide an integer number $n$. By turns (A begins), each player must choose some person $x$ that is currently wearing his hat, and change the state (from on to off, or the other way around) of the $n$ people to the right of $x$, starting at $x$. Note that the $n-1$ rightmost persons can never be chosen.

Fo instance, assume that ‘N’ means on, and that ‘F’ means off. If $n = 4$ and we pick the third person of the row below (note that his state is on), we get the next state of the game that is shown underneath:

The player that cannot play loses the game. Assuming perfect play from both players, can you tell who will win?

Input

Input consists of several cases, each one with a string $s$ made up of only ‘N’ and ‘F’, followed by $n$. Assume $1 \le n \le \vert s \vert \le 10^5$.

Output

For every case, print the name of the winner.