After a long day, Alice and Bob decided to play a little game. The game board consists of $n$ cells in a straight line, numbered from $1$ to $n$, where each cell contains a number $a_i$ between $1$ and $n$. Furthermore, no two cells contain the same number. 

A token is placed in one of the cells. They take alternating turns of moving the token around the board, with Alice moving first. The current player can move from cell $i$ to cell $j$ only if the following two conditions are satisfied:   the number in the new cell $j$ must be strictly larger than the number in the old cell $i$ (i.e. $a_j > a_i$), and  the distance that the token travels during this turn must be a multiple of the number in the old cell (i.e. $|i-j|\bmod a_i = 0$). 

Whoever is unable to make a move, loses. For each possible starting position, determine who wins if they both play optimally. It can be shown that the game is always finite, i.e. there always is a winning strategy for one of the players.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 10^5$) — the number of numbers.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$). Furthermore, there are no pair of indices $i \neq j$ such that $a_i = a_j$.


-----Output-----

Print $s$ — a string of $n$ characters, where the $i$-th character represents the outcome of the game if the token is initially placed in the cell $i$. If Alice wins, then $s_i$ has to be equal to "A"; otherwise, $s_i$ has to be equal to "B". 


-----Examples-----
Input
8
3 6 5 4 2 7 1 8

Output
BAAAABAB

Input
15
3 11 2 5 10 9 7 13 15 8 4 12 6 1 14

Output
ABAAAABBBAABAAB



-----Note-----

In the first sample, if Bob puts the token on the number (not position):   $1$: Alice can move to any number. She can win by picking $7$, from which Bob has no move.  $2$: Alice can move to $3$ and $5$. Upon moving to $5$, Bob can win by moving to $8$. If she chooses $3$ instead, she wins, as Bob has only a move to $4$, from which Alice can move to $8$.  $3$: Alice can only move to $4$, after which Bob wins by moving to $8$.  $4$, $5$, or $6$: Alice wins by moving to $8$.  $7$, $8$: Alice has no move, and hence she loses immediately.

Difficulty: interview

Starter code:

Solutions:
import sys


def __starting_point():
    cin = sys.stdin

    n = int(next(cin))
    a = list(map(int, next(cin).split()))

    n2idx = {a[i]: i for i in range(n)}

    f = [False] * (n+1)

    for i in range(n, 0, -1):
        idx_lg = n2idx[i]

        win_flag = False
        for j in range(idx_lg%i, n, i):
            if a[j] > i and not f[a[j]]:
                win_flag = True
                break
        f[i] = win_flag
        
    f = ''.join(['A' if f[a_i] else 'B' for a_i in a])
    print(f, flush=True)

__starting_point()

n = int(input())
board = list(map(int,input().split(" ")))
index = list(range(0,n))
ascending = [x for _,x in sorted(zip(board,index))]

winners = n * [""]


for c in reversed(ascending):
	if board[c] == n:
		winners[c] = "B"
	# going down
	toCheck = c - board[c]
	while(toCheck >= 0):
		if winners[toCheck] == "B":
			winners[c] = "A"
		toCheck = toCheck - board[c]
	if winners[c] == "":
		toCheck = c + board[c]
		while(toCheck < n):
			if winners[toCheck] == "B":
				winners[c] = "A"
			toCheck = toCheck + board[c]
	if winners[c] == "":
		winners[c] = "B"
	#print("board at c",board[c])
	#print(c)
	#print(winners)

for i in range(n):
	print(winners[i],end="")
print()
		
	



n=int(input())
l=[-1 for i in range(n+1)]
s=input().split()
ll=[int(i) for i in s]
for i in range(n):
    j=ll[i]
    l[j]=i
res=["." for i in range(n+1)]
res[n]="B"
for i in range(n-1,0,-1):
    toadd="B"
    pos=l[i]%i
    while pos<n:
        j=ll[pos]
        if j<=i:
            pos+=i
            continue
        if abs(l[i]-l[j])%i==0 and res[j]=="B":
            toadd="A"
            break
        pos+=i
    res[i]=toadd
