Time Limit: 1000 ms
Memory Limit: 65535 KB
Over centuries ago, mankind faced a new enemy, the Titans. The difference of power between mankind and their newfound enemy was overwhelming. Soon, mankind was driven to the brink of extinction. Luckily, the surviving humans managed to build three walls: Wall Maria, Wall Rose and Wall Sina. Owing to the protection of the walls, they lived in peace for more than one hundred years.
But not for long, a colossal Titan appeared out of nowhere. Instantly, the walls were shattered, along with the illusory peace of everyday life. Wall Maria was abandoned and human activity was pushed back to Wall Rose. Then mankind began to realize, hiding behind the walls equaled to death and they should manage an attack on the Titans.
While commander Pixis think intelligence is the key of winning the war. So,he chooses the very clever soldiers Armin to play a game with him with the purpose of training him.And the game’s rules are: Pixis and Armin play the game on a white board with many grids.The board has f(n) rows and f(m) columns, so it contains f(n)*f(m) grids. The two people play the game in turn and Pixis let Armin start first and then he plays. In every turn the man who plays need to choose a quadrilateral with the sizes of 1*k or k*1 and the area he choose has to be completely white, then fill the area in black.(The positive integer k(1<=k<=max(f(n),f(m))) is decided by the player in every turn). So, the man who fills the last grid in black is the winner.
Now,we let f(n) be a sum of digits for positive integer n. If f(n) is one-digit number then f(n) is n and otherwise f(n) is equal to f(f(n)). For example, f(987) is 6,because f(987)=f(24)=f(6)=6.
And now we assume the two man are both clever enough,so they can both take the best strategy. Can you predict who is the winner just according the size of board ?