새로운 수학

"이런!" 찰스가 소리쳤다. "이 멍청한 올림 자막이 내 엔진에서 작동하지 않아! 방금 어떤 수의 제곱을 계산하려 했는데, 결과가 틀렸어. 올림이 전부 사라졌어."

"흠," 에이다가 생각에 잠겨 말했다. "올림 없는 산술이라니! 엔진에 보이는 결과를 보고 네가 원래 입력한 값이 무엇이었는지 알아낼 수 있을지 궁금하네."

$\oplus$로 표기하는 올림 없는 덧셈은 (10진법에서) 올림을 무시한다는 점만 빼면 일반 덧셈과 같다. 따라서 $37 \oplus 48$은 $85$가 아니라 $75$이다.

$\otimes$로 표기하는 올림 없는 곱셈은 학교에서 배우는 곱셈 알고리즘처럼 열별로 수행하되, 중간 덧셈을 올림 없는 덧셈으로 계산한다. 더 형식적으로, $a$의 자릿수를 $a\_m a\_{m-1} \ldots a\_1 a\_0$라 하자. 여기서 $a\_0$은 최하위 자릿수이다. 마찬가지로 $b$의 자릿수를 $b\_n b\_{n-1} \ldots b\_1 b\_0$라 하자. $c = a \otimes b$의 자릿수는 다음 식으로 주어진다. [ c_k = \left( a_0 b_k \oplus a_1 b_{k-1} \oplus \cdots \oplus a_{k-1} b_1 \oplus a_k b_0 \right) \bmod{10}, ] 여기서 $i > m$이거나 $j > n$이면 $a\_i$ 또는 $b\_j$는 0으로 본다. 예를 들어 $9 \otimes 1\,234$는 $9\,876$이고, $90 \otimes 1\,234$는 $98\,760$이며, $99 \otimes 1\,234$는 $97\,536$이다.

$N$이 주어질 때, $a \otimes a = N$을 만족하는 가장 작은 양의 정수 $a$를 구하라.

입력은 한 줄로 주어지며, 자릿수가 최대 $25$자리이고 앞에 0이 없는 양의 정수 $N$이 들어 있다.

$a \otimes a = N$을 만족하는 가장 작은 양의 정수 $a$를 한 줄에 출력한다. 그러한 $a$가 없으면 대신 '-1'을 출력한다.