for i in ll:
    print(res[i],end="")
print("")


n=int(input())
L=list(map(int,input().split()))
ans=['']*n
revL=[0]*n
ans[-1]='B'
for i in range(n):
    revL[L[i]-1]=i+1
for i in range(n-2,-1,-1):
    t=revL[i]-1
    counter='B'
    for j in range(t,-1,-i-1):
        if j==t:continue
        if ans[L[j]-1]=='B':
            counter='A'
            break
    if counter!='A':
        for k in range(t,n,i+1):
            if k==t:continue
            if ans[L[k]-1]=='B':
                counter='A'
                break
    ans[i]=counter
for i in range(n):
    print(ans[L[i]-1],sep='',end='')

n = int(input())
a = [int(i) for i in input().split()]
indx = [0] * n
winners = [''] * n

for i, ai in enumerate(a):
    indx[ai-1] = i

for ai in range(n, 0, -1):
    i = indx[ai-1]
    can_win = False

    for j in range(i + ai, n, ai):
        if a[j] > ai and 'B' == winners[j]:
            can_win = True
            break

    if not can_win:
        for j in range(i - ai, -1, -ai):
            if a[j] > ai and 'B' == winners[j]:
                can_win = True
                break

    if can_win:
        winners[i] = 'A'
    else:
        winners[i] = 'B'

print(''.join(winners))


import sys

next(sys.stdin)

positions = {}
pos2x = {}
for i, x in enumerate(next(sys.stdin).split()):
    x = int(x)
    positions[x] = i
    pos2x[i] = x

answers = ['' for _ in range(len(positions))]

for x in range(len(positions), 0, -1):

    position = positions[x]

    def can_go_to_looser():

        next_position = position + x
        while next_position < len(positions):

            if pos2x[next_position] > x and answers[next_position] == "B":
                return True

            next_position += x

        next_position = position - x
        while next_position >= 0:

            if pos2x[next_position] > x and answers[next_position] == "B":
                return True

            next_position -= x

        return False

    if can_go_to_looser():
        answers[position] = "A"
    else:
        answers[position] = "B"

print(''.join(answers))


n = int(input())

arr = list(map(int, input().split()))

memo = [-1 for i in range(n+1)]
def can_win(idx):
	if memo[idx] != -1: return memo[idx]
	res = False

	delta = arr[idx]
	# right
	nidx = idx + delta
	while nidx < n:
		if arr[nidx] > arr[idx] and not can_win(nidx):
			res = True
			break
		nidx += delta

	#left
	nidx = idx - delta
	while not res and nidx >= 0:
		if arr[nidx] > arr[idx] and not can_win(nidx):
			res = True
			break
		nidx -= delta

	memo[idx] = res
	return res

ans = ['A' if can_win(i) else 'B' for i in range(n)]
print(''.join(ans))


import sys
input = sys.stdin.readline

n=int(input())
A=list(map(int,input().split()))
PLACE=[None]*(n+1)
for i in range(n):
    PLACE[A[i]]=i

al=n


WINLIST=[None]*(n+1)#0:そこに行けば必敗,1:そこにいけば必勝

def move(n,al):
    place=PLACE[n]
    for i in range(place,-1,-n):
        if A[i]>n and WINLIST[A[i]]=="B":
            WINLIST[n]="A"
            return
            
    for i in range(place,al,n):
        if A[i]>n and WINLIST[A[i]]=="B":
            WINLIST[n]="A"
            return 

    else:
        WINLIST[n]="B"
        return 
   

for j in range(n,0,-1):
    move(j,al)


ANS=""
for i in A:
    ANS+=WINLIST[i]

print(ANS)


