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

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

Ваша задача — по данному набору артефактов вывести все различные коллекции, которые можно составить.

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

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

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

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

Выведите все различные коллекции артефактов.

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

Коллекции можно выводить в любом порядке.

Ограничения

• 1 <= n <= 10
• -100 <= ai <= 100

Пример 1

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

3
1 2 2

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

1
1 2
1 2 2
2
2 2

Примечание

Для набора 1 2 2 различными коллекциями будут:

• пустая коллекция
• 1
• 2
• 2 2
• 1 2
• 1 2 2

Обратите внимание: коллекция 2 должна быть выведена только один раз, даже если в исходном наборе есть два одинаковых артефакта этого типа.