Problem F. Fixing lottery

Author:A. Klenin
Input file: input.txt   Time limit:1 sec
Output file: output.txt   Memory limit:256 Mb

Statement

Well-known store chain "Three cats" decided to create a marketing lottery. Customers were given tickets with sequential integer numbers, and each month a single ticket number was selected as a winner.

To promote company image, it was decided that winning number must be divisible by 3.

For the first month of the lottery, company selected a ticket and printed it on a large banner to hang inside the store. Unfortunately, a person from marketing who selected a ticket did not know math, and selected ticket number which is not divisible by 3.

To quickly fix the banner, your program must change exactly one digit in the number so that:

  1. Result is divisible by 3.
  2. Result is less than original number.
  3. Result has no leading zeroes.

Input file format

Input file contains a string of N decimal digits. First digit is non-zero.

Output file format

Output file must contain a string of N decimal digits — fixed ticket number. If there is more than one solution, output numerically smallest of them. If there is no solution, output string IMPOSSIBLE.

Constraints

2 ≤ N ≤ 100

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
13
12
2
200
IMPOSSIBLE
3
55
15

0.019s 0.007s 9