Задача G. Gablerd Lettres

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

Условие

По рзелульаттам илссеовадний одонго анлигйсокго унвиертисета, не иеемт занчнеия, в кокам пряокде рсапожолены бкувы в солве. Галвоне, чотбы преавя и пслоендяя бквуы блыи на мсете. Осатьлыне бкувы мгоут селдовтаь в плоонм бсепордяке, все-рвано ткест чтаитсея без побрелм. Пичрионй эгото ялвятеся то, что мы чиатем не кдаужю бкуву по отдльенотси, а все солво цликеом.

Алексей решил проверить, будет ли выполняться это свойство для целых чисел. Он придумал число N и хочет переставить в нём цифры так, чтобы:

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

Напишите программу которая переставляет цифры данного числа в соответствии с требованиями Алексея.

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

Входной файл содержит единственное целое число N.

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

Выходной файл должен содержать единственное целое число — ответ на задачу. Если ответов несколько, выведите любой из них.

Если ответа не существует, выведите  − 1.

Ограничения

1 ≤ N ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
238965
269385
2
123
-1

0.100s 0.031s 15