Эта задача является интерактивной.

Жюри загадало полное корневое бинарное дерево с n листьями. Полное бинарное дерево — такое дерево, каждая вершина которого имеет либо 0, либо 2 ребенка. Вершины с 0 детьми называются листьями. Так как дерево полное бинарное, то всего в нем 2n - 1 вершина. Листья загаданного дерева имеют индексы от 1 до n. Вы хотите построить дерево, изоморфное дереву жюри. Чтобы это сделать, вы можете спрашивать некоторые вопросы.

Вопрос состоит из трех различных листьев a₁, a₂, a₃. Пусть глубина вершины равна кратчайшему расстоянию от вершины до корня дерева. Пусть LCA(a, b) означает вершину с максимальной глубиной такую, что эта вершина является общим предком вершин a и b.

Пусть X = LCA(a₁, a₂), Y = LCA(a₂, a₃), Z = LCA(a₃, a₁). Жюри ответит вам, какая из вершин X, Y, Z имеет наибольшую глубину. Заметьте, что ответ определен однозначно, так как дерево бинарное.

Формально, если наибольшую глубину имеет X (или Y, Z соответственно), жюри ответит строкой «X» (или «Y», «Z» соответственно).

Вы можете задать не более 10·n вопросов.

Чтобы задать вопросы, выведите три различных целых числа a₁, a₂, a₃. Эти числа должны быть от 1 до n включительно.

Программа жюри ответит единственным символом: «X», «Y» или «Z».

Если ответ равен «X» (или «Y», «Z», соответственно), то пара (a₁, a₂) (или (a₂, a₃), (a₃, a₁), соответственно) имеет наиболее глубокий LCA среди всех трех пар.

Вы можете задать не более 10·n вопросов, иначе вы получите вердикт Неправильный ответ.

Когда вы будете готовы вывести ответ, выведите число «-1» на отдельной строке. Следующая строка должна содержать 2n - 1 целых чисел. i-е из этих чисел должно равняться индексу родителя i-й вершины, или -1, если это корень. Не забудьте сделать операцию flush после вывода ответа тоже. Вывод ответа не учитывается при подсчете количества вопросов.

Вы получите вердикт Неправильный ответ, если

• Ваш вопрос или ответ не соответствует формату, описанному в условии.
• Вы спросили строго больше 10·n вопросов.
• Ваш вопрос содержит повторяющиеся индексы.
• Ваше дерево не изоморфно дереву жюри.

Вы получите вердикт Решение «зависло», если не будете ничего выводить, или забудете сделать операцию flush после вывода вопроса или ответа (смотрите ниже информацию, как сделать flush).

Чтобы выполнить операцию flush, можете использовать (сразу после вывода чисел и перевода строки):

• fflush(stdout) в C++;
• System.out.flush() в Java;
• stdout.flush() в Python;
• flush(output) в Pascal;
• Смотрите документацию для других языков.

Если в любой момент ваша программа считывает -1 как ответ, она должна немедленно нормально завершиться (например, вызовом exit(0)). Вы получите вердикт Неправильный ответ, и это будет означать, что вы задали больше вопросов, чем разрешено, или сделали некорректный вопрос. Если вы проигнорируете это, то можете получить любой вердикт, так как ваша программа продолжит читать из закрытого потока ввода.

Взломы Чтобы взломать кого-нибудь, используйте следующий формат.

n
p_1 p_2 ... p_{2n-1}

Это описывает дерево, где родителем вершины i является вершина p_i (p_i =  - 1 or n < p_i ≤ 2n - 1). Значение p_i, равное -1 означает, что вершина i является корнем. Эти данные должны описывать корректное полное бинарное дерево.

Конечно, взламываемая программа не будет иметь доступ к этим данным.