Каждый день на линию одного из автобусных маршрутов выходит K (1 ≤ K ≤ 50) машин, на каждой из которых работает кондуктор. Перед началом работы кондукторы получают по рулону автобусных билетов. Все билеты пронумерованы шестизначными числами. Каждый рулон состоит из 1000 билетов с номерами от ###000 до ###999, то есть три первых цифры номера билетов из одного рулона совпадают. Кондукторы получают рулоны с последовательными номерами билетов. Например, если первый кондуктор получает рулон с билетами 000000–000999, то второй получит рулон с билетами 001000–001999, третий 002000–002999 и так далее...

Получив рулон билетов, каждый кондуктор пересчитывает, сколько из них «счастливые». «Счастливым» считается билет, у которого сумма цифр, стоящих на чётных местах, совпадает с суммой цифр, стоящих на нечётных местах. Например, билет с номером  112233 является «счастливым» (1 + 2 + 3 = 1 + 2 + 3), а билет с номером 321213 — нет (3 + 1 + 1  ≠ 2 + 2 + 3).

Для каждого из K кондукторов известно, сколько счастливых билетов он насчитал в своём рулоне. Требуется определить, какие номера билетов в рулоне у первого кондуктора.

Формат входных и выходных данных

Первая строка входных данных содержит целое число K — число автобусов, вышедших на маршрут. Вторая строка содержит K целых чисел из диапазона [0; 1000], разделённых пробелами — количество «счастливых» билетов у кондукторов: первого, второго, ..., K-го.

Выведите одно целое число — номер рулона первого кондуктора. Номером рулона будем считать первые 3 цифры номеров билетов рулона без ведущих нулей. Если решений несколько, требуется вывести минимальное из них. Если решений нет, требуется вывести число -1.

Примеры

Входные данные	Выходные данные
3 75 75 73	4
4 28 36 45 55	30
1 0	-1