В Академии магии хранится коллекция из n различных артефактов. Каждый артефакт имеет свой уникальный номер.

Для подготовки к выставке архивариус хочет составить список всех возможных наборов артефактов, которые можно выбрать из этой коллекции. В набор может входить любое количество артефактов: от нуля до всех сразу.

Помогите архивариусу вывести все такие наборы.

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

В первой строке дано целое число n — количество артефактов.

Во второй строке даны n различных целых чисел a1, a2, ..., an — номера артефактов.

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

Выведите все возможные подмножества данного множества артефактов.

Каждое подмножество выводите в отдельной строке.

Если подмножество пустое, выведите пустую строку.

Подмножества можно выводить в любом порядке. Элементы подмножества должны быть в неубывающем порядке.

Ограничения

• 1 <= n <= 15
• -10^9 <= ai <= 10^9
• Все ai различны.

Пример 1

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

3
1 2 3

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

1 2 3
1 2
1 3
1
2 3
2

3

Пример 2

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

2
10 20

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

10 20
10

20

Примечание

Подмножество — это набор элементов, выбранных из исходного множества. Для каждого артефакта есть два варианта: взять его в набор или не брать. Поэтому всего для n различных артефактов существует 2^n различных подмножеств.