n=int(input())
arr=[int(x) for x in input().split()]
pos=dict()
if(n==1):print("B")
else:
    for i in range(n):
        pos[arr[i]]=i
    ans=["Q"]*n
  
    ans[pos[1]]="A"
    ans[pos[n]]="B"
    for i in range(n-1,0,-1):
        flag=0
        p=pos[i]
        j=1
        while(p+j*i<n):
            if(ans[p+j*i]=="B"):
                flag=1
                ans[pos[i]]="A"
                break
            j+=1
        if(flag==0):
            j=1
            while(p-j*i>=0):
                if(ans[p-j*i]=='B'):
                    flag=1
                    ans[pos[i]]="A"
                    break
                j+=1
        if(flag==0):ans[pos[i]]="B"
    print("".join(ans))
        



n = int(input())
a = [int(s) for s in input().split()]
ans = [None]*n

def get(p):
    # print(ans)
    if ans[p] is not None:
        return ans[p]
    elif a[p] == 1:
        ans[p] = "A"
    elif a[p] == n:
        ans[p] = "B"
    else:
        for i in range(p+a[p], n, a[p]):
            if a[i] > a[p]:
                if get(i) == "B":
                    ans[p] = "A"
                    return ans[p]
        for i in range(p-a[p], -1, -a[p]):
            if a[i] > a[p]:
                if get(i) == "B":
                    ans[p] = "A"
                    return ans[p]
        ans[p] = "B"
    return ans[p]

if n == 1:
    print("B")
else:
    for i in range(n-1, -1, -1):
        get(i)
    print(''.join(ans))

n = int(input())
l = [0]+list(map(int,input().split()))
from collections import defaultdict
ans = ['A','B']
x = defaultdict(int)
table = [-1]*(n+1)
for i in range(1,n+1):
	x[l[i]] = i

table[x[n]] = 1
for i in range(n-1,0,-1):
	if(x[i]-i>0):
		for j in range(x[i],0,-i):
			if(l[j]>i):
				if(table[j]==1):
					table[x[i]] = 0
					break
	if(n-i>0 and table[x[i]]==-1):
		for j in range(x[i],n+1,i):
			if(l[j]>i):
				if(table[j]==1):
					table[x[i]] = 0
					break

	if(table[x[i]]==-1):
		table[x[i]] = 1

for i in table[1:]:
	print(ans[i],end='')

from operator import itemgetter
n = int(input())
ai = list(map(int,input().split()))
ai2 = [[ai[i], i] for i in range(n)]
answer = [0] * n
ai2.sort(key = itemgetter(0))
answer[ai2[0][1]] = 1
answer[ai2[-1][1]] = 0
for i in range(n-2,0,-1):
    num = ai2[i][1] % ai2[i][0]
    for j in range(num,n,ai2[i][0]):
        if ai[j] > ai2[i][0] and answer[j] == 0:
            answer[ai2[i][1]] = 1
            break
for i in range(n):
    if answer[i] == 1:
        print("A",end="")
    else:
        print("B",end="")


a = int(input())
lister = input().split()
lister = [int(i) for i in lister]

ans = dict()
	
def findans(n):
	if n in ans:
		return ans[n]
	mod = n%lister[n]
	ok = True
	if n + lister[n] >= a and n - lister[n] < 0:
		ok = False
	else:
		for i in range(mod, a, lister[n]):
			if i != n and lister[i] > lister[n]:
				ok = ok and findans(i) 
				
		ok = not(ok)
		
	ans[n] = ok
	return ok
	
for i in range(len(lister)):
	findans(i)
	
level = []
for i in range(a):
	if ans[i] == True:
		level.append('A')
	else:
		level.append('B')
		
print(''.join(level))

# from collections import deque

n = int(input())
a = [int(x) for x in input().split()]

a_reverse = a.copy()
status = []
for i in range(n):
    a_reverse[a[i]-1] = i
    status.append(None)


