High Dragon Curve#2865
The dragon curve is an infinite broken line made up of segments of unit length, constructed as follows. A point on the plane is chosen (for example, the point ), and one of the four directions parallel to the coordinate axes is selected. The left (or right) dragon of order is constructed as follows:
If is , draw a segment of length from the current point in the current direction, moving to the endpoint.
Otherwise, construct a left dragon of order n-1 from the current point in the current direction, turn degrees to the left (or right) at its endpoint, and construct a right dragon of order n-1.
Since the left dragon of order starts with the left dragon of order n-1, the left dragon of infinite order is well defined. This broken line is called the dragon curve.
We construct dragon curves from the point in all four directions. There is a theorem proven by D. Knuth stating that these curves do not intersect each other (except for touching at vertices) and completely cover the integer grid on the plane. In this problem, you are required to check this theorem, that is, for a given unit grid segment, determine which of the four dragons it belongs to.
The input contains a single line with integers: the coordinates of one end of a segment parallel to one of the coordinate axes, and the coordinates of the other end.
All numbers are less than or equal to 10^9 by absolute value. The distance between the points is .
In the first line, output the number of the dragon curve containing the given segment ( for the dragon in the positive direction, for the positive direction, for the negative direction, for the negative direction). On the second line, output the sequence number of this segment in the corresponding broken line. It is guaranteed that this number does not exceed 10^{12}.
Esempio 1