Задача Q. Код Хаффмана ≡

Автор:	stdalg		Ограничение времени:	1 сек
Входной файл:	input.txt		Ограничение памяти:	64 Мб
Выходной файл:	output.txt

Условие

Построить код Хаффмана для алфавита из N символов и соответствующих им частот встречаемости.

Формат входного файла

Во входном файле содержится число N, за которым следуют N чисел f_i — частота встречаемости i − го символа.

Формат выходного файла

Выходной файл должен содержать N строк вида h_i — коды Хаффмана для символов в порядке, соответствующем входному файлу. Каждый код должен представлять собой строку из цифр 0 и 1. Если существует несколько решений, вывести любое из них.

Ограничения

2 ≤ N ≤ 100, 0 ≤ f_i ≤ 100000.

Примеры тестов

№	Входной файл (input.txt)	Выходной файл (output.txt)
1	6 45 13 12 16 9 5	0 101 100 111 1101 1100

---