Traffic Signal Navigation Optimization

You are given a grid of size \(N\) rows and \(M\) columns representing a road network. Every vehicle starts at a given location and needs to reach its destination. However, the vehicles can only move in certain directions depending on the state of the traffic signals.

The traffic signal switches between two states every \(T\) time units. When the signal is in the first state (i.e. when \(\lfloor\frac{time}{T}\rfloor\) is even), vehicles can only move horizontally (left or right). When the signal is in the second state (i.e. when \(\lfloor\frac{time}{T}\rfloor\) is odd), they can only move vertically (up or down). Vehicles are always allowed to wait in place for one time unit.

Your task is to compute the minimum time required for each vehicle to reach its destination following the rules above. The grid is 1-indexed, and movements outside the grid are prohibited.

inputFormat

The input consists of multiple datasets. Each dataset is formatted as follows:

1. A line containing three integers \(N\), \(M\), and \(T\) separated by spaces, where \(N\) and \(M\) are the number of rows and columns of the grid, and \(T\) is the duration for which the traffic signal stays in one state.
2. A line containing a single integer \(V\), the number of vehicles.
3. \(V\) lines follow, each containing four integers: \(sx\), \(sy\), \(dx\), \(dy\), representing the starting and destination coordinates of a vehicle.

The input terminates with a line containing "0 0 0" which should not be processed.

outputFormat

For each dataset, output a single line containing the minimum travel times for each vehicle separated by a space. If a vehicle cannot reach its destination, output -1 for that vehicle.

## sample

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

4 2
6

</p>