Дана полоска из клеток, пронумерованных от 1 до N. На каждом ходе разрешено поставить фишку на клетку (если её там еще нет) или снять фишку с клетки (если она там есть). При этом, можно выбрать не любую клетку, а только клетку под номером 1 или клетку, следующую за самой первой фишкой.
Изначально полоска пуста. Требуется занять все клетки.

Входные данные

С клавиатуры вводится натуральное число N (1 ≤ N ≤ 10).

Выходные данные

Требуется вывести последовательность номеров клеток, с которыми совершается действие. Если фишка снимается, то номер клетки должен выводиться со знаком минус. Количество действий не должно превышать 104. Если существует несколько возможных решений задачи, то разрешается вывести любое.


Примеры

ВводВывод
3
1 2 -1 3 1

Примеры
Входные данные
3
Выходные данные
 
Сдать: для сдачи задач необходимо войти в систему