No tags yet

No tag edit access

J. Keep talking and nobody explodes – hard

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThis is an unusual problem in an unusual contest, here is the announcement: http://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

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/29/2020 03:46:20 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|