Cups

Minseung gives Jungmoon the following game. Jungmoon is blindfolded, so he cannot see which cup contains the ball.

There are N cups numbered from 1 to N. At first, Minseung puts a ball into one of them, but Jungmoon does not know which one. Then, at each step, Jungmoon says one letter, either A or B. Minseung takes the ball from its current cup and puts it into another cup; he may also put it back into the same cup.

If the ball is currently in cup K, saying A moves it to cup A_K, and saying B moves it to cup B_K. All of these destinations are fixed in advance and are known to Jungmoon.

Jungmoon must choose a string so that, no matter which cup initially contained the ball, after all letters are applied the ball is certainly in cup 1. Find and print one string consisting only of A and B that satisfies this condition. The printed string must have length at most 10,000.

The first line contains the number of cups N (1 ≤ N ≤ 500). Each of the next N lines contains two integers A_K and B_K for one cup K. In other words, the second input line contains A_1 and B_1, the third line contains A_2 and B_2, and so on.

Print the string Jungmoon should say. The string must consist only of the letters A and B. If several valid strings exist, print any one of them. Every input is guaranteed to have at least one valid answer, and the printed string must have length at most 10,000.