Hide

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.

$\includegraphics[width=0.35\textwidth ]{TBO_Sombra.png}$

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^{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^{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

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;
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^{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

Your output (standard output)	Kattis’ answer (standard input)	Interpretation
	$5$	There will be a total of $N = 5$ locations of military significance.
	$42$	The first location has Equestrian advantage $G_{1} = 4$ and Sombran advantage $B_{1} = 2$ .
$G$		As Equestria goes first, Equestrian victory is obvious: they simply send troops to capture the only location.
	$15$	The second location has Equestrian advantage $G_{2} = 1$ and Sombran advantage $B_{2} = 5$ .
$B$		Now, Sombran victory is guaranteed no matter what. If Equestria sends troops to capture the first location, Sombran forces will capture the second, and Sombra wins with $5$ military advantage to Equestria’s $4$ . If Equestria instead goes for the second location, Sombran forces will capture the first, and Sombra again wins, this time with $2$ military advantage to Equestria’s $1$ .
	$13$	The third location has Equestrian advantage $G_{3} = 1$ and Sombran advantage $B_{3} = 3$ .
$S$		Equestria cannot force a victory, but they can force a military stalemate. One way is to go for the first location. Now, Sombran forces can choose either the second or third location. Choosing the third location results in Equestrian victory, so Sombran forces will instead force a military stalemate by choosing the second location.
	$91$	The fourth location has Equestrian advantage $G_{4} = 9$ and Sombran advantage $B_{4} = 1$ .
$G$		Now Equestria can force a victory. One way is to go for the fourth location. Sombran forces will get two of the remaining locations so their maximum possible military advantage is $8$ , which is less than the $9$ Equestria is guaranteed.
	$25$	The fifth location has Equestrian advantage $G_{5} = 2$ and Sombran advantage $B_{5} = 5$ .
$G$		Equestria can still force a victory. One way is to go for the fourth location. Sombran forces will get two of the remaining locations so their maximum possible military advantage is $10$ , but Equestria will also get two of the remaining locations so they are guaranteed a military advantage of at least $11$ .

Problem AThe Beginning of the End - Part 1

Interaction

Sample interaction

Problem A
The Beginning of the End - Part 1