Problem E
The Beginning of the End - Part 2

Previously...

A bigger threat looms over Equestria today.

Chief Equestrian strategists in Canterlot identified potential locations of military significance. The $i^\text {th}$ location identified was estimated to have an Equestrian advantage $g_ i$ and a Sombran advantage $b_ i$.

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.

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

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

Now...

Canterlot has fallen. It was inevitable—we could not risk the capture of the princesses. They evacuated safely, but without them, it was only a matter of time before even the valiant royal guards succumbed to King Sombra’s dark magic.

Figure 1: Illustration by Kyle Coate.

Before Canterlot was sequestered, the strategists managed to telegraph to us the results of their findings. They sent a string of length $N$, describing the outcomes as each new location was identified. We also know where these locations are.

Regrettably, they were unable to send their original estimations for each location’s Equestrian or Sombran advantages in time, and with our dwindling numbers we have neither the time nor resources to do the research and determine those estimations again. Our only hope is to recover some estimate—any estimate—of these numbers consistent with the data and the model they were using, and wield them to the best of our ability to turn the tides of this war and defeat King Sombra once and for all.

It may not be good. It may not be accurate. But it’s all we have left. We have to try!

Input

The first line of input contains a single integer $N$ ($1 \leq N \leq 200\, 000$), the number of locations eventually identified by chief Equestrian strategists.

The second line of input contains a string of $N$ characters. In particular, the $i^\text {th}$ of these characters describes the outcome after including the $i^\text {th}$ location in the model:

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

• a B denotes that a perfect strategy by both factions results in Sombran victory, and

• an S denotes that a perfect strategy by both factions results in a military stalemate.

Output

If there is no set of estimates consistent with the given data, output a single line containing the string IMPOSSIBLE.

Otherwise, output $N$ lines, containing the potential estimates of the locations in the order they could have been identified. In particular, the $i^\text {th}$ of these lines 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 could have been estimated to have an Equestrian advantage of $g_ i$ and a Sombran advantage of $b_ i$;

If there are multiple correct answers, you can output any of them.

5
GBSGG

4 2
1 5
1 3
9 1
2 5

5
GSGSG

1 1
1 1
1 1
1 1
1 1