cho.sh

Next Special String

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.

Medium7StringGreedyCombinatoricsImplementationNo attempts yetTime limit2sMemory limit512 MB

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 NN. Sort every special string of length NN in lexicographic order and report the string that comes immediately after S.

Input

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

Output

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