This is an unusual problem in an unusual contest, here is the announcement: [http://codeforces.com/blog/entry/73543](//codeforces.com/blog/entry/73543)

You have the safe lock which consists of 100 decimal digits. If you rotate some digit, it increases by one, except 9 which becomes 0.

Initially, the lock contains number x. To unlock the safe you must do the following operations in order (and be careful, don't mix up if and else statements).

If digit 39 is odd, rotate digit 39 by 9 times, else rotate digit 37 by 1 times. If digit 24 is odd, rotate digit 24 by 1 times, else rotate digit 76 by 3 times. If sum of digits 13 and 91 is greater than 10, rotate digit 14 by 6 times, else rotate digit 34 by 8 times. If digit 87 is odd, rotate digit 87 by 7 times, else rotate digit 22 by 9 times. If digit 79 is greater than digit 15, rotate digit 74 by 7 times, else rotate digit 84 by 6 times. If sum of digits 26 and 66 is greater than 9, rotate digit 31 by 7 times, else rotate digit 95 by 4 times. If sum of digits 53 and 1 is greater than 8, rotate digit 66 by 1 times, else rotate digit 94 by 6 times. If digit 41 is greater than digit 29, rotate digit 67 by 5 times, else rotate digit 41 by 9 times. If sum of digits 79 and 20 is greater than 10, rotate digit 18 by 2 times, else rotate digit 72 by 9 times. If sum of digits 14 and 24 is greater than 10, rotate digit 64 by 2 times, else rotate digit 84 by 2 times. If digit 16 is greater than digit 34, rotate digit 81 by 5 times, else rotate digit 15 by 2 times. If sum of digits 48 and 65 is greater than 9, rotate digit 57 by 2 times, else rotate digit 28 by 5 times. If digit 81 is odd, rotate digit 81 by 5 times, else rotate digit 25 by 4 times. If digit 70 is odd, rotate digit 70 by 9 times, else rotate digit 93 by 3 times. If sum of digits 92 and 49 is greater than 9, rotate digit 81 by 2 times, else rotate digit 42 by 3 times. If digit 96 is greater than digit 20, rotate digit 45 by 4 times, else rotate digit 45 by 1 times. If digit 91 is greater than digit 21, rotate digit 60 by 3 times, else rotate digit 72 by 1 times. If digit 89 is greater than digit 7, rotate digit 98 by 9 times, else rotate digit 52 by 7 times. If digit 38 is greater than digit 97, rotate digit 92 by 6 times, else rotate digit 35 by 4 times. If digit 96 is greater than digit 99, rotate digit 42 by 4 times, else rotate digit 40 by 9 times. If digit 86 is odd, rotate digit 86 by 1 times, else rotate digit 14 by 3 times. If digit 23 is odd, rotate digit 23 by 5 times, else rotate digit 55 by 9 times. If digit 79 is odd, rotate digit 79 by 1 times, else rotate digit 29 by 8 times. If digit 4 is greater than digit 91, rotate digit 98 by 8 times, else rotate digit 69 by 4 times. If digit 93 is greater than digit 24, rotate digit 75 by 9 times, else rotate digit 95 by 3 times. If sum of digits 32 and 50 is greater than 10, rotate digit 91 by 3 times, else rotate digit 1 by 5 times. If digit 81 is greater than digit 31, rotate digit 86 by 7 times, else rotate digit 67 by 5 times. If digit 83 is greater than digit 86, rotate digit 48 by 7 times, else rotate digit 2 by 6 times. If digit 20 is greater than digit 88, rotate digit 9 by 2 times, else rotate digit 99 by 4 times. If digit 14 is odd, rotate digit 14 by 5 times, else rotate digit 97 by 7 times. If digit 38 is greater than digit 14, rotate digit 48 by 2 times, else rotate digit 81 by 5 times. If digit 92 is greater than digit 74, rotate digit 92 by 1 times, else rotate digit 50 by 9 times. If digit 76 is greater than digit 89, rotate digit 68 by 6 times, else rotate digit 69 by 5 times. If digit 2 is greater than digit 28, rotate digit 75 by 1 times, else rotate digit 89 by 1 times. If digit 67 is odd, rotate digit 67 by 9 times, else rotate digit 49 by 1 times. If digit 23 is odd, rotate digit 23 by 1 times, else rotate digit 59 by 3 times. If digit 81 is odd, rotate digit 81 by 9 times, else rotate digit 9 by 4 times. If sum of digits 92 and 82 is greater than 9, rotate digit 81 by 2 times, else rotate digit 91 by 5 times. If sum of digits 42 and 48 is greater than 9, rotate digit 35 by 8 times, else rotate digit 59 by 6 times. If digit 55 is odd, rotate digit 55 by 9 times, else rotate digit 61 by 6 times. If digit 83 is odd, rotate digit 83 by 5 times, else rotate digit 85 by 4 times. If digit 96 is odd, rotate digit 96 by 1 times, else rotate digit 72 by 4 times. If digit 17 is odd, rotate digit 17 by 1 times, else rotate digit 28 by 3 times. If digit 85 is greater than digit 74, rotate digit 37 by 3 times, else rotate digit 10 by 3 times. If sum of digits 50 and 67 is greater than 9, rotate digit 85 by 9 times, else rotate digit 42 by 4 times. If sum of digits 11 and 43 is greater than 10, rotate digit 56 by 7 times, else rotate digit 50 by 7 times. If sum of digits 95 and 64 is greater than 9, rotate digit 95 by 4 times, else rotate digit 95 by 9 times. If sum of digits 21 and 16 is greater than 9, rotate digit 87 by 3 times, else rotate digit 30 by 1 times. If digit 91 is odd, rotate digit 91 by 1 times, else rotate digit 77 by 1 times. If digit 95 is greater than digit 82, rotate digit 53 by 2 times, else rotate digit 100 by 5 times. If sum of digits 88 and 66 is greater than 10, rotate digit 34 by 4 times, else rotate digit 57 by 4 times. If digit 73 is greater than digit 84, rotate digit 52 by 3 times, else rotate digit 42 by 9 times. If digit 66 is greater than digit 38, rotate digit 94 by 7 times, else rotate digit 78 by 7 times. If digit 23 is greater than digit 12, rotate digit 78 by 2 times, else rotate digit 62 by 8 times. If digit 13 is greater than digit 9, rotate digit 42 by 7 times, else rotate digit 1 by 9 times. If digit 43 is greater than digit 29, rotate digit 20 by 2 times, else rotate digit 47 by 2 times. If sum of digits 100 and 51 is greater than 8, rotate digit 10 by 6 times, else rotate digit 89 by 1 times. If digit 19 is greater than digit 37, rotate digit 26 by 7 times, else rotate digit 30 by 8 times. If digit 73 is greater than digit 25, rotate digit 77 by 3 times, else rotate digit 41 by 1 times. If sum of digits 67 and 96 is greater than 10, rotate digit 47 by 6 times, else rotate digit 33 by 5 times. If digit 11 is greater than digit 10, rotate digit 33 by 3 times, else rotate digit 4 by 3 times. If digit 85 is odd, rotate digit 85 by 7 times, else rotate digit 37 by 9 times. If digit 14 is odd, rotate digit 14 by 1 times, else rotate digit 28 by 4 times. If sum of digits 30 and 18 is greater than 8, rotate digit 93 by 5 times, else rotate digit 68 by 1 times. If sum of digits 54 and 72 is greater than 8, rotate digit 88 by 8 times, else rotate digit 25 by 8 times. If digit 72 is odd, rotate digit 72 by 5 times, else rotate digit 10 by 3 times. If digit 15 is odd, rotate digit 15 by 3 times, else rotate digit 68 by 1 times. If sum of digits 81 and 31 is greater than 9, rotate digit 2 by 5 times, else rotate digit 35 by 1 times. If digit 57 is odd, rotate digit 57 by 1 times, else rotate digit 25 by 9 times. If sum of digits 75 and 51 is greater than 9, rotate digit 73 by 8 times, else rotate digit 49 by 1 times. If sum of digits 81 and 61 is greater than 10, rotate digit 61 by 3 times, else rotate digit 88 by 1 times. If digit 60 is odd, rotate digit 60 by 1 times, else rotate digit 31 by 2 times. If digit 93 is odd, rotate digit 93 by 5 times, else rotate digit 50 by 1 times. If sum of digits 19 and 82 is greater than 9, rotate digit 48 by 7 times, else rotate digit 88 by 8 times. If digit 45 is odd, rotate digit 45 by 7 times, else rotate digit 100 by 1 times. If digit 46 is greater than digit 71, rotate digit 28 by 8 times, else rotate digit 37 by 6 times. If digit 79 is odd, rotate digit 79 by 5 times, else rotate digit 10 by 1 times. If digit 19 is greater than digit 95, rotate digit 76 by 9 times, else rotate digit 95 by 8 times. If digit 49 is odd, rotate digit 49 by 5 times, else rotate digit 66 by 3 times. If digit 62 is odd, rotate digit 62 by 1 times, else rotate digit 26 by 8 times. If digit 67 is greater than digit 33, rotate digit 27 by 8 times, else rotate digit 96 by 2 times. If sum of digits 73 and 15 is greater than 8, rotate digit 98 by 6 times, else rotate digit 11 by 6 times. If digit 63 is greater than digit 42, rotate digit 66 by 1 times, else rotate digit 58 by 2 times. If digit 41 is odd, rotate digit 41 by 9 times, else rotate digit 99 by 5 times. If digit 93 is odd, rotate digit 93 by 5 times, else rotate digit 53 by 1 times. If digit 46 is odd, rotate digit 46 by 3 times, else rotate digit 64 by 4 times. If sum of digits 99 and 64 is greater than 10, rotate digit 72 by 9 times, else rotate digit 51 by 5 times. If digit 75 is greater than digit 23, rotate digit 89 by 2 times, else rotate digit 76 by 7 times. If digit 6 is odd, rotate digit 6 by 1 times, else rotate digit 44 by 6 times. If digit 58 is odd, rotate digit 58 by 3 times, else rotate digit 49 by 9 times. If digit 5 is greater than digit 13, rotate digit 46 by 9 times, else rotate digit 21 by 7 times. If sum of digits 44 and 94 is greater than 9, rotate digit 36 by 4 times, else rotate digit 15 by 3 times. If sum of digits 52 and 43 is greater than 8, rotate digit 29 by 8 times, else rotate digit 72 by 6 times. If sum of digits 87 and 48 is greater than 9, rotate digit 61 by 8 times, else rotate digit 14 by 3 times. If digit 81 is odd, rotate digit 81 by 7 times, else rotate digit 64 by 2 times. If digit 88 is odd, rotate digit 88 by 7 times, else rotate digit 53 by 9 times. If sum of digits 86 and 78 is greater than 10, rotate digit 96 by 7 times, else rotate digit 79 by 1 times. If digit 20 is odd, rotate digit 20 by 7 times, else rotate digit 2 by 7 times. If digit 77 is greater than digit 80, rotate digit 60 by 5 times, else rotate digit 38 by 8 times. If digit 65 is odd, rotate digit 65 by 1 times, else rotate digit 85 by 3 times.

Input

Input contains single number x consisting of exactly 100 digits, leading zeroes are allowed.

Output

Output the number after applying all operations.

Examples

Input


0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000


Output


9700010006000300020000111706617034943099970012861000908700093104145749080706326060507070104603727696


Input


1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890


Output


0434577839123736809081959678791214963899953499955062244348594338577599113453106002302374004287484136

Source: codeforces | Difficulty: UNKNOWN_DIFFICULTY


Solutions: