A land far, far away has ~N~ Members of Parliament (MP). They had a turbulent and passionate debate on the law on amendments to the law on a new referendum on referendums. From Monday to Friday, all MPs joyfully came to work and argued all day.

A diligent news reporter photographed MPs at their workplace in the heat of the argument every working day of the week. What she captured on the photos are pairs of MPs fighting and scowling at each other. The five photographs have been forwarded to you for thorough analysis.

It is a fact that each MP belongs to one of the two political parties. Let's denote them with letters A and B. Your task is to estimate which MP belongs to which party, so that the following holds for your estimation: each MP argued with at most two distinct members of their own party.

Input

The first line of input contains an integer ~N~ ~(2 \le N \le 200\,000)~, the number of MPs. MPs are denoted with numbers from ~1~ to ~N~.

The following five lines describe the photographs taken from Monday to Friday. Each of the five lines contains the list of pairs of MPs that are arguing on the photograph that day (scowling at each other). Stated first is the number of pairs ~P~ ~(1 \le P \le \dfrac{N}{2})~, followed by ~P~ pairs in the form of K L, where ~K~ and ~L~ are labels of MPs scowling at each other. Before each pair there is a double space.

Of course, each MP is stated at most once per line.

Output

The first and only line of output must contain an array consisting of only characters A and B, so that the ~K^{th}~ character denotes the party of ~K^{th}~ MP in a division that satisfies the given conditions.

Since the solution isn't going to be unique, output any.

Scoring

In test cases worth 30% of total points, it will hold ~N \le 15~.

Sample Input 1

7
2  1 2  7 3
2  1 3  7 4
2  1 4  7 5
2  1 5  7 6
2  1 6  7 2

Sample Output 1

ABBBBBA

Sample Input 2

10
3  1 2  7 3  9 4
3  1 3  7 4  9 5
3  1 4  7 5  9 6
3  1 5  7 6  9 8
3  1 6  7 8  9 10

Sample Output 2

ABBBBBAAAA