pos = a_reverse[n-1]
status[pos] = False
fails = set()
fails.add(pos)
for i in range(n-1,0,-1):
    i_ = i-1
    pos = a_reverse[i_]
    for k in range((pos+1)%i-1,n,i):
        if k == pos:
            continue
        if k in fails:
            status[pos] = True
            break
    if not status[pos]:
        status[pos] = False
        fails.add(pos)


# BAAAABAB
# ABAAAABBBAABAAB


# status = []
# for i in range(n):
#     status.append(None)

# queue = deque()

# def eval_(pos):
#     pos_status = status[pos]
#     for i in range(n):
#         if i == pos:
#             continue
#         if status[i] != None:
#             continue
#         if  a[i] > a[pos]:
#             continue
#         if (abs(i - pos) % a[i]) == 0:
#             status[i] = not pos_status
#             queue.append(i)

# pos = a.index(n)
# status[pos] = False
# queue.append(pos)
#
# while len(queue) != 0:
#     item = queue.popleft()
#     eval_(item)
#
# print(status)
#
result = ""
for i in status:
    if i == True:
        result=result+"A"
    else:
        result=result+"B"

print(result)






from math import ceil

n=int(input())
r=list(map(int,input().split()))
l=[-1]
l.extend(r)
a=['']*(n+1)
d={}
rd={}
ind={}
for i in range(1,n+1):
    x=l[i]
    ind[x]=i
    d.setdefault(i,[])
    s=x+i
    while s<=n:
        if l[s]>x:
            d[i].append(s)
            if s not in rd:
                rd[s]=[]
            rd[s].append(i)
        s+=x
    s = i-x
    while s >=1:
        if l[s] > x:
            d[i].append(s)
        s -= x

ans=0

for i in d:
    if len(d[i])==0:
        a[i]='B'
        ans+=1
#print(a)
#print(d[5])
while ans!=n:
    for i in d:
        dont=False
        if a[i]!='':
            continue
        for j in d[i]:
            if a[j]=='B':
                a[i]='A'
                ans+=1
                break
            if a[j]=='':
                dont=True
        else:
            if not dont:
                a[i]='B'
                ans+=1
 #   print(a)
print(''.join(a))

from collections import deque
from sys import stdin
lines = deque(line.strip() for line in stdin.readlines())

def nextline():
    return lines.popleft()

def types(cast, sep=None):
    return tuple(cast(x) for x in strs(sep=sep))

def ints(sep=None):
    return types(int, sep=sep)

def strs(sep=None):
    return tuple(nextline()) if sep == '' else tuple(nextline().split(sep=sep))

def main():
    # lines will now contain all of the input's lines in a list
    n = int(nextline())
    a = ints()
    bs = set()
    moves = {}
    for i in range(n):
        moves[a[i]] = list(a[j] for j in range(i % a[i], n, a[i]) if a[j] > a[i])
    winners = {}
    for i in range(n, 0, -1):
        winner = 'A' if any(winners[j] == 'B' for j in moves[i]) else 'B'
        if winner == 'B':
            bs.add(i)
        winners[i] = winner
    print(''.join(winners[ai] for ai in a))


def __starting_point():
    main()

__starting_point()

n = int(input())
board = list(map(int, input().strip().split()))
board.insert(0,0)
hashed = [0] * (n+1)
for i in range(n+1):
	hashed[board[i]] = i
answer = ['C'] * (n+1)
for i in range(n,0,-1):	
	flag = 0
	k = hashed[i] - board[hashed[i]]
	while(k > 0):
		if(answer[k] == 'B'):
			flag = 1
			break
		k-=board[hashed[i]]
	k = hashed[i] + board[hashed[i]]
	while(k <= n and k != 0):
		if(answer[k] == 'B'):
			flag = 1
			break
		k+=board[hashed[i]]
	if(flag == 1):
		answer[hashed[i]] = 'A'
	else:
		answer[hashed[i]] = 'B'
answer.pop(0)
print(''.join(answer))


