Let's consider equation:x^2 + s(x)·x - n = 0,  

where x, n are positive integers, s(x) is the function, equal to the sum of digits of number x in the decimal number system.

You are given an integer n, find the smallest positive integer root of equation x, or else determine that there are no such roots.


-----Input-----

A single line contains integer n (1 ≤ n ≤ 10^18) — the equation parameter.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier. 


-----Output-----

Print -1, if the equation doesn't have integer positive roots. Otherwise print such smallest integer x (x > 0), that the equation given in the statement holds.


-----Examples-----
Input
2

Output
1

Input
110

Output
10

Input
4

Output
-1



-----Note-----

In the first test case x = 1 is the minimum root. As s(1) = 1 and 1^2 + 1·1 - 2 = 0.

In the second test case x = 10 is the minimum root. As s(10) = 1 + 0 = 1 and 10^2 + 1·10 - 110 = 0.

In the third test case the equation has no roots.

Difficulty: interview

Starter code:

Solutions:
import re
import itertools
from collections import Counter, deque

class Task:
    maxDigitSum = 18 * 9
    n = 0
    answer = "" 
	
    def getData(self):
        self.n = int(input())
        #inFile = open('input.txt', 'r')
        #inFile.readline().rstrip()
        #self.childs = inFile.readline().rstrip()

    def solve(self):
        if self.n == 1:
            self.answer = '-1'
            return

        xL, xR = 0, self.n
        while xL + self.maxDigitSum < xR:
            xM = (xL + xR) // 2
            if xM**2 + self.digitSum(xM) * xM < self.n:
                for x in range(xM - 1, max(xL, xM - self.maxDigitSum) - 1, -1):
                    if x**2 + self.digitSum(x) * x == self.n:
                        self.answer = x
                        return
                xL = xM
            else:
                for x in range(xM + 1, min(xR, xM + self.maxDigitSum) + 1):
                    if x**2 + self.digitSum(x) * x == self.n:
                        self.answer = x
                        return
                xR = xM
        for x in range(xL, xR + 1):
            if x**2 + self.digitSum(x) * x == self.n:
                self.answer = x
                return
        self.answer = -1

    def digitSum(self, n):
        return sum([int(x) for x in str(n)])

    def printAnswer(self):
        print(self.answer)
        #outFile = open('output.txt', 'w')
        #outFile.write(self.answer)

task = Task()
task.getData()
task.solve()
task.printAnswer()


def s(x):
    return sum(int(i) for i in str(x))

n = input()
l, n = 9 * len(n), int(n)
ans, m = -1, int(n ** 0.5)
for x in range(max(1, m - l), m + 1):
    if n % x == 0 and x * (x + s(x)) == n:
        ans = x
        break
print(ans)

def f(x):
    s = str(x)
    ans = 0
    for i in s:
        ans += ord(i) - ord('0')
    return ans

n = int(input())
for sx in range(1, 91):
    x = ((sx*sx + 4.0*n)**0.5 - sx) / 2.0
    if abs(x - round(x)) > 1e-5:
        continue
    lx = int(x)
    if f(lx) != sx:
        continue
    if lx*lx + sx*lx != n:
        continue
    print(lx)
    return
print(-1)


def readln(): return tuple(map(int, input().split()))

n, = readln()
for s in range(1, 180):
    d = int((s**2 + 4 * n)**0.5)
    if d**2 == s**2 + 4 * n and (-s + d) % 2 == 0:
        x = (-s + d) // 2
        if sum(map(int, list(str(x)))) == s:
            import sys
            print(x)
            return
print(-1)


n = int(input())
x = int(round(n**0.5-0.499999))
y=x-9999
while (x >= y) and (x>0): 
    list_1 = list(map(int, str(x)))
    s = 0
    for i in list_1:
        s = s + i
    if (x*x+s*x-n)==0:
        print(x)
        break
    else: x = x-1
if (not (x*x+s*x-n)==0) : print('-1')
    


