Problem Description

Little F wants to play a game with others, but he does not want to lose, so he asks you to help him study a strategy.

There are $m$ stones. Little F and Little B take turns removing stones. Little F goes first. The player who cannot make a move loses.

Given a positive integer $n$, the number of stones removed each time $k$ ($k$ is a positive integer) must satisfy at least one of the following two conditions:

• $k$ is a multiple of $n$.
• $k$ is a perfect square less than $n$.

They will play $T$ games. In each game, $n$ is fixed, and only the number of stones $m$ changes.

For each game, assuming both players are smart enough, determine who has a winning strategy.

Input Format

The first line contains two positive integers $T, n$.

The second line contains $T$ positive integers $m$, where each $m$ is the number of stones in that game.

Output Format

Output a string of length $T$, one character per game. Each character is F or B, meaning the first player wins or the second player wins in that game, respectively.

5 2
1 2 3 4 5

FFBFF

Hint

Sample Explanation

The following explains that when $n = 2, m = 3$, the second player will win. Consider the number of stones the first player removes on the first move:

• If the first player removes $1$ stone, then the second player can remove all remaining $2$ stones.
• If the first player removes $2$ stones, then the second player can remove the remaining $1$ stone.

Therefore, no matter what, the second player will always win.

Constraints

For all testdata, it is guaranteed that $1\le T, n\le 5\times 10^5$ and $1\le m\le 10^9$.

For odd-numbered test points, the memory limit is $512\ \text{MB}$; for even-numbered test points, the memory limit is $64\ \text{MB}$.

Translated by ChatGPT 5