Кривая дракона Junior
Кривая дракона – это бесконечная ломаная из звеньев единичной длины, которая строится следующим образом. Выбирается некоторая точка на плоскости (например, точка (0, 0)) и одно из четырех направлений, параллельных координатным осям. Левый(правый) дракон порядка n строится так:
если n равно 0, то отложить отрезок длины 1 от текущей точки в текущем направлении, переместившись в конечную точку;
в противном случае построить левого дракона порядка n-1 от текущей точки в текущем направлении, повернуться на 90 градусов налево (направо) в его конечной точке и построить правого дракона порядка n-1.
Поскольку левый дракон порядка n содержит в качестве своего начала левого дракона порядка n-1, то вполне корректно определяется левый дракон бесконечного порядка. Именно эта ломаная и называется кривой дракона.
Построим из точки (0, 0) кривые дракона во всех четырех направлениях. Есть теорема, доказанная Д.Кнутом, о том, что эти кривые не пересекаются (за исключением касания в вершинах) и полностью покрывают целочисленную сетку на плоскости. В данной задаче от вас потребуется проверить эту теорему, а именно по заданному единичному отрезку сетки определить какому из четырех драконов он принадлежит.
Входные данные
В единственной строке входного файла задаются 4 целых числа: две координаты одного конца некоторого отрезка, параллельного одной из осей координат, и две координаты другого конца.
Все числа не превышают по модулю 10^9. Расстояние между точкам равно 1.
Выходные данные
В первой строке выходного файла выведите номер драконовой кривой, которой принадлежит соответствующее звено (1 – дракон, отложенный в положительном направлении оси Ox, 2 – в положительном направлении оси Oy, 3 – в отрицательном направлении оси Ox, 4 – в отрицательном направлении оси Oy). Во второй строке выведите номер этого звена в соответствующей ломаной. Гарантируется, что это число не превосходит 10^7.