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

Вам дано дерево с N вершинами порядка K , то есть каждая вершина дерева может иметь не более K потомков. Дерево создано по принципу "минимальной энергии": вершины в нем располагается на новом уровне только тогда, когда все места на предыдущем уровне (слева направо) заняты. В таком же порядке вершины дерева пронумерованы, начиная с 1.

Вам необходимо ответить на Q запросов вида " x y ", где ответом является расстояние (количество ребер в минимальном пути) в данном дереве между вершинами с номерами x и y .

Давным-давно в одной далекой-далекой галактике, было N планет. Также было N - 1 межпланетных магистралей, соединявших между собой все планеты (не обязательно напрямую). Иными словами, сеть планет и магистралей образовывала дерево. Кроме того, каждая магистраль имеет свой показатель интересности, заданный неотрицательным целым числом. Пара планет ( A , B ) называется скучной, если выполняются следующие условия:

1. A и B - различные планеты.

2. В действующей сети межпланетных магистралей существует путь между A и B .

3. Побитовый XOR показателей интересности всех магистралей в этом пути равен 0.

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

На лесистой луне Эндора находится, если верить Имперской Книге Рекордов, самая длинная ветка в галактике. На этой ветке длиной L метров сидит N дружелюбных хамелеонов. Каждый хамелеон ходит вдоль ветки со скоростью 1 м/с в одном из двух возможных направлений (налево или направо), а также имеет собственный цвет среди одного из K возможных.

Известно, что хамелеоны на Эндоры следуют древним законам, в соответствии с которыми любая прогулка вдоль ветки должна продолжаться до ее конца (после чего хамелеон спрыгивает с ветки), а в случае столкновения двух хамелеонов, они должны развернуться на 180 градусов и продолжить движение в противоположном направлении. Кроме того, при таком столкновении, если хамелеон, двигавшийся налево, имел цвет a , а хамелеон, двигавшийся направо - цвет b , то после разворота первый хамелеон изменит свой цвет на b , а второй хамелеон - на ( a + b ) modK .

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

Случилось ужасное! Отважный хорватский охотник попал в его собственную ловушку. В погоне за ценной добычей он помчался вперед и оказался пойман. Чтобы выбраться наружу, он должен решить следующую задачу (а так как умом он не блещет, вам придется ему помочь):

Вам даны 3 целых числа L, D и X. Определите минимальное такое число N , для которого L ≤ N ≤ D и сумма цифр которого равна X . Также определите максимальное M для которого L ≤ M ≤ D и сумма цифр которого равна X . Гарантируется, что такие числа всегда существуют.

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

Мультиграмма – это слово, которое состоит из конкатенации двух и более анаграмм. Первая из этих анаграмм называется корнем мультиграммы. Например, слово bbabab – мультиграмма с корнем bba, потому что она состоит из анаграмм bba и bab.

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