AC ou WA?

Um dos problemas do que Tarcísio participou era o de determinar o $i$-ésimo caractere da string de Fibonacci $F_\infty$, onde $$\begin{array}{ll} F_1 = \mathtt{B} \\ F_2 = \mathtt{A} \\ F_n = F_{(n - 1)}F_{(n - 2)},\ n > 2, \end{array}$$ onde a expressão $F_{(n - 1)}F_{(n - 2)}$ significa a concatenação das últimas duas strings de Fibonacci. Por exemplo, $F_3$ = "AB", $F_4$ = "ABA" e $F_5$ = "ABAAB".

Conversando com os colegas após o encerramento do evento, Tarcísio percebeu que cometeu um equívoco na implementação: ele concatenou as strings em ordem oposta à definição, isto é, fez $F_{(n - 2)}F_{(n - 1)},\ n > 2$. Esta modificação produzia strings $S_i$ não necessariamente iguais a $F_i$. Por exemplo, $S_3$ = "BA", $S_4$ = "ABA" e $S_5$ = "BAABA".

Para determinar o $i$-ésimo caractere de $F_\infty$, ele gerou a string $S_k$ de menor tamanho $m$ tal que $m\geq i$ e retornou seu $i$-ésimo caractere, sendo que os índices são contados de $1$ a $m$.

O que o deixou surpreso foi o fato do código errado ter passado pelos pré-testes do evento, ou seja, o código errado produziu as respostas corretas para estes testes. O veredito final do problema ainda não saiu, e Tarcísio está na dúvida: receberá um ou um ?

Dado os índices que serão usados nos testes secretos, determine este veredito.

Entrada

A primeira linha da entrada contém o número $N$ ($1\leq N\leq 2\times 10^5$) de índices que serão usados nos testes secretos.

A segunda linha contém $N$ inteiros positivos $i$ ($1\leq i\leq 10^{18}$), separados por um espaço em branco, representando os índices que fazem parte dos testes secretos.

Saída

Se o código de Tarcísio concordar com o gabarito em todos os índices presentes nos testes secretos imprima, em uma linha, a mensagem AC. Caso contrário, imprima WA.

Exemplo de entrada 1

3
1 3 7

Exemplo de saída 1

AC

Exemplo de entrada 2

5
1 2 3 4 5

Exemplo de saída 2

WA

Exemplo de entrada 3

4
3 6 7 11

Exemplo de saída 3

AC