Как вы знаете, Васин брат живет во Флатландии. Во Флатландии n городов, соединенных n - 1 двухсторонней дорогой. Города пронумерованы от 1 до n . Из любого города можно добраться до любого другого.

Компания «Два пути», в которой работает Васин брат, выиграла тендер на ремонт двух путей во Флатландии. Путем называется последовательность различных городов, последовательно соединенных дорогами. Пути, которые надо отремонтировать, компания может выбрать самостоятельно. Единственное условие, накладываемое тендером, они не должны пересекаться (то есть иметь общих городов).

Известно, что прибыль, которую получит компания «Два пути», равна произведению длин выбранных двух путей. Считая длину каждой дороги один, а длину пути равной количеству дорог в ней, найдите максимальную возможную прибыль.

Много в мире разных часовых поясов! Именно поэтому соревнования по программированию часто бывают в неудобное для некоторых людей время. Как-то раз Гриша и Егор решили поучавствовать в соревновании, которое заканчивалось очень поздно. Именно поэтому ребята решили переночевать в гостинице, чтобы не возвращаться домой поздно. Однако все не так просто. Родители Егора и Гриши очень волнуются за своих детей, поэтому они решили установить по всему городу камеры, чтобы видеть, где находятся ребята.

В городе, где живут программисты 1 ≤ n ≤ 500 000 перекрестков, соединенных n - 1 дорогой так, что между любыми двумя перекрестками существует путь по дорогам.

Родители собираются установить на перекрестках города камеры, радиус действия которых равен длине дороги. Родители будут спокойны, если смогут видеть ребят на любой дороге и на любом про перекрестке. Иными словами, для каждого перекрестка должен существовать перекресток, находящийся на расстоянии не более одной дороги, такой что на нем установлена камера и для любой дороги должна быть установлена камера хотя бы на одном конце этой дороги. Установка камер  — затратное дело, поэтому для каждого перекрестка с номером i известна стоимость 1 ≤ cost _i ≤ 10 ⁹ установки камеры на нем.

Помогите родителям установить камеры надлежащим образом за минимальную стоимость.

Мирко стал генеральным директором крупной корпорации. В компании работает N человек, пронумерованных от 1 до N , Мирко имеет номер 1 . У всех кроме Мирко есть начальник. Начальник может иметь несколько подчинённых, но не более одного своего начальника.

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

Этот работник получает 1 монету, его начальник получает 2 монеты, начальник этого начальника получает 3 и так далее. Потом тот, кто на самом деле сделал работу, осознаёт, насколько эта капиталистическая система несправедлива и увольняется с работы.

Мирко получает задания до тех пор, пока в корпорации не останется всего один сотрудник — сам Мирко. Тогда он выполняет это задание, получает 1 монету и уходит из корпорации. Ему стало интересно, сколько всего монет получил каждый бывший сотрудник. Помогите ему с этим.

Фермер Джон спрятал ключи от трактора в сейфе. Коровы пытаются взломать этот сейф. Сейф защищён сложной парольной системой.

Она организована как подвешенное за вершину 0 дерево из \(n\) (\(1 \le n \le 20000\)) вершин, каждая из которых требует цифру от \(0\) до \(9\). Вершины пронумерованы от \(0\) до \(n - 1\).

Единственная информация, которой владеют коровы – что определённые последовательности длины \(5\) не появляютя на путях в этом дереве начиная с каких-то стартовых позиций при движении вверх по дереву.

По заданным \(m\) (\(0 \le m \le 50000\)) последовательностям длины \(5\), вместе с их стартовой позицией в дереве помогите коровам вычислить сколько паролей будет не подходить.

Вы должны выводить свой ответ по модулю \(1234567\).

Мислав и Мирко разработали новую игру под названием повороты.

Сначала Мирко выбирает последовательность чисел длины \(n\) и число \(k\) и разбивает последовательность на секции, каждая из которых содержит \(k\) чисел (\(n\) делится на \(k\)). Первая секция содержит первые \(k\) позиций в последовательности, вторая секция содержит последующие \(k\) позиций в последовательности и так далее.

После этого Мирко начинает применять различные операции на данной последовательности. Есть два типа операций:

1. Совершить циклический сдвиг элементов последовательности чисел в каждой секции на \(x\) влево или вправо.

2. Совершить циклический сдвиг элементов последовательности чисел целиком на \(x\) влево или вправо.

Заметим, что операция типа 2 может изменить то, к какой секции принадлежит какое число.

После применения всех операций, Мирко сообщает Миславу получившуюся последовательность и применённые операции. Задача Мислава заключается в том, чтобы восстановить исходную последовательность. Он попросил вас о помощи.