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

import sys

sys.setrecursionlimit(100000000)

def dfs(x):
  if x == N:
    return 1
  if x > N or x in a:
    return 0
  if memo.get(x):
    return memo[x]
  memo[x] = dfs(x+1) + dfs(x+2)
  return memo[x]

N, M = map(lambda x: int(x), input().split())
a = [int(input()) for i in range(M)]
#print(N)
#print(M)
#print(a)
memo = {}
count = dfs(0)
print(count%1000000007) 



### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)

def dfs(x):
  if x == N:
    return 1
  if x > N:
    return 0
  if memo[x] >= 0:
    return memo[x]
  memo[x] = dfs(x+1) + dfs(x+2)
  return memo[x]

N, M = map(lambda x: int(x), input().split())
a = [int(input()) for i in range(M)]
#print(N)
#print(M)
#print(a)
memo = [-1]*(N+1)
for ai in a:
  memo[ai] = 0
count = dfs(0)
print(count%1000000007)
### BUGGY CODE ###



def merge(p1, p2):
    inds = list(set(p1 + p2))
    inds.sort(key=lambda i: a[i],reverse=True)
    return inds[:2]


n = input()
a = map(int, raw_input().split())
a.append(0) #default value used for a[-1]

best = a[0]
dp = [[i, -1] for i in range(1 << n)]
for mask in range(1, len(dp)):
    for j in range(n):
        if mask & (1 << j):
            dp[mask] = merge(dp[mask], dp[mask ^ (1 << j)])
    best = max(best, sum(map(lambda x: a[x], dp[mask])))
    print(best)


### FIXED CODE ###



def merge(a, b):
    if a[0] > b[0]:
        if a[1] > b[0]:
            return a
        return a[0], b[0]
    if b[1] > a[0]:
        return b
    return b[0], a[0]


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

dp = [(a[i], 0) for i in range(1 << n)]
for j in range(n):
    for mask in range(1, len(dp)):
        if mask & (1 << j):
            dp[mask] = merge(dp[mask], dp[mask ^ (1 << j)])

best = a[0]
for i in range(1, len(dp)):
    best = max(best, sum(dp[i]))
    print(best)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
S = list(input())
S.pop(-1)
n = int(input())
s = []
for i in range(n):
    array = list(map(str,input().split()))
    s.append(array)
for i in range(n):
    if s[i][0] == "1":
        S.reverse()
    else:
        if s[i][1] == "1":
            S.insert(0,s[i][2])
        else:
            S.append(s[i][2])
print("".join(S))

### FIXED CODE ###

x = input()
s = []
n = int(input())
for i in range(n):
    array = list(map(str,input().split()))
    s.append(array)
    
a = ""
b = ""
c = 0
for i in range(n):
    if s[i][0] == "1":
        c += 1
        c = c%2
    else:
        if c == 0:
            if s[i][1] == "1":
                a = s[i][2] + a
            else:
                b = b + s[i][2]
        else:
            if s[i][1] == "1":
                b = b + s[i][2]
            else:
                a = s[i][2] + a
if c == 0:
    print(a + x + b)
else:
    print(''.join(list(reversed(b))) + ''.join(list(reversed(x))) + ''.join(list(reversed(a))))
### BUGGY CODE ###

X, N = map(int, input().split())
if N == 0:
  print(X)
  exit()
P = list(map(int, input().split()))
 
i = 0
while 1:
  for d in [-1, +1]:
    if not X+i*d in P:
      print(X+i*d)
      break
  i += 1

### FIXED CODE ###

X, N = map(int, input().split())
if N == 0:
  print(X)
  exit()
P = list(map(int, input().split()))

i = 0
while 1:
  if not X-i in P:
    print(X-i)
    break
  if not X+i in P:
    print(X+i)
    break
  i += 1
### BUGGY CODE ###

n = int(input())
d = list(map(int, input().split()))
m = int(input())
t = list(map(int, input().split()))
d.sort()
t.sort()

a = 0
cnt = 0
last = t[-1]
for i in range(n):
    for j in range(a, m):
        if d[i] == t[j]:
            cnt += 1
            a = j+1
            break
        elif d[i] > last:
            break
        
