[The problem appeared in TopCoder SRM 594 (Div-2, Level-1)]
Problem link: http://community.topcoder.com/stat?c=problem_statement&pm=12811
Fox Ciel is now in high school. The seats in her classroom are arranged into an n by m matrix. The rows are numbered from 0 to n-1 (front to back) and the columns from 0 to m-1 (left to right).
At the beginning, Ciel can choose any of the seats. Then, at the end of each week Ciel will shift one row to the back and one column to the right, wrapping around whenever necessary. Formally, if her current seat is in row r and column c, then her seat next week will be the one in row ((r+1) modulo n) and column ((c+1) modulo m).
Fox Ciel now wonders whether she can sit in all the seats in the classroom if she follows the above procedure. As we already mentioned, she can start in any of the seats. Also, she can attend the school for as many weeks as she wants to. Return “Possible” if she can sit in all the seats and “Impossible” otherwise.