IMP - The Imp

An Imp jumps on an infinite chessboard. Moves possible for the Imp are described by two pairs of integers: (a, b) and (c, d) - from square (x, y) the Imp can move to one of the squares: (x+a, y+b), (x-a, y-b), (x+c, y+d), (x-c, y-d). We want to know for which square different from (0, 0) to which the Imp can jump from (0, 0) (possibly in many moves) the value |x|+|y| is the lowest.

Task

Write a program which

  • reads from standard input two pairs (a, b) and (c, d) of integers, different from (0, 0), describing moves of the Imp,
  • determines a pair of integers (x, y) different from (0, 0), for which the Imp can jump (possibly in many moves) from square (0, 0) to square (x, y) and for which the value |x|+|y| is the lowest.
  • writes out to standard output the value |x|+|y|.

Input

Ten test cases. Each test consists of four numbers a, b, c, d in one line, separated by spaces.
-100000 <= a, b, c, d <= 100000

Output

For every test case your program should write a single line with a number equal the lowest possible value |x|+|y|.

Example

Input:
13 4 17 5
[and 9 test cases more]

Output:
2
[and 9 answers more]

Added by:Adam Dzedzej
Date:2004-06-15
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:Internet Contest Pogromcy Algorytmow(Algorithm Tamers) 2003 Round V

hide comments
2018-10-22 15:48:31 :D
Solution that gives 10 for "-7 6 9 2" also passes. It very possible there's only one test file with 10 cases, so they would be weak.
2016-03-12 14:42:45 Aayush Sharda
there is something wrong with this question
consider the test case
-7 6 9 2
an acceptable solution is the one which gives 13 as the answer but the correct answer is 10 (just add the two points |-7+9|+|6+2|)
2012-07-21 13:15:09 Haris Khan
more test cases plzz......
2010-06-17 18:17:56 .::Manish Kumar::.
can ne1 explain how example is correct...i don't have time to figure that out!! :P
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.