Dragon Curve Junior
The dragon curve is an infinite sequence of connected segments, each of unit length, constructed in the following manner. Begin by selecting a point on the plane, such as (0, 0), and choose one of the four directions parallel to the coordinate axes. The left (or right) dragon of order n is constructed as follows:
If n is 0, draw a segment of length 1 from the current point in the current direction, ending at the new endpoint.
Otherwise, construct the left dragon of order n-1 starting from the current point in the current direction. At its endpoint, turn 90 degrees to the left (or right) and then construct the right dragon of order n-1.
Since the left dragon of order n begins with the left dragon of order n-1, the left dragon of infinite order is well-defined. This sequence of segments is known as the dragon curve.
Let's construct dragon curves starting from the point (0, 0) in each of the four directions. According to a theorem proven by D. Knuth, these curves do not intersect (except at their vertices) and completely cover the integer grid on the plane. Your task is to verify this theorem by determining which of the four dragon curves a given unit grid segment belongs to.
Input
The input consists of a single line containing 4 integers: the coordinates of one endpoint of a segment parallel to one of the coordinate axes, followed by the coordinates of the other endpoint.
All numbers are within 10^9 in absolute value, and the distance between the points is 1.
Output
On the first line of the output, print the number corresponding to the dragon curve to which the segment belongs (1 for the dragon in the positive Ox direction, 2 for the positive Oy direction, 3 for the negative Ox direction, 4 for the negative Oy direction). On the second line, print the sequence number of this segment within the corresponding dragon curve. It is guaranteed that this number does not exceed 10^7.