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

X=int(input())
i=0
while True:
    x1=(X+i**5)**(1/5)
    x2=(X-i**5)**(1/5)
    if x1==int(x1):
        print(int(x1),i)
        exit()
    elif isinstance(x2,complex):
        i=i
    elif x2==int(x2):
        print(int(x2),-i)
        exit()
    i+=1

### FIXED CODE ###

X=int(input())
J=1000
N=[0]*J
for i in range(0,J):
    N[i]=i**5
for i in range(0,J):
    for j in range(0,J):
        if abs(N[i]-N[j])==X:
            print(int(max(N[i],N[j])**(1/5)),int(min(N[i],N[j])**(1/5)))
            exit()
        elif N[i]+N[j]==X:
            print(int(N[i]**(1/5)),int(-1*N[j]**(1/5)))
            exit()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
# import random

# N = 10**5
# A = [random.randrange(1,10**9+1) for _ in range(N)]

# import time

def main():
    l = 0
    r = N
    while r-l > 1:
        m = (r+l)//2
        ok = True
        if m == 1:
            pre = -1
            for a in A:
                if pre >= a:
                    ok = False
                    break
                pre = a
        else:
            dp = {}
            needreset = 10**15
            exception = set()
            pre = -1
            for a in A:
                ind = a
                for _ in range(40):
                    # 修正
                    if needreset >= ind or ind in exception:
                        if not ind in dp.keys():
                            dp[ind] = 0 if pre < a else 1
                    else:
                        dp[ind] = 0 if pre < a else 1
                        exception.add(ind)
                    # たす
                    if dp[ind] < m:
                        dp[ind] += 1
                        break
                    elif ind == 1:
                        ok = False
                        break
                    else:
                        # 繰り上がり
                        dp[ind] = 1
                        ind -= 1
                if not ok: break
                # 更新
                if pre > a:
                    needreset = a
                    exception = set()
                pre = a

        if ok:
            r = m
        else:
            l = m

    print(r)


if __name__ == "__main__":
    #dt = time.time()
    main()
    #print(time.time()-dt)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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


def check(m):
    if m == 1:
        pre = -1
        for a in A:
            if pre >= a:
                return False
            pre = a
    else:
        dp = {}
        pre = 0
        #count = 0
        for a in A:
            if pre < a:
                pre = a
                continue
            todelete = []
            for b in dp.keys():
                if b > a:
                    todelete.append(b)
            ind = a
            while ind > 0:
                if ind in dp and dp[ind] >= m-1:
                    todelete.append(ind)
                else:
                    break
                ind -= 1
            # 更新
            if ind in dp:
                dp[ind] += 1
            else:
                dp[ind] = 1
            if ind == 0 or dp[ind] >= m:
                return False
            for d in todelete:
                del dp[d]
            pre = a
    #print(m, count)
    return True



def main():
    l = 0
    r = N
    while r-l > 1:
        m = (r+l)//2
        if check(m):
            r = m
        else:
            l = m
    print(r)


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

N, W = list(map(int, input().split()))
w, v = [None] * N, [None] * N
for i in range(N):
    w[i], v[i] = list(map(int, input().split()))


