Когда кот Бенедикт был котёнком, он с удовольствием взбирался по шторам на гардину и гулял по ней. Собственно, он и сейчас не прочь пройтись по гардине, но предпочитает перебираться на неё со шкафа, поскольку путь по шторам по ряду причин не представляется ему безопасным. К тому же не так давно его хозяйка решила поменять шторы. Бенедикт с интересом наблюдал за процессом развешивания штор.

Каждая штора держится на $$$n$$$ крючках. К сожалению, крючки уже не очень хорошо двигаются вдоль гардины, поэтому шторы приходится вешать, почти не смещая крючки. Впрочем, шторы достаточно легкие, поэтому хозяйка кота Бенедикта действует следующим образом.

Сначала она закрепляет штору на крючках с номерами $$$1$$$ и $$$n$$$ (можете считать, что это происходит одновременно). После этого она каждый раз выбирает наиболее длинный отрезок из неиспользованных крючков и закрепляет штору в середине этого отрезка. Опишем процесс более формально.

Пусть на некотором шаге имеется некоторое количество $$$k$$$ отрезков $$$[l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]$$$, где $$$l_j$$$ и $$$r_j$$$ — номера крючков, $$$1 \lt l_1 \le r_1 \lt l_2 \le r_2 \lt \ldots \lt l_k \le r_k \lt n$$$. Для каждого такого отрезка верно, что ни на одном крючке, начиная с $$$l_j$$$ и заканчивая $$$r_j$$$, штора ещё не закреплена.

Хозяйка Бенедикта выберет тот отрезок, для которого $$$r_j - l_j$$$ максимально; если же таких отрезков несколько, выберет самый левый из них (с наименьшим $$$j$$$). Количество свободных крючков на отрезке $$$[l_j, r_j]$$$ равно $$$r_j - l_j + 1$$$. Если это количество нечётное, хозяйка Бенедикта закрепляет штору на среднем крючке (его номер $$$l_j + (r_j - l_j)/2$$$). Если же количество крючков чётное, хозяйка Бенедикта закрепляет штору на двух средних крючках (с номерами $$$l_j + (r_j - l_j - 1)/2$$$ и $$$l_j + (r_j - l_j +1)/2$$$).

Ваша задача — по заданным номерам крючков определить, на каком шаге на каждом из них была закреплена штора.

В первых трех подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.

В следующих трёх подзадачах баллы начисляются только в случае прохождения всех тестов этой подзадачи. Участнику сообщается либо номер первого непройденного теста и результат проверки на этом тесте, либо что все тесты подзадачи пройдены.

Также для некоторых подзадач требуется, чтобы программа верно решала предшествующие подзадачи. Более подробно разбиение на подзадачи показано в таблице ниже.