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

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
def main():
  n=int(input())
  a=[list(map(int,input().split())) for _ in range(n)]
  f=lambda x:((x[0]-1)*(n-1+n-x[0]+1))//2+x[1]-x[0]-1
  m=(n*(n-1))//2
  g=[[] for _ in range(m)]
  for i in range(n):
    for j in range(n-2):
      if i+1>a[i][j]:
        t0=f((a[i][j],i+1))
      else:
        t0=f((i+1,a[i][j]))
      if i+1>a[i][j+1]:
        t1=f((a[i][j+1],i+1))
      else:
        t1=f((i+1,a[i][j+1]))
      g[t0].append(t1)
  def dfs(t):
    if v[t]:
      if c[t]==0:
        return -1
      else:
        dp[t]
    v[t]=1
    for l in g[t]:
      ret=dfs(l)
      if ret==-1:return -1
      dp[t]=max(dp[t],ret+1)
    c[t]=1
    return dp[t]
  ans=0
  for i in range(m):
    v=[0]*m
    c=[0]*m
    dp=[0]*m
    tmp=dfs(i)
    if tmp==-1:
      print(-1)
      exit()
    ans=max(ans,tmp)
  print(ans+1)

if __name__=='__main__':
  main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
def main():
  n=int(input())
  a=[list(map(int,input().split())) for _ in range(n)]
  f=lambda x:((x[0]-1)*(n-1+n-x[0]+1))//2+x[1]-x[0]-1
  m=(n*(n-1))//2
  g=[[] for _ in range(m)]
  for i in range(n):
    for j in range(n-2):
      if i+1>a[i][j]:
        t0=f((a[i][j],i+1))
      else:
        t0=f((i+1,a[i][j]))
      if i+1>a[i][j+1]:
        t1=f((a[i][j+1],i+1))
      else:
        t1=f((i+1,a[i][j+1]))
      g[t0].append(t1)
  def dfs(t):
    if v[t]:
      if c[t]==0:
        return -1
      else:
        return dp[t]
    v[t]=1
    for l in g[t]:
      ret=dfs(l)
      if ret==-1:return -1
      dp[t]=max(dp[t],ret+1)
    c[t]=1
    mi.discard(t)
    return dp[t]
  ans=0
  v=[0]*m
  c=[0]*m
  dp=[0]*m
  #print(g)
  mi=set(list(range(m)))
  while mi:
    i=mi.pop()
    tmp=dfs(i)
    if tmp==-1:
      print(-1)
      exit()
    ans=max(ans,tmp)
    #print(dp)
  print(ans+1)

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

def solve(N,A,X):  
  X.append(0)
  X.sort()
  ma=sum(X)

#[x]までのy個を使ってzを作る場合の数を数え上げるdp
#dp[x][y][z]=dp[x-1][y][z]+dp[x-1][y-1][z-X[x]](zが残っている場合）
#dp[x][y][z]=dp[x-1][y][z](zが残っていない場合)
  dp=[[[0] * (ma+1) for _ in range(N+1)] for _ in range(N+1)]
  
#[x]までの0個を使って0を作る方法は1つ（dp初期化）
  for i in range(N+1):
    dp[i][0][0]=1
  for i in range(1,N+1):
    cnt=X[i]
    for j in range(1,N+1):
      for k in range(ma+1):
        if k < cnt:
          dp[i][j][k]=dp[i-1][j][k]
        else:
          dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-cnt]

#ansはN枚中j枚使用かつj枚*平均Aを作れる個数。
  ans=0
  for x in range(1,N+1):
    if x*A<=ma:
      ans+=dp[N][x][x*A]
  return ans

N,A=map(int,input().split())
X=[int(a) for a in input().split()]
ans=solve(N,A,X)
print(ans)


### FIXED CODE ###

def solve(N,A,X):  
  X.append(0)
  X.sort()
  ma=sum(X)

