Numbers

Interview

Time limit1sMemory limit512 MB

Summary

Given x and a mood flag, find the smallest y at least x whose digits are all equal, or all equal except one digit when the flag is 1.

Level: Medium5 of 10
Topics: Brute force, Implementation, Greedy
Solved: No attempts yet

Problem

Anya likes numbers made of identical digits. She likes 777 or 5555, but she does not like 1234 at all.

When Anya is in a good mood, she still likes all numbers made of identical digits, and she also likes numbers in which all digits except one are the same, such as 77727.

Anya has an integer $x$ . She wants to find the smallest integer $y \ge x$ that she will like.

Given an integer $x$ and whether Anya is in a good mood, write a program that finds the smallest integer $y \ge x$ that Anya likes.

Input

The first line contains an integer $x$ ( $1 \le x \le 10^{17}$ ). This number does not fit in a 32-bit type, so use a 64-bit type such as long long in C++ or int64 in Pascal.

The second line contains $k$ , which is 0 or 1. $k = 1$ means Anya is in a good mood, and $k = 0$ means she is not.

Output

Print one integer $y$ .

It must satisfy:

$y \ge x$
if $k = 0$ , all digits of $y$ are the same
if $k = 1$ , all digits of $y$ except possibly one are the same

Examples2

Example 1
Input
```
700
0
```
Expected output
```
777
```
Example 2
Input
```
700
1
```
Expected output
```
700
```