Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

X = int(input())

i = 0

while abs(X-i**5) > abs(X-(i+1)**5):
  i = i + 1
  
A = i
a = i**5
j = 0

while a - j**5 != X:
  if j == 0:
    j += 1
  elif j > 0:
    j = -j
  else:
    j = -j+1
    
print(A, j)

### FIXED CODE ###

X = int(input())

for A in range(-200,200):
  for B in range(-200,200):
    if A**5-B**5 == X:
      print(A,B)
      exit()
### BUGGY CODE ###

import sys

def solve():
    input = sys.stdin.readline
    s = input().strip("\n")
    K = int(input())
    substr = set()
    N = len(s)
    for i in range(N):
        for j in range(i+1, N + 1):
            substr |= {s[i:j]}
    sl = list(substr)
    sl.sort()
    print(sl[K-1])

    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys

def solve():
    input = sys.stdin.readline
    s = input().strip("\n")
    K = int(input())
    substr = set()
    N = len(s)
    for i in range(N):
        for j in range(1, min(6, N - i + 1)):
            substr |= {s[i:i+j]}
    sl = list(substr)
    sl.sort()
    print(sl[K-1])

    return 0

if __name__ == "__main__":
    solve()
### BUGGY CODE ###

a, b, c, d = map(int, input().split())
while d != 0 or a != 0:
  c -= b  # 高橋君の攻撃
  a -= d  # 青木君の攻撃
  if c == 0:
    print("Yes")
    break
  elif a == 0:
    print("No")
    break

### FIXED CODE ###

a, b, c, d = map(int, input().split())
while d != 0 or a != 0:
  c -= b  # 高橋君の攻撃
  a -= d  # 青木君の攻撃
  if c <= 0:
    print("Yes")
    break
  elif a <= 0:
    print("No")
    break
### BUGGY CODE ###

a, b, n = list(map(int, input().split(' ')))

arr = []
for i in range(n):
    x = i + 1
    solve = ((a*x)//b) - a * (x//b)
    arr.append(solve)

print(max(arr))


### FIXED CODE ###

a, b, n = list(map(int, input().split(' ')))
x = 0
# arr = []
# for i in range(n):
#     x = i + 1
#     solve = ((a*x)//b) - a * (x//b)
#     arr.append(solve)

# print(max(arr))

if n < b:
    x = n
elif n > b:
    x = b - 1
else:
    if b > 1:
        x = b - 1
    else:
        1
ans = (a * x) // b

if b == 1:
    ans = 0

print(ans)
### BUGGY CODE ###

N, X, Y= map(int, input().split())
List=[]
for i in range(1,N+1,1):
	for j in range(i,N+1,1):
		saitan = min(abs(i-j), abs(i-X)+abs(Y-j)+1, abs(i-Y)+abs(X-j)+1)
		List.append(saitan)

for i in range(1,N):
    	print(List.count(i))

### FIXED CODE ###

N, X, Y= map(int, input().split())
List=N*[0]

for i in range(1,N+1,1):
	for j in range(i,N+1,1):
		saitan = min(abs(i-j), abs(i-X)+abs(Y-j)+1, abs(i-Y)+abs(X-j)+1)
		List[saitan] += 1


for i in range(1,N):
    	print(List[i])
### BUGGY CODE ###

def main():
  import sys
  input = sys.stdin.readline
  h, w = map(int, input().split())
  A = []
  AB = []
  for i in range(h):
    row = list(map(int, input().split()))
    A.append(row)
  for i in range(h):
    row = [abs(A[i][j] - int(b)) for j, b in enumerate(input().split())]
    AB.append(row)
 
  dp = [[{} for j in range(w+1)] for i in range(h+1)]
  dp[0][0][AB[0][0]] = 1
  for i in range(h):
    for j in range(w):
      dif1 = 0
      dif2 = 0
      if j < w - 1:
        dif1 = AB[i][j+1]
      if i < h - 1:
        dif2 = AB[i+1][j]
      for item in dp[i][j]:
        if j < w - 1:
          dp[i][j+1][item+dif1] = 1
          dp[i][j+1][abs(item-dif1)] = 1
        if i < h - 1:
          dp[i+1][j][item+dif2] = 1
          dp[i+1][j][abs(item-dif2)] = 1
  print(min(dp[h-1][w-1].keys()))
if __name__ == '__main__':
  main()


### FIXED CODE ###

import sys
def main():
  input = sys.stdin.readline
  h, w = map(int, input().split())
  A = []
  AB = []
  A_append = A.append
  AB_append = AB.append
  for i in range(h):
    row = list(map(int, input().split()))
    A_append(row)
  for i in range(h):
    row = [abs(A[i][j] - int(b)) for j, b in enumerate(input().split())]
    AB_append(row)
 
  dp_cur = [set([]) for _ in range(w)]
  dp_cur[0].add(AB[0][0])
  for i in range(h):
    dp_next = [set([]) for _ in range(w)]
    for j in range(w):
      if j < w - 1:
        add1 = dp_cur[j+1].add
        dif1 = AB[i][j+1]
      if i < h - 1:
        add2 = dp_next[j].add
        dif2 = AB[i+1][j]
      for item in dp_cur[j]:
        if j < w - 1:
          add1(item+dif1)
          add1(abs(item-dif1))
        if i < h - 1:
          add2(item+dif2)
          add2(abs(item-dif2))
    if i == h - 1:
      break
    dp_cur = dp_next
  print(min(dp_cur[w-1]))
if __name__ == '__main__':
  main()
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))