#[x]までのy個を使ってzを作る場合の数を数え上げるdp
#dp[x][y][z]=dp[x-1][y][z]+dp[x-1][y-1][z-X[x]](zが残っている場合）
#dp[x][y][z]=dp[x-1][y][z](zが残っていない場合)
  dp=[[[0] * (ma+1) for _ in range(N+1)] for _ in range(N+1)]
  
#[x]までの0個を使って0を作る方法は1つ（dp初期化）
  for i in range(N+1):
    dp[i][0][0]=1
  for i in range(1,N+1):
    cnt=X[i]
    for j in range(1,N+1):
      for k in range(ma+1):
        if k < cnt:
          dp[i][j][k]=dp[i-1][j][k]
        else:
          dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-cnt]

#ansはN枚中j枚使用かつj枚*平均Aを作れる個数。
  ans=0
  for x in range(1,N+1):
    if x*A<=ma:
      ans+=dp[N][x][x*A]
  return ans

N,A=map(int,input().split())
X=[int(a) for a in input().split()]
ans=solve(N,A,X)
print(ans)
### BUGGY CODE ###


N, Q = list(map(int, input().split()))
tree = [dict() for i in range(N)]
for i in range(N):
	tree[i]["edge"] = []
	tree[i]["ope"] = 0
	tree[i]["score"] = 0
	tree[i]["parent"] = -1

for i in range(N - 1):
	a, b = list(map(int, input().split()))
	tree[a - 1]["edge"].append(b - 1)
	tree[b - 1]["edge"].append(a - 1)

for i in range(Q):
	p, x = list(map(int, input().split()))
	tree[p - 1]["ope"] += x

que = []
que.append(0)
tree[0]["score"] = tree[0]["ope"]
for ss in range(N - 1):
	loc = que.pop()
	for edge in tree[loc]["edge"]:
		if tree[loc]["parent"] != edge:
			tree[edge]["score"] += tree[loc]["score"] + tree[edge]["ope"]
			que.append(edge)
			tree[edge]["parent"] = loc

for i in range(N - 1):
	print(tree[i]["score"], end = "")
	print(" ", end = "")
print(tree[N - 1]["score"])

### FIXED CODE ###


import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math
import heapq


N, Q = list(map(int, input().split()))
eda = [[] for i in range(N)]
ope = [0]*N
score = [0]*N
parent = [-1]*N


for i in range(N - 1):
	a, b = list(map(int, input().split()))
	eda[a - 1].append(b - 1)
	eda[b - 1].append(a - 1)

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


que = []
que.append(0)
score[0] = ope[0]
for ss in range(N - 1):
	loc = que.pop()
	for edge in eda[loc]:
		if parent[loc] != edge:
			score[edge] += score[loc] + ope[edge]
			que.append(edge)
			parent[edge] = loc

for i in range(N - 1):
	print(score[i], end = "")
	print(" ", end = "")
print(score[N - 1])
### BUGGY CODE ###

n = int(input())
ans = [0] * (n + 1)
loop = int((n/6) ** 1.5) + 1

def f(i, j, k):
    return i ** 2 + j ** 2 + k ** 2 + i*j + j*k + k*i

for i in range(1, loop+1):
    for j in range(1, loop+1):
        for k in range(1, loop+1):
            res = int(f(i, j, k))
            if res <= n:
                ans[res] += 1

for a in ans[1:]:
    print(a)


### FIXED CODE ###

n = int(input())
ans = [0] * (n + 1)
loop = int(n ** .5) + 1

def f(i, j, k):
    return i ** 2 + j ** 2 + k ** 2 + i*j + j*k + k*i

for i in range(1, loop+1):
    for j in range(1, loop+1):
        for k in range(1, loop+1):
            res = int(f(i, j, k))
            if res <= n:
                ans[res] += 1

for a in ans[1:]:
    print(a)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
