ZGODAN

Time limit1sMemory limit32 MB

Summary

Given a non-handsome integer with up to 1000 digits, find the nearest integer whose consecutive digits alternate between even and odd, printing both on a tie.

Level: Medium6 of 10
Topics: Greedy, String, Backtracking
Solved: No attempts yet

Problem

An integer is handsome if every pair of consecutive digits has different parity (one even, one odd). Single-digit numbers are handsome.

Given a positive integer $N$ that is not handsome, find the closest handsome integer(s). Distance is absolute difference. If two different handsome numbers tie for minimum distance, print the smaller, then the larger, separated by one space.

Input

One line with a positive integer $N$ of at most 1000 digits. $N$ is not handsome.

Output

Print the closest handsome number(s). If the tie is between two distinct numbers, print both in increasing order separated by a single space.

Examples4

Example 1
Input
```
13
```
Expected output
```
12 14
```
Example 2
Input
```
5801001
```
Expected output
```
5810101
```
Example 3
Input
```
22
```
Expected output
```
21 23
```
Example 4
Input
```
100
```
Expected output
```
101
```