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

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

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

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

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

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