If main streets are not used

In this case, the solution is \((|S_x-G_x|+|S_y-G_y|) \times K\).

If main streets are used

Let us call a lattice point a good lattice point if at least one of the \(x\) and \(y\) coordinates is a multiple of \(B\). Also, let us call a lattice point a wonderful lattice point if both \(x\) and \(y\) coordinates are multiples of \(B\).

We search the first and the last good lattice point on the path exhaustively.

The candidates of the first good lattice point are the first point you reach a main street when you start walking from \((S_x,S_y)\) in one of the four directions: up, down, left, or right.

For example, if \(B=3,(S_x,S_y)=(1,1)\), then the candidates are \((1,3),(1,0),(0,1),(3,1)\).

This property can be justified because if a lattice point \(A\) the first good lattice point on the path, then you can reach \(A\) earlier by heading one of the four good lattice points above first.

The candidates of the last lattice points are the same.

Thus, it is sufficient to solve the case where \((S_x,S_y)\) and \((G_x,G_y)\) are both good lattice points.

If one can travel from \((S_x,S_y)\) to \((G_x,G_y)\) in an Manhattan distance only using the main streets, then that is optimal.

If at least one of \((S_x,S_y)\) and \((G_x,G_y)\) are wonderful lattice points, then such path exists, so we assume that neither \((S_x,S_y)\) nor \((G_x,G_y)\) is a wonderful lattice point.

One can travel in an Manhattan distance only using the main streets if at least of the following is satisfied:

• \(S_x \bmod N = 0\) and \(G_y \bmod N = 0\)
• \(S_y \bmod N = 0\) and \(G_x \bmod N = 0\)
• \(S_x \bmod N = 0\) and \(G_x \bmod N = 0\) and \(\lfloor \frac{S_y}{B} \rfloor \neq \lfloor \frac{G_y}{B} \rfloor\)
• \(S_y \bmod N = 0\) and \(G_y \bmod N = 0\) and \(\lfloor \frac{S_x}{B} \rfloor \neq \lfloor \frac{G_x}{B} \rfloor\)

Conversely, the conditions above are not satisfied if:

• \(S_x \bmod N = 0\) and \(G_x \bmod N = 0\) and \(\lfloor \frac{S_y}{B} \rfloor = \lfloor \frac{G_y}{B} \rfloor\)
• \(S_y \bmod N = 0\) and \(G_y \bmod N = 0\) and \(\lfloor \frac{S_x}{B} \rfloor = \lfloor \frac{G_x}{B} \rfloor\)

Here, we solve the case where \(S_x \bmod N = 0\) and \(G_x \bmod N = 0\) and \(\lfloor \frac{S_y}{B} \rfloor = \lfloor \frac{G_y}{B} \rfloor\).

In this case, we may try two paths: only using main roads, and escaping from the main roads, as in the blue and red path in the figure below, respectively:

Therefore, the problem has been solved in a total of \(\mathrm{O}(T)\) time.