問題文
有一天,鹿 AtCoDeerN由术语组成的数字字符串 找到{d_i} (0≦i≦N-1)。根据AtCoDeer的直觉,这背后是一个由非负整数组成的算术级数。尤其,
- 非負整数A,B,正整数X。 定义
- a_0 = A , a_i = a_{i-1} + B (1≦i≦N-1) 和a_i。
- 然后, 对于i (0≦i≦N-1) , 从下面(以十进制表示)a_i(以十进制表示)从下往上X数字是 等于d_i。
AtCoDeer-kun 计算第一项(即A) 是最小值。 对于
制約
- 1≦N≦10^4
- 各0≦i≦N-1,d_i是 0 到 9 之间的整数。
- d_0≠0
入力
输入将以以下格式从标准输入给出。
d_0d_1....d_{N-1}
请注意,它们不是用空格分隔的。
出力
输出满足条件的等差数列第一项的最小值。如果不存在这样的算术级数,那么-1。
入力例1
6925814703
出力例1
6
A=6,B=3,X=1满足条件并且此A的最小值。
入力例2
6925814704
出力例2
61
A=61,B=31,X=2满足条件。
入力例3
6925814705
出力例3
-1
没有满足条件的算术级数。
入力例4
9
出力例4
9