S=input()
N=int(len(S))
for _ in range(N):
    A=S
    S=S.replace("0110","")
    S=S.replace("0101","")
    S=S.replace("10","")
    S=S.replace("01","")
    if A==S:
        break
print(N-int(len(S)))

### FIXED CODE ###

S=input()
print(min(S.count("0"),S.count("1"))*2)
### BUGGY CODE ###

def grid_bfs(h,w,start,maze):
    INF = 10**9+7
    distance = [[INF for _ in range(w)] for _ in range(h)]
    queue = []
    for s in start:
        queue.append(s)
        distance[s[0]][s[1]] = 0
    while len(queue):
        y, x = queue.pop()
        for i in range(0, 4):
            nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
            if (0 <= nx < w and 0 <= ny < h and maze[ny][nx] != '#' and distance[ny][nx] > distance[y][x] + 1):
                queue.append([ny, nx])
                distance[ny][nx] = distance[y][x] + 1
    return distance
def examA():
    H, W = LI()
    A = [SI() for _ in range(H)]
    start = []
    for i in range(H):
        for j in range(W):
            if A[i][j]=="#":
                start.append([i,j])
    D = grid_bfs(H,W,start,A)
#    print(D,V)
    ans = 0
    for v in D:
        ans = max(ans,max(v))
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examA()


### FIXED CODE ###

def grid_bfs(h,w,start,maxD):
    INF = 10**9+7
    distance = [[INF for _ in range(w)] for _ in range(h)]
    queue = deque()
    for s in start:
        queue.append(s)
        distance[s[0]][s[1]] = 0
    while len(queue):
        y, x = queue.popleft()
        for i in range(0, 4):
            nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
            if (0 <= nx < w and 0 <= ny < h):
                if (distance[ny][nx] > distance[y][x] + 1):
                    queue.append([ny, nx])
                    distance[ny][nx] = distance[y][x] + 1
                    if maxD<distance[ny][nx]:
                        maxD = distance[ny][nx]
    return maxD
def examA():
    H, W = LI()
    A = [[1 if a == "#" else 0 for a in SI()] for _ in range(H)]
    start = []
    for i in range(H):
        for j in range(W):
            if A[i][j]==1:
                start.append([i,j])
    ans = grid_bfs(H,W,start,0)
#    print(D,V)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

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

mod = 10 ** 9 + 7


def read_valus():
    return map(int, input().split())


def read_list():
    return list(read_valus())


def read_lists(N):
    return [read_list() for n in range(N)]


def p(N, a):
    return (a * (N - a)) % mod


def main():
    N = int(input())
    A = read_list()

    num = [0] * 65
    for a in A:
        b = format(a, "065b")[::-1]
        for i in range(65):
            num[i] += int(b[i])

    res = 0
    for i in range(65):
        res = (res + (pow(2, i, mod) * p(N, num[i])) % mod) % mod

    print(res % mod)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

mod = 10 ** 9 + 7


def read_valus():
    return map(int, input().split())


def read_list():
    return list(read_valus())


def read_lists(N):
    return [read_list() for n in range(N)]


def p(N, a):
    return (a * (N - a)) % mod


def main():
    pows = [1] * 66
    for i in range(65):
        pows[i + 1] = (pows[i] * 2) % mod

    N = int(input())
    A = read_list()

    num = [0] * 65
    for a in A:
        tmp = a
        for i in range(65):
            if tmp == 0:
                break
            num[i] += tmp % 2
            tmp //= 2

    res = 0
    for i in range(65):
        if num[i] == 0:
            continue

        res = (res + (pows[i] * p(N, num[i])) % mod) % mod

    print(res % mod)


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

z=int(input())

def inv_gcd(a, b):
    a = (a + b) % b
    if a == 0:
        return (b, 0)
    s, t = b, a
    m0, m1 = 0, 1
 
    while t:
        u = s // t
        s -= t * u
        m0 -= m1 * u
 
        tmp = s
        s = t
        t = tmp
        tmp = m0
        m0 = m1
        m1 = tmp
    
    if m0 < 0:
        m0 += b // s
    return (s, m0)
 
 
