← 返回题目列表

Codeforces · 282/B

B. 画鸡蛋

中文机器翻译题面 查看原题

比特兰人是很奇怪的人。他们有非常奇特的习俗。

按照惯例,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