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 ≤ n ≤ | s | ≤ 10⁵.

Output

For every case, print the name of the winner.