if cnt == m:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

n = int(input())
d = list(map(int, input().split()))
m = int(input())
t = list(map(int, input().split()))
d.sort()
t.sort()

a = 0
b = 0
cnt = 0
last = t[-1]
for i in range(a, n):
    for j in range(b, m):
        if d[i] == t[j]:
            cnt += 1
            b = j+1
            break
        elif d[i] < t[j]:
            break

if cnt == m:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###


import itertools

def main():
    
    input_lines_n = input()
    n = int(input_lines_n)
    
    for i in range(1, n+1):
        ans = 0
        cnt = 0
        for x, y, z in itertools.product(range(n), range(n), range(n)):
            if x > 0 and y > 0 and z > 0:
                #ans = x**2 + y**2 + z**2 + x*y + y*z + z*x
                ans = (x + y + z)**2 - (x*y + y*z + z*x)
                if ans == i:
                    cnt = cnt + 1
        
        print(cnt)
                    
    
if __name__ == "__main__":
    main()


### FIXED CODE ###


import itertools

def main():
    
    input_lines_n = input()
    n = int(input_lines_n)
    xyz_max = 100
    l = [0] * 10001
    
    for x, y, z in itertools.product(range(xyz_max), range(xyz_max), range(xyz_max)):
        fn = 0
        if x > 0 and y > 0 and z > 0:
            fn = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if fn <= n:
                l[fn] += 1
    
    for i in range(1, n+1):
        print(l[i])
                    
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N = int(input())
S = input()

total = 0

for i in range(N):
  for  j in range(i + 1, N):
    if S[i] == S[j]:
      continue
    for k in range(j + 1, N):
      if (S[i] == S[k]) | (S[j] == S[k]):
        continue
      if (j - i) == (k - j):
        continue
      total += 1
      
print(total)

### FIXED CODE ###

N = int(input())
S = input()

RGB = S.count("R") * S.count("G") * S.count("B")

for i in range(N - 2):
  for j in range(i + 1, N - 1):
    k = 2 * j - i
    if ( k >= N ):
      break
    if (S[i] != S[j]) & (S[j] != S[k]) & (S[i] != S[k]):
      RGB -= 1


print(RGB)
### BUGGY CODE ###

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

#output
import numpy as np
dp = np.zeros((N+1, W+1), int)

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

print(dp[-1, -1])

### FIXED CODE ###

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

#output
import numpy as np
dp = np.zeros((N+1, W+1), int)

for i in range(N):
    dp[i+1, w[i]:] = np.maximum(dp[i, w[i]:], dp[i, :-w[i]] + v[i])
    dp[i+1, :w[i]] = dp[i, :w[i]]

print(dp[-1, -1])
### BUGGY CODE ###

def main():
    A, B, K = map(int, input().split(' '))
    l = B + 1 - A
    for i, x in enumerate(range(A, B+1), 1):
        if i <= K or l - i < K:
            print(x)

if __name__ == '__main__':
    main()


### FIXED CODE ###

A, B, K = map(int, input().split())
ans = set()

i = 0
tmp = A
while i < K and tmp <= B:
    ans.add(tmp)
    tmp += 1
    i += 1

i = 0
tmp = B
while i < K and A <= tmp:
    ans.add(tmp)
    tmp -= 1
    i += 1

for i in sorted(ans):
    print(i)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    n = int(input())
    A = [int(i) for i in input().split()]

    MOD = 10 ** 9 + 7
    A.sort()
    A.append(MOD)
    s = set()

    ans = 0
    if A[0] != A[1]:
        ans += 1

    for i in range(1, n):
        if A[i] == A[i + 1] or i in s:
            continue

        for j in range(i):
            if A[i] % A[j] == 0:
                s.add(i)
                break
        else:
            ans += 1
            # print(f"{i = }, {j = }, {ans = }")

    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.readline


def main():
    n = int(input())
    A = np.array([int(i) for i in input().split()])

    max_dp = np.max(A) + 1
    dp = np.zeros(max_dp, dtype="int32")

    for a in A:
        if dp[a] >= 2:
            continue
        fancy = np.arange(a, max_dp, a)
        dp[fancy] += 2
        dp[a] -= 1
    print(np.sum(dp == 1))


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

