Problem Description

Define a Handsome number: in this positive integer, the parity of any two adjacent digits is different.

Given a positive integer $n$, find the Handsome number closest to $n$. If there are multiple answers, output them in increasing order.

Input Format

A positive integer $n$.

Output Format

The Handsome number(s) closest to $n$.

13

12 14

5801001

5810101

Hint

For $100\%$ of the testdata, $1 \leq n \leq 10^{1000}$.

Translated from COCI 2014/2015 CONTEST #5.

Translated by ChatGPT 5