E - Arithmetic Number Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

以下の条件を満たす正の整数 n を、 等差数 と呼びます。

  • (n を先頭に余計な 0 を付けずに 10 進法で表記した際、) n の上から i 桁目を d_i とする。このとき、 n が k 桁の整数であったとすると、 (d_2-d_1)=(d_3-d_2)=\dots=(d_k-d_{k-1}) が成立する。
    • この条件は、「 数列 (d_1,d_2,\dots,d_k) が等差数列である」と言い換えることができる。
    • 但し、 n が 1 桁の整数である時、 n は等差数であるものとする。

たとえば、 234,369,86420,17,95,8,11,777 は等差数ですが、 751,919,2022,246810,2356 は等差数ではありません。

等差数のうち、 X 以上で最小のものを求めてください。

制約

  • X は 1 以上 10^{17} 以下の整数である

入力

入力は以下の形式で標準入力から与えられる。

X

出力

答えを整数として出力せよ。

入力例 1

152

出力例 1

159

152 以上で最小の等差数は 159 です。

入力例 2

88

出力例 2

88

X 自身が等差数である場合もあります。

入力例 3

8989898989

出力例 3

9876543210

Score : 500 points

Problem Statement

Let us call a positive integer n that satisfies the following condition an arithmetic number.

  • Let d_i be the i-th digit of n from the top (when n is written in base 10 without unnecessary leading zeros.) Then, (d_2-d_1)=(d_3-d_2)=\dots=(d_k-d_{k-1}) holds, where k is the number of digits in n.
    • This condition can be rephrased into the sequence (d_1,d_2,\dots,d_k) being arithmetic.
    • If n is a 1-digit integer, it is assumed to be an arithmetic number.

For example, 234,369,86420,17,95,8,11,777 are arithmetic numbers, while 751,919,2022,246810,2356 are not.

Find the smallest arithmetic number not less than X.

Constraints

  • X is an integer between 1 and 10^{17} (inclusive).

Input

Input is given from Standard Input in the following format:

X

Output

Print the answer as an integer.

Sample Input 1

152

Sample Output 1

159

The smallest arithmetic number not less than 152 is 159.

Sample Input 2

88

Sample Output 2

88

X itself may be an arithmetic number.

Sample Input 3

8989898989

Sample Output 3

9876543210