from math import gcd
from functools import reduce

def solve():
    K = int(input())
    ans = 0

    for i in range(1,K+1):
        num = [0, 0, 0]
        num[0] = i
        for k in range(1,K+1):
            num[1] = k
            for m in range(1,K+1):
                num[2] = m
                ans += reduce(gcd, num)
    return ans

print(solve())

### FIXED CODE ###

from math import gcd

K = int(input())
ans = 0

for i in range(1,K+1):
    for k in range(1,K+1):
        b = gcd(i, k)
        for m in range(1,K+1):
            ans += gcd(b, m)

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

from collections import deque

n,m = map(int, input().split())
dic = {}

AB = [map(int, input().split()) for _ in range(m)]

dic = [[] for _ in range(n + 1)]

for a,b in AB:
    a -= 1
    b -= 1

    dic[a].append(b)
    dic[b].append(a)

dist = {}
queue = deque([0])
visited = []
pre = {}

dist[0] = 0 
#queue.append(0)

while queue:
    v = queue.popleft()
    
    for i in dic[v]:
        if i in visited:
            continue
        
        visited.append(i)
        dist[i] = dist[v] + 1
        pre[i]= v
        queue.append(i)


print("Yes")
for i in range(n):
    ans = 0
    
    if(i == 0):
        continue
    
    ans = pre[i]
    ans += 1
    print(ans)

### FIXED CODE ###

from collections import deque

n,m = map(int, input().split())
dic = {}

AB = [map(int, input().split()) for _ in range(m)]

dic = [[] for _ in range(n + 1)]

for a,b in AB:
    a -= 1
    b -= 1

    dic[a].append(b)
    dic[b].append(a)

#dist = {}
queue = deque([0])
visited = []
pre = [-1] * (n+1)

#dist[0] = 0 
queue.append(0)

while queue:
    v = queue.popleft()
    
    for i in dic[v]:
        if pre[i] == -1:
        #dist[i] = dist[v] + 1
            pre[i]= v
            queue.append(i)

print("Yes")
for i in range(n):
    ans = 0
    
    if(i == 0):
        continue
    
    ans = pre[i]
    ans += 1
    print(ans)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    N, Q = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(N-1)]
    px = [list(map(int, input().split())) for _ in range(Q)]

    edge = [[False]*N for _ in range(N)]
    for i in ab:
        edge[i[0]-1][i[1]-1] = True
        edge[i[1]-1][i[0]-1] = True
    cnt = [0]*N
    for i in px:
        cnt[i[0]-1] += i[1]

    stk = []
    visited = set()
    stk.append(0)
    par = -1
    while len(stk):
        v = stk.pop()
        if not v in visited:
            visited.add(v)
            if v>0:
                cnt[v] += cnt[par]
        for j in range(N):
            if edge[v][j] and j!=par and not j in visited:
                stk.append(j)
        par = v

    print(*cnt)

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**6)

def resolve():
    N, Q = map(int, input().split())
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    cnt = [0]*N
    for i in range(Q):
        p, x = map(int, input().split())
        cnt[p-1] += x

    def dfs(v, par):
        if v>0:
            cnt[v] += cnt[par]
        for i in edge[v]:
            if i!=par:
                dfs(i, v)

    dfs(0, -1)

    print(*cnt)

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

S = list(input())
cnt = 0
i = 0

cnt = 0
while i < len(S) - 1:
    key = i
    #print(i)
    if S[i] == "B" and S[i + 1] == "W":
        S[i] = "W"
        S[i + 1] = "B"
        cnt += 1
        j = i - 1
        while True:
            #print(0, 0, j, S[j], S[j + 1])
            if j < 0:
                break
            if S[j] == "B" and S[j + 1] == "W":
                S[j] = "W"
                S[j + 1] = "B"
                #print(10000)
                cnt += 1
                key = j
                j -= 1
            else:
                break
    i = key
    i += 1
print(cnt)

### FIXED CODE ###


