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:

NFNNFFFNFFNFFF

NFFFNNFNFFNFFF

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^{5}.

Output

For every case, print the name of the winner.

Public test cases

**Input**

NFFFF 5 FFFFFFFFFF 6 NFNNFFFNFFNFFF 4 NNNNNNNNN 1

**Output**

A B B A

Information

- Author
- Marc Felipe
- Language
- English
- Official solutions
- C++
- User solutions
- C++