n=int(input())
l=[-1 for i in range(n+1)]
s=input().split()
ll=[int(i) for i in s]
for i in range(n):
    j=ll[i]
    l[j]=i
res=["." for i in range(n+1)]
res[n]="B"
for i in range(n-1,0,-1):
    toadd="B"
    pos=l[i]%i
    while pos<n:
        j=ll[pos]
        if j<=i:
            pos+=i
            continue
        if abs(l[i]-l[j])%i==0 and res[j]=="B":
            toadd="A"
            break
        pos+=i
    res[i]=toadd
for i in ll:
    print(res[i],end="")
print("")

n = int(input())
a = [int(x) for x in input().split()]
h = [-1]*(n)
b = [(a[i],i) for i in range(n)]
b.sort(reverse=True)
for e in b:
	# ~ print(e)
	num,idx = e
	flag = True
	allNeg = True
	foundLosing = False
	foundWin = False
	for i in range(idx%num,n,num):
		# ~ print(i)
		if i == idx:
			continue
		if h[i]!= -1:
			allNeg = False
		if h[i] == 0:
			foundLosing = True
			break
		if h[i] == 1:
			foundWin = False
	if allNeg:
		h[idx] = 0
	elif foundLosing:
		h[idx] = 1
	else:
		h[idx] = 0	
	# ~ print(" ".join(str(ss) for ss in h))
for i in range(n):
	if h[i]==0:
		print('B',end='')
	else:
		print('A',end='')
		
# ~ print(h)


n = int(input())
l = [*map(int, input().split())]

p = [0] * n
for i in range(n): p[l[i] - 1] = i

res = ['?'] * n

for e in range(n, 0, -1):
    i = p[e - 1]
    res[i] = 'B'
    for j in range(i % e, n, e):
        if i != j and l[i] <= l[j] and res[j] == 'B':
            res[i] = 'A'
            break 
print(''.join(res))

n=int(input())
a=[*list(map(int,input().split()))]
b=[0]*n
s=[0]*n
m=n
while m:
 for i,x in enumerate(a):
  if s[i]==0:
   r=list(range(i%x,n,x))
   if all(a[j]<=x or s[j]=='A'for j in r):s[i]='B';m-=1
   if any(a[j]>x and s[j]=='B'for j in r):s[i]='A';m-=1
print(''.join(s))
  
 


n=int(input())
a=[*map(int,input().split())]
b=[0]*n
s=[0]*n
m=n
while m:
 for i,x in enumerate(a):
  if s[i]==0:
   r=range(i%x,n,x)
   if all(a[j]<=x or s[j]=='A'for j in r):s[i]='B';m-=1
   if any(a[j]>x and s[j]=='B'for j in r):s[i]='A';m-=1
print(''.join(s))

n=int(input())
a=[*map(int,input().split())]
s=[0]*n
m=n
while m:
 for i,x in enumerate(a):
  if s[i]==0:
   r=range(i%x,n,x)
   if all(a[j]<=x or s[j]=='A'for j in r):s[i]='B';m-=1
   if any(a[j]>x and s[j]=='B'for j in r):s[i]='A';m-=1
print(''.join(s))

n=int(input())
a=[*map(int,input().split())]
s=[0]*n
m=n
while m:
 for i,x in enumerate(a):
  if s[i]==0:
   r=range(i%x,n,x)
   if all(a[j]<=x or s[j]=='A'for j in r):s[i]='B';m-=1
   elif any(a[j]>x and s[j]=='B'for j in r):s[i]='A';m-=1
print(''.join(s))

n=int(input())
a=[*map(int,input().split())]
s=[0]*n
m=n
while m:
 for i,x in enumerate(a):
  if s[i]==0:
   r=range(i%x,n,x)
   if all(a[j]<=x or s[j]=='A'for j in r):s[i]='B';m-=1
   if any(a[j]>x and s[j]=='B'for j in r):s[i]='A';m-=1
print(''.join(s))