Sabor

Μια χώρα πολύ μακριά έχει \(Ν\) βουλευτές. Είχαν μια πολυτάραχη και παθιασμένη συζήτηση για τροπολογίες του νόμου για νέο δημοψήφισμα σχετικά με τα δημοψηφίσματα. Από Δευτέρα έως Παρασκευή όλοι οι βουλευτές έρχονταν χαρούμενοι στη δουλειά και μάλωναν όλη μέρα.

Ένας επιμελής ρεπόρτερ ειδήσεων φωτογράφιζε βουλευτές στο χώρο εργασίας τους εν μέσω καυγάδων κάθε εργάσιμη ημέρα της εβδομάδας. Αυτό που απαθανάτισε στις φωτογραφίες είναι ζευγάρια βουλευτών να τσακώνονται και να αγριοκοιτάγονται μεταξύ τους. Οι πέντε φωτογραφίες σας έχουν διαβιβαστεί για ενδελεχή ανάλυση.

Είναι γεγονός ότι κάθε βουλευτής ανήκει σε ένα από τα δύο πολιτικά κόμματα. Ας τα συμβολίσουμε με τα γράμματα ~A~ και ~B~. Το καθήκον σας είναι να υπολογίσετε ποιος βουλευτής ανήκει σε ποιο κόμμα, έτσι ώστε για την εκτίμησή σας να ισχύουν τα εξής: κάθε βουλευτής μάλωνε με το πολύ δύο ξεχωριστά μέλη του κόμματός του.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει έναν ακέραιο αριθμό ~N\;(2 \leq N \leq 200\,000)~, τον αριθμό των βουλευτών. Οι βουλευτές συμβολίζονται με αριθμούς από το 1 έως το ~N~.

Οι ακόλουθες πέντε γραμμές περιγράφουν τις φωτογραφίες που τραβήχτηκαν από Δευτέρα έως Παρασκευή. Κάθε μία από τις πέντε γραμμές περιέχει τη λίστα των ζευγαριών των βουλευτών που τσακώνονται στη φωτογραφία εκείνη την ημέρα (να αγριοκοιτάζονται μεταξύ τους).
Δηλώνεται πρώτος ο αριθμός των ζευγών ~P\;(1 \leq P \leq N/2)~, ακολουθούμενος από ~P~ ζεύγη με τη μορφή "~K\;L~", όπου το ~K~ και το ~L~ είναι ετικέτες των βουλευτών που αγριοκοιάζονται μεταξύ τους. Πριν από κάθε ζευγάρι υπάρχει ένα διπλό κενό.
Φυσικά, κάθε βουλευτής δηλώνεται το πολύ μία φορά ανά γραμμή.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει έναν πίνακα που αποτελείται μόνο από χαρακτήρες ~A~ και ~B~, έτσι ώστε ο ~K~-οστός χαρακτήρας να υποδηλώνει το κόμμα του ~K~-οστού πολιτικού σε ένα τμήμα που ικανοποιεί τις δεδομένες συνθήκες.

Εφόσον η λύση δεν θα είναι μοναδική, τυπώστε οποιαδήποτε.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας ~30~% των συνολικών πόντων, θα έχει ~N \leq 15~.

Παραδείγματα

input

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

output

ABBBBBA

input

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

output

ABBBBBAAAA