import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans

def erast(n):
  num_set=set()
  prime_set=set()
  for i in range(2,n+1):
    if i not in num_set:
      prime_set.add(i)
      for j in range(i*i,n+1,i):
        num_set.add(j)
  s=list(prime_set)
  return s

check=set()

if setwise_coprime(a)==1:
  s=erast(1000000)
  s.sort()
  for i in range(n):
    if a[i]!=1:
      for j in range(len(s)):
        if s[j]>a[i]:
          break
        if a[i]%s[j]==0:
          if s[j] in check:
            print("setwise coprime")
            sys.exit()
          else:
            check.add(s[j])
            
  print("pairwise coprime")    
else:
  print("not coprime")
  
  



      
      
    


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))

import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans

#エラストテネスのふるい
def create_sieve(n):
  sieve=[0]*(n+1)
  for i in range(2,n+1):
    if sieve[i]==0:
      for j in range(i*i,n+1,i):
        sieve[j]=i
  return sieve

#高速素因数分解
def fast_factorization(n, sieve):
  prime={}
  while n>1:
    p=sieve[n]
    #nが素数の場合
    if p==0:
      prime[n]=prime.get(n,0)+1
      break
    #nが素数ではない場合
    else:
      prime[p]=prime.get(p,0)+1
      n=n//p
  return prime

check=set()
if setwise_coprime(a)==1:
  #素因数のダブリをcheck
  sieve=create_sieve(10**6)
  for i in range(n):
    if a[i]!=1:
      s=fast_factorization(a[i], sieve)
      for i in s:
        if i in check:
          print("setwise coprime")
          sys.exit()
        else:
          check.add(i)
  print("pairwise coprime")    
else:
  print("not coprime")
### BUGGY CODE ###

from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
NX = [1, 0, -1, 0]
NY = [0, 1, 0, -1]
PX = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2]
PY = [-2, -1, 0, 1, 2, -2, -1, 1, 2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for i in range(4):
        nx = x + NX[i]
        ny = y + NY[i]
        if 0 <= nx < w and 0 <= ny < h and S[ny][nx] != "#":
            if grid[ny][nx] == -1 or grid[ny][nx] > count:
                grid[ny][nx] = count
                que.appendleft((count, ny, nx))
    for i in range(20):
        px = x + PX[i]
        py = y + PY[i]
        if 0 <= px < w and 0 <= py < h and S[py][px] != "#":
            if grid[py][px] == -1:
                grid[py][px] = count + 1
            que.append((count + 1, py, px))

print(grid[dh][dw])


### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [list(input()) for _ in range(h)]

Ch, Cw = Ch - 1, Cw - 1
Dh, Dw = Dh - 1, Dw - 1
d = [[-1] * w for _ in range(h)]
d[Ch][Cw] = 0
walk = [[0, 1], [0, -1], [1, 0], [-1, 0]]
warp = [[2, 2], [2, 1], [2, 0], [2, -1], [2, -2], [1, 2], [1, 1], [1, -1], [1, -2], [0, 2], [0, -2], [-1, 2], [-1, 1],
        [-1, -1], [-1, -2], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -2]]

