Чтобы поднять на N-й этаж M-этажного дома новый холодильник, Витя вызвал бригаду грузчиков. Оплата работы грузчиков производится так: за подъем холодильника на один этаж требуется заплатить 200 рублей, за спуск на один этаж — 100 рублей. За подъем и спуск на лифте плата не взимается. Несмотря на то, что в Витином доме есть лифт, ему возможно все же придется заплатить грузчикам, поскольку лифт останавливается только на каждом K-м этаже, начиная с первого (то есть на этажах с номерами 1, K+1, 2K+1, 3K+1, …). Требуется вычислить, какой минимальной суммы денег достаточно, чтобы грузчики доставили холодильник с первого этажа на N-й.

Числовая последовательность называется пилообразной если каждый ее член (кроме первого и последнего) либо больше обоих своих соседей, либо меньше обоих соседей. Например, последовательность 1, 2, 1, 3, 2 является пилообразной, а 1, 2, 3, 1, 2 — нет, поскольку 1 < 2 < 3. Любая последовательность из одного элемента является пилообразной. Последовательность из двух элементов является пилообразной, если ее элементы не равны.

Дана последовательность. Требуется определить, какое наименьшее количество ее членов нужно вычеркнуть, чтобы оставшаяся последовательность оказалась пилообразной.

Вася подошел к перекрестку и увидел, что на светофоре в этот момент загорелся красный свет. Вася залюбовался тем, как четко переключаются сигналы светофора:

красный – желтый – зеленый – желтый – красный – желтый – зеленый - …

Когда в очередной раз загорелся зеленый свет, Вася решил-таки перейти дорогу. К этому моменту зеленый свет зажегся в i-ый раз. Напишите программу, которая определит, сколько раз за это время загорался красный свет (считая и тот момент, когда Вася только подошел к перекрестку) и сколько раз — желтый.

Оргкомитет Московской олимпиады по информатике решил издать книгу с решениями олимпиадных задач сразу на двух языках – на Паскале и на Си. При этом тексты решений на Паскале решили напечатать с одной стороны книги, а на Си – с другой стороны. Таким образом книгу стало можно читать как с начала, так и с конца, предварительно ее перевернув.

Тексты решений на Паскале заняли N первых страниц, которые пронумеровали от 1 до N. А тексты на Си – M последних страниц, которые пронумеровали числами от 0 (последняя страница) до M–1.

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

Например, если N=5 и M=3 страницы книги идут в следующем порядке. Сначала страницы решений на Паскале: 1 2 3 4 5, затем – страницы решений на Си – 2 1 0. Здесь на первый лист попадают страницы номер 1 и 2 решений на Паскале, на второй – 3 и 4, на третий — страница 5 решений на Паскале и страница 2 решений на Си, и, наконец, на четвертый лист — страницы 1 и 0 решений на Си (ровно в таком порядке!).

Если же, например, N=2 и M=3, то на первом листе будут напечатаны страницы 1 и 2 решений на Паскале, на втором – пустая страница и страница 2 решений на Си, на третьем – страницы 1 и 0 решений на Си.

Напишите программу, которая по номеру листа определяет, решения на каком языке и какие номера страниц должны быть напечатаны на этом листе.

Заданы целые числа X, Y, P, Q (–10¹⁰⁰ <= X, Y, P, Q <= 10¹⁰⁰). Требуется проверить равенство X^Y = P^Q. Напомним, что a^b определяется следующим образом:

• при b > 0, a^b = a*a*...*a (b сомножителей)
• при b = 0, a <> 0 a^b = 1
• при b < 0, a <> 0 a^b = 1/a^-b
• для остальных комбинаций a и b значение a^b не определено.