Многие пользователи мобильных телефонов при наборе sms-сообщений используют режим T9. При этом сообщения, например на английском языке, они набирают следующим образом. Для набора слова по буквам соответствующая букве кнопка нажимается один раз, вне зависимости от того, сколько букв соответствуют этой кнопке, и какой по счету идет нужная буква (см. картинку), а программа в телефоне подбирает из имеющегося словаря подходящее для данной комбинации кнопок слово. Если подходящих слов несколько, то в первую очередь предлагается наиболее часто встречающееся слово (изначально слова одинаковой встречаемости предлагаются по алфавиту). Если слово не подошло, то пользователь нажимает кнопку ‘*’ и программа предлагает второе по встречаемости слово, образуемое той же комбинацией кнопок (в первую очередь следующее слово с той же частотой встречаемости, если такое имеется). Если и оно не подошло, то кнопка ‘*’ нажимается еще раз и т.д. Для простоты будем считать, что современные модели телефонов содержат полный словарь используемых слов, и нужное слово обязательно найдется. Когда предлагаемое слово подошло, пользователь нажимает на кнопку “пробел”, нажимает на кнопку ‘1’ (последняя соответствует набору знака препинания), или заканчивает набирать сообщение. Когда знак препинания не подошёл, опять же нажимается кнопка ‘*’, до тех пор пока не появится требуемый знак. После набора пробела или знака препинания пользователь может ввести ещё один пробел или знак препинания, начать набирать следующее слово или закончить набирать сообщение. Будем считать, что пользователю достаточно трех знаков препинания, и они предлагаются в следующем порядке: точка (‘.’), запятая (‘,’), вопросительный знак (‘?’). После того как пользователь “утвердил” набранное слово (нажав на пробел или ‘1’), частота его встречаемости в словаре увеличивается на 1, и новое значение частоты учитывается, в том числе, и при наборе в режиме T9 остальных слов того же сообщения. При этом данное слово будет предлагаться первым среди слов с такой же частотой встречаемости, порядок предложения остальных слов остается неизменным. Когда появится еще одно слово с той же частотой, то уже оно будет предлагаться первым, не меняя порядка остальных, и т. д. Вам требуется написать программу, которая по имеющемуся словарю, содержащему первоначальные характеристики частоты встречаемости того или иного английского слова, и известной последовательности нажатий кнопок пользователем при наборе sms-сообщения в режиме T9 воспроизведет появившееся на экране сообщение.

Одна из новых возможностей текстового редактора «World XP» — это сортировка слов в предложении. Выход новой бета-версии редактора должен состоятся не позднее, чем через пять часов, а заявленная функция еще не реализована.

Требуется написать программу, осуществляющую сортировку слов в предложении. При этом все символы, отличные от букв, должны сохранится и не поменять своего положения относительно вхождений слов. Для упрощения при подаче входных данных на вход вашей программы все такие символы будут заменены на символ «.» (точка). Таким образом символ «.» имеет смысл разделителя между словами. Например, строка «..aba.a..ba» после сортировки пример вид «..a.aba..ba», а строка «c..bb.a» примет вид «a..bb.c». Слова следует сортировать лексикографически, как в словаре.

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

Конечно, скидываться придется всем поровну. То есть, если Коля позовет k своих друзей, то каждому придется заплатить S / (k + 1) рублей (да, сам Коля тоже должен внести свою долю). При этом S не обязательно должно делиться на k + 1: главное — купить билет, а между собой друзья уж как-нибудь договорятся.

Всего у Коли n друзей, при этом i-й из них готов пойти с Колей в парк, если доля, которую ему придется заплатить не больше b_i (больше денег у него просто с собой нет) и не меньше a_i (иначе он решит, что Колин день рождения — это скучно, и пойдет играть в волейбол с Сережей).

Так что может так получиться, что всех позвать не удастся. Ну и ладно. Для каждого своего друга Коля знает число f_i — количество веселья, который тот произведет, если его позвать.

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

Маленький мальчик Глеб еще толком не познал жизнь, но он уже ОЧЕНЬ любит КАРАТЬ, НЕ ПРОЩАТЬ! И вот в очередной раз он решил поиздеваться над бедным Лёшиком =(

Он сказал, что у него есть первая четверть плоскости, он умеет добавлять на нее прямоугольник с нижней левой точкой (0;0) и верхней правой (x;y), умеет считать площадь получившейся фигуры, умеет считать площадь объединения этой фигуры с прямоугольником на точках (x₁;y₁) и (x₂;y₂) и даже площадь пересечения.

Лёшик в печальке... =(

Спасите Лёшика, решите эту задачу. Но помните, Глеб настолько суров, что заставил решать поставленную задачу в он-лайне!!!

Задано подвешенное дерево, содержащее n (1 ≤ n ≤ 100000) вершин, пронумерованных от 0 до n - 1. Требуется ответить на m (1 ≤ m ≤ 100000) запросов о наименьшем общем предке для пары вершин.

Запросы генерируются следующим образом. Заданы числа a₁, a₂ и числа x, y и z. Числа a₃, ..., a_2m генерируются следующим образом: a_i = (x·a_i - 2 + y·a_i - 1 + z)mod: n. Первый запрос имеет вид (a₁, a₂). Если ответ на (i - 1)-й запрос равен v, то i-й запрос имеет вид ((a_2i - 1 + v)mod: n, a_2i).