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

1540. 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.


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 «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.


3 1 2 1
1 1
1 1
3 2 1 2
1 1
Problem Author: Alexander Ipatov
Problem Source: VIII USU Open Personal Contest (March 3, 2007)