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|mod 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 ≤ n ≤ 10^5) — the number of numbers.

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ n). Furthermore, there are no pair of indices i ≠ 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. 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class C {
	
	public static void main(String[] args) {
		FastScanner fs=new FastScanner();
		int n=fs.nextInt();
		int[] board=fs.readArray(n);
		Space[] spaces=new Space[n];
		for (int i=0; i<n; i++) spaces[i]=new Space(board[i], i);
		Arrays.sort(spaces);
		boolean[] losingSpaces=new boolean[n];
		for (int i=n-1; i>=0; i--) {
			Space cur=spaces[i];
			boolean canHitLose=false;
			for (int dx=0; dx<=n; dx+=spaces[i].value) {
				int newPos=cur.pos+dx;
				if (newPos<0||newPos>=n) continue;
				if (board[newPos]>cur.value && losingSpaces[newPos]) {
					canHitLose=true;
				}
			}
			for (int dx=0; dx<=n; dx+=spaces[i].value) {
				int newPos=cur.pos-dx;
				if (newPos<0||newPos>=n) continue;
				if (board[newPos]>cur.value && losingSpaces[newPos]) {
					canHitLose=true;
				}
			}
			losingSpaces[cur.pos]=!canHitLose;
		}
		for (int i=0; i<n; i++) {
			System.out.print(losingSpaces[i]?"B":"A");
		}
		System.out.println();
	}
	
	static class Space implements Comparable<Space>{
		int value, pos;
		public Space(int value, int pos) {
			this.value=value;
			this.pos=pos;
		}
		
		public int compareTo(Space o) {
			return Integer.compare(value, o.value);
		}
	}

	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		
		public String next() {
			while (!st.hasMoreElements())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		
		public int nextInt() {
			return Integer.parseInt(next());
		}
		
		public long nextLong() {
			return Long.parseLong(next());
		}
		
		public int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) {
				a[i]=nextInt();
			}
			return a;
		}
		
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		
	}

}
