Problem Description

Firmino has a positive integer $d$ (of length $N$), and let's denote its digits from left to right (from high to low) as $d_0, d_1, \cdots, d_{N-1}$.

Firmino claims that behind this integer is a sequence of non-negative integers $\{a_i\}$ that forms an arithmetic sequence. Specifically, for non-negative integers $A, B$ and a positive integer $X$, the sequence is defined as:

$$ a_i=\begin{cases} A, & i=0 \\ a_{i-1}+B & i\gt 0 \end{cases} $$

Moreover, this sequence satisfies: for $i=0, 1, \cdots, N-1$, the $X$-th digit (counting from right to left) of $a_i$ is $d_i$. Formally, $\forall i \in [0, N-1]$, it holds that $\displaystyle d_i=\left\lfloor\frac{a_i}{10^{X-1}}\right\rfloor \bmod 10$. For example, the 1st digit of $114$ is $4$, and the 2nd and 3rd digits are $1$.

Firmino wants to know the smallest possible first term (i.e., $A$) of such an arithmetic sequence that satisfies the above conditions. Since he calculated it in his mind in less than $0.5\mathrm{s}$, he challenges you to compute it within $5\mathrm{s}$.

If no such arithmetic sequence exists, output -1.

Input Format

A single line containing a positive integer $d$.

Output Format

A single line containing a non-negative integer $A$, which is the smallest possible first term of the arithmetic sequence that satisfies the conditions.

If no such arithmetic sequence exists, output -1.

Sample Input and Output

Sample Input #1

6925814703

Sample Output #1

6

Sample Input #2

6925814704

Sample Output #2

61

Sample Input #3

6925814705

Sample Output #3

-1

Sample Input #4

9

Sample Output #4

9

Notes/Hints

Explanation for Sample 1: Taking $A=6, B=3, X=1$ satisfies the conditions. It can be proven that this is the smallest first term.

Explanation for Sample 2: Taking $A=61, B=31, X=2$ satisfies the conditions. It can be proven that this is the smallest first term.

For $100\%$ of the data, it is guaranteed that $1 \le N \le 10^4$, and $d$ does not have leading zeros.

$\texttt{Statement fixed by Starrykiller.}$

见题面 Input 部分

见题面 Output 部分