Vasya 收集交通票已经有一段时间了。他收藏了数千张电车、无轨电车和公共汽车票。瓦西亚已经厌倦了幸运彩票的传统定义。因此,他正在寻找新的视角。另外,瓦夏不明白为什么所有的门票都只分为幸运票和倒霉票。他认为所有的门票都是幸运的,只是程度不同。经过深思熟虑后,瓦夏制定了彩票幸运程度的定义。设一张票由 2n 位数字组成。我们将每个数字视为如图所示:
你在电子钟上见过这样的数字:用七段来显示数字。每个部分可以是彩色的,也可以是不彩色的。彩色部分形成一个数字。 Vasya 认为这些数字就是这样写的,他把票的右半部分放在左边,这样第一个数字与第 n + 1 个数字重合,第二个数字与第 n + 2 个数字重合,......,第 n 个数字与第 2n 个数字重合。对于每一对数字,将一个数字放在另一个数字上,他计算两个数字中着色的部分的数量,并总结所得的数字。所得值称为彩票的幸运程度。例如,票03的幸运度等于4,票2345的幸运度等于6。
给您包含 2n 位数字的票号。你的任务是在彩票中找出数量超过这张彩票的号码,但又包含 2n 位这样的彩票,其幸运程度超过给定彩票的幸运程度。此外,如果有几张这样的票,您应该只选择号码最小的一张。
输入
第一行包含由 k 个字符组成的票号(k = 2n, 1 ≤ n ≤ 105)。
输出
打印所寻找票证的编号,如果不存在此类票证,则打印“-1”(不带引号)。
示例
输入 #1
13
输出 #1
20
输入 #2
2345
输出 #2
2348
输入 #3
88
输出 #3
-1