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
daedaldan: 2020-01-14 00:09:14

@joe85123 @harish_49 @psetter Would you mind sending me your solution at daniel22373@gmail.com? I've working on this one, and I want a hint or two to push me in the right direction. Thanks!

harish_49: 2019-09-23 11:19:25

AC in 1 go

itssanat: 2019-03-30 10:19:15

nice problem:)

joe85123: 2018-07-11 17:34:11

Really nice problem! Finally AC after so many tries

Last edit: 2019-11-18 17:59:57
khoaph: 2018-06-30 10:12:33

Oh my pretty code but got TLE

drexter: 2018-04-12 18:05:34

@psetter please check my code having id :- 21512185..i am getting wrong answer after 15 test cases

soham_12345: 2017-07-19 22:18:39

Can anyone tell me where I am going wrong? Submission id : 19827082 .. I used a simple dfs

shanku_iiith: 2016-10-13 15:41:13

Last edit: 2016-10-13 22:57:40
mohitsinghdz: 2016-09-30 11:30:28

the reason this problem cant be solved is snakes,
these SOB's mood cant be determined hence cant find which light the will lit

aeon: 2016-09-17 23:00:58

@psetter Kindly have a look at my solution ( id : 17732677 ), I have considered even the cyclic cases, but still I am getting WA after 15 test cases.


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")