Дерево — связный граф без циклов. Можно показать, что любое дерево из $$$n$$$ вершин имеет ровно $$$n - 1$$$ ребро.

Лист — вершина в дереве, из которой выходит ровно одно ребро.

Расстояние между двумя вершинами $$$u$$$ и $$$v$$$ в дереве — минимальное количество рёбер, которое нужно пройти, чтобы из вершины $$$u$$$ прийти в вершину $$$v$$$.

У Лёши скоро день рождения, и Тимофею хотелось бы подарить ему дерево из $$$n$$$ вершин. Однако Лёша очень капризный мальчик. Каждый день на протяжении $$$q$$$ дней он будет выбирать целое число, обозначим выбранное в $$$i$$$-й день число $$$d_i$$$. Если в $$$i$$$-й день в дереве не будет двух листов на расстоянии ровно $$$d_i$$$, то Лёша будет разочарован.

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

• Выбрать вершины $$$u$$$, $$$v_1$$$ и $$$v_2$$$, такие, что между $$$u$$$ и $$$v_1$$$ есть ребро, а между $$$u$$$ и $$$v_2$$$ нет ребра. После этого удалить ребро между $$$u$$$ и $$$v_1$$$ и добавить ребро между $$$u$$$ и $$$v_2$$$. Эту операцию нельзя выполнить, если после неё граф перестанет быть деревом.

Чудесным образом Тимофею удалось узнать все $$$d_i$$$. После этого его посетила ещё одна гениальная мысль — на всякий случай сделать инструкцию к набору, при этом такую, чтобы Лёша не был разочарован.

Тимофей не такой ленивый, как Лёша, но когда он увидел число $$$n$$$, у него резко пропало желание разрабатывать инструкцию и придумывать изначальное дерево, поэтому он поручил эту задачу вам. Можно показать, что дерево и последовательность операций, удовлетворяющие описанным условиям, всегда существуют.

Вот пример операции, где были выбраны вершины: $$$u$$$ — $$$6$$$, $$$v_1$$$ — $$$1$$$, $$$v_2$$$ — $$$4$$$.