Крива дракона Junior#2866

Крива дракона Junior

1 секунда

64 мегабайти

Дуже легка

Драконова крива — це нескінченна послідовність з'єднаних відрізків одиничної довжини, яку будуємо таким чином. Починаємо з вибраної точки на площині (наприклад, $(0, 0)$ ) і вибору одного з чотирьох напрямків, паралельних координатним осям. Лівий (або правий) дракон порядку $n$ будується так:

Якщо $n = 0$ n = 0, проведіть відрізок довжини $1$ з поточної точки у поточному напрямку, перемістившись до його кінця.
Інакше побудуйте лівого дракона порядку $n - 1$ n-1 з поточної точки у поточному напрямку. У його кінці поверніть на $90$ градусів вліво (або вправо), а потім побудуйте правого дракона порядку $n - 1$ n-1.

Оскільки лівий дракон порядку $n$ починається з лівого дракона порядку $n - 1$ n-1, лівий дракон нескінченного порядку визначений коректно. Ця послідовність відрізків називається драконовою кривою.

Побудуємо драконові криві, починаючи з точки $(0, 0)$ у всіх чотирьох напрямках. Згідно з теоремою, доведеною Д. Кнутом, ці криві не перетинаються (крім вершин) і повністю покривають цілочислову ґратку на площині. У цій задачі вам потрібно перевірити цю теорему: для заданого одиничного ґраткового відрізка визначити, до якої з чотирьох драконових кривих він належить.

Вхідні дані

Єдиний рядок вхідних даних містить $4$ цілі числа: координати одного кінця відрізка, паралельного одній із координатних осей, та координати іншого кінця.

Усі числа не перевищують $1 0^{9}$ 10^9 за модулем. Відстань між точками дорівнює $1$ .

Вихідні дані

У першому рядку виведіть номер драконової кривої, до якої належить цей відрізок ( $1$ — дракон у додатному напрямку $O x$ , $2$ — у додатному напрямку $O y$ , $3$ — у від'ємному напрямку $O x$ , $4$ — у від'ємному напрямку $O y$ ). У другому рядку виведіть індекс цього відрізка у відповідній драконовій кривій. Гарантується, що це число не перевищує $1 0^{7}$ 10^7.

Приклади

Приклад 1