SP19224 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.

The first line contains an integer N (2 N ), 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.

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**.