Задано множество s мощности n, содержащее все элементы из интервала [1..n]. Необходимо сгенерировать все его подмножества.

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

Единственное число n (1 ≤ n ≤ 8).

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

В каждой строчке необходимо вывести одно из подмножеств исходного множества. Подмножество записывается перечислением своих элементов в порядке возрастания. Элементы подмножества должны быть записаны слитно, то есть без пробелов. Каждое подмножество должно встречаться не более одного раза. Подмножества также нужно перечислять в возрастающем порядке (см. пример). Пустое подмножество выводить не нужно.