Таємне повідомлення

Limits: 4 sec., 1024 MiB

Зеник та Марічка виконують таємне, але дуже важливе завдання. На жаль, розповісти більше вони не можуть. Зараз наші герої готують для Малюка таємне повідомлення, котре потрібно закодувати у двійковому форматі та надіслати через мережу.

Весь текст містить \(n\) різних слів. Для зручності Зеник пронумерував їх від 1 до \(n\). Слова зустрічаються у тексті \(c_1, c_2, \ldots, c_n\) разів відповідно. Для кожного слова Марічка хоче визначити код, що складається з нулів та одиниць. Вона вважає кодування прийнятним за таких умов:

• довжина коду для кожного слова є не меншою ніж \(a\) та не більшою ніж \(b\);

• усі коди слів є різними;

• жоден код не є префіксом іншого коду.

Щоб згенерувати закодоване повідомлення, Зеник по черзі записує коди слів що зустрічаються у тексті без жодних розділювачів між ними. Оскільки ми хочемо мінімізувати час надсилання через мережу, довжина закодованого повідомлення має бути якнайменшою. Допоможіть Зеникові та Марічці обрати серед усіх прийнятних кодувань таке, що дозволить згенерувати найкоротший можливий закодований текст.

Input

Перший рядок містить три цілих числа через пробіл \(n\), \(a\) та \(b\). Наступний рядок містить \(n\) цілих чисел через пробіл \(c_i\).

Output

Виведіть \(n\) рядків з кодуваннями слів. Рядок \(i\) має містити кодування для \(i\)-го слова. Кодування має бути прийнятним, а відповідний закодований текст має бути одним з найкоротших. Якщо існує декілька оптимальних кодувань, виведіть будь-яке з них. Якщо ж не існує жодного прийнятного кодування, виведіть -1 натомість.

Constraints

\(1 \le n \le 10^5\),

\(1 \le a \le b \le 100\),

\(1 \le c_i \le 10^{18}\).

Samples