ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

USU Open Personal Contest 2007

About     Problems     Submit solution     Judge status     Standings
Contest is over

I. Battle for the Ring

Time limit: 1.0 second
Memory limit: 64 MB
Saruman the White and Gandalf the Grey play a game. The winner will get the Master-ring. There are rings joined into K chains lying in front of the players. For each ring, the percentage of gold is known; it is an integer in the range from 1 to 100. Saruman and Gandalf make moves by turns. In each move a player chooses a ring and dematerializes it together with all the rings from the same chain that contain no more gold than the chosen ring. As a result, the chain may break up into several smaller chains, and the game is continued with the remaining chains. He who dematerializes the last ring is a winner. Gandalf moves first. Your task is to determine if Gandalf can win and if he can which ring he must choose for his first move.

Input

The first line contains the integer K, 1 ≤ K ≤ 50. Each of the next K lines describes the corresponding chain in the following format: the first number is the length of the chain, which is an integer from 1 to 100, then there go the percentages of gold in the rings of this chain. The numbers in the line are separated with a space.

Output

Output «S» if Saruman will win the Master-ring. Otherwise, in the first line output «G» and in the second line output two integers that describe Gandalf's first move: the number of the chain and the number of the ring in it. The chains and rings in them are numbered from 1. If there are several first moves that guarantee Gandalf's win, output the move with the minimal number of the chain, and if there are several such moves, output the move with the minimal number of the ring.

Samples

inputoutput
2
3 1 2 1
1 1
G
1 1
2
3 2 1 2
1 1
S
Problem Author: Alexander Ipatov
Problem Source: VIII USU Open Personal Contest (March 3, 2007)
To submit the solution for this problem go to the Problem set: 1540. Battle for the Ring