def crt(r, m):
    n = len(r)
    r0, m0 = 0, 1
 
    for i in range(n):
        r1, m1 = (r[i] + m[i]) % m[i], m[i]
 
        if m0 < m1:
            m0, m1 = m1, m0
            r0, r1 = r1, r0
        
        if m0 % m1 == 0:
            if r0 % m1 != r1:
                return (0, 0)
            continue
        
        g, im = inv_gcd(m0, m1)
 
        u1 = m1 // g
        if (r1 - r0) % g:
            return (0, 0)
        
        x = (r1 - r0) // g % u1 * im % u1
 
        r0 += x * m0
        m0 *= u1
        if (r0 < 0):
            r0 += m0
        
    return (r0, m0)


def divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i:
        divisors.append(n//i)
  divisors.sort()
  return divisors


# for n in range(1,10):
#   # (変数) = (条件がTrueのときの値) if (条件) else (条件がFalseのときの値)
#   ans = n-1 if n%2 else 2*n-1
#   print(ans)

#print(chinese_remainder([2, 3, 2], [3, 5, 7]))

ans = z-1 if z%2 else 2*z-1
for i in divisors(2*z):
  y=2*z//i
  if y == 1:
    continue
  a=[0,y-1]
  b=[i,y]
  rem, mod = crt(a, b)
  #print(rem)
  #print(mod)
  if rem == mod == 0:
      continue
  ans = min(ans, rem)

print(ans if z-1 else 1)

### FIXED CODE ###

def inv_gcd(a, b):
    a = (a + b) % b
    if a == 0:
        return (b, 0)
    s, t = b, a
    m0, m1 = 0, 1
 
    while t:
        u = s // t
        s -= t * u
        m0 -= m1 * u
 
        tmp = s
        s = t
        t = tmp
        tmp = m0
        m0 = m1
        m1 = tmp
    
    if m0 < 0:
        m0 += b // s
    return (s, m0)
 
 
def crt(r, m):
    n = len(r)
    r0, m0 = 0, 1
 
    for i in range(n):
        r1, m1 = (r[i] + m[i]) % m[i], m[i]
 
        if m0 < m1:
            m0, m1 = m1, m0
            r0, r1 = r1, r0
        
        if m0 % m1 == 0:
            if r0 % m1 != r1:
                return (0, 0)
            continue
        
        g, im = inv_gcd(m0, m1)
 
        u1 = m1 // g
        if (r1 - r0) % g:
            return (0, 0)
        
        x = (r1 - r0) // g % u1 * im % u1
 
        r0 += x * m0
        m0 *= u1
        if (r0 < 0):
            r0 += m0
        
    return (r0, m0)


def divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i:
        divisors.append(n//i)
  divisors.sort()
  return divisors


# print(divisors(z))

z=int(input())


ans = z-1 if z%2 else 2*z-1
for i in divisors(2*z):
  y=2*z//i
  if y == 1:
    continue
  a=[0,-1]
  b=[i,y]
  rem, mod = crt(a, b)
  #print(rem)
  #print(mod)
  if rem == mod == 0:
      continue
  ans = min(ans, rem)

print(ans if z-1 else 1)
### BUGGY CODE ###

mod=10**9+7
n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp1=[1]*(m+1)
dp2=[1]*(m+1)
for i in range(n):
  if i%2==0:
    for j in range(m):
      if s[i]==t[j]:dp1[j+1]=dp2[j+1]+dp1[j]
      else:dp1[j+1]=dp2[j+1]+dp1[j]-dp2[j]
      dp1[j+1]%=mod
  else:
    for j in range(m):
      if s[i]==t[j]:dp2[j+1]=dp1[j+1]+dp2[j]
      else:dp2[j+1]=dp1[j+1]+dp2[j]-dp1[j]
      dp2[j+1]%=mod
if n%2==0:print(dp2[-1])
else:print(dp1[-1])

### FIXED CODE ###

mod=10**9+7
n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[(m+1)*[1]for _ in range(n+1)]
for i in range(n):
  for j in range(m):
    if s[i]==t[j]:dp[i+1][j+1]=dp[i][j+1]+dp[i+1][j]
    else:dp[i+1][j+1]=dp[i][j+1]+dp[i+1][j]-dp[i][j]
    dp[i+1][j+1]%=mod
print(dp[-1][-1])
### BUGGY CODE ###

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

ans = 1
for i in range(n):
    ans *= a[i]

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

### FIXED CODE ###

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

ans = 1
t = 1e18
if 0 in a:
    print(0)
    exit(0)

for i in range(n):
    ans *= a[i]
    if ans > t:
        print(-1)
        exit(0)

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

import sys


def solve(k, ax, bx, cx):
    ab = sorted([a + b for a in ax for b in bx], reverse=True)[:k]
    abc = sorted([abi + c for abi in ab for c in cx], reverse=True)[:k]

    return abc


if __name__ == '__main__':
    _, _, _, k = map(int, input().split())
    *ax, = map(int, sys.stdin.readline().split())
    *bx, = map(int, sys.stdin.readline().split())
    *cx, = map(int, sys.stdin.readline().split())

    ans = solve(k, ax, bx, cx)

    for a in ans:
        print(a)


### FIXED CODE ###

import sys


def solve(k, ax, bx, cx):
    ab = []
    for a in ax:
        for b in bx:
            ab.append(a+b)

    ab.sort(reverse=True)
    abk = ab[:k]

    ans = []
    for c in cx:
        for abi in abk:
            ans.append(c+abi)

    return sorted(ans, reverse=True)[:k]


if __name__ == '__main__':
    _, _, _, k = map(int, input().split())
    ax = sorted(list(map(int, sys.stdin.readline().split())), reverse=True)
    bx = sorted(list(map(int, sys.stdin.readline().split())), reverse=True)
    cx = sorted(list(map(int, sys.stdin.readline().split())), reverse=True)

    ans = solve(k, ax, bx, cx)

    print(*ans, sep="\n")
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
for _ in range(q):
  l,r=map(int,input().split())
  word=s[l-1:r]
  print(word.count("AC"))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
num=[0]
be=""

for i in range(n):
  if be=="A" and s[i]=="C":
    num.append(num[-1]+1)
    
  else:
    num.append(num[-1])
    
  be=s[i]
    
for i in range(q):
  l,r=map(int,input().split())
  
  print(abs(num[l]-num[r]))
### BUGGY CODE ###

x, n = map(int, input().split())
p = list(map(int, input().split()))
 

_x = x 
x_ = x
while True:
  if _x not in p:
    print(_x)
    break
    if x_ not in p:
      print(x_)
      break
      _x -= 1
      x_ += 1

### FIXED CODE ###

X, N = map(int, input().split())
p = list(map(int, input().split()))

p = set(p)
for i in range(200):
    if X - i not in p:
        print(X - i)
        break
    if X + i not in p:
        print(X + i)
        break
### BUGGY CODE ###

import sys

input = sys.stdin.readline
n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [-1] * n
dp[0] = 0
dp[1] = abs(h[0] - h[1])
if n == 2:
    print(dp[1])
else:
    for i in range(2, n):
        if i <= k:
            dp[i] = min(abs(h[i] - h[i - j]) + dp[i - j] for j in range(1, i + 1))
        else:
            dp[i] = min(abs(h[i] - h[i - j]) + dp[i - j] for j in range(1, k + 1))
    print(dp[n - 1])


### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [0] * n
    dp[0] = 0
    dp[1] = abs(h[0] - h[1])

    for i in range(2, n):
        dp[i] = min(abs(h[i] - h[j]) + dp[j] for j in range(max(0, i - k), i))
    print(dp[n - 1])


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

# coding: utf-8
from functools import lru_cache

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

@lru_cache(maxsize = None)
def f2(i, j):
    if i == j:
        return(a[i])
    return(max(a[i] - f2(i + 1, j), a[j] - f2(i, j - 1)))

n = int(input()) # 1 <= n <= 3000
a = list(map(int, input().split()))
print(f2(0, n - 1))


### FIXED CODE ###

# coding: utf-8

import sys
input = sys.stdin.readline

def f(n, a):
    dp = [[0] * n for _ in range(n)]
    # dp[i][i] を a[i] で初期化
    for i in range(n):
        dp[i][i] = a[i]
    for i in range(n - 2, -1, -1):
        dpi = dp[i]
        dpi1 = dp[i + 1]
        for j in range(i + 1, n):
            r = a[i] - dpi1[j]
            l = a[j] - dpi[j - 1]
            dp[i][j] = r if r > l else l
            # dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])
    return(dp[0][-1])

n = int(input()) # 1 <= n <= 3000
a = list(map(int, input().split()))
print(f(n, a))
### BUGGY CODE ###

k = int(input())
s = 7
counter = 0
mod_box=[]


if k % 2 == 0:
    print(-1)

else:
    m = s % k
    counter += 1
    if m == 0:
        print(counter)
    else:
        mod_box.append(m)
        while True:
            m = 10 * m + 7
            m = m % k
            counter += 1
            if m == 0:
                print(counter)
                break
            elif m in mod_box:
                print(-1)
            else:
                mod_box.append(m)
        
        
    

### FIXED CODE ###

k = int(input())
m = 7%k

for i in range(1, 10**6+1):
    if m == 0:
        print(i)
        exit()
    else:
        m = (10 * m + 7) % k

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

N = int(input())
num = input()
X = int(num,2)
c = num.count('1')
def A(s):
    if s == 0:
        return 1
    return A(s%(bin(s).count('1'))) + 1
if c==1:
  for i in range(N):
    if num[i] == '1':
      print(0)
    elif i == N-1:
      print(2)
    else:
      print(1)
  exit()
amari1 = X%(c+1)
amari2 = X%(c-1)
for i in range(N):
    if num[i] == '1':
        print(A((amari2-2**(N-1-i))%(c-1)))
    else:
        print(A((amari1+2**(N-1-i))%(c+1)))

### FIXED CODE ###

N=int(input())
X=input()
Y=int(X,2)
Z=Y
C=X.count('1')
if C==1:
  for i in range(N):
    if X[i]=='1':
      print(0)
    elif i==N-1:
      print(2)
    else:
      print(1)
  exit()
Y,Z=Y%(C+1),Z%(C-1)
def f(x):
  if x==0:
    return 0
  return 1+f(x%bin(x).count('1'))
 
for i in range(N):
  if X[i]=='1':
    print(1+f((Z-pow(2,N-i-1,C-1))%(C-1)))
  else:
    print(1+f((Y+pow(2,N-i-1,C+1))%(C+1)))
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding:utf-8 -*-
import sys
for n in sys.stdin:
    prime=[]
    n=int(n)
    for i in range(2,n+1):
        if all(i%p!=0 for p in prime):
            prime+=[i]
    print len(prime)

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding:utf-8 -*-
#from __future__ import print_function
import time
import sys
import io
import re
import math
start = time.clock()

def prime(n):
    l=[True for _ in range(n+1)]
    i=2
    while i**2<=n:
        if l[i]:
            j=i+i
            while j<=n:
                l[j]=False
                j+=i
        i+=1
    return l
#    lis=[i for i in range(n+1) if l[i] and i>=2]

for n in sys.stdin:
    print (prime(int(n))).count(True)-2
### BUGGY CODE ###

class Unbalanced:
	def searchStrings(self,s):
		words=[[[0 for j in range(26)] for i in range(len(s)-1)]for k in range(len(s))]
		for k in range(len(s)):
			for i in range(0,len(s)-1):
				words[k][i][ord(s[i])-97]+=1
				for j in range(i+1,len(s)):
					words[k][i][ord(s[j])-97]+=1
					if max(words[k][i])>=len(s[i:j+1])/2+1:
						print i+1,j+1
						return
		print -1,-1

if __name__ == "__main__":
	s=raw_input()
	u=Unbalanced()
	u.searchStrings(s)

### FIXED CODE ###

class nUnbalanced:
	def searchStrings(self,s):
		if len(s)==2:
			x_f=s[0]; x_s=s[1]
			if x_f==x_s: print 1,2; return
			else: print -1,-1; return
		for base in range(len(s)-2):
			x_f=s[base]; x_s=s[base+1]; x_t=s[base+2]
			if x_f==x_s or x_s==x_t or x_f==x_t: print base+1,base+3; return
		print -1,-1

if __name__ == "__main__":
	s=raw_input()
	u=nUnbalanced()
	u.searchStrings(s)
### BUGGY CODE ###

N,W=map(int,input().split())
dp=[[0]*(W+1) for _ in range(N+1)]
for i in range(1,N+1):
	w,v=map(int,input().split())
	for j in range(1,W+1):
		if j-w>=0:
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)
		else:
			dp[i][j]=dp[i-1][j]
print(dp[N][W])

### FIXED CODE ###

N,W=map(int,input().split())
dp=[[0]*(W+1) for _ in range(N+1)]
for i in range(1,N+1):
	w,v=map(int,input().split())
	for j in range(1,W+1):
		if j-w>=0:
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)
		else:
			dp[i][j]=dp[i-1][j]