dp = [[0] * (W + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    for j in range(W + 1):
        if w[i - 1] <= j:
            dp[i][j] = max(dp[i - 1][j], v[i - 1] + dp[i - 1][j - w[i - 1]])
        else:
            dp[i][j] = dp[i - 1][j]

ans = max(dp[N])
print(ans)
        

### FIXED CODE ###

N, W = list(map(int, input().split()))
w, v = [None] * N, [None] * N
for i in range(N):
    w[i], v[i] = list(map(int, input().split()))


dp = [[0] * (W + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    for j in range(W + 1):
        if w[i - 1] <= j:
            dp[i][j] = max(dp[i - 1][j], v[i - 1] + dp[i - 1][j - w[i - 1]])
        else:
            dp[i][j] = dp[i - 1][j]

ans = max(dp[N])
print(ans)
### BUGGY CODE ###

import collections
N = int(input())
stock = list()
ans = 0
for i in range(N):
    s = list(input())
    c  = collections.Counter(s)
    for sto in stock:
        #print(sto)
        #print(c)
        #print(sto == c)
        if c == sto:
            ans +=1
    
    stock.append(collections.Counter(s))
print(ans)

### FIXED CODE ###

import collections
N = int(input())
stock = dict()
ans = 0
for i in range(N):
    c="".join(sorted(input()))
    if c in stock:
        ans += stock[c]
        stock[c] += 1
    else:
        stock[c] = 1
print(ans)
### BUGGY CODE ###

"""
dp[i][j][k] = 寿司が1個、2個、3個残っている皿の数がそれぞれi皿、j皿、k皿であるような状態に
なるまでに必要な操作回数の期待値
dp[c_1][c_2][c_3] = 0として、dp[0][0][0]が答え
"""

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
A = tuple(map(int, input().split()))
C = [0]*3
for a in A:
  C[a-1] += 1
dp = [[[-1]*(n+1) for i in range(n+1)] for j in range(n+1)]
dp[0][0][0] = 0
def f(i, j, k):
  if dp[i][j][k] != -1:
    return dp[i][j][k]
  res = 1
  if i:
    res += f(i-1, j, k)*(i/n)
  if j:
    res += f(i+1, j-1, k)*(j/n)
  if k:
    res += f(i, j+1, k-1)*(k/n)
  res /= (i+j+k)/n
  dp[i][j][k] = res
  return res
ans = f(C[0], C[1], C[2])
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
A = tuple(map(int, input().split()))
C = [0]*3
for a in A:
  C[a-1] += 1
dp = [[[-1]*(n+1) for i in range(n+1)] for j in range(n+1)]
dp[0][0][0] = 0
def f(i, j, k):
  if dp[i][j][k] != -1:
    return dp[i][j][k]
  res = 1
  if i:
    res += f(i-1, j, k)*(i/n)
  if j:
    res += f(i+1, j-1, k)*(j/n)
  if k:
    res += f(i, j+1, k-1)*(k/n)
  res /= (i+j+k)/n
  dp[i][j][k] = res
  return res
ans = f(C[0], C[1], C[2])
print(ans)
### BUGGY CODE ###

N,Q = map(int, input().split())
S = input()
T = []
D = []

ord_A = ord('A')

for i in range(Q):
  t,d = input().split()
  #T.append(ord(t) - ord_A)
  T.append(t)
  D.append(d)

#P = [[] for _ in range(ord('Z') - ord('A') + 1)]
#for i in range(N):
#  p = ord(S[i]) - ord_A
#  P[p].append(i)

G = []
for i in range(Q-1,-1,-1):
  t = T[i]
  d = D[i]
  
  
  for g in G:
    #print(g[0], g[1])
    if ('L' == d):
      tmp = g[0]+1
      if (tmp < N):
        if (t == S[tmp]):
        	G.append((tmp, S[tmp]))
    elif ('R' == d):
      tmp = g[0]-1
      if (0 < tmp):
        if (t == S[tmp]):
        	G.append((tmp, S[tmp]))
  
  if ('L' == d):
    if (t == S[0]):
      G.append((0, S[0]))
  elif ('R' == d):
    if (t == S[N-1]):
      G.append((N-1, S[N-1]))
  #print(G)
  G = list(set(G))
  

print(N - len(G))


### FIXED CODE ###

N,Q = map(int, input().split())
S = input()
C = [tuple(map(str, input().split())) for _ in range(Q)]
C = C[::-1]

left = -1
right = N

for (t,d) in C:
  if ('L' == d):
    if (S[left+1] == t):
      left += 1
      if (N-1 <= left):
        print(0)
        exit()
    if (right < N):
      if (S[right] == t):
        right += 1
        if (N < right):
          right = N
  else:
    if (S[right-1] == t):
      right -= 1
      if (right <= 0):
        print(0)
        exit()
    if (-1 < left):
      if (S[left] == t):
        left -= 1
        if (left < -1):
          left = -1

print(right - left - 1)
### BUGGY CODE ###

import numpy as np
from numba import jit

N = int(input())
A = np.asarray(list(map(int, input().split())))
Q = int(input())
B, C = np.zeros(Q, dtype=np.int64), np.zeros(Q, dtype=np.int64)
for i in range(Q):
    [b, c] = list(map(int, input().split()))
    B[i], C[i] = b, c
    
@jit(nopython=True)
def calc(A, B, C, Q):
    for i in range(Q):
        A = np.where(A==B[i], C[i], A)
        print(np.sum(A))

calc(A, B, C, Q)


### FIXED CODE ###

import array

N = int(input())
A = array.array('L', list(map(int, input().split())))
MAX = 10**5+1
X = array.array('L', [0]) * MAX
Y = array.array('L', range(MAX))

for i in range(len(A)): X[A[i]] += 1
    
Q = int(input())
cur = sum(array.array('L', (X[i]*Y[i] for i in range(len(X)))))

for i in range(Q):
    [b, c] = list(map(int, input().split()))
    cur = cur - X[b]*b + X[b]*c
    print(cur)
    X[c] += X[b]
    X[b] = 0
### BUGGY CODE ###

n = int(input())
num = list(map(int,input().split()))
for i in range(1,n+1):
    print(num.index(i) + 1, end=" ")


### FIXED CODE ###

n = int(input())
num_list = list(map(int,input().split()))
num_array = [0]*n
for i in range(n):
    num_array[num_list[i]-1] = i+1
for i in range(n):
    print(num_array[i])
### BUGGY CODE ###

import collections
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))

A_keys = collections.Counter(A)
keys_list= A_keys.keys()
for k in range(N):
    Ak = A[k]
    result = 0
    for i in keys_list:
        cnt = A_keys[i]
        if i == A[k] and cnt >= 2:
            result += (cnt-1)*(cnt-2)/2
        elif i != A[k] and cnt >= 2:
            result += cnt*(cnt-1)/2
    print(int(result))

### FIXED CODE ###

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

A_keys = collections.Counter(A)
keys_list= A_keys.keys()

combi_sum = {}
for i in keys_list:
    cnt = A_keys[i]
    combi_sum[i] = cnt * (cnt-1)//2 

v_sum = sum(combi_sum.values())
for k in range(N):
    Ak = A[k]
    k_cnt = A_keys[Ak] - 1
    result = v_sum - combi_sum[Ak] + k_cnt*(k_cnt -1)//2
    print(int(result))
### BUGGY CODE ###

def main() :
    n = int(input())
    nums = []
    for i in range(n) :
        x = int(input())
        nums.append(x)

    max = float("-inf")
    for i in range(n) :
        for j in range(i):
            if (nums[i] - nums[j]) > max :
                max = nums[i] - nums[j]

    print(max)



if __name__ == '__main__' :
    main()

### FIXED CODE ###

def main() :
    n = int(input())
    nums = []
    for i in range(n) :
        x = int(input())
        nums.append(x)

    max = float("-inf")
    min = nums[0]
    for i in range(1,n) :
        if nums[i] - min > max :
            max = nums[i] - min

        if nums[i] < min :
            min = nums[i]

    print(max)



if __name__ == '__main__' :
    main()
### BUGGY CODE ###

import numpy as np

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(m)]

a = np.array(a)

for b, c in bc:
    a.sort()
    c_under_cnt = a[a<c].size

    idx = b if b<c_under_cnt else c_under_cnt
    a[0:idx] = [c] * idx

print(a.sum(dtype="int64"))


### FIXED CODE ###

n, m = map(int, input().split())
*a, = map(int, input().split())
bc = [list(map(int, input().split())) for _ in range(m)]

a.sort()
bc.sort(key=lambda x:-x[1])
i = 0

for b,c in bc:
    for j in range(i, min(n, i+b)):
        if a[j]<c:
            a[j] = c
    i = i+b
print(sum(a))
### BUGGY CODE ###

import numpy as np
H,W=map(int,input().split())
S=[]
for i in range(H):
    s=input()
    s1=[]
    for j in range(len(s)):
        if s[j]=='.':
            s1+=[1]
        else:
            s1+=[0]
    S+=[s1]
S=np.array(S)
T1=[]
for i in range(S.shape[0]):
    s=S[i]
    t2=s[0]
    if t2==1:
        t1=1
    else:
        t1=0
    t=[]
    k=0
    for j in range(1,len(s)):
        if s[j]==t2:
            if t2==1:
                t1+=1
        else:
            t2=s[j]
            t+=[t1]*(j-k)
            k=j
            if t2==1:
                t1=1
            else:
                t1=0
    else:
        t+=[t1]*(len(s)-k)
    T1+=[t]
T1=np.array(T1)


T2=[]
for i in range(S.T.shape[0]):
    s=S.T[i]
    t2=s[0]
    if t2==1:
        t1=1
    else:
        t1=0
    t=[]
    k=0
    for j in range(1,len(s)):
        if s[j]==t2:
            if t2==1:
                t1+=1
        else:
            t2=s[j]
            t+=[t1]*(j-k)
            k=j
            if t2==1:
                t1=1
            else:
                t1=0
    else:
        t+=[t1]*(len(s)-k)
    T2+=[t]
T2=np.array(T2).T
print(np.max(T1+T2)-1)

### FIXED CODE ###

import numpy as np
H,W=map(int,input().split())
S=[]
for i in range(H):
    s=input()
    s1=[]
    for j in range(W):
        if s[j]=='.':
            s1+=[1]
        else:
            s1+=[0]
    S+=[s1]
S=np.array(S)

Tl=np.zeros((H,W),dtype=np.int)
Tr=np.zeros((H,W),dtype=np.int)

Tu=np.zeros((H,W),dtype=np.int)
Td=np.zeros((H,W),dtype=np.int)
for i in range(1,W):
    Tl[:,i]+=(Tl[:,i-1]+1)*S[:,i-1]

for i in range(W-2,-1,-1):
    Tr[:,i]+=(Tr[:,i+1]+1)*S[:,i+1]

for i in range(1,H):
    Tu[i,:]+=(Tu[i-1,:]+1)*S[i-1,:]

for i in range(H-2,-1,-1):
    Td[i,:]+=(Td[i+1,:]+1)*S[i+1,:]

print(((Tl+Tr+Tu+Td)*S).max()+1)
### BUGGY CODE ###

N,M=map(int,input().split())
A=[int(x) for x in input().split()]
for i in range(M):
  for j in range(N):
    if A[j]==max(A):
      A[j]=A[j]/2
      break
for i in range(N):
  A[i]=int(A[i])
print(sum(A))

### FIXED CODE ###

import heapq
N,M =map(int,input().split())
A=[-int(x) for x in input().split()]#大きい順で扱う為にマイナスを付ける

heapq.heapify(A)#Aを優先度付キューへ変換

for i in range(M):
  saitakane = heapq.heappop(A)#最高値を取り出す
  heapq.heappush(A,-(-saitakane//2))#切り捨ての為に正の数にしてから半分にして戻す（追加）
print(-sum(A))
### BUGGY CODE ###

from operator import mul
from functools import reduce

def cmb(n, r):
    r = min(n - r, r)
    if r == 0:
        return 1
    numer = reduce(mul, range(n, n - r, -1))
    denom = reduce(mul, range(1, r + 1))
    return numer // denom


n = int(input())
a = list(map(int, input().split()))
ai = max(a)
ans_val = 0
for aj in set(a):
    if cmb(ai, aj) > ans_val:
        ans = [ai, aj]
        ans_val = cmb(ai, aj)
print(' '.join(map(str, ans)))


### FIXED CODE ###

from operator import mul
from functools import reduce

def cmb(n, r):
    r = min(n - r, r)
    if r == 0:
        return 1
    numer = reduce(mul, range(n, n - r, -1))
    denom = reduce(mul, range(1, r + 1))
    return numer // denom


n = int(input())
a = list(map(int, input().split()))
ai = max(a)
diff = float("inf")
for aj in set(a):
    if abs(ai / 2 - aj) < diff:
        ans = [ai, aj]
        diff = abs(ai / 2 - aj)
print(' '.join(map(str, ans)))
### BUGGY CODE ###

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

mod=10**9+7

ans=0
for i in range(60):
  on=0
  off=0
  for j in a:
    if (j>>i)&1:
      on+=1
    else:
      off+=1
  ans+=(on*off)*(2**i)
  ans%=mod

print(ans)

### FIXED CODE ###

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

mod=10**9+7

ans=0
for i in range(60):
  on=0
  off=0
  for j in a:
    if (j>>i)&1:
      on+=1
    else:
      off+=1
  ans+=(on*off)*(2**i)
  ans%=mod

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

k, s = map(int, input().split())
count = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if (x + y + z == s):
                count = count + 1
print(count)

### FIXED CODE ###

k, s = map(int, input().split())
count = 0
for x in range(k+1):
    if(x > s):
        break
    for y in range(k+1):
        if(x + y > s):
            break
        if(s - (x + y) <= k):
            count = count + 1
print(count)
### BUGGY CODE ###

N,K = map(int,input().split())
X = [int(i) for i in input().split()]

X_sub = []

for i in range(N-K+1):
    X_sub.append(X[i:i+K])

min_cost = float('inf')

for i in X_sub:
    tmp_l = abs(i[0]) + abs(i[-1]-i[0])
    tmp_r = abs(i[-1]) + abs(i[0]-i[-1])
    tmp = min(tmp_l,tmp_r)

    if min_cost > tmp:
        min_cost = tmp

print(min_cost)


### FIXED CODE ###

N,K = map(int,input().split())
X = [int(i) for i in input().split()]

min_cost = float('inf')

for i in range(N-K+1):
    l = X[i]
    r = X[i+K-1]
    tmp_l = abs(l) + abs(r-l)
    tmp_r = abs(r) + abs(l-r)
    tmp = min(tmp_l,tmp_r)

    if min_cost > tmp:
        min_cost = tmp

print(min_cost)
### BUGGY CODE ###

n = int(raw_input())
a = map(int, raw_input().split())


def check(b1, b2):
  res = ''
  for x, y in zip(b1, b2):
    if x == '0' and y == '0':
      res += '0'
    elif (x == '0' and y == '1') or (x == '1' and y == '0'):
      res += '1'
    else:
      return False
  return res


total = n
for i in range(n):
  b_1 = '{0:020b}'.format(a[i])
  for j in range(i+1, n):
    b_2 = '{0:020b}'.format(a[j])
    t = check(b_1, b_2)
    if t:
      b_1 = t
      total += 1
    else:
      break

print(total)


### FIXED CODE ###

n = int(raw_input())
a = map(int, raw_input().split())

i = 0
j = 1
res = a[i]
total = n

while i < n and j < n:
  if res & a[j] == 0:
    res += a[j]
    j += 1
  else:
    res -= a[i]
    i += 1
    total += j - i
    if j == i:
      j += 1
      res = a[i]

if j == n:
  if i < n-1:
    for k in range(i+1, n):
      total += j-k

print(total)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
arr = [0]
ans = 0
for i, j in enumerate(a):
    arr.append(arr[i] + j)

_set = set(arr)
for i in _set:
    c = arr.count(i)
    ans += (c * (c - 1)) // 2

print(ans)


### FIXED CODE ###

import itertools
from collections import Counter

n = int(input())
a = list(map(int,input().split()))
arr = [0]
arr += list(itertools.accumulate(a))
ans = 0

c = Counter(arr)
for v in c.values():
    if v > 1:
        ans += v * (v - 1) // 2

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

N, M= map(int, input().split())
a =[str(input()) for _ in range(M)]
DP = [0]*(N+1)
num = 1000000007
DP[0] = 1
for i in range(N):
  if str(i) in a:
    DP[i] = 0
  else:
    DP[i] = DP[i] % num 
    if i < N:
      DP[i+1] += DP[i]
      if i < N-1:
        DP[i+2] += DP[i]
print(DP[-1]%num)

### FIXED CODE ###

N, M, = map(int, input().split())
a = set([int(input()) for _ in range(M)])
DP = [0]*(N+2)
num = 1000000007
DP[0] = 1
for i in range(N):
  if i in a:
    DP[i] = 0
  else:
    DP[i] = DP[i] % num 
    if i < N:
      DP[i+1] += DP[i]
      DP[i+2] += DP[i]
print(DP[-2]%num)
### BUGGY CODE ###

#!/usr/bin/env python3
def main():
    from collections import deque

    N, M, K = map(int, input().split())
    friends = [set() for _ in range(N + 1)]
    for _ in range(M):
        a, b = map(int, input().split())
        friends[a].add(b)
        friends[b].add(a)
    blocks = [set() for _ in range(N + 1)]
    for _ in range(K):
        c, d = map(int, input().split())
        blocks[c].add(d)
        blocks[d].add(c)

    friends_chain = []
    seen = [-1] * (N + 1)
    cnt = 0
    for person in range(1, N + 1):
        if seen[person] != -1:
            continue
        q = deque([person])
        friends_chain.append(set(q))
        while q:
            now = q.pop()
            seen[now] = cnt
            for next in friends[now]:
                if seen[next] != -1:
                    continue
                friends_chain[-1].add(next)
                q.append(next)
        cnt += 1

    ans = []
    for person in range(1, N + 1):
        res = friends_chain[seen[person]]
        tmp_ans = len(res) - len(friends[person]) - 1
        for block in blocks[person]:
            tmp_ans -= 1 if block in res else 0
        ans.append(tmp_ans)
    print(*ans, sep=' ')


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
def main():
    from collections import deque

    N, M, K = map(int, input().split())
    friends = [set() for _ in range(N + 1)]
    for _ in range(M):
        a, b = map(int, input().split())
        friends[a].add(b)
        friends[b].add(a)
    blocks = [set() for _ in range(N + 1)]
    for _ in range(K):
        c, d = map(int, input().split())
        blocks[c].add(d)
        blocks[d].add(c)

    friends_chain = []
    seen = [-1] * (N + 1)
    cnt = 0
    for person in range(1, N + 1):
        if seen[person] != -1:
            continue
        q = deque([person])
        friends_chain.append(set(q))
        while q:
            now = q.pop()
            seen[now] = cnt
            for next in friends[now]:
                if seen[next] != -1:
                    continue
                friends_chain[-1].add(next)
                q.append(next)
        cnt += 1

    for person in range(1, N + 1):
        res = friends_chain[seen[person]]
        tmp_ans = len(res) - len(friends[person]) - 1
        for block in blocks[person]:
            tmp_ans -= 1 if block in res else 0
        print(tmp_ans, end=' ')


if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import defaultdict, deque

S = input()

D = defaultdict(set)
for x in range(2019, 10**8, 2019):
  y = str(x)
  D[y[0:4]].add(y)

L = deque()
D1 = defaultdict(set)
D2 = {}
for i in range(len(S)-3):
  ii = i
  R = ''
  while ii < len(S):
    y = R + S[ii:ii+4-len(R)]
    for d in D[y]:
      if R + S[ii:ii+len(d)-len(R)] == d:
        L.appendleft(i)
        D1[i].add(ii+len(d)-len(R))
        D2[ii+len(d)-len(R)] = i
        break
    else:
      X = int(R + S[ii:ii+8-len(R)])
      ii += 8-len(R)
      R = str(X % 2019)
      continue
    break

for x in L:
  if x in D2:
    D1[D2[x]] += D1[x]
print(sum(len(x) for x in D1.values()))

### FIXED CODE ###

from collections import defaultdict

S = input()

D = defaultdict(int)
D[0] += 1
x = 0
d = 1
for s in reversed(S):
  x = (x + int(s) * d) % 2019
  D[x] += 1
  d = (d * 10) % 2019

print(sum(x * (x-1) // 2 for x in D.values()))
### BUGGY CODE ###

from itertools import*;input();a=0
r=[0]+list(accumulate(map(int,input().split())))
for i in set(r):c=r.count(i);a+=c*~-c//2
print(a)

### FIXED CODE ###

from itertools import*
from collections import*
input();a=0
r=[0]+list(accumulate(map(int,input().split())))
for j in Counter(r).values():a+=j*~-j//2
print(a)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
n,q = map(int, input().split())
e = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    e[a-1].append(b-1)
    e[b-1].append(a-1)

ans = [0]*n

for i in range(q):
    p,x = map(int,input().split()) 
    ans[p-1] += x

def dfs(i = 0, r = -1):
    for j in e[i]:
        if j != r:
            ans[j] += ans[i]
            dfs(j, i)

dfs()

print(*ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
n,q = map(int, input().split())
e = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    e[a-1].append(b-1)
    e[b-1].append(a-1)

ans = [0]*n

for i in range(q):
    p,x = map(int,input().split()) 
    ans[p-1] += x

def dfs(i = 0, r = -1):
    for j in e[i]:
        if j != r:
            ans[j] += ans[i]
            dfs(j, i)

dfs()

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

n=int(input())
d=dict({i:0 for i in range(1,n+1)})
for s in range(3,501):
    for x in range(1,s+1-2):
        for y in range(1,s+1-x-1):
            z=s-x-y
            if x<y or y<z:
                continue
            v=x**2+y**2+z**2+x*y+y*z+z*x
            if not v in d:
                continue
            if x==y==z:
                d[v]+=1
            else:
                d[v]+=3
for k in d.keys():
    print(d[k])


### FIXED CODE ###

n=int(input())
d=dict({i:0 for i in range(1,n+1)})
for s in range(3,201):
    for x in range(1,s+1-2):
        for y in range(1,s+1-x-1):
            z=s-x-y
            v=x**2+y**2+z**2+x*y+y*z+z*x
            if not v in d:
                continue
            d[v]+=1
for k in d.keys():
    print(d[k])