COCI 2007/2008, Contest #4

Task VECI

Your program will be given an integer X. Find the smallest number larger than X consisting of the same digits as X.

Input

The first line of input contains the integer X (1 ≤ X ≤ 999 999).

The first digit in X will not be a zero.

Output

Output the result on a single line. If there is no such number, output 0.

Examples

Input

156

Output

165

Input

330

Output

0

Input

27711

Output

71127

All Submissions
Best Solutions


Point Value: 5
Time Limit: 1.00s
Memory Limit: 32M
Added: Aug 02, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

ss3happy1 on Apr 23, 2015 - 10:47:21 pm UTC Does Python Take Import Itertools
  • (0/0)
I have a solution that works perfectly with the test cases. I used import itertools and generated all the permutations into one list, then looped through it to find correct answer. It works pretty well, but since I get a traceback error, I'm wondering if it doesn't take this import.

jargon on Apr 26, 2015 - 12:54:41 am UTC Re: Does Python Take Import Itertools
  • (0/0)
Sorry about this. This problem's testdata was directly uploaded from the COCI site, and contained carriage returns. I've removed these and rejudged your latest submission, which now gets AC.

Ajna on Nov 19, 2014 - 12:34:51 pm UTC And thanks again :)!
  • (2/0)
I wanted to avoid using itertools or a similar tool to brute force all the interesting combinations and then pick up the minimum, so I changed my point of view analyzing the input as a string and thinking if a simple swap+sorting could have done the trick.

Well, I did after a night of sleep and learnt something new again: thanks guys for the ever interesting problems :)!

[I hope I am not annoying you, but seeing that you are doing a good work, yet I presume still a hard one, you surely deserve some praise once in a while, ne?]