def A():
    S = list(input())
    W = [0 for i in range(len(S))]
    B = [0 for i in range(len(S))]
    ans = 0
    if S[0] == "B":
               B[0] = 1
    else:
        W[0] = 1

    for i in range(1, len(S)):
        B[i] += B[i - 1]
        if S[i] == "B":
            B[i] += 1
        else:
            ans += B[i]
    print(ans)
A()
### BUGGY CODE ###

def set(a, b):
  R[a].append(b)
  R[b].append(a)

N = int(input())
xy = [[i] + list(map(int, input().split())) for i in range(N)]
R = [[] for _ in range(N)]
xy.sort(key = lambda x: x[1])
for i in range(1, N):
  a = xy[i]
  b = xy[i - 1]
  set(a[0], b[0])
xy.sort(key = lambda x: x[2])
for i in range(1, N):
  a = xy[i]
  b = xy[i - 1]
  set(a[0], b[0])

xy.sort()
import heapq
q = [[0, 0]]
L = [True] * N
pop = heapq.heappop
push = heapq.heappush
ans = 0

for _ in range(N):
  k, t = pop(q)
  while not L[t]:
    k, t = pop(q)
  L[t] = False
  ans += k
  for i in R[t]:
    if L[i]:
      x = abs(xy[t][1] - xy[i][1])
      x = min(x, abs(xy[t][2] - xy[i][2]))
      push(q, [x, i])
print(ans)


### FIXED CODE ###

def set(a, b):
  R[a].append(b)
  R[b].append(a)

N = int(input())
xy = [[i] + list(map(int, input().split())) for i in range(N)]
R = [[] for _ in range(N)]
xy.sort(key = lambda x: x[1])
for i in range(1, N):
  a = xy[i]
  b = xy[i - 1]
  set(a[0], b[0])
xy.sort(key = lambda x: x[2])
for i in range(1, N):
  a = xy[i]
  b = xy[i - 1]
  set(a[0], b[0])

xy.sort()
import heapq
q = [[0, 0]]
L = [True] * N
pop = heapq.heappop
push = heapq.heappush
ans = 0

for _ in range(N):
  k, t = pop(q)
  while not L[t]:
    k, t = pop(q)
  L[t] = False
  ans += k
  for i in R[t]:
    if L[i]:
      x = abs(xy[t][1] - xy[i][1])
      x = min(x, abs(xy[t][2] - xy[i][2]))
      push(q, [x, i])
print(ans)
### BUGGY CODE ###

#!usr/bin/env python3
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LIR(n):
    return [LI() for i in range(n)]

