厌倦了总是排队，你发明了一个革命性的餐厅概念：“STACKS!，最后进来的顾客最先被服务”。

餐厅的运作方式如下： 餐厅内只有一条队伍。 当顾客进入时，他们会立即加入队伍的末尾。 * 每当一份糖霜煎饼（STACKS! 的唯一菜品）准备好时，它会被提供给队伍末尾的顾客，该顾客随后立即吃掉煎饼并离开餐厅。

这种商业模式非常成功，以至于 STACKS! 开始扩张。事实上，你刚刚开设了第一家 STACKS!+，提供两种煎饼：糖霜煎饼和咸味煎饼。新餐厅的运作方式如下： 有两条队伍，每种煎饼各对应一条。每位顾客加入他们想要的煎饼类型所对应的队伍末尾。 每当一份糖霜煎饼准备好时，它会被提供给糖霜煎饼队伍末尾的顾客，该顾客立即吃掉它并离开餐厅。 * 每当一份咸味煎饼准备好时，它会被提供给咸味煎饼队伍末尾的顾客，该顾客立即狼吞虎咽地吃掉它并离开餐厅。

作为老板，你希望确保员工遵循这一概念并维持你的愿景。给定顾客进出餐厅的顺序，你需要确定是否存在一种顾客分配方案，使得 STACKS!+ 的概念得以遵循。

你可以假设每当顾客进入餐厅时，他们会立即加入某条队伍的末尾，并且他们在被服务后立即离开。此外，每位顾客只访问餐厅一次。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 1000$)，表示访问 STACKS!+ 的顾客数量。每位顾客由 $1$ 到 $N$ 之间的一个不同整数标识。

第二行包含 $2N$ 个带符号整数 $X_1, X_2, \dots, X_{2N}$ ($1 \le |X_i| \le N$，对于 $i = 1, 2, \dots, 2N$)，按时间顺序表示顾客的进入和离开。值 $X_i = +c$ 表示顾客 $c$ 进入餐厅，而 $X_i = -c$ 表示其离开。保证每位顾客恰好进入和离开一次，且他们不会在进入之前离开。

输出格式

如果存在一种顾客分配方案使得 STACKS!+ 的概念得以遵循，则输出一行长度为 $N$ 的字符串。在这种情况下，字符串的第 $i$ 个字符必须是大写字母“G”（如果顾客 $i$ 被分配到糖霜煎饼队伍）或大写字母“S”（如果他们被分配到咸味煎饼队伍）。如果存在多种方案，输出其中任意一种即可。

如果给定输入无法遵循 STACKS!+ 的概念，则输出字符“*”（星号）。

样例

输入 1

2
+2 +1 -1 -2

输出 1

GG

输入 2

2
+1 +2 -1 -2

输出 2

GS

输入 3

3
+1 +2 +3 -1 -2 -3

输出 3

*