B. Раскрашивание яиц
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Необъяснимый народ эти битландцы. Какие же у них странные обычаи!

Как обычно, дядя J. хочет раскрасить n яиц для известного Битландского фестиваля, который называется Битруз. Дядя J. попросил выполнить эту работу G. и A. Дети очень обрадовались. Ведь они знают, что им заплатят за работу.

Всего у дяди J. есть n яиц. Для каждого яйца G. назвал количество денег, которое он требует за покраску этого яйца. Аналогично, для каждого яйца A. назвал количество денег, которое он требует за покраску этого яйца. Оказалось, что для каждого яйца сумма количеств денег, которые требует за покраску A. и G., равна 1000.

Дядя J. хочет поделить яйца между детьми так, чтобы каждое яйцо было отдано на покраску ровно одному ребенку. Также дядя хочет, чтобы сумма денег которая достанется A. отличалась от суммы денег, которая достанется G. не более чем на 500.

Помогите дяде J. Найдите требуемое распределение яиц или скажите, что разделить яйца требуемым образом не получится.

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 106) — количество яиц. В каждой из следующих n строк записано два целых числа: ai, gi (0 ≤ ai, gi ≤ 1000; ai + gi = 1000) — количество денег, которое требует A. за покраску i-того яйца, и количество денег, которое требует G. за покраску i-того яйца.

Выходные данные

Если разделить яйца между детьми требуемым образом нельзя, выведите «-1» (без кавычек).

Иначе выведите строку, состоящую из n символов «G» и «A»: i-тый символ должен обозначать того, кому достанется i-тое яйцо в требуемом распределении (символ «A» обозначает A., символ «G» обозначает G.). Если обозначить сумму денег, которую дядя должен будет отдать A. за покраску, через Sa, а сумму денег, которую дядя должен будет отдать G. за покраску, через Sg, должно выполняться неравенство |Sa - Sg| ≤ 500.

Если существует несколько решений, разрешается вывести любое.

Примеры
Входные данные
2
1 999
999 1
Выходные данные
AG
Входные данные
3
400 600
400 600
400 600
Выходные данные
AGA