que = deque([[0, Ch, Cw]])
while que:
    count, y, x = que.popleft()
    if d[y][x] < count:
        continue
    for NY, NX in walk:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count:
                d[y + NY][x + NX] = count
                que.appendleft([count, y + NY, x + NX])
    for NY, NX in warp:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count + 1:
                d[y + NY][x + NX] = count + 1
                que.append([count + 1, y + NY, x + NX])

print(d[Dh][Dw])
### BUGGY CODE ###

import numpy as np

n, K = map(int, input().split())
h = np.array(list(map(int,input().split())))

cost_dp = np.array([float('inf')]*n)
cost_dp[0] = 0

for i in range(1,n):
    k = min(i,K)
    cost_dp[i] = np.min((cost_dp+np.absolute(h-h[i]))[i-k:i])

print(int(cost_dp[-1]))

### FIXED CODE ###

import numpy as np

n, K = map(int, input().split())
h = np.array(list(map(int,input().split())))

cost_dp = np.array([100000000]*n)
cost_dp[0] = 0

for i in range(1,n):
    k = min(i,K)
    cost_dp[i] = np.min(cost_dp[i-k:i]+np.absolute(h[i-k:i]-h[i]))

print(int(cost_dp[-1]))
### BUGGY CODE ###

import sys
f = sys.stdin

while True:
    n, m = map(int, f.readline().split())
    if n == 0:
        break
    abct = [list(map(int, f.readline().split())) for _ in range(n)]
    dist = [[(float('inf'),float('inf'))  for j in range(m)] for i in range(m)]    
    for ai, bi, cost, time in abct:
        dist[ai - 1][bi - 1] = (cost, time)
    for k in range(m):
        for i in range(m):
            for j in range(m):
                if dist[i][j][0] > dist[i][k][0] + dist[k][j][0]:
                    dist[i][j] = (dist[i][k][0] + dist[k][j][0], dist[i][j][1])
                if dist[i][j][1] > dist[i][k][1] + dist[k][j][1]:
                    dist[i][j] = (dist[i][j][0], dist[i][k][1] + dist[k][j][1])
        
    k = int(f.readline())
    for i in range(k):
        p, q, r = map(int, f.readline().split())
        print(dist[p - 1][q - 1][r])

### FIXED CODE ###

import heapq
import sys
from collections import defaultdict

def dijkstra(graph, size, start):
    d = [float('inf')] * size
    d[start] = 0
    q = [(0, start)]
    while len(q):
        du, u = heapq.heappop(q)
        for length, v in graph[u]:
            if d[v] > du + length:
                d[v] = du + length
                heapq.heappush(q, (d[v], v))
    return d

f = sys.stdin

while True:
    n, m = map(int, f.readline().split())
    if n == 0:
        break
    abct = [map(int, f.readline().split()) for _ in range(n)]
    d = [defaultdict(list), defaultdict(list)]
    
    for ai, bi, ci, ti in abct:
        ai -= 1
        bi -= 1
        d[0][ai].append((ci, bi))
        d[0][bi].append((ci, ai))
        d[1][ai].append((ti, bi))
        d[1][bi].append((ti, ai))
    
    dist = {}
    for i in range(int(f.readline())):
        p, q, r = map(int, f.readline().split())
        p -= 1
        q -= 1
        try:
            print(dist[(q,r)][p])
        except KeyError:
            try:
                print(dist[(p,r)][q])
            except:
                dist[(p,r)] = dijkstra(d[r], m, p)
                print(dist[(p,r)][q])
### BUGGY CODE ###

from operator import itemgetter

