Программист Вася заказывает пиццу. В меню есть N топпингов, пронумерованных от 1 до N. Вася хочет попробовать ВСЕ возможные комбинации топпингов (включая пиццу без топпингов).
Помогите Васе составить список всех возможных пицц. Каждая пицца описывается набором номеров топпингов на ней.
ВАЖНО: Пиццы в списке должны быть отсортированы в лексикографическом порядке. Топпинги внутри каждой пиццы должны быть в порядке возрастания номеров.
ВХОДНЫЕ ДАННЫЕ:
Одно число N (1 ≤ N ≤ 10) - количество топпингов в меню.
ВЫХОДНЫЕ ДАННЫЕ:
Выведите 2^N строк - все возможные пиццы.
Пустая пицца (без топпингов) обозначается как "-".
Для непустых пицц выведите номера топпингов через пробел.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
|
-
1
|
|
2
|
3
|
-
1
1 2
1 2 3
1 3
2
2 3
3
|