Копирование больших шестнадцатеричных строк (то есть чисел в системе счисления по основанию 16) вручную может вызывать много ошибок, но это не останавливает людей. Вы обнаружили ошибку в программе, которая, скорее всего, была вызвана ошибкой при копировании такой строки. Вы думаете, что тот, кто копировал строку, не изменил ни одной цифры, и не изменил длину, но, возможно, перепутал порядок цифр. Например, если исходная строка была 0abc, то, возможно, она была изменена в a0cb или 0bca, но не в abc или 0abb.
К сожалению, у вас нет доступа ни к изначальной строке, ни к скопированной, но вы знаете длину этих строк и модуль их разницы (как чисел). Вам будет дана эта разница как шестнадцатеричная строка S, которая дополнена ведущими нулями до длины изначальной (и скопированной) строки. Определите наименьшее возможное численное значение исходной строки.
Выходные данные
Если описанное невозможно, выведите «NO» (без кавычек).
Иначе выведите минимальную шестнадцатеричную строку, соответствующую минимально возможному исходному числу, включая все ведущие нули, дополняющие его до нужной длины. Выводите число в том же формате, что и во входных данных.
Примечание
Численное значение шестнадцатеричной строки вычисляется как сумма произведений каждой из цифр на последовательные степени числа 16, начиная с самой правой цифры, которая умножается на 160. Шестнадцатеричные цифры, большие 9, обозначаются строчными буквами: a = 10, b = 11, c = 12, d = 13, e = 14, f = 15.
Например, численное значение 0f1e равно 0·163 + 15·162 + 1·161 + 14·160 = 3870, численное значение 00f1 равно 0·163 + 0·162 + 15·161 + 1·160 = 241, численное значение 100f равно 1·163 + 0·162 + 0·161 + 15·160 = 4111. Так как 3870 + 241 = 4111 и 00f1 — перестановка 100f, то 00f1 — корректный ответ на второй пример.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
f1e
|
NO
|
|
2
|
0f1e
|
00f1
|
|
3
|
12d2c
|
00314
|