P15119 [ICPC 2024 LAC] Expanding STACKS!

厌倦了总是排队等候，你发明了一个革命性的餐厅概念：“STACKS！最后来的顾客最先被服务”。 这家餐厅的运营方式如下： - 餐厅内只有一条队伍。 - 当顾客进入餐厅时，他们立即排到队伍的末尾。 - 每当一份浇了糖浆的煎饼（STACKS！唯一供应的菜品）准备好时，它会被提供给队伍末尾的人，然后该顾客立即吃掉煎饼并离开餐厅。 这种商业模式取得了巨大成功，以至于 STACKS！开始扩张。 事实上，你刚刚开了第一家 STACKS！+，提供两种类型的煎饼：浇糖浆的和咸味的。新餐厅的运营方式如下： - 有两条队伍，每种煎饼对应一条。每位顾客排到他们想要的那种煎饼所对应的队伍的末尾。 - 每当一份浇糖浆的煎饼准备好时，它被提供给浇糖浆煎饼队伍末尾的顾客，该顾客立即吃掉它并离开餐厅。 - 每当一份咸味煎饼准备好时，它被提供给咸味煎饼队伍末尾的顾客，该顾客立即狼吞虎咽地吃掉它并离开餐厅。 作为老板，你想确保员工遵循这一概念并维护你的愿景。给定顾客进出餐厅的顺序，你需要判断是否存在一种将顾客分配到两条队伍的方法，使得 STACKS！+ 的概念得以遵循。 你可以假设每当顾客进入餐厅时，他们立即排到一条队伍的末尾，并且他们一被服务就立即离开。此外，每位顾客恰好光顾餐厅一次。

第一行包含一个整数 $N$（$1 \le N \le 1000$），表示光顾 STACKS！+ 的顾客数量。每位顾客由 $1$ 到 $N$ 之间的一个不同整数标识。 第二行包含 $2N$ 个有符号整数 $X_1, X_2, \dots, X_{2N}$（对于 $i = 1, 2, \dots, 2N$，有 $1 \le |X_i| \le N$），按时间顺序表示顾客的进入和离开。值 $X_i = +c$ 表示顾客 $c$ 进入餐厅，而 $X_i = -c$ 表示他们离开。保证每位顾客恰好进入和离开餐厅各一次，且他们不会在进入之前离开。

如果存在一种将顾客分配到两条队伍的方法使得 STACKS！+ 的概念得以遵循，则输出一行一个长度为 $N$ 的字符串。在这种情况下，字符串的第 $i$ 个字符必须是大写字母 "G"（如果顾客 $i$ 被分配到浇糖浆煎饼队伍）或大写字母 "S"（如果被分配到咸味煎饼队伍）。如果存在多种解决方案，输出任意一种即可。 如果给定的输入无法遵循 STACKS！+ 的概念，则输出字符 "*"（星号）。

翻译由 DeepSeek V3 完成