Limits 2s, 512 MB

Sawda and Alayna have received a remote-controlled toy robot as a gift from their beloved uncle, Mridul. They are happily playing with it together in a rectangular room with LL meters in length and WW meters in width, surrounded by walls in all directions. The walls are parallel to either the North-South line or the East-West line. We can imagine this room with 2D coordinates, where (0,0)(0,0) means the North-West corner and (L,W)(L,W) means the South-East corner. The robot has minimal length and width, you can assume it as a point on the floor. The remote-controlled robot can do the following actions any number of times (possibly zero) -

  1. Rotate 90o90^{o} clockwise, or

  2. Go forward exactly xx meters in the direction the robot is currently facing. But if the distance to the wall in that direction is strictly less than xx meters, it crashes and stops at the wall.

However, the robot cannot rotate while moving or move while rotating.

The robot is currently in (a,b)(a,b) position, facing north. They want to move the robot to the (c,d)(c,d) position. I don't know why. They are children. They do weird things. But they don't want to crash it too many times, because too many crashes can break the toy.

Determine the minimum number of crashes required to move the robot from (a,b)(a,b) to (c,d)(c,d), or report if it is impossible.


The first line contains an integer TT (1T105)(1 \le T \le 10^5) denoting the number of test cases. Each test case is described by four line lines -

  • The first line of each test case contains two space-separated integers LL and WW (1L,W109)(1 \leq L,W \leq 10^9) denoting the length and the width of the room in meters respectively.

  • The second line of each test case contains an integer xx (1x109)(1 \leq x \leq 10^9) denoting the distance the robot moves in meters in each ‘‘go forward’’ action if it doesn't crash in the meantime.

  • The third line contains two space-separated integers aa (0aL)(0 \leq a \leq L) and bb (0bW)(0 \leq b \leq W) denoting the initial coordinates of the robot.

  • The fourth line contains two space-separated integers cc (0cL)(0 \leq c \leq L) and dd (0dW)(0 \leq d \leq W) denoting the coordinates of the expected destination.


For each test case, print an integer in a single line denoting the minimum number of crashes required to go from (a,b)(a,b) to (c,d)(c,d), or print -1 if it is impossible.


3 3
1 1
2 2
3 3
2 1
1 1

For the first test case, the robot can go (1,1)(1,2)(2,2)(1,1) \rightarrow (1,2) \rightarrow (2,2).

For the second test case, the robot can go (2,1)(3,1)(1,1)(2,1) \rightarrow \textbf{(3,1)} \rightarrow (1,1).

Here bold letters imply that the robot has encountered a crash.


Login to submit.


50% Solution Ratio
asifm91Earliest, 6M ago
nafim1703Fastest, 0.1s
Cloud_Lightest, 5.1 MB
asifm91Shortest, 447B
Toph uses cookies. By continuing you agree to our Cookie Policy.