def solve():
    def add(i,x):
        while i < len(bit):
            bit[i] += x
            i += i&-i
    def sum_(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res
    n,Q = LI()
    c = LI()
    c = [0]+c
    q = LIR(Q)
    q = [[i,q[i]] for i in range(Q)]
    q.sort(key = lambda x:x[1][1])
    bit = [0]*(n+2)
    i = 1
    p = [None]*(n+1)
    ans = [0]*Q
    s = 0
    for ind,(l, r) in q:
        l -= 1
        while i <= r:
            ci = c[i]
            j = p[ci]
            if j is not None:
                add(j,1)
            else:
                s += 1
            p[ci] = i
            i += 1
        ans[ind] = s-l+sum_(l)
    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()


### FIXED CODE ###

#!usr/bin/env python3
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LIR(n):
    return [LI() for i in range(n)]
class BIT:
    def __init__(self, size):
        self.size = size + 1
        self.dat = [0]*self.size

    def add(self, i, x=1):
        while i < self.size:
            self.dat[i] += x
            i += i&-i

    # sum[l,r)
    # sum[0,l] (r = None)
    def sum(self, l, r=None):
        if r is None:
            res = 0
            while l > 0:
                res += self.dat[l]
                l -= l&-l
            return res

        else:
            rres = 0
            while r > 0:
                rres += self.dat[r]
                r -= r&-r

            l -= 1
            lres = 0
            while l > 0:
                lres += self.dat[l]
                l -= l&-l

            return rres - lres


def solve():
    n,Q = LI()
    c = LI()
    c = [0]+c
    q = LIR(Q)
    q = [[i,q[i]] for i in range(Q)]
    q.sort(key = lambda x:x[1][1])
    bit = BIT(n+1)
    i = 1
    p = [None]*(n+1)
    ans = [0]*Q
    s = 0
    for ind,(l, r) in q:
        l -= 1
        while i <= r:
            ci = c[i]
            j = p[ci]
            if j is not None:
                bit.add(j)
            else:
                s += 1
            p[ci] = i
            i += 1
        ans[ind] = s-l+bit.sum(l)
    for i in ans:
        print(i)
    return

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

n = int(input())
s = input()
ans = 0

for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            if s[i] != s[j] and s[j] != s[k] and s[k] != s[i] and j-i != k-j:
          	    ans += 1
            	
print(ans)


### FIXED CODE ###

n = int(input())
s = input()

r_cnt = s.count('R')
g_cnt = s.count('G')
b_cnt = s.count('B')

# print(r_cnt, g_cnt, b_cnt)
ans = r_cnt * g_cnt * b_cnt
# print(ans)

for i in range(n):
    for d in range(n):
        j = i + d
        k = j + d
        # print(i,j,k)
        if k >= n: 
            # print('/')
            break
        if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            ans -= 1

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

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

#n,*a = [int(i) for i in read().split()]
n = int(readline())
#a = []
C = [0]*n
D = [0]*n

M = 10**9
for i in range(n):
    bi = float(readline())
    ai = int(round(bi*M))
        
    c2=c5=0    
    x = ai
    while x%2==0:
        c2 += 1
        x//=2
    
    x = ai
    while x%5==0:
        c5 += 1
        x//=5
    #print(ai,c2,c5)
    #a.append((c2,c5,v))
    C[i] = c2
    D[i] = c5
    #print(ai)
#print(C)
#print(D)

ans = 0
for i in range(n):
    for j in range(i+1,n):
        if C[i]+C[j] >= 18 and D[i]+D[j] >= 18:
            ans += 1

print(ans)




### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n = int(readline())
#C = [0]*n
#D = [0]*n

"""
dp[i][j] = 2,5で何回割れるか
"""
dp = [[0]*20 for _ in range(50)]

M = 10**9
for i in range(n):
    bi = float(readline())
    ai = int(round(bi*M))
    
    c2=c5=0    
    x = ai
    while x%2==0:
        c2 += 1
        x//=2
    
    x = ai
    while x%5==0:
        c5 += 1
        x//=5
    #C[i] = c2
    #D[i] = c5
    dp[c2][c5] += 1
    #print(c2,c5)

"""
dp[i][j] = 2,5で何回割れるか(50*20)
"""
acc = [dp[i][:] for i in range(50)]
for i in range(49,-1,-1):
    for j in range(19,-1,-1):
        if i != 49:
            acc[i][j] += acc[i+1][j] 
        if j != 19:
            acc[i][j] += acc[i][j+1] 
        if i != 49 and j != 19:
            acc[i][j] -= acc[i+1][j+1] 
            
ans = 0
for i in range(50):
    for j in range(20):
        ans += dp[i][j] * acc[max(0,18-i)][max(0,18-j)]
        if i >= 9 and j >= 9: ans -= dp[i][j]

#print(ans)
print(ans//2)
### BUGGY CODE ###

import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

h,n = nm()
v = [nl() for _ in range(n)]
dp = [1<<30]*(h+10020)
dp[0] = 0
for a,b in v:
    for i in range(h+1):
        if dp[i+a] > dp[i] + b:
            dp[i+a] = dp[i] + b
print(min(dp[h:]))


### FIXED CODE ###

import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

h,n = nm()
v = [nl() for _ in range(n)]
dp = [1<<30]*(h+10020)
dp[0] = 0
for a,b in v:
    for i in range(h+1):
        if dp[i+a] > dp[i] + b:
            dp[i+a] = dp[i] + b
print(min(dp[h:]))
### BUGGY CODE ###

n=int(input())
p=list(map(int,input().split()))
f=0
b=[]
t=0
c=[]
for i in range(n-1):
 for l in range(i+1,n):
  b=p[i:l+1]
  c.append(sorted(set(b))[-2])
print(sum(c))

### FIXED CODE ###

n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)
### BUGGY CODE ###

import sys
import math
MAX_INT = int(10e9)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def judge(x):
  l = []
  for i in range(N):
    l.append(a[i]%x)
  l.sort()

  aa = 0
  bb = 0
  for i in l:
    tmp = i
    if aa + tmp > K:
      bb += x-tmp
      if bb > K:
        return False
    else:
      aa += tmp
  else:
    return True

N,K = IL()
a = IL()
a.sort()
num = sum(a)
ans = []

for i in range(num,int(math.sqrt(num)-1),-1):
  if num%i == 0:
    if judge(i):
      ans.append(i)
    if judge(num//i):
      ans.append(num//i)

ans.sort()
print(ans[-1])

### FIXED CODE ###

import sys
import math
MAX_INT = int(10e9)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def judge(x):
  l = []
  for i in range(N):
    l.append(a[i]%x)
  l.sort()

  aa = 0
  bb = 0
  for i in l:
    tmp = i
    if aa + tmp > K:
      bb += x-tmp
      if bb > K:
        return False
    else:
      aa += tmp
  else:
    return True

N,K = IL()
a = IL()
num = sum(a)
ans = []

for i in range(1,int(math.sqrt(num)+1)):
  if num%i == 0:
    if judge(i):
      ans.append(i)
    if judge(num//i):
      ans.append(num//i)

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

N, C, K = map(int, input().split())
users = []
for i in range(N):
    users.append(int(input()))

users = sorted(users, reverse=False)

ans = 0
pos = 0
start = 0

while True:
    count = 0

    if pos == N:
        break
        
    start = users[pos]
#     print("start:{}".format(start))
    for i in range(C):
        if pos+i < N and users[pos+i] <= start+K:
            count += 1
    pos += count
#     print("pos:{}".format(pos))
    ans += 1
#     print("ans:{}".format(ans))

print(ans)

### FIXED CODE ###

N, C, K = map(int, input().split())
users = []
for i in range(N):
    users.append(int(input()))

users = sorted(users, reverse=False)

ans = 0
pos = 0
start = 0

while True:
    count = 0

    if pos == N:
        break
        
    start = users[pos]
#     print("start:{}".format(start))
    for i in range(C):
        if pos+i < N and users[pos+i] <= start+K:
            count += 1
        else:
            break
    pos += count
#     print("pos:{}".format(pos))
    ans += 1
#     print("ans:{}".format(ans))

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

N, M = map(int, input().split())
p = list()
d = dict()
for i in range(M):
    inp = [int(i) for i in input().split()]
    p.append(inp)
    if inp[0] in d:
        d[inp[0]].append(inp[1])
    else:
        d[inp[0]] = [inp[1]]
for i in d:
    d[i] = sorted(d[i])
for i, j in p:
    print("{:06d}{:06d}".format(i, d[i].index(j)+1))

### FIXED CODE ###

N, M = map(int, input().split())
p = [[] for i in range(M)]
counter = [0] * N
ans = [""] * M

for i in range(M):
    k, y = map(int, input().split())
    p[i] = [k, y, i]

p.sort(key=lambda x:x[1])
for k, y, i in p:
    counter[k-1] += 1
    ans[i] = "{:06d}{:06d}".format(k, counter[k-1])

for i in ans:
    print(i)
### BUGGY CODE ###

n = int(input())

for x in range(1,n+1):
    ans = 0
    found = []
    for i in range(1,33):
        if i in found:
            break
        for j in range(i,33):
            for k in range(j,33):
                if i**2 + j**2 + k**2 + i*j + j*k + k*i == x:
                    ans += 3**(len(set([i,j,k]))-1)
                    found.append(i)
                    found.append(j)
                    found.append(k)

                elif x < i**2 + j**2 + k**2 + i*j + j*k + k*i:
                    break
                else:
                    pass
    print (ans)


### FIXED CODE ###

n = int(input())

ans = [0 for _ in range(10050)]
for i in range(1,105):
    for j in range(1,105):
        for k in range(1,105):
            v = i**2 + j**2 + k**2 + i*j + j*k + k*i
            if v < 10050:
                ans[v] += 1

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