Задача A4. Breaking digits

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

Условие

Требуется написать программу, которая, получив целое число A в десятичной записи, разделит его цифры между двумя числами B и C таким образом, чтобы:

  1. Каждая цифра числа A встречалась ровно один раз либо в B, любо в C.
  2. Сумма B + C была максимально возможной.

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

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

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

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

Ограничения

10 ≤ A ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
11
1
1
2
439
94
3
3
1000
100
0

0.175s 0.023s 15