n = int(input())
x = 4 * n

def is_square(m):
    x = 1
    for i in range(100):
        x = 0.5 * (x + m / x)
    x = int(x)
    if x * x == m:
        return x
    else:
        return -1

ans = -1
for s in range(9 * 18):
    d = s ** 2 + x
    root = is_square(d)
    if root != -1:
        val = -s + root
        if val % 2 == 0 and (val // 2 < ans or ans == -1) and sum(list(map(int, str(val // 2)))) == s:
            ans = val // 2
if ans == -1:
    print(-1)
else:
    print(ans)



def sumd(n):
    v = 0
    while n > 0:
        v += n % 10
        n //= 10
    return v

n, v = int(input()), -1
a, b = 0, n + 1
while a < b - 1:
    c = (a + b) // 2
    if c ** 2 <= n:
        a = c
    else:
        b = c
while a > 0 and n // a - a <= 81:
    if n % a == 0 and n // a - a == sumd(a):
        v = a
    a -= 1
print(v)


n = int(input())

ans = 10 ** 18

def f(x):
    s = 0
    while x > 0:
        s += x % 10
        x //= 10
    return s

def sqr(x):
    l, r = 0, 10 ** 10
    while r > l + 1:
        m = (l + r) // 2;
        if m * m <= x:
            l = m
        else:
            r = m
    return l

for s in range(100):
    if sqr(s ** 2 + 4 * n) ** 2 == s ** 2 + 4 * n:
        x1 = (-s + sqr(s ** 2 + 4 * n)) / 2
        x2 = (-s - sqr(s ** 2 + 4 * n)) / 2
        if x1 > 0 and int(x1) == x1 and f(int(x1)) == s:
            ans = min(ans, int(x1))
        if x2 > 0 and int(x2) == x2 and f(int(x2)) == s:
            ans = min(ans, int(x2))

if ans == 10 ** 18:
    print(-1)
else:
    print(ans)

n=int(input())
f=lambda x:x*x+sum(map(int,str(abs(x))))*x
def b(l,r):
	while l<r-1:
		m=(l+r)//2
		if f(m)<n:l=m
		else:r=m
	return r
r=b(0,10**18)
for i in range(max(1,r-1000),r+1000):
	if f(i)==n:r=i;break
else:r=-1
print(r)

import math

def digit_sum(n):
    su = 0
    while n:
        su += n%10
        n = math.floor(n/10)
    return su

def main():
    n = int(input())
    mini = -1
    for s in range(1, (9 * 10) + 1):
        a = (-s + math.sqrt((s * s) + (4 * n)))/2
        b = (-s - math.sqrt((s * s) + (4 * n)))/2
        x = math.floor(a)
        y = math.floor(b)
        if a.is_integer() and x != 999959999 and x > 0 and digit_sum(x) == s and (mini == -1 or x < mini):
            mini = x
        if b.is_integer() and x != 999959999 and y > 0 and digit_sum(y) == s and (mini == -1 or y < mini):
            mini = y
        # print("mini", mini)
    print(mini)


def __starting_point():
    main()

__starting_point()

"""http://codeforces.com/problemset/problem/233/B"""

def s(x): return sum(map(int, str(x)))
def val(x): return x*x + s(x)*x
def solve(n):
    l = 1; r = int(n ** 0.5) + 1
    while l <= r:
        mid = (l + r) // 2
        print(l, mid, r,  val(mid))
        if val(mid) == n: return mid
        elif mid ** 2 < n: l = mid + 1
        elif mid ** 2 > n: r = mid - 1
    return -1

def solve2(n):
    for sx in range(1, 81):
        x = int((-sx + (sx**2 + 4*n)**0.5) // 2)
        if s(int(x)) == sx and x*(x+sx) == n:
            return x
    return -1

def test():
    assert solve2(4) == -1

def __starting_point():
    test()
    print(solve2(int(input())))

__starting_point()

"""http://codeforces.com/problemset/problem/233/B"""

def s(x): return sum(map(int, str(x)))
def solve(n):
    l = 1; r = int(n ** 0.5); max_s = 81
    for x in range(max(1, r - max_s), r + 1):
        if x * (x + s(x)) == n:
            return x
    return -1

def test():
    assert solve(2) == 1
    assert solve(110) == 10
    assert solve(4) == -1
    assert solve(10000006999999929) == 99999999


def __starting_point():
    test()
    print(solve(int(input())))

__starting_point()

#!/usr/bin/env python3

from math import sqrt

def sum_digits(x):
    res = 0
    while x > 0:
        res += (x % 10)
        x //= 10
    return res


n = int(input())
root = int(sqrt(n))


for i in range(max(root - 100, 1), root + 1, 1):
    sd = sum_digits(i)
    if i * i + sd * i - n == 0:
        print(i)
        return

print('-1')



'''
def main():
	from sys import stdin,stdout
def __starting_point():
	main()
'''
#349B
'''
def main():
	from sys import stdin,stdout
	N = int(stdin.readline())
	arr = list(map(int,stdin.readline().split()))
	div = []
	for i in arr:
		div.append(N//i)
	maxim = 0
	maxindex = -1
	for i in range(9):
		if div[i] >maxim:
			maxim = div[i]
			maxindex = i
	if maxindex > -1:
		ans = [ (maxindex+1) for i in range(maxim)]
		N= N%arr[maxindex]
		#print(N)
		i = 0
		while i<maxim:
			#print('i=',i,'N=',N)
			for j in range(8,maxindex,-1):
				#print('j=',j,'diff=',arr[j]-arr[ans[i]-1])
				if arr[j]-arr[ans[i]-1] <=N:
					N -= arr[j]-arr[ans[i]-1]
					ans[i] = j+1
					break
			i+=1
		for i in ans:
			stdout.write(str(i))
	else:
		stdout.write('-1\n')
def __starting_point():
	main()
'''
#234B Input and Output
'''
def main():
	from sys import stdin,stdout
	import collections
	with open('input.txt','r') as ip:
		N,K = map(int,ip.readline().split())
		arr = list(map(int,ip.readline().split()))
	mydict = collections.defaultdict(set)
	for i in range(len(arr)):
		mydict[arr[i]].add(i+1)
	ans = []
	i=0
	while K>0:
		for it in mydict[sorted(mydict.keys(),reverse=True)[i]]:
			ans.append(it)
			K-=1
			if K<1:
				break
		minim=i
		i+=1
	with open('output.txt','w') as out:
		out.write(str(sorted(mydict.keys(),reverse=True)[minim])+'\n')
		ans=' '.join(str(x) for x in ans)
		out.write(ans+'\n')		
def __starting_point():
	main()
'''
#151B
'''
def main():
	from sys import stdin,stdout
	import collections
	names = collections.defaultdict(list)
	counter = 0
	order = {}
	for i in range(int(stdin.readline())):
		n,ns = stdin.readline().split()
		names[ns]=[0,0,0]
		order[ns]=counter
		counter+=1
		n=int(n)
		while n:
			ip=stdin.readline().strip()
			ip=ip.replace('-','')
			#test for taxi
			flag=True
			for i in range(1,6):
				if ip[i]!=ip[0]:
					flag=False
					break
			if flag:
				names[ns][0]+=1
				n-=1
				continue
			#test for pizza
			flag = True
			for i in range(1,6):
				if int(ip[i])>=int(ip[i-1]):
					flag =False
					break
			if flag:
				names[ns][1]+=1

			else:
				names[ns][2]+=1
			n-=1
	#print(names)
	#for all girls
	t=-1
	p=-1
	g=-1
	for i in names:
		t=max(t,names[i][0])
		p = max(p, names[i][1])
		g = max(g, names[i][2])

	taxi=list(filter(lambda x: names[x][0]==t, names.keys()))
	pizza = list(filter(lambda x: names[x][1] == p, names.keys()))
	girls = list(filter(lambda x: names[x][2] == g, names.keys()))

	pizza.sort(key= lambda x: order[x])
	taxi.sort(key= lambda x: order[x])	
	girls.sort(key= lambda x: order[x])

	print('If you want to call a taxi, you should call:',', '.join(x for x in taxi),end='.\n')
	print('If you want to order a pizza, you should call:', ', '.join(x for x in pizza),end='.\n')
	print('If you want to go to a cafe with a wonderful girl, you should call:', ', '.join(x for x in girls),end='.\n')

def __starting_point():
	main()
'''
#SQUADRUN Q2
'''
def LCMgen(a):
	import math
	lcm = a[0]
	for i in range(1,len(a)):
		g = math.gcd(lcm,a[i])
		lcm = (lcm*a[i])//g
	return lcm	
	
def main():
	from sys import stdin,stdout
	import collections
	import math
	N,W = map(int,stdin.readline().split())
	counter = collections.Counter(map(int,stdin.readline().split()))
	lcm = LCMgen(list(counter.keys()))
	W*=lcm
	div = 0
	for i in counter:
		div+=counter[i]*(lcm//i)
	ans = math.ceil(W/div)
	stdout.write(str(ans))
def __starting_point():
	main()
'''
#143B
'''
def main():
    from sys import stdin,stdout
    ip = stdin.readline().strip()
    inte = None
    flow = None
    for i,j in enumerate(ip):
        if j=='.':
            flow = ip[i:]
            inte = ip[:i]
            break
    if flow == None:
        flow = '.00'
        inte = ip
    else:
        if len(flow)==2:
            flow+='0'
        else:
            flow = flow[:3]
    ne = False
    if ip[0]=='-':
        ne = True
    if ne:
        inte = inte[1:]
    inte = inte[::-1]
    ans =''
    for i,j in enumerate(inte):
        ans += j
        if i%3 == 2:
            ans+=','
    ans = ans[::-1]
    if ans[0]==',':
        ans = ans[1:]
    ans = '$'+ans
    if ne:
        stdout.write('({})'.format(ans+flow))
    else:
        stdout.write(ans+flow)
def __starting_point():
    main()

'''
#A
'''
def main():
    from sys import stdin,stdout
    n = int(stdin.readline())
    arr = list(map(int,stdin.readline().split()))
    minim = min(arr)
    my_l = []
    for i,j in enumerate(arr):
        if j==minim:
            my_l.append(i)
    my_l_ = []
    for i in range(1,len(my_l)):
        my_l_.append(my_l[i]-my_l[i-1])
    stdout.write(str(min(my_l_)))
def __starting_point():
    main()
'''
#B
'''
def main():
    from sys import stdin,stdout
    n,a,b = map(int,stdin.readline().split())
    maxim = -1
    for i in range(1,n):
        maxim = max(min(a//i,b//(n-i)),maxim)
    stdout.write(str(maxim))
def __starting_point():
    main()
'''
#233B
'''
def main():
    from sys import stdin,stdout
    def foo(x):
        tsum = 0
        c = x
        while c:
            tsum+=(c%10)
            c//=10
        return tsum

    N = int(stdin.readline())
    up,down = 0 , int(1e18)
    flag = False
    while up<down:
        mid = (up+down)//2
        val = foo(mid)
        val = (mid+val)*mid
        if val<N:
            up = mid
        elif val >N:
            down = mid
        else:
            flag=True
            break
        
    if flag:
        stdout.write(str(mid)+'\n')
    else:
        stdout.write('-1')
def __starting_point():
    main()

def main():
    def foo(x):
        n= x
        tsum = 0
        while n:
            tsum += n%10 
            n//=10
        return x*x + tsum*x - int(1e18)
        
    import matplotlib.pyplot as plt
    y = [foo(x) for x in range(1,int(1e18)+1)]
    x = range(1,int(1e18)+1)
    print(y[:100])
    plt.plot(y,x)
    plt.show()
def __starting_point():
    main()
'''
#RECTANGL
'''
def main():
    from sys import stdin,stdout
    import collections
    for _ in range(int(stdin.readline())):
        c = collections.Counter(list(map(int,stdin.readline().split())))
        flag = True
        for i in c:
            if c[i]&1:
                flag=False
        if flag:
            stdout.write('YES\n')
        else:
            stdout.write('NO\n')
def __starting_point():
    main()
'''
#MAXSC
'''
def main():
    from sys import stdin,stdout
    import bisect
    for _ in range(int(stdin.readline())):
        N = int(stdin.readline())
        mat = []
        for i in range(N):
            mat.append(sorted(map(int,stdin.readline().split())))
##        print(mat)
        temp = mat[-1][-1]
        tsum = mat[-1][-1]
        flag = True
        for i in range(N-2,-1,-1):
            ind = bisect.bisect_left(mat[i],temp)-1
            if ind == -1:
                flag = False
                break
            else:
                tsum+=mat[i][ind]
        if flag:
            stdout.write(str(tsum)+'\n')
        else:
            stdout.write('-1\n')
def __starting_point():
    main()
'''
#233B ********************
def main():
    def rev(x):
        tsum = 0
        while x:
            tsum += x%10
            x//=10
        return tsum
    from sys import stdin,stdout
    from math import sqrt,ceil
    n = int(stdin.readline())
    for i in range(91):
        r = i*i+(n<<2)
        x = ceil(sqrt(r))
##        print(i,x)
        if x*x == r:
            num = (x-i)/2
            if num == int(num):
                if rev(num)==i:
                    stdout.write(str(int(num)))
                    return
    stdout.write('-1')
def __starting_point():
    main()

__starting_point()

from math import *

def s(x):
    S = 0
    while x!=0:
        S += x%10
        x//=10
    return(S)

def Solve(n):
    sqrt = n**0.5//1
    x = int((10**(log(sqrt,10)//1)))-1

    if((sqrt - x)*log(sqrt,10) >= 10**4):
        x = int(sqrt-10**4)
    
    while(x <= sqrt):
        if x**2+int(s(x))*x == n:
            return(x)
        x+=1
    return(-1)


def solve(n):
    if(n >= 1024974):
        return(Solve(n))
    if(n == 0):
        return(0)
    sqrt = n**0.5//1
    x = int((10**(log(sqrt,10)//1-1)))
    while(x <= sqrt):
        if x**2+int(s(x))*x == n:
            return(x)
        x+=1
    return(-1)



n = int(input())
print(int(solve(n)))


from math import *

def s(x):
    S = 0
    while x!=0:
        S += x%10
        x//=10
    return(S)

def Solve(n):
    sqrt = n**0.5//1
    x = int((10**(log(sqrt,10)//1)))-1

    if((sqrt - x)*log(sqrt,10) >= 10**4):
        x = int(sqrt-10**4)

    while(x <= sqrt):
        if x**2+int(s(x))*x == n:
            return(x)
        x+=1
    return(-1)


def solve(n):
    if(n >= 1024974):
        return(Solve(n))
    if(n == 0):
        return(0)
    sqrt = n**0.5//1
    x = int((10**(log(sqrt,10)//1-1)))
    while(x <= sqrt):
        if x**2+int(s(x))*x == n:
            return(x)
        x+=1
    return(-1)



n = int(input())
print(int(solve(n)))


import math

def solve(n):
    upper = int(n**0.5)+1
    lower = 10**(math.log10(n**0.5//1)//1)-1
    if n**0.5 - 10**(math.log10(n**0.5//1)//1) >= 10000:
        lower = n**0.5-10000
    for i in range(int(lower),upper):
        if i**2 + s(i)*i == n:
            return(i)
    return(-1)

    
def s(x):
    output = 0
    while x != 0:
        output += x%10
        x //=10
    return output


n = int(input())
print(solve(n))

def sum_of_digits(nr):
    s = 0
    while nr > 0:
        s += nr % 10
        nr //= 10
    return s


def main():
    n = int(input())
    solutions = []
    for s in range(154):
        delta = (s ** 2 + 4 * n) ** 0.5
        x = (-s + delta)/2
        if int(x) != x:
            continue
        x = int(x)
        if sum_of_digits(x) == s and x ** 2 + sum_of_digits(x) * x - n == 0:
            solutions.append(x)
    if solutions:
        print(min(solutions))
    else:
        print(-1)


def __starting_point():
    main()

__starting_point()

def calc_exp(n):
    return n * ( n + sum(map(int,str(n))) )
    
    
def binary_search(n):
    l, r = 0, 1<<61
    while (l <= r):
        mid = l+r >> 1
        if (calc_exp(mid) < n):
            l = mid+1
        else:
            r = mid-1
    return l

def main():
    n = int(input())
    res = binary_search(n)
    for i in range(max(1, res-100), res+100):
        if (calc_exp(i) == n):
            print(i)
            return
    print(-1)

main()


def calc_exp(n):
    return n * ( n + sum(map(int,str(n))) )
    
def binary_search(n):
    l, r = 0, 1<<61
    while (l <= r):
        mid = l+r >> 1
        if (calc_exp(mid) < n):
            l = mid+1
        else:
            r = mid-1
    return l

def main():
    n = int(input())
    res = binary_search(n)
    for i in range(max(1, res-100), res+100):
        if (calc_exp(i) == n):
            print(i)
            return
    print(-1)

main()


import math

def digit_sum(num):
    res = 0
    while num:
        res += num % 10
        num //= 10
    return res

R = lambda: map(int, input().split())
n = int(input())
res = math.inf
for s in range(1, 91):
    l, r = 1, 10**9
    while l < r:
        x = (l + r) // 2
        ne = x * x + s * x
        if ne < n:
            l = x + 1
        elif ne > n:
            r = x - 1
        else:
            l = r = x
            break
    if l * (l + digit_sum(l)) == n:
        res = min(l, res)
print(res if res < math.inf else -1)

import math
c = int(input())
f = False
for b in range(82):
   x = [(-b + math.sqrt(b**2+(4*c)))/2, (-b - math.sqrt(b**2+(4*c)))/2]
   x = max(x)
   
   if int(x)**2 + b*int(x) -c == 0 and int(x) == x :
      y = 0
      for i in str(int(x)):
         y += int(i)
      if b == y :
         print(int(x))
         f = True

if f == False:
   print(-1)

import math
c = int(input())
f = False
for b in range(82):
   x = (-b + math.sqrt(b**2+(4*c)))/2
   
   if int(x)**2 + b*int(x) -c == 0 and int(x) == x :
      y = 0
      for i in str(int(x)):
         y += int(i)
      if b == y :
         print(int(x))
         f = True
         SystemExit()

if f == False:
   print(-1)

def s(x):

    return sum(int(i) for i in str(x))



n = input()

l, n = 9 * len(n), int(n)

ans, m = -1, int(n ** 0.5)

for x in range(max(1, m - l), m + 1):

    if n % x == 0 and x * (x + s(x)) == n:

        ans = x

        break

print(ans)



# Made By Mostafa_Khaled


n = int(input())
flag = 0

for i in range(1,9000*18 + 1):

    if (-i + (i**2 + 4*n)**(1/2))/2 == int((-i + (i**2 + 4*n)**(1/2))/2):
      c = int((-i + (i**2 + 4*n)**(1/2))/2)
      if sum(list(map(int,list(str(c))))) == i:
        if c**2 + c*i - n == 0:
          print(int((-i + (i**2 + 4*n)**(1/2))/2))


          flag = 1
          break
if flag == 0:
    print(-1)