Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Hex Dyslexia

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputCopying large hexadecimal (base 16) strings by hand can be error prone, but that doesn't stop people from doing it. You've discovered a bug in the code that was likely caused by someone making a mistake when copying such a string. You suspect that whoever copied the string did not change any of the digits in the string, nor the length of the string, but may have permuted the digits arbitrarily. For example, if the original string was 0*abc* they may have changed it to *a*0*cb* or 0*bca*, but not *abc* or 0*abb*.

Unfortunately you don't have access to the original string nor the copied string, but you do know the length of the strings and their numerical absolute difference. You will be given this difference as a hexadecimal string *S*, which has been zero-extended to be equal in length to the original and copied strings. Determine the smallest possible numerical value of the original string.

Input

Input will contain a hexadecimal string *S* consisting only of digits 0 to 9 and lowercase English letters from *a* to *f*, with length at most 14. At least one of the characters is non-zero.

Output

If it is not possible, print "NO" (without quotes).

Otherwise, print the lowercase hexadecimal string corresponding to the smallest possible numerical value, including any necessary leading zeros for the length to be correct.

Examples

Input

f1e

Output

NO

Input

0f1e

Output

00f1

Input

12d2c

Output

00314

Note

The numerical value of a hexadecimal string is computed by multiplying each digit by successive powers of 16, starting with the rightmost digit, which is multiplied by 16^{0}. Hexadecimal digits representing values greater than 9 are represented by letters: *a* = 10, *b* = 11, *c* = 12, *d* = 13, *e* = 14, *f* = 15.

For example, the numerical value of 0*f*1*e* is 0·16^{3} + 15·16^{2} + 1·16^{1} + 14·16^{0} = 3870, the numerical value of 00*f*1 is 0·16^{3} + 0·16^{2} + 15·16^{1} + 1·16^{0} = 241, and the numerical value of 100*f* is 1·16^{3} + 0·16^{2} + 0·16^{1} + 15·16^{0} = 4111. Since 3870 + 241 = 4111 and 00*f*1 is a permutation of 100*f*, 00*f*1 is a valid answer to the second test case.

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/18/2022 09:13:53 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|