Problem A
The Beginning of the End - Part 1

Last year, the two rulers of Equestria, Princess Celestia and Princess Luna, had a row over what each perceived as the other’s lack of gratitude to her efforts. With your help, they conquered their friendship problem and a major calamity was averted.

A bigger threat looms over Equestria today.

Figure 1: Illustration by Kyle Coate.

The feared and ruthless King Sombra, who once enslaved the entire Crystal Empire, has returned to exact his revenge. Moving quickly and stealthily through the kingdom, he usurped its throne and swiftly imprisoned the monarchs before enslaving its population. Now, with his massive army, he plans to invade the rest of Equestria!

Chief Equestrian strategists in Canterlot immediately got to work, identifying potential locations of military significance. Every location identified was also given two estimations; the $i^\text {th}$ location identified was estimated to have an Equestrian advantage $G_ i$ and a Sombran advantage $B_ i$. This denotes the military advantage Equestria and Sombra receive when capturing the $i^\text {th}$ location, respectively. Note that $G_ i$ is not necessarily equal to $B_ i$; there are some locations that are more strategically valuable to one faction or the other. For example, some locations may have magical weapons only usable by one faction.

The strategists have created a simplified model for the conquest phase of the war:

• Both factions alternate turns, with Equestria going first.

• During a faction’s turn, it sends troops to capture one location that has not previously been captured by either faction.

• The conquest phase is over when no location remains that is still not captured by either faction.

• At the end of the conquest phase, the victor is the faction whose total military advantage is larger. If they are equal, there is no victor and the conquest has gone into a military stalemate.

A perfect strategy is one where

1. if a faction can force a victory (i.e. regardless of the other faction’s actions, there is a response that eventually leads to a victory), they will;

2. if a faction cannot force a victory, they will instead try to force a military stalemate.

Assuming a perfect strategy by both factions, it is possible to determine with certainty the outcome based on this model.

Alas, the problem is not this simple! The data is coming in live, as strategists are discovering more and more locations of military significance. Prompt response is imperative, so as each location comes in, the strategists need to know: what will be the outcome this time?

There will be a total of $N$ locations. Determine the outcome as each new location is identified.

Interaction

First, your program should read a single integer $N$ ($1 \leq N \leq 200\, 000$), the number of locations eventually identified by chief Equestrian strategists.

Then, we repeat the following process $N$ times:

• Your program should read two integers $G_ i$ ($1\leq G_ i \leq 200\, 000$) and $B_ i$ ($1 \leq B_ i \leq 200\, 000$), denoting that the $i^\text {th}$ location identified was estimated to have an Equestrian advantage of $G_ i$ and a Sombran advantage of $B_ i$.

• Your program writes a single line to the standard output containing a single character:

  • G, if a perfect strategy by both factions results in Equestrian victory,

  • B, if a perfect strategy by both factions results in Sombran victory, or

  • S, if a perfect strategy by both factions results in a military stalemate.

Note in particular that your program will not be provided the estimates for the next location until you have provided the response for the current set of locations.

After you have provided all $N$ responses, your answer will be checked. Your program should terminate immediately after this.

After giving each response, do not forget to output end of line and flush the output. To do this, use:

• fflush(stdout) or cout.flush() in C++;

• System.out.flush() in Java;

• stdout.flush() in Python;

• see documentation for other languages.

Sample interaction