CAGES - Lights, Snakes and Cages


In the zoo there are N cages in which we keep N snakes: each snake in its cage. For experimental reasons, in a month we will move each snake to a different cage: this reordering is given in the input.

Each cage is illuminated by special light, which may be of type A, type B or type C. Your task is to assign the lights A, B, C to the cages so that:

  1. each snake will change its lighting, i.e. it will be moved to the cage illuminated differently from the cage it currently inhabits;
  2. lightings are equally distributed, i.e. the number of cages A, the number of cages B and the number of cages C differ by at most one.

Input

The first line contains an integer N (2 ≤ N ≤ 300 000), the number of snakes and cages. Cages are numbered from 1 to N.

Each of the next N lines contains an integer. When K-th of these lines contains the number L, it means that the snake from the cage K will be moved to the cage L (K ≠ L). Two snakes will not move to the same cage.

Output

Print the string composed of the characters A, B and C, such that the K-th character denotes the lighting of the cage K. If there are multiple solutions, print any.

Example

Input:
4
4
3
2
1

Output:
ACBC

hide comments
anurag garg: 2014-03-28 04:48:36

thanks for the reply...
still WA though...
good question
I checked my code with random case generator but couldn't find any testcase..:(

Last edit: 2014-04-03 12:02:11
Adrian Satja Kurdija: 2014-03-27 21:59:52

@garg Your program fails on this case:

7
4
7
6
1
2
5
3

anurag garg: 2014-03-27 20:43:13

@author can you have a look at my submission :11341176 and tell me where my algorithm fails
thanks

Bhavik: 2014-03-26 18:51:35

@psetter: thank you
now i can see where my algo fails! i will try it again

Adrian Satja Kurdija: 2014-03-26 18:35:34

ABABC

Bhavik: 2014-03-26 18:13:06

@psetter: can you kindly tell what will be the output of this:
5
2 1 4 5 3

i am unable to find the right configuration?

Last edit: 2014-03-26 18:13:21
Adrian Satja Kurdija: 2014-03-26 17:59:34

Yes.

Bhavik: 2014-03-26 12:15:38

@psetter: can u kindly explain the testcase? can ACAB be also the ans to the given test case??

Last edit: 2014-03-26 12:54:15

Added by:Adrian Satja Kurdija
Date:2014-03-24
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Croatia nationals 2014 (6th grade, 3rd problem "Zmije")