A dragon curve is a self-similar fractal curve. In this problem, it is a curve that consists of straight-line segments of the same length connected at right angles. A simple way to construct a dragon curve is as follows: take a strip of paper, fold it in half \(n\) times in the same direction, then partially unfold it such that the segments are joined at right angles. This is illustrated here:
In this example, a dragon curve of order \(3\) is constructed. In general, a dragon curve of a higher order will have a dragon curve of a lower order as its prefix. This allows us to define a dragon curve of infinite order, which is the limit of dragon curves of a finite order as the order approaches infinity.
Consider four dragon curves of infinite order. Each starts at the origin (the point \((0,0)\)), and the length of each segment is \(\sqrt2\). The first segments of the curves end at the points \((1,1)\), \((-1,1)\), \((-1,-1)\) and \((1,-1)\), respectively. The first turn of each curve is left (that is, the second segment of the first curve ends at the point \((0,2)\)). In this case, every segment is a diagonal of an axis-aligned unit square with integer coordinates, and it can be proven that there is exactly one segment passing through every such square.
Given a point \((x,y)\), your task is to find on which of the four curves lies the segment passing through the square with the opposite corners at \((x,y)\) and \((x+1,y+1)\), as well as the position of that segment on that curve. The curves are numbered \(1\) through \(4\). Curve \(1\) goes through \((1,1)\), \(2\) through \((-1,1)\), \(3\) through \((-1,-1)\), and \(4\) through \((1,-1)\). The segments are numbered starting with \(1\).
Output
For each test case, print a line containing two integers — the first is the index of the curve (an integer between \(1\) and \(4\), inclusive), and the second is the position on the curve (the first segment has the position \(1\)).