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

Цель игры — убрать карты в таком порядке, чтобы минимизировать общее количество набранных очков.

Например, если карты содержат числа 10, 1, 50, 20 и 5, игрок может взять карту с числом 1, затем 20 и 50, получая очки 10·1·50 + 50·20·5 + 10·50·5 = 500 + 5000 + 2500 = 8000. Если бы он взял карты в обратном порядке, то есть 50, затем 20, затем 1, количество очков было бы таким: 1·50·20 + 1·20·5 + 10·1·5 = 1000 + 100 + 50 = 1150.

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

Он сказал, что у него есть первая четверть плоскости, он умеет добавлять на нее прямоугольник с нижней левой точкой (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).

«И молвил тогда Король: Ты храбро сражался, Рыцарь, и твой подвиг не будет забыт в веках. За доблесть твою я дарую тебе сей замок и земли вокруг него. Однако нарушен был тобой строжайший из запретов все войны видели, как ты сражался без Шляпы на голове подобно дикарям, и их злые духи могли вселиться в тебя. Ты знаешь, что закон предков велит отправлять на небеса души подобных тебе, пока зло, которое могло укорениться в них, не вырвалось наружу. Но в моей воле пощадить тебя, ибо я вижу, что ты достаточно силен чтобы не позволить этому злу проникнуть в мысли и душу твои. Ты должен дать обет три месяца и три дня не покидать своей земли и каждый день три часа после захода солнца молить добрых духов о защите. Дела торопят меня, и не могу я препроводить тебя до замка. Поэтому я дарую тебе и дорогу от этого места до замка. А сейчас иди, и возвращайся по истечении срока.»

— так записано в Зеленой Книге Лет.

Помимо этого из Зеленой Книги Лет известно, что земли, вместе с которыми был дарован замок, имели форму круга. Король был очень мудр и, во избежание лишних разбирательств относительно права на землю всегда даровал только области земли, на карте имеющие выпуклую форму. Недавно в распоряжении историков оказалась информация о том, где располагался замок и где происходил этот исторический разговор. Их интересует, участок земли какой площади получил Рыцарь в предположении, что дорога до замка была идеально прямой.