N, M = map(int, input().split())
pairs = [tuple(map(int, input().split())) for _ in range(N)]
pairs.sort(key = itemgetter(1), reverse = True)

A_max = M + 1
schedule = [0] * (M+1)
for A, B in pairs:
    if A_max == 1:
        break
    elif A < A_max:
        for i in range(A, A_max):
            if schedule[i] == 0:
                schedule[i] = B
                break
        else:
            A_max = A
    


print(sum(schedule))            


### FIXED CODE ###

from operator import itemgetter
import heapq

N, M = map(int, input().split())
pairs = [tuple(map(int, input().split())) for _ in range(N)]
pairs.sort(key = itemgetter(0))

heap = []
reward = 0
index_of_pairs = 0   
for i in range(1, M+1):
    while index_of_pairs < N and pairs[index_of_pairs][0] <= i:
        heapq.heappush(heap, -pairs[index_of_pairs][1])
        index_of_pairs += 1
    if heap:
        reward -= heapq.heappop(heap)

print(reward)
### BUGGY CODE ###

from collections import deque
from itertools import product

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x)-1, input().split()))
d = tuple(map(lambda x: int(x)-1, input().split()))
s = list(input() for _ in range(h))

move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
move_b_area = [(i, j) for i, j in product(range(-2, 3), repeat=2) if (i, j) not in [(0, 0)] + move_a_area]

cost = [[float('inf')] * w for _ in range(h)]
cost[c[0]][c[1]] = 0
que = deque([(c[0], c[1], 0)])

while que:
    y, x, m = que.popleft()
    # Move A
    for dx, dy in move_a_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '#' or cost[hh][ww] <= m:
            continue
        cost[hh][ww] = m
        que.append((hh, ww, m))
    # Move B
    for dx, dy in move_b_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '#' or cost[hh][ww] <= m + 1:
            continue
        cost[hh][ww] = m + 1
        que.append((hh, ww, m + 1))

print(cost[d[0]][d[1]] if cost[d[0]][d[1]] < float('inf') else -1)


### FIXED CODE ###

from collections import deque
from itertools import product

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x)-1, input().split()))
d = tuple(map(lambda x: int(x)-1, input().split()))
s = list(input() for _ in range(h))

move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
move_b_area = [(i, j) for i, j in product(range(-2, 3), repeat=2) if (i, j) not in [(0, 0)] + move_a_area]

cost = [[float('inf')] * w for _ in range(h)]
cost[c[0]][c[1]] = 0
que = deque([(c[0], c[1], 0)])

while que:
    y, x, m = que.popleft()
    # Move A
    for dx, dy in move_a_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '#' or cost[hh][ww] <= m:
            continue
        cost[hh][ww] = m
        que.appendleft((hh, ww, m))
    # Move B
    for dx, dy in move_b_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '#' or cost[hh][ww] <= m + 1:
            continue
        cost[hh][ww] = m + 1
        que.append((hh, ww, m + 1))

print(cost[d[0]][d[1]] if cost[d[0]][d[1]] < float('inf') else -1)
### BUGGY CODE ###

import math
n, k = map(int, input().split())
a = list(map(int, input().split()))
f = list(map(int, input().split()))

a = sorted(a)
f = sorted(f,reverse = True)

hq = []

upper_limit = int(1e+12)
lower_limit = int(0)

def is_ok(checking):
    cost = 0
    for i in range(n):
        cost += max(0,math.ceil((a[i]*f[i]-checking)/f[i]))
    if cost <= k:
        return True
    else:
        return False

def meguru_bisect(ng, ok):
    while (abs(ok-ng)>1):
        mid = (ok+ng)//2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

ok = meguru_bisect(-1, 1e+100) 
print(int(ok))
# 初期値の範囲は取りえる値-1～+1とする←範囲内はok,ngどちらもあり得るため

### FIXED CODE ###

import math
n, k = map(int, input().split())
a = list(map(int, input().split()))
f = list(map(int, input().split()))

a = sorted(a)
f = sorted(f,reverse = True)

hq = []

