Вася играет в компьютерную игру про ниндзя. На данном уровне игры ниндзя, за которого играет Вася, нужно выбраться из глубокого ущелья.

Ущелье представляет из себя две отвесные параллельные стены высотой n метров. Мысленно разобьем эти стены на участки длины 1 метр и пронумеруем их натуральными числами от 1 до n снизу вверх. Некоторые участки обычные — по ним ниндзя может карабкаться. Другие же покрыты шипами и ниндзя не может на них находиться. Назовем такие участки опасными.

Изначально нинздя находится на нижнем участке левой стены. Каждую секунду он может сделать одно из действий:

• подняться на один участок вверх;
• спуститься на один участок вниз;
• перепрыгнуть на противоположную стену, при этом ниндзя оказывается на участке, который ровно на k метров выше того участка, с которого производился прыжок. Более формально, если до прыжка ниндзя находился на участке номер x одной стены, то после прыжка, он будет находиться на участке номер x + k другой стены.

Если в какой-то момент времени, ниндзя пытается переместиться на участок с номером большим n, то считается, что ниндзя выбрался из ущелья.

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

Уровень считается пройденным, если ниндзя удалось выбраться из ущелья.

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