比特兰人是很奇怪的人。他们有非常奇特的习俗。
按照惯例,J. 叔叔想要为 Bitruz(一个古老的比特兰节日)画 n 个鸡蛋。他已要求 G. 和 A. 来做这项工作。
孩子们很兴奋,因为按照惯例,他们将获得这份工作的报酬!
J叔叔总共有n个鸡蛋。 G. 列出了为每个鸡蛋上漆的价格。同样,A. 列出了为每个鸡蛋上漆的价格。事实证明,对于每个鸡蛋,A. 和 G. 想要购买这幅画的钱总和等于 1000。
J.叔叔想要在孩子们之间分配鸡蛋,以便将每个鸡蛋恰好给一个孩子。此外,J. 叔叔希望支付给 A. 的总金额与支付给 G. 的总金额相差不超过 500。
帮助J叔叔找到所需的鸡蛋分配,否则说以所需的方式分配鸡蛋是不可能的。
输入
第一行包含整数 n (1 ≤ n ≤ 106) — 鸡蛋的数量。
接下来的 n 行分别包含两个整数 ai 和 gi (0 ≤ ai, gi ≤ 1000; ai + gi = 1000):ai 是 A. 对第 i 个鸡蛋所说的价格,gi 是 G. 对第 i 个鸡蛋所说的价格。
输出
如果无法分配绘画,请打印“-1”(不带引号)。
否则打印一个字符串,由 n 个字母“G”和“A”组成。该字符串的第 i 个字母应代表将在所需分配中获得第 i 个鸡蛋的孩子。字母“A”代表 A.,字母“G”代表 G。如果我们将 J. 叔叔必须为这幅画支付给 A. 的钱表示为 Sa,而 J. 叔叔必须为这幅画支付给 G. 的钱为 Sg,那么这个不等式必须成立: |Sa - Sg| ≤ 500。
如果有多个解决方案,您可以打印其中任何一个。
示例
输入 #1
2 1 999 999 1
输出 #1
AG
输入 #2
3 400 600 400 600 400 600
输出 #2
AGA