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

Суть игры заключается в том, что группа людей по сигналу одновременно показывает рукой один из трёх символов: камень, ножницы или бумагу. Известно, что камень бьёт ножницы, ножницы бьют бумагу, а бумага бьёт камень. Если по сигналу среди знаков, показанных участниками, обнаружились все три, то такая ситуация называется «каша», объявляется ничья и игра продолжается тем же составом. То же самое происходит, если все участники показали один и тот же знак. Если же имеются только два из трёх знаков, то участники, показавшие проигравший знак, считаются кандидатами на вылет и игра продолжается уже среди них. Так до тех пор, пока проигравший не останется один. Он-то и едет на маршрут.

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

И вот однажды из гаража пропала тара с особо важной жидкостью. Точнее, тара-то как раз осталась, а вот жидкость бесследно исчезла. Водители, естественно, подозревают последнего из тех, кто выезжал на маршрут, но не помнят точно, кто это был. Дело в том, что они по очереди вели лог игры, но из лени записывали туда только знаки, которые были показаны, не разделяя их на раунды и не выписывая проигравших. Ваша задача — помочь водителям по логу игры определить победителя.

Лог представляет собой обычную строку, каждый символ которой обозначает знак, показанный очередным водителем: «R» обозначает камень, «S» — ножницы, а «P» — бумагу. Никаких пометок о том, когда закончился раунд, или определился очередной проигравший, не имеется. Ваша задача — определить номер игрока-победителя, если нумеровать их в том порядке, в котором они записывались в лог.

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

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

Теперь инспектор Баблалюбов хочет понять, насколько велика вероятность аварий, если он задаст те или иные настройки светофора. Для простоты он рассматривает конкретный промежуток времени с восьми до девяти часов утра, причём ровно в восемь на светофоре загорается зелёный свет. Зелёный свет горит $$$g$$$ секунд, и потом переключается на красный, который горит $$$r$$$ секунд и снова сменяется зелёным. Известно, что за этот час каждая маршрутка наверняка появится ровно один раз, причём она может сделать это равновероятно в любой момент. Ваша задача — помочь инспектору Баблалюбову найти вероятность начала сумасшедшей гонки на маршрутках, прибывших на перекрёсток в этот час.

Инспектор ГАИ Баблалюбов стал замечать, что водители маршрутных такси подозрительно часто стали нарушать правила дорожного движения. Это навело его на мысль, что ни один из зарегистрированных $$$n$$$ водителей вообще не знает правил, а права они все достали какими-то тёмными малолегальными способами.

Чтобы проверить свои догадки, он решил устроить всем водителям маршрутных такси экзамен по вождению. Более того, чтобы усложнить им задачу, он решил так распределить транспортные средства, на которых они будут сдавать экзамен, чтобы никакие $$$k$$$ из них не сдавали на своих собственных автомобилях марки «Газель», а попали на автомобиль другого водителя. Иными словами, когда все водители уже будут распределены по автомобилям, на которых они будут сдавать экзамен, то из любых произвольным образом выбранных $$$k$$$ водителей хотя бы один должен сдавать экзамен на чужом автомобиле. Теперь он крепко задумался, сколькими способами он может так распределить сдающих водителей по автомобилям марки «Газель».

Главный начальник всех водителей маршрутных такси Ровшан Мухамедович Шумахер уже редко водит свой автомобиль марки «Газель». Всё чаще он сидит дома за бутылочкой кофе и размышляет о том, как бы повысить прибыль с маршрутных такси. Не так давно он придумал систему тарификации, при которой проезд будет дорожать в зависимости от числа остановок, которое хочет проехать пассажир. Теперь он задумался, как бы лучше установить зависимость оплаты за проезд от числа остановок.

Сначала он хотел просто добавлять какую-нибудь фиксированную сумму в один условный рубль к проезду за каждую остановку, но ему показалось это не очень выгодно, да и к тому же слишком банально. Ровшан Шумахер любил быструю езду, русский шансон и деньги, но не любил ничего банального. Тогда, вспомнив школьный курс арифметики, он решил сделать проезд дорожающим, как квадраты натуральных чисел. Получилось неплохо, да и гораздо прибыльнее, чем раньше. В конце концов, он задумался, как разделять тарификацию на разные маршруты, ведь он хотел часть маршрутов сделать в принципе дороже, чем часть других. Умножать на какой-нибудь коэффициент показалось ему слишком банально.

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

Идея Ровшану очень понравилась. Он сразу распределил маршруты по ценности. Маршрут имеет ценность $$$k$$$, если плата за проезд по нему возрастает как $$$k$$$-угольник числа остановок, которые хочет проехать пассажир.

Поскольку водители не смогут быстро посчитать, сколько брать за проезд, зная только эту идею, нужно было быстро составить список тарифов на каждый маршрут. Ваша задача — написать для этого программу, которая будет интегрироваться в бортовой компьютер каждого автомобиля марки «Газель».

В государстве R есть только две действительно серьёзных проблемы: люди не самого высокого интеллектуального уровня и труднопроходимые проезжие части. У водителей маршрутных такси марки «Газель» в городе S обе эти проблемы слились в одну — инспекторов ГАИ. Так, водителей такси часто штрафует инспектор Баблалюбов за всевозможные мелочи вроде нерабочей фары, отсутствия аптечки или огнетушителя, а то и просто за превышение скорости. Хорошая сторона дела состоит в том, что водителям всегда удаётся договориться и отдавать штраф инспектору Баблалюбову прямо на месте. Причём суммы штрафа в результате продолжительных торгов могут быть самые разные.

