Kile, a board games enthusiast, recently discovered the game Robots. The game consists of a board with n rows and m columns and one robot. The field (1, 1) is the top-left field of the board, while the field (n, m) is the bottom-right.

At the beginning, the robot is positioned on some field (x, y) (x-th row, y-th column), and the player can direct it in one of the four directions: up, down, left, or right. Depending on the chosen direction, it will move in that direction until it encounters its goal or a special field on the board. If at any point it wants to exit the board, it wraps around to the other side. For example, if it is located at the field (n, 3) and wants to move down, it will arrive at the field (1, 3).

The board has three types of fields:

Empty field - the robot continues moving in the same direction
Left turn field - when the robot steps on this field, it will turn left by 90° and continue moving
Right turn field - when the robot steps on this field, it will turn right by 90° and continue moving

Most fields on the board are empty, only k of them are left or right turn fields.

The game consists of q rounds. In the i-th round of the game, the robot will be placed on the field (a_i , b_i). The goal is to reach the field (c_i , d_i) using the minimum number of turns, or determine that it is impossible.

After playing this game several times, Kile realized that it is more challenging than it initially seemed. That is why he needs your help now. Help him determine the minimum number of turns required for each round of the game!

Note: If the robot starts or finishes its path on a left or right turn field, that turn is not counted.

#7075 upload - done - how_to_reg - call_split Subtask

Roboti timer 2s memory 1024MB

#7075
Subtask

Roboti 2s 1024MB