def is_ok(checking):
    cost = 0
    for i in range(n):
        cost += max(0,math.ceil((a[i]*f[i]-checking)/f[i]))
    if cost <= k:
        return True
    else:
        return False

def meguru_bisect(ng, ok):
    while (abs(ok-ng)>1):
        mid = (ok+ng)//2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

ok = meguru_bisect(-1, 1e+12+1) 
print(int(ok))
# 初期値の範囲は取りえる値-1～+1とする←範囲内はok,ngどちらもあり得るため
### BUGGY CODE ###

n = int(input())
ans=0
for i in range(n):
    ans += i
print(ans)

### FIXED CODE ###

n = int(input())

if (n-1)%2 == 0:
    print((n*(n-1)//2))
else:
    print(n*(n-2)//2 + n//2)
### BUGGY CODE ###

from collections import deque

n, m = map(int, input().split())
a_list = list(map(int, input().split()))
m_list = []
for _ in range(m):
    b, c = map(int, input().split())
    m_list += [c]*b
a_list.sort()
m_list.sort(reverse=True)
m_q = deque(m_list)
ans = 0
check = m_q.popleft()
for a in a_list:
    if a < check:
        ans += check
        if len(m_q) > 0:
            check = m_q.popleft()
        else:
            check = 0
    else:
        ans += a
print(ans)


### FIXED CODE ###

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
a_list = list(map(int, input().split()))
m_list = []
for _ in range(m):
    b, c = map(int, input().split())
    m_list.append([c, b])
m_list.sort(reverse=True)
cnt = 0
tmp_list = []
for c, b in m_list:
    if cnt < n:
        tmp_list += [c]*b
    else:
        break
    cnt += b
a_list.extend(tmp_list)
a_list.sort(reverse=True)
print(sum(a_list[:n]))
### BUGGY CODE ###

class unionfind:
	def __init__(self, n):
		self.parent = list(range(n))
	def find(self, i):
		if self.parent[i] != i: self.parent[i] = self.find(self.parent[i])
		return self.parent[i]
	def unite(self, i, j):
		i = self.find(i)
		j = self.find(j)
		if i != j: self.parent[i] = j
	def issame(self, i, j):
		return self.find(i) == self.find(j)
	def groups(self):
		r = range(len(self.parent))
		return [[j for j in r if self.issame(j, i)] for i in r if i == self.parent[i]]
	@staticmethod
	def isconnected(l, u = None):
		nw, nh = len(l), len(l[0])
		rw, rh = range(nw), range(nh)
		if not u: u = unionfind(nw * nh)
		f = -1
		for i in rw:
			for j in rh:
				if not l[i][j]: continue
				if f < 0: f = i + j * nw
				if j > 0 and l[i][j] == l[i][j - 1]: u.unite(i + j * nw, i + j * nw - nw)
				if i > 0 and l[i][j] == l[i - 1][j]: u.unite(i + j * nw, i + j * nw - 1)
		return f >= 0 and all([u.issame(f, i + j * nw) for i in rw for j in rh if l[i][j]])
	@staticmethod
	def isconnectedlist(nw, nh, lst):
		l = [[False] * nw for j in range(nh)]
		for i, j in lst: l[i][j] = True
		return unionfind.isconnected(l)

def culc(x):
    return int(x * (x-1) //2)

N , M = map(int, input().split())
ans_lst = []
lst = []
for i in range(M):
    A , B = map( int , input().split())
    lst.append([A , B] )
cu = unionfind(N)
maxroute = culc(N)
temp = maxroute
for ls  in  reversed(lst):
    if temp == 0 :
        ans_lst.append(temp)
        continue
    temp = maxroute
    for subg in cu.groups():
        temp -= culc(len(subg))
    ans_lst.append(temp)
    cu.unite(ls[0]-1 , ls[1]-1)

for y in reversed(ans_lst):
    print(y)

### FIXED CODE ###

#学習用
def root(x):
    # xが根であれば
    if x == p[x]:
        # xを返す
        return x
    # xが根でなければp[x]の根をp[x]に設定する
    p[x] = y = root(p[x])
    # p[x]の根を返却する
    return y
def unite(x, y):
    # xとyの根を取得する
    px = root(x); py = root(y)
    # xとyの根が同じならば
    if px == py:
        # 根が同じならば、0を返す
        return 0
    # yの根がxの根より大きければ、
    if px < py:
        # yの根の位置のp[]を、xの根にする
        p[py] = px
        # xの根の位置のサイズszを、yの根の位置のサイズだけ加算する
        sz[px] += sz[py]
    else:
    # yの根がxの根より小さければ
        # xの根の位置のp[]を、yの根を指すようにする
        p[px] = py
        sz[py] += sz[px]
    # 根が異なっていた＝結合した場合は、1を返却する
    return 1

N , M = map(int, input().split())
*p , = range(N)
sz = [1] * N
E = []
for i in range(M):
    a , b = map(int, input().split())
    E.append((a-1, b-1))

ans = [None] * M
E.reverse()
res = 0
ans[-1] = "%d\n" % (N*(N-1)//2)

for i , (a,b) in enumerate(E[:-1]):
    sa = sz[root(a)]; sb = sz[root(b)]
    if unite(a , b):
        sc = sz[root(a)]
        res += sc*(sc-1)//2 - sa*(sa-1)//2 - sb*(sb-1)//2
    ans[-2-i] = "%d\n" % (N*(N-1)//2 -res)
open(1, 'w').writelines(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))

for i in range(0,M):
    b,c = map(int,input().split())
    for j in range(0,b):
        A.append(c)

A.sort()
A.reverse()

result = 0
for k in range(0,N):
    result += A[k]
print(result)


### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
cards = []
for i in range(0,N):
    cards.append((A[i],1))

for i in range(0,M):
    b,c = map(int,input().split())
    cards.append((c,b))

cards.sort()
cards.reverse()

result = 0
total = N
for num, cnt in cards:
    total -= cnt
    result += num*cnt
    if total < 0:
        result += num * total
        break
print(result)
### BUGGY CODE ###




N,M = map(int, input().split())
ab = []
c = []
for _ in range(M):
    a,b = map(int, input().split())
    ab.append((a,b))
    tmp = tuple(map(int, input().split()))
    bit_c = 0
    # c[i]で開けられる宝箱はbitの１が立っている部分
    for i in tmp:
        bit_c = bit_c | (1 << (i - 1))

    c.append(bit_c)

INF = 10**9
# m番目の鍵をつかって、開けた宝箱がbitの状態になったときの、最小コスト
dp = [INF] * (1 << N)
dp[0] = 0


for bit in range(1 << N):
    for i in range(M):
        dp[bit | c[i]] = min(dp[bit | c[i]], dp[bit] + ab[i][0])

print(dp[-1] if dp[-1] < INF else -1)

### FIXED CODE ###




N,M = map(int, input().split())
ab = []
c = []
for _ in range(M):
    a,b = map(int, input().split())
    ab.append((a,b))
    tmp = tuple(map(int, input().split()))
    bit_c = 0
    # c[i]で開けられる宝箱はbitの１が立っている部分
    for i in tmp:
        bit_c = bit_c | (1 << (i - 1))

    c.append(bit_c)

INF = 10**9
# m番目の鍵をつかって、開けた宝箱がbitの状態になったときの、最小コスト
dp = [INF] * (1 << N)
dp[0] = 0


for bit in range(1 << N):
    for i in range(M):
        dp[bit | c[i]] = min(dp[bit | c[i]], dp[bit] + ab[i][0])

print(dp[-1] if dp[-1] < INF else -1)
### BUGGY CODE ###

N = int(input())

def f(n):
    ans = 0
    for x in range(1, n+1):
        for y in range(1, n-x):
            c = (x**2) + (y**2) + (x*y)
            a = n - c
            for z in range(1, a+1):
                if n == c + (x*z) + (y*z) + (z**2):
                    ans += 1
                    break
    return ans

for i in range(1, N+1):
    print(f(i))


### FIXED CODE ###

N = int(input())

ans = [0] * (N+1)
for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            n = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if n < (N+1):
                ans[n] += 1

for i in range(1, N+1):
    print(ans[i])