Задача H. Hidden tree ≡

Условие

Данная задача является интерактивной. Ваша программа будет взаимодействовать с программой жюри путем отправки и приема сообщений определенного вида.

У мальчика Пети есть N вершин. Он хочет соединить их ребрами, чтобы получилось дерево. Напомним, что дерево — это связный граф из N вершин и N − 1 ребра.

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

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

Формат входных данных

В первой строке входных данных записано целое число N — количество вершин в дереве.

Протокол взаимодействия

Чтобы добавить ребро, ваша программа должна вывести "+ Ai Bi", где A_i, B_i — целые числа, номера вершин, которые нужно соединить ребром.

На это программа жюри ответит вашей программе строчкой "ok". Если после этого еще можно добавлять ребра, то программа жюри также выведет "+ Ai Bi", где A_i, B_i — целые числа, номера вершин, которые соединяются ребром. Гарантируется, что программа жюри добавляет ребра согласно всем описанным правилам. После этого ход вновь переходит вашей программе.

Когда в дереве будет ровно N − 1 ребро, ваша программа должна завершиться.

Если ваша программа добавит лишнее ребро, то она получит вердикт "Wrong answer".

Если ваша программа сделает недопустимый запрос, то она получит вердикт "Presentation error".

Если ваша программа получила от программы жюри строку "error" вместо "ok", то она должна немедленно завершиться. Такое возможно, если ваша программа нарушила протокол взаимодействия. Если ваша программа не завершится, то вердикт может отличаться от описанных выше (например, может быть вердикт "Runtime error").

Каждый запрос должен быть одиночной строкой заканчивающейся одиночным переводом строки (\n). Буфер вывода необходимо сбрасывать после каждой строки:

Ограничения

3 ≤ N ≤ 1000

1 ≤ A_i, B_i ≤ N

Примеры тестов

6

ok
+ 5 6

ok
+ 1 6

ok

+ 1 2


+ 1 3


+ 2 4

3

ok
+ 2 3

+ 1 2