print(dp[N][W])
### BUGGY CODE ###

N,P = map(int, input().split())

count = 1
ans = 0

if N > 1000001:
    print(1)
    exit()

while True:

    if count**N > P:
        break

    if P % count**N == 0:
        ans = count

    count += 1
 
print(ans)

### FIXED CODE ###

N,P = map(int, input().split())

count = 1
ans = 0

if N == 1:
    print(P)
    exit()

if N > 1000001:
    print(1)
    exit()

while True:

    if count**N > P:
        break

    if P % count**N == 0:
        ans = count

    count += 1
 
print(ans)
### BUGGY CODE ###

import sys
import numpy as np

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


def solve():
    N, K = map(int, input().split())
    p = list(map(int, input().split()))
    p = np.array(p, dtype='f8')
    p = (p + 1) / 2

    ans = 0
    for i in range(N - K + 1):
        ans = max(ans, np.sum(p[i:i + K]))

    print(ans)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
import numpy as np

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


def solve():
    N, K = map(int, input().split())
    p = np.array(list(map(int, input().split())), dtype='f8')
    p = (p + 1) / 2
    rs = np.zeros(N + 1, dtype='f8')
    for i in range(N):
        rs[i + 1] = rs[i] + p[i]
    ans = 0
    for i in range(N - K + 1):
        ans = max(ans, rs[i + K] - rs[i])

    print(ans)


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

N=int(input())

for n in range(1,N+1):
    count=0
    for x in range(1,n+1):
        for y in range(1,n+1):
            for z in range(1,n+1):
                if (x+y+z)**2-(x*y+y*z+z*x)==n:
                    count=count+1
    print(count)



### FIXED CODE ###

N=int(input())

a=[0]*10**4

for x in range(1,100):
     for y in range(1,100):
         for z in range(1,100):
             n=(x+y+z)**2-(x*y+y*z+z*x)
             if n<=10000:
                 a[n-1]+=1

for n in range(N):
    print(a[n])