Ещё одна проблема заключается в том, что алчный инспектор Баблалюбов не привык давать сдачу с этих штрафов, так что нужно стараться выплатить штраф без сдачи, иначе сдача останется инспектору на чай. Иными словами, задача водителя — набрать имеющимися купюрами минимальную сумму, не меньшую суммы штрафа. Теперь это ещё и ваша задача, потому что бортовой компьютер автомобилей марки «Газель» должен быть снабжён компьютерной программой, автоматизирующей процесс выдачи штрафов.

В ту пору, когда на улицах города S уже продавали новогодние ели, по радио звучали поздравления с наступающим Новым годом, а в воздухе чувствовалось приближение большого застолья, неожиданно выпал снег. Если бы это произошло не так внезапно и не так быстро, в городе обошлось бы без сугробов на дорогах и без километровых пробок. Однако снег никого не предупреждал, в том числе и водителей маршрутных такси, которые теперь по его вине вынуждены тратить часы, чтобы вытащить свое маршрутное такси марки «Газель» из встреченного по дороге сугроба.

Вечером, расходясь по домам, водители пересчитываются, чтобы проверить, все ли благополучно вернулись из рейса, и не остался ли кто-нибудь из них в сугробе на одной из улиц города. Если же выясняется, что кого-то не хватает, водители обращаются к тетрадке, которая лежит на выходе из гаража. В ней каждый из них пишет свою фамилию, каждый раз отправляясь в рейс и каждый раз, возвращаясь из рейса. Изрядно поспорив и порывшись в записях, водители понимают, кто же именно еще не вернулся из рейса. Нужно отметить, что в тетрадь водители пишут только свои фамилии без каких-либо пометок о том, отправляются они в рейс или возвращаются из него. Однажды вечером водители поняли, что кто-то одного среди них не хватает. Но вот кого? Это и предстоит выяснить Вам.

Однажды главному начальнику всех маршрутных такси города S Ровшану Мухамедовичу Шумахеру внезапно по мобильному телефону пришёл очень важный заказ на доставку не менее важной жидкости на секретный загородный объект, где праздновал свой День рождения один важный человек из городской администрации. Дело пахло большими деньгами, которые Ровшан Мухамедович очень любил, а провал дела пах совсем плохо, вплоть до отмены некоторых маршрутов такси. Поскольку все водители давно были на маршрутах, да и знать о сумме вознаграждения им было совсем не к чему, он решил тряхнуть стариной и отправиться в путь самостоятельно, благо требуемая жидкость в требуемых количествах (даже больших) всегда была у Ровшана Мухамедовича в наличии.

Дом Ровшана стоит на окраине города, и расстояние по прямой линии от него до секретного загородного объекта составляет $$$s$$$ метров. Добраться до этого объекта по прямой, в принципе, можно, но такой дороги нет, и придётся пробираться по пересечённой местности. По такому бездорожью автомобиль марки «Газель» может ехать с предельной скоростью $$$u$$$ метров в секунду (именно с такой скоростью Ровшан Мухамедович и ездит по ней). Однако есть дорога, которая ведёт из города, и дом Ровшана Мухамедовича стоит именно на ней. По дороге автомобиль марки «Газель» может ехать с предельной скоростью $$$v$$$ метров в секунду. Надо ли говорить, что Ровшан Мухамедович ездит по дороге только с такой скоростью?

Ровшан Мухамедович был далеко не глупым человеком. Он догадывался, что быстрее всего добраться до объекта, проехав некоторое расстояние по дороге, а потом свернуть и поехать напрямик к объекту. С помощью Google Maps Ровшан уже выяснил, что загородный объект находится на расстоянии $$$h$$$ метров от дороги. Во время своей поездки Ровшан будет видеть на приборной панели своего автомобиля марки «Газель» расстояние от своего дома, которое он уже проехал. Теперь он задумался, через сколько метров от своего дома ему стоит свернуть и поехать напрямик к целевому объекту, чтобы затратить на весь переезд минимальное время. Это и будет вашей задачей.

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

Во время таких простоев водители очень много нервничают и думают. Ну а чем, собственно, им ещё заниматься? В процессе размышлений они решают всевозможные мировые проблемы: о смысле жизни, о бренности всего сущего, о том, почему российская сборная по футболу не может выиграть кубок мира и так далее. Среди водителей маршрутных такси волей судьбы есть и доктора технических наук, мысли которых, в основном, связаны с математикой. В очередной пробке они на салфетках решают сильную и слабую проблемы Гольдбаха, доказывают гипотезы Римана и Лежандра, пытаются построить слегка избыточное число и треугольник с целочисленными сторонами, медианами и площадью.

Вот и начальник всех маршрутных такси города S Ровшан Мухамедович Шумахер сам некогда учился в одном из технических вузов города с аэрокосмическим уклоном. Недавно он поделился со своим другом-водителем по отчеству <censored> (бывшим профессором кафедры в этом вузе) задачей, которая пришла ему в голову как-то ночью. Пусть есть два простых числа $$$p$$$ и $$$q$$$. Задача заключается в том, чтобы определить, является ли число $$$(p+1)^q$$$ точным квадратом какого-нибудь натурального числа. Теперь <censored> призадумался, как это сделать. Вас, вероятно, эта задача тоже уже заинтересовала.