Охотник Боб часто гуляет со своей собакой Ральфом. Боб гуляет с постоянной скоростью и его путь – ломаная (возможно, самопересекающаяся), каждая вершина которой задается двумя целыми числами (X_i, Y_i) – декартовыми координатами.

Ральф бегает сам по себе, но обязательно должен встречаться с хозяином в указанных N точках. Собака начинает свой путь одновременно с хозяином в точке (X₁, Y₁) и завешает его вместе с хозяином в точке (X_N, Y_N).

Ральф может бегать с любой скоростью, не превышающей в два раза скорость Боба. Пока Боб идет по прямой из точки в точку, собака ищет деревья, кусты, холмики и прочие интересные места, которые заданы парами целых чисел (X^'_j, Y^'_j). Всего таких мест M. Тем не менее, покидая своего хозяина в точке (X_i, Y_i) (где 1 ≤ i ≤ N), Ральф посещает не более одного интересного места перед тем, как опять встретить хозяина в точке (X_i + 1, Y_i + 1).

Ваша задача – найти маршрут, удовлетворяющий указанным выше условиям, с максимальным количеством посещаемых интересных мест. Он представляется ломаной, по которой бегает Ральф. Ее вершинами должны быть все точки (X_i, Y_i) и посещенные интересные места (X^'_j, Y^'_j). Последние должны быть посещены (то есть встречаться в описании пути) не более одного раза.

Пример пути Боба (сплошная линия), набора интересных мест (точки) и одного из лучших путей Ральфа представлены на рисунке:

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

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

Предположим теперь, что житель страны хочет совершить путешествие из города A в город B. Новый указ королевы гласит, что при проезде по любой дороге страны во время этого путешествия, полицейские могут взять с этого жителя таможенную пошлину в пользу королевского двора (а могут и не взять). Если при этом у жителя недостаточно денег для уплаты пошлины, то он автоматически попадает в тюрьму. Указ также устанавливает величину пошлины для каждой дороги страны. Так как королева заботится о жителях своей страны, то она запретила полицейским брать с жителя пошлину более чем два раза во время одного путешествия.

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

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

В одной из звездных систем Галактической Республики произошло дерзкое ограбление банка "13-е Общество межгалактического кредита", из которого было похищено несколько миллиардов буказоидов. Оказалось, что Армия Республики в данном секторе имеет ограниченные силы и не в состоянии блокировать все возможные пути бегства грабителей, поэтому встала задача о минимизации числа кордонов.

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

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

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