University of Toronto ACM-ICPC Tryouts 2012
We're all familiar with the classic 2-player game of skill, Rock Paper Scissors. In each round, both players first choose one of the three objects. If both players choose the same one, it's a tie. Otherwise, if one player chooses Rock and the other chooses Scissors, the first player wins - similarly, Scissors beats Paper, and Paper beats Rock.
This game is pretty boring, though, so you're playing a variation with your friend - Rock Paper Scissors Fox. In addition to the above objects, a player may choose Fox - and, if the other player chooses one of the three basic objects, the first player wins. However, because this is so powerful, it should only be used when necessary. The only thing that can beat a Fox is, naturally, several of them - namely, Foxen. Nothing beats Foxen.
You're planning to play ~N~ ~(1 \le N \le 10^6)~ rounds of this game, and you conveniently know what object your opponent will choose in each one. You'd like to use this knowledge to beat him every time. If he chooses one of the three basic objects, you should pick the basic one that beats it. If he chooses Fox, you should choose Foxen. And if he chooses Foxen, you should of course walk away before that round occurs, and not play any rounds from then onwards.
Line 1: 1 integer, ~N~
Next ~N~ lines: Your opponent's choice in the ~i~-th round (one of the strings
for ~i = 1\ldots N~
~X~ lines (where ~X~ is the number of rounds you play): Your choice in the ~i~th round (in the same format as the input), for ~i = 1 \dots N~.
5 Scissors Fox Rock Foxen Paper
Rock Foxen Paper
Explanation of Sample
In the first round, your opponent chooses Scissors, so you should choose Rock to beat it. In the second, you beat his Fox with Foxen, and in the third, you choose Paper to beat Rock. You don't play any more rounds, because your opponent will choose Foxen in the fourth round, which can't be overcome.