Задано подвешенное дерево, содержащее 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).

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

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

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

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

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

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

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

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

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

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