merge

Cerință

Se dau două șiruri, $a$ și $b$, fiecare a câte $n$ numere naturale. Prin aplicarea unei permutări $p$ asupra unui șir $v$, înțelegem înlocuirea lui $v_i$ cu $v_{p_i}$. Practic, prin aplicarea lui $p$ asupra unui șir $v$, înțelegem reordonarea elementelor lui $v$ în funcție de ordinea dată de $p$.

Pentru o permutare $p$, considerăm următorul algoritm:

Fie a' șirul a asupra căruia am aplicat p.
Fie b' șirul b asupra căruia am aplicat p.

i <- 1
j <- 1
cât timp i <= n și j <= n:
  dacă a'[i] <= b'[j]:
    i <- i + 1
  altfel:
    j <- j + 1
	
dacă i == n + 1 atunci:
  șirul a câștigă permutarea p
altfel:
  șirul b câștigă permutarea p

Pentru $t$ scenarii independente, se cere să se afle care dintre $a$ și $b$ câștigă mai multe permutări ale $\{1, 2, ..., n\}$, conform algorimului de mai sus.

Date de intrare

Pe prima linie se află numărul $t$ - numărul de teste pe care trebuie să le rezolvați. Formatul unui test este următorul:

• pe prima linie se află numărul $n$;
• pe a doua linie se află numerele $a_1$, $a_2$, ..., $a_n$;
• pe a treia linie se află numerele $b_1$, $b_2$, ..., $b_n$;

Date de ieșire

Pentru fiecare dintre cele $t$ teste, se va afișa "A" (fără ghilimele) dacă șirul $a$ câștigă mai multe permutări, respectiv "B" altfel.

Restricții și precizări

• $1 \leq t \leq 10^5$
• $1 \leq n \leq 10^6$
• $1 \leq a_i, b_i \leq 10^9$, pentru $i = 1, 2, \dots, n$
• Suma $n$-urilor din fiecare fișier de test nu va depăși $10^6$
• Se garantează că pentru datele de intrare, șirurile $a$ și $b$ nu pot câștiga același număr de permutări.
• Pentru tests în valoarea de 40 de puncte, $1 \leq n \leq 7$

Exemplu

stdin

2
2
1 2
2 2
3
4 5 6
1 2 3

stdout

A
B

Explicație

Avem de rezolvat două teste. Pentru primul test, avem două permutări:

1. $p = (1, 2)$. Atunci $a' = [1, 2]$ și $b' = [2, 2]$.
2. $p = (2, 1)$. Atunci $a' = [2, 1]$ și $b' = [2, 2]$.

Se poate observa că șirul $a$ câștigă ambele permutări.

Pentru al doilea test se poate arăta că șirul $b$ câștigă mai multe permutări decât $a$.