nr

Be there x a positive integer with exactly n digits, written in base 10.

Task

Write a program that determines the smallest positive integer larger than x, that is made up of the same digits as x and which is a palindrome.

Input Data

Input file nr.in contains two lines. Line one contains n, the number of digits of x. Line two contains the n digits of x.

Output Data

Output file nr.out will contain a single line with the smallest positive integer larger than x, that is made up of the same digits as x and which is a palindrome. If there is no solution, line one of the output file will be 0.

Constraints and Statements

• 1 < n < 1000
• We call a palindrome a number which is the same read from left to right or right to left (e.g.: 1331, 12321, etc).
• The first digit of a number must be non-zero.
• By the same digits we mean that each digit from 0 to 9 shows up in the result the same number of times as in x.
  

Time limit: 0.1 seconds/test

prof. Emanuela Cerchez
"Grigore Moisil" Iaşi IT High School
Contact:emanuela.cerchez@gmail.com