When the game ends, it will happen either at the original position or right after hitting a corner. You can only hit a wall from ~2~ possible directions, so it must come back from the reverse direction to hit the same spot again. Otherwise, it could have only come from the original position which would have already been visited twice. Thus, we just need to look for the first time the bullet revisits the starting position or hits a corner.

Subtask 1

A well implemented simulation which only visits necessary cells should run in ~\mathcal{O}(NM)~ time.

Subtask 2

Set up a system of congruences to find the first time the bullet revisits the starting position or hits a corner. Since modulo are not necessarily coprime, a modified chinese remainder theorem is required to solve the system. Calculate all the times, then take the minimum value for the answer.