Bouncing Ball and Laser Beams

Consider a ball (modeled as a point) moving inside an $n\times m$ grid. The bottom‑left corner of the grid is at $(1,1)$ and the top‑right corner is at $(m,n)$. In the grid, there are laser beams along every vertical line $x=k$ (for integer $k$ between $1$ and $m$) and every horizontal line $y=k$ (for integer $k$ between $1$ and $n$). When the ball touches a laser beam, it is counted as a hit; if the ball touches a crossing point (i.e. where a vertical and a horizontal laser meet) at the same time, it is only counted once.

The ball is given an initial position and moves with a constant velocity. However, when it touches a boundary, it reflects perfectly: if the ball’s horizontal velocity is $v_x$ and vertical velocity is $v_y$, then upon touching the left or right boundary the horizontal component reverses (i.e. $v_x$ becomes $-v_x$), and upon touching the top or bottom boundary the vertical component reverses (i.e. $v_y$ becomes $-v_y$).

You are given $q$ queries; in each query the ball’s initial position, velocity, and the duration of motion are provided. Assume that the ball’s initial coordinates and velocity components are integers, and that the ball always starts exactly on a laser beam (since its coordinates are integers). However, the initial condition is not counted as a hit. You are to determine the number of times the ball touches any laser beam over the given time period.

Unfolding Idea: It can be shown using an unfolding argument that the total number of beam touches is equal to the total number of crossings with vertical and horizontal lines. If we let

[ A = |v_x| \times t, \quad B = |v_y| \times t, ]

then if both $A>0$ and $B>0$, the number of beam touches is

[ \text{touches} = A+B - \gcd(A,B). ]

If one of $A$ or $B$ is zero then the touches equal the positive one (since no overlapping can occur in that case). For example, if $v_x=0$, then the ball only moves vertically and the number of touches is $B$, while if both $v_x=0$ and $v_y=0$ the answer is $0$.

Note: The grid dimensions affect the ball’s bouncing behavior but not the overall count of beam touches, because the unfolding method preserves the total traveled distance.

inputFormat

The first line contains three integers n, m, and q --- the grid dimensions and the number of queries, respectively.

Each of the next q lines contains five integers: x, y, vx, vy, and t. Here, (x, y) is the starting position of the ball, and every second the ball's position is updated as follows: the x-coordinate increases by vx and the y-coordinate increases by vy. Note that when the ball hits a boundary it reflects according to the rules described above.

outputFormat

For each query, output a single integer --- the total number of times the ball touches a laser beam. If the ball touches an intersection (where a vertical and horizontal beam meet) at the same moment, it is counted as only one hit.

sample

5 5 3
2 3 1 1 3
1 1 1 0 4
3 4 2 1 3

3
4
6