問題文

シカのAtCoDeerくんはある日$N$項からなる数字列${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$に等しい。

ここで、非負整数$n$の下から$x$桁目とは、 $(n/10^{x-1})$%$10$ のことを指す(ただし, /は除算(切り捨て), %はあまりを取る操作)。 例えば、102の下から一桁目は2,二桁目は0,三桁目は1,四桁目は0,百桁目は0である。

AtCoDeerくんは、このような条件を満たす等差数列の内、初項(すなわち$A$)が最小のものを求めることにした。

制約

• $1≦N≦10^4$
• 各$0≦i≦N-1$に対し,$d_i$は0以上9以下の整数
• $d_0≠0$

入力

入力は以下の形式で標準入力から与えられる。

$d_0$$d_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