Hello.

I'm stuck in this problem for a while now.(It reminded me with the "Berzerk" problem here)

To be honest; I never really understood this kind of problems nor did I ever understand why a solution is always possible(When the author says so).

When I think of it(or any similar problem) I always believe that it will go on forever..

Specially when the statement says; "If both the players play clever and cautious(or optimally)..

When I read the examples, an idea crossed my mind; the player will win if and only if he can get to the north-east,north-west,south-east,south-west cell of his opponent's.

However, I don't know whether that is the only possibility.

Please note that I don't need help with the first two subtasks which are: R=2 & C=2 and R <= 100 & C=1.

The real problem is with the other two subtasks: R,C <= 100 and R,C <= 1e9 ...

Any hints?

Thanks!