Мальчик Вася, чтобы попасть к себе домой на 10-й этаж, сначала поднимается до 7-го, а потом идет 3 этажа наверх, потому что в лифте кнопки расположены высоко, а Вася дотягивается максимум до кнопки 7-го этажа.
Сегодня Вася переезжает в новый многоэтажный дом с N этажами в квартиру на K-м этаже. Войдя в лифт, Вася увидел, что панель управления — это некоторое количество столбцов, в каждом из которых T кнопочек, причем в каждом столбце одинаковое число кнопок.
Первый столбец — это все этажи с 1 по T снизу вверх, второй — с T + 1 по 2·T, и так далее. Но Вася дотягивается только до первых L кнопок в каждом столбце.
Помогите Васе — напишите программу, которая определит, на какой этаж ему стоит ехать, чтобы пройти потом минимальное количество этажей по лестнице до этажа K. Если таких этажей несколько, то Вася выбирает тот, где нужно спускаться вниз, а не подниматься наверх.
В единственной строке дано 4 целых числа через пробел — N, K, T, L, положительные числа, не превосходящие 109 (T — делитель числа N, K ≤ N, L ≤ T).
Выведите единственное число — ответ на задачу.
10 5 2 1
5
20 9 5 2
11
Во первом примере из условия в доме 10 этажей, и в каждом столбце по 2 кнопки. Получаем 5 столбцов, а Вася достает в каждом столбце только 1 нижнюю кнопку. И, поэтому, он может сразу поехать на нужный ему 5-й этаж.
Марсианин Василий сегодня устроился работать в одну Очень Секретную Организацию. Для выполнения дальнейших заданий Вася должен придумать свой секретный пароль для шифровки сообщений. Он ответственно подошел к делу и заранее приготовил отличное слово на марсианском языке (известно, что марсианский алфавит состоит из 105 символов). Но к сожалению, новому сотруднику никто не сказал, что существует одно Очень Важное Правило: пароль не может содержать двух одинаковых подстрок (до появления этого правила ленивые агенты просто много раз повторяли свое имя, что плохо сказывалось на безопасности).
Подстрокой называется непустая часть строки, состоящая из подряд идущих символов исходной строки. Для примера, в строке «abс» имеются подстроки «a», «b», «c», «ab», «bc» и «abc». Других подстрок в строке «abc» нет.
Василий потратил очень много времени и сил, чтобы запомнить свой пароль, и совсем не хочет придумывать что-то новое. Поэтому он решил, что возьмет паролем подстроку исходного слова, которая не противоречит Очень Важному Правилу. Тогда ему не придется запоминать ничего нового. В то же время он хочет, чтобы пароль был как можно более надежным, поэтому нужна самая длинная такая подстрока. Но времени, чтобы искать ее, уже почти не осталось. Напишите программу, которая найдет такую подстроку.
В первой строке вводится целое число n (1 ≤ n ≤ 105) — длина слова.
В следующей строке вводится пароль Васи, состоящий из n букв марсианского алфавита. Каждая буква марсианского алфавита представляется натуральным числом, не превосходящим 105. Числа разделены пробелами.
В первой строке выведите максимальную длину пароля, который сможет использовать Василий. Во второй строке — сам пароль.
Если таких паролей несколько, выведите любой из них.
5
1 1 1 1 1
1
1
4
2 2 1 2
2
2 1
Петя занимается игрой на гитаре с малых лет и уже освоил почти все известные ему приемы игры на ней. В поисках достойного испытания для его недюжинных способностей Петя наткнулся на компьютерную игру «Виртуоз гитары».
В этой игре Пете дается маленькая игрушечная гитара, на которой есть всего две струны, и игрок должен исполнить композицию, состоящую из n нот. На каждой струне можно сыграть только одну из семи нот: от «до» до «си».
К счастью, Петя настолько наловчился играть в данную игру, что в перерыве между воспроизведением нот может чуть-чуть донастроить одну из струн на одну ноту выше или ниже. Однако он не может натягивать струну, если данная струна уже играет ноту «си», чтобы не порвать ее; и не может слишком сильно струну ослаблять, если струна уже играет ноту «до». Таким образом, Петя всегда остается в пределах одной октавы (ноты от «до» до «си»).
Поиграв так немного, Петя дошел до самого высокого уровня сложности и наткнулся на очень сложную мелодию. Напишите программу, определяющую по данной последовательности из n нот, сможет ли он исполнить эту композицию, и, если да, то какие струны нужно будет перенастраивать между исполнением нот. Перед началом своего выступления Петя может настроить струны на своей гитаре на любые ноты от «до» до «си» в пределах одной октавы.
В первой строке входных данных задано число n (1 ≤ n ≤ 200 000) — количество нот в композиции.
Во второй строке даны n целых чисел от 1 до 7 — ноты. Число 1 обозначает ноту «до», 2 — «ре», 3 — «ми», 4 — «фа», 5 — «соль», 6 — «ля», 7 — «си».
В первой строке выходных данных требуется вывести «YES», если данную мелодию можно исполнить, и «NO», если нельзя.
В случае, если мелодию можно сыграть, то в следующих n строках должны быть записаны пары чисел — на какие ноты настроена первая и вторая струна перед исполнением i-й ноты.
Если существует несколько правильных решений, необходимо вывести любое из них.
7
1 2 3 4 5 6 7
YES
3 1
3 2
3 1
4 1
5 1
6 1
7 1
4
1 3 7 2
NO