IMP - The Imp

no tags 

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]


hide comments
:D: 2018-10-22 15:48:31

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.

Aayush Sharda: 2016-03-12 14:42:45

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|)

Haris Khan: 2012-07-21 13:15:09

more test cases plzz......

.::Manish Kumar::.: 2010-06-17 18:17:56

can ne1 explain how example is correct...i don't have time to figure that out!! :P


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