Next Special String

Time limit2sMemory limit512 MB

Summary

Given a binary special string (each split satisfies U < V), find the next special string of the same length in lexicographic order, or -1 if none exists.

Level: Medium7 of 10
Topics: String, Greedy, Combinatorics, Implementation
Solved: No attempts yet

Problem

A string S is called special when both of the following hold.

Every character of S is '0' or '1'.
For every way of cutting S into two non-empty parts U and V with S = UV, U comes before V in lexicographic order.

For example, S = "00101" is special, because "0" < "0101", "00" < "101", "001" < "01" and "0010" < "1" all hold. A string of length 1 cannot be cut into two parts, so "0" and "1" are both special.

You are given a special string S of length $N$ . Sort every special string of length $N$ in lexicographic order and report the string that comes immediately after S.

Input

The first line contains the special string S. Its length $N$ satisfies $1 \le N \le 50$ .

Output

Print the special string of length $N$ that comes immediately after S in lexicographic order. If S is the last special string in that order, print -1 instead.

Examples3

Example 1
Input
```
01
```
Expected output
```
-1
```
Example 2
Input
```
00101
```
Expected output
```
00111
```
Example 3
Input
```
0010111
```
Expected output
```
0011011
```