Kaprekar Transformation

Time limit2sMemory limit1024 MB

Summary

Given x, the task is to rearrange its digits into the largest and smallest numbers and print their difference, padded to the digit count of x.

Level: Easy2 of 10
Topics: Sorting, Implementation
Solved: No attempts yet

Statement

Given an integer $x$ , consider the following operation. Let $M$ be the largest number that can be obtained by rearranging the digits of $x$ , and let $m$ be the smallest such number (this number may have leading zeros). Let $K(x)$ denote the difference $M-m$ , padded with leading zeros if needed so that it has the same number of digits as $x$ .

For example, $K(100) = 100 - 001 = 099$ and $K(2414) = 4421 - 1244 = 3177$ .

Kaprekar proved that if you start with a four-digit number $x$ whose digits are not all equal and repeatedly apply this operation ( $K(x), K(K(x)), \ldots$ ), you eventually reach 6174. Since $K(6174) = 7641 - 1467 = 6174$ , the process cycles at 6174.

Your task is to write a program that computes $K(x)$ for a given number $x$ .

Input

The input file contains one integer $x$ without leading zeros ( $1 \le x \le 10^9$ ).

Output

Print $K(x)$ to the output file.

Examples2

Example 1
Input
```
100
```
Expected output
```
099
```
Example 2
Input
```
2414
```
Expected output
```
3177
```