题目描述

有$n$ 个蛋，A和G需要给这$n$ 个鸡蛋涂色。A涂第$i$ 个鸡蛋得到的钱为$A_i$ ，G涂第$i$ 个鸡蛋得到的钱为$G_i$ ，且满足$A_i+G_i=1000$ 。需要把这$n$ 个鸡蛋分配给A和G，求怎样分配使得A和G得到的钱$S_A$ 和$S_G$ 的差不超过$500$ 。

输入格式

第一行一个整数$n(1\le n\le 10^6)$ 。

接下来$n$ 行，每行两个整数$A_i,G_i(0\le A_i,G_i\le 1000,A_i+G_i=1000)$ 。

输出格式：

一行，长度为 $n$ 的字符串，第 $i$ 个字符为 A或G，表示分配方案。

有多种解输出任意一种，需要满足 $|S_A-S_G|\le 500$。

如果无解，输出 -1。

2
1 999
999 1

AG

3
400 600
400 600
400 600

AGA