n = read_line.to_i64 e = read_line.to_i if e == 0 puts 0 exit end if n < 0 n %= 5 ** e n += 5 ** e end ab = n.abs a = Array.new(e + 1) do v = ab % 5 ab //= 5 n < 0 ? (5 - v) % 5 : v end if a[0] == 2 || a[0] == 3 puts "NaN" exit end if a[0] == 0 q = [[0, 0]] elsif a[0] == 1 q = [[1, 0], [4, 3]] else q = [[2, 0], [3, 1]] end 1.upto(e) do |i| nq = [] of Array(Int32) q.each do |cand| sum = cand[i] 1.upto(i - 1) do |j| sum += cand[j] * cand[i - j] end 5.times do |j| if (j * cand[0] * 2 + sum) % 5 == a[i] carry = (j * cand[0] * 2 + sum) // 5 nc = cand.dup nc[i] = j nc << carry nq << nc end end end if nq.empty? puts "NaN" exit end q = nq end ans = 0i64 base = 1i64 (e + 1).times do |i| ans += base * q[0][i] base *= 5 end while ans > 1 << 29 ans -= 5 ** 13 end v = ans * ans - n c = 0 while v != 0 && v % 5 == 0 v //= 5 c += 1 end if v != 0 && c < e puts q.size puts q[0] puts ans puts c puts "invalid" while true end end puts ans