Harryxun/stf_run huggingface dataset:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import Counter
    n = int(input())
    a = list(map(int, readline().split()))

    def factorization(n):
        factors = []

        if n < 2:
            return n

        while n % 2 == 0:
            factors.append(2)
            n //= 2

        for i in range(3, int(n ** 0.5) + 5, 2):
            while n % i == 0:
                factors.append(i)
                n //= i
        if n != 1:
            factors.append(n)

        return Counter(factors)

    a_fac = [0] * n

    for i, num in enumerate(a):
        a_fac[i] = factorization(num)

    lcm = Counter([1])

    for i, fac in enumerate(a_fac):
        add_temp = fac - lcm
        add = {key: value for key, value in add_temp.items() if value > 0}
        lcm += add

    b = [0] * n

    for i, fac in enumerate(a_fac):
        b_fac = lcm - fac
        temp = 1
        for key, value in b_fac.items():
            temp *= pow(key, value, MOD)
            temp %= MOD
        b[i] = temp

    ans = 0
    for elem in b:
        ans += elem
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import Counter
    n = int(input())
    a = list(map(int, readline().split()))

    def factorization(n):
        factors = []

        while n % 2 == 0:
            factors.append(2)
            n //= 2

        for i in range(3, int(n ** 0.5) + 5, 2):
            while n % i == 0:
                factors.append(i)
                n //= i
        if n != 1:
            factors.append(n)

        return Counter(factors)

    a_fac = [0] * n

    for i, num in enumerate(a):
        a_fac[i] = factorization(num)

    lcm = {1: 1}

    for fac in a_fac:
        for key, value in fac.items():
            lcm[key] = max(lcm.get(key, 0), value)

    ans = 0

    lcmmod = 1

    for key, value in lcm.items():
        lcmmod *= pow(key, value, MOD)
        lcmmod %= MOD

    for ele in a:
        ainv = pow(ele, MOD - 2, MOD)
        ans += ((lcmmod*ainv) % MOD)
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()
S = input()
is_hitachi = True
for i in range(0, len(S), 2):
    if not (S[i] == 'h' and S[i + 1] == 'i'):
        is_hitachi = False
print('YNeos'[not is_hitachi::2])


### FIXED CODE ###

S = input()
is_hitachi = True
if len(S) %2 == 0:
    for i in range(0, len(S), 2):
        if not (S[i] == 'h' and S[i + 1] == 'i'):
            is_hitachi = False
    print('YNeos'[not is_hitachi::2])
else:
    print('No')
import sys
input = sys.stdin.readline

def main():
    X = int(input())
    i = 0
    while True:
        a = (X + i**5)**(1/5)
        if isinstance(a, float):
            if a.is_integer():
                print(str(int(a))+' '+str(i))
                break

        a = (X - i**5)**(1/5)
        if isinstance(a, float):
            if a.is_integer():
                print(str(int(a))+' '+str(-i))
                break
        i += 1

if __name__ == '__main__':
    main()

### FIXED CODE ###

a = input()
if a == 'ABC':
    print('ARC')
else:
    print('ABC')
n, q = map(int, input().split())
s = input()

for i in range(3):
    first, last = map(int, input().split())
    print(s.count("AC", first - 1, last))


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
# table = [0] * 100005
table = [0] * n
for i in range(1, n):
    table[i] = table[i - 1]
    if s[i] == "C" and s[i - 1] == "A":
        table[i] += 1

for i in range(q):
    first, last = map(int, input().split())
    print(table[last - 1] - table[first - 1])
a, b = map(int, input().split())
price = (a // 0.09)+1
while (price * 0.08) => a:
    if (price * 0.1) //1== b:
        print(int(price))
        exit()
    price += 1
print('-1')


### FIXED CODE ###

a, b = map(int, input().split())
for i in range(1002):
    if (i*0.08)//1==a and (i*0.1)//1==b:
        print(i)
        exit()
print('-1')
n = int(input())
a = list(map(int, input().split()))
sorted_a = sorted([i[0]for i in Counter(a).most_common() if i[1] >= 2], reverse=True)
print(sorted_c_a[0] * sorted_c_a[1] if len(sorted_c_a) >= 2 else 0)

### FIXED CODE ###

from collections import *

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

filtered_a = sorted([i for i in Counter(a).most_common() if i[1] >= 2], reverse=True)

print(  0 if len(filtered_a) < 2
        else filtered_a[0][0] ** 2 if filtered_a[0][1] >= 4
        else filtered_a[0][0] * filtered_a[1][0])
#n,a,b,c,d=map(int,input().split())
n=int(input())
a=[int(i) for i in input().split()]
ans=False
c=[]

t=sum(a)//((n*(n+1))//2)

if sum(a)%((n*(n+1))//2)!=0:
    ans=False
else:
    if n==1:
        ans=True
        break
    for i in range(n):
        if i==0:
            d=a[0]-a[-1]
        else:
            d=a[i]-a[i-1]
        if (t-d)%n!=0:
            ans=False
            break
        s=(t-d)//n
        c.append(s)
    if sum(c)==t:
        ans=True
print('YES' if ans else 'NO')

### FIXED CODE ###

#n,a,b,c,d=map(int,input().split())
n=int(input())
a=[int(i) for i in input().split()]
ans=True
c=[]

t=sum(a)//((n*(n+1))//2)

if sum(a)%((n*(n+1))//2)!=0:
    ans=False
else:
    for i in range(n):
        if i==0:
            d=a[0]-a[-1]
        else:
            d=a[i]-a[i-1]
        if (t-d)%n!=0 or d-t>0:
            ans=False
            break
        s=(t-d)//n
        c.append(s)
    #if sum(c)==t:
        #ans=True
if n==1:
    ans=True
print('YES' if ans else 'NO')
n = int(input())
a = list(map(int, input().split()))
a_cur = a[0]

m = 1000
s = 0

for i in range(1, n):
  a_next = a[i]
  elif a_cur < a_next:
    # buy current and sell next
    s = m // a_cur
    m += s * (a_next - a_cur)
    a_cur = a_next
    if s > 0:
      m += s * a[-1]
      print(m)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
# dp[buy][sell]
dp = [0 for j in range(n)]
dp[0] = 1000
for i in range(n):
    ai = a[i]
    m = dp[i]
    s = m // ai

    for j in range(i + 1, n):
        dp[j] = max(dp[j], m + s * (a[j] - ai))

    for j in range(n - 1):
        dp[j + 1] = max(dp[j + 1], dp[j])
print(dp[-1])
# x = input()
# print(x[-1]+x[:-1])
# y = x[-1]+x[:-1]
# print(y[-1]+y[:-1])

count=0

def check():
	count=0
	for i in range(len(a[0])):
		if(a[0][i]!=a[1][i]):
			break
		if(i==int(len(a[0])-1)):
			count=1
			print("Yes")
	return count


def change():
	b=[]
	for i in range(len(a[0])-1):
		b.append(a[1][i+1])
	b.append(a[1][0])

	a[1]=b


###変数を得る
a = []
for i in range(2):
    a.append(input())



check()

if(count==0):
	for i in range(len(a[0])-1):
		change()
		count=check()

		if(count==1):
			break

if(count==0):
	print("No")


### FIXED CODE ###

x=list(map(int,input().split()))
y=sorted(x)
#print(y)
print(abs(y[0]-y[1])+abs(y[2]-y[1]))
#print(int(x[3]-x[2]))
N,M,Q=map(int,input().split())

A=[]
for i in range(Q):
    A.append(list(map(int,input().split())))

C=[]
score = 0
max = 0
for i in range(1,2**(M+1)):
    flg=[0,0,0,0,0,0,0,0,0,0]
    C.clear()
    for j in range(1,M+1):
        if ( i & (1 << (j-1)) ) != 0:
            C.append(j)

    if len(C) < N:
        continue
    score = 0
    for j in range(N):
        if C[A[j][1]-1] - C[A[j][0]-1] == A[j][2]:
            score += A[j][3]
    if max < score and score > 0:
        max = score

print(max)


### FIXED CODE ###

import itertools

N,M,Q=map(int,input().split())

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

score = 0
max = 0

for iter in itertools.combinations_with_replacement(range(1,M+1),N):

    score = 0
    for i in range(Q):
        if iter[A[i][1]] - iter[A[i][0]] == A[i][2]:
            score += A[i][3]

    if max < score:
        max = score


print(max)
from math import factorial
n,m=map(int,input().split())
mod=10**9+7
if abs(n-m)>=2:
  print(0)
elif abs(n-m)==1:
  print((factorial(n,mod)*factorial(m,mod))%mod)
else:
  print((2*factortial(n,mod)*factorial(m,mod))%mod)

### FIXED CODE ###

from math import factorial
n,m=map(int,input().split())
mod=10**9+7
if abs(n-m)>=2:
  print(0)
elif abs(n-m)==1:
  print((factorial(n)%mod*factorial(m)%mod)%mod)
else:
  print((2*factorial(n)%mod*factorial(m)%mod)%mod)
import math

def lcm(a,b):
    return a*b //math.gcd(a,b)

n=int(input())
t=[]
for i in range(n):
    t.append(int(input()))
t.sort()
if(n==1):
    print(t[0])
    exit()
ans=lcm(t[0],t[1])
if(n==2):
    print(ans)
    exit()
for i in range(2,n):
    ans=lcm(ans,t[i])
print(ans)



### FIXED CODE ###

def gcd(x,y):
  if x>y: x,y = y,x
  while x:
    x,y = y%x, x
  return y

def lcm(a,b):
    return a*b //gcd(a,b)

n=int(input())
t=[]
for i in range(n):
    t.append(int(input()))
t.sort()
if(n==1):
    print(t[0])
    exit()
ans=lcm(t[0],t[1])
if(n==2):
    print(ans)
    exit()
for i in range(2,n):
    ans=lcm(ans,t[i])
print(ans)
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <sstream>
#include <queue> 
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm> 
#include <numeric>  
#include <functional>
#include <cassert>
#include <bitset>
#include <cctype>  
#include <iomanip> 
#include <limits>  
#include <regex>
// std::numeric_limits<int>::max(), min()
// std::setprecision(X)
// std::islower(), std::isupper(), std::tolower, std::toupper
// std::accumulate(m.begin(), m.end(), 0LL);
// std::sort(begin(),end()) // 0, 1, 2, 3 ,4 (default, less);
// std::priority_queue<int, vector<int>, less<int>> que; // 4, 3, 2, 1 (defualt, less) : 
// if ( std::regex_match(S, std::regex("(dream|dreamer|erase|eraser)*")) ) std::cout << "YES" << std::endl;
 
#define rep(i, n) for(int i = 0; i < (int)(n);    i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef long long ll;
typedef std::vector<int> vi;
typedef std::vector<std::vector<int>> vvi;

ll gcd ( ll a, ll b ) { if ( b == 0 ) return a; else return gcd ( b, a%b ); }
ll lcm ( ll a, ll b ) { return a * b / gcd(a, b); }


int main (void) {
  std::cin.tie(0);  std::ios::sync_with_stdio(false);

  return 0;
}


### FIXED CODE ###


import numpy as np

N = int(input())
A = [int(x) for x in input().split()]
a = np.array(A)

#mask = a%6==0 or a%10==0 or a%2==1 
mask = np.logical_or.reduce( (a%6==0 , a%10==0, a%2==1) )
if mask.all() : 
    print("APPROVED")
else :
    print("DENIED")
for i in range(1,10):$
    for j in range(1,10):$
       print i,"*",j,"=",i*j$

### FIXED CODE ###

for i in range(1,10):
 for j in range(1,10):
  print "%dx%d=%d" %(i,j,i*j)
A=[int(input()) for i in range(5)]
ans=0
for i in range(5):
    if A[i]%10==0:
        ans+=A[i]
        A[i]=0
B=[str(i) for i in A]
C=[B[i][-1] for i in range(5)]
C=[int(C[i]) for i in range(5)]
D=[None]*5
for i in range(5):
    D[i]=int(B[i])-int(C[i])
E=list([n for n in(sorted(C,reverse=True)) if n>0])
for i in range(len(E)-1):
    ans+=10
ans=ans+E[-1]+int(sum(D))
print(ans)

### FIXED CODE ###

A=[int(input()) for i in range(5)]
ans=0
for i in range(5):
    if A[i]%10==0:
        ans+=A[i]
        A[i]=0
B=[str(i) for i in A]
C=[B[i][-1] for i in range(5)]
C=[int(C[i]) for i in range(5)]
D=[None]*5
for i in range(5):
    D[i]=int(B[i])-int(C[i])
E=list([n for n in(sorted(C,reverse=True)) if n>0])
for i in range(len(E)-1):
    ans+=10
try:
    ans=ans+E[-1]+int(sum(D))
except(IndexError):
    ans=ans+int(sum(D))
print(ans)
N = int(input())
A = list(map(int,input().split()))

if N == 2:
    print(max(A))
    exit()

maxa = max(A)
import fractions
d = []
for i in range(N):
    d.append(fractions.gcd(maxa , A[i]))
d = list(set(d))
d = sorted(d)
print(d[1])


### FIXED CODE ###

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

l = []
r = []
import fractions as fr
l.append(0)
l.append(A[0])
for i in range(1,N-1):
    l.append(fr.gcd(l[i],A[i]))
r.append(0)
r.append(A[-1])
for i in range(1,N-1):
    r.append(fr.gcd(r[i],A[-i-1]))

ans = 0
for i in range(N):
    ans = max(ans, fr.gcd(l[i],r[-i-1]))
print(ans)
import sys
input = sys.stdin.readline

N,M = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

l = [[] for _ in range(M)]
for j in range(M):
    b,c = [int(i) for i in input().split()]
    l[j] = [c,b]

l.sort(reverse=True)
A.sort()
ans = 0

for i,j in l:
    for k in range(N):
        if i <= A[k]:
            break
    k = min(k,j)
    ans += k*i
    A = A[k:]
    print(ans)

print(ans+sum(A))


### FIXED CODE ###

N,M = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
bc = [tuple(int(i) for i in input().split()) for _ in range(M)]

A.sort()
bc.sort(key=lambda t: t[1], reverse=True)

index = 0
count = 0
for i in range(N):
    if index >= M or A[i] >= bc[index][1]:
        break
    A[i] = bc[index][1]
    count += 1
    if bc[index][0] <= count:
        index += 1
        count = 0

print(sum(A))
[N,L] = [int(x) for x in input().split()]
A = {}
B = [True]*N
ANS = {}
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    B[i] = x
    if x in A : A[x] += [i]
    else : A[x] = [i]
for i in sorted(A) :
    for j in A[i] :
        for k in range(L) :
            if j + k not in ANS :
                ANS[j+k] = i
                count += 1
    if (N-count)**2 < N : break

for i in range(N):
    if i not in ANS:
        try :
            ANS[i] = min(B[i+1-L:i+1])
        except IndexError :
            ANS[i] = min(B[:i+1])
for i in range(L-1,N-1) : print(ANS[i], end=" ")
print(ANS[N-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
def get_root(s):
    if s != root[s]:
        root[s] = get_root(root[s])
        return root[s]
    return s

def unite(s, t):
    global c
    root_s = get_root(s)
    root_t = get_root(t)
    if not root_s == root_t:
        c -= union_count[root_s] * union_count[root_t]
        if rank[s] == rank[t]:
            root[root_t] = root_s
            rank[root_s] += 1
            union_count[root_s] += union_count[root_t]
        elif rank[s] > rank[t]:
            root[root_t] = root_s
            union_count[root_s] += union_count[root_t]
        else:
            root[root_s] = root_t
            union_count[root_t] += union_count[root_s]

n, m = map(int, input().split())
root = [i for i in range(n)]
rank = [1 for _ in range(n)]
union_count = [1 for _ in range(n)]
s = [list(map(int, input().split())) for _ in range(m)]
ans = []
c = n * (n - 1) // 2
for _ in range(m):
    t = s.pop()
    unite(t[0] - 1, t[1] - 1)
    ans.append(c)
for i in range(m - 2, -1, -1):
    print(ans[i])
print(n * (n - 1) // 2)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

def get_root(s):
    if s != root[s]:
        root[s] = get_root(root[s])
        return root[s]
    return s

def unite(s, t):
    root_s = get_root(s)
    root_t = get_root(t)
    if not root_s == root_t:
        if rank[s] == rank[t]:
            root[root_t] = root_s
            rank[root_s] += 1
        elif rank[s] > rank[t]:
            root[root_t] = root_s
        else:
            root[root_s] = root_t

def same(s, t):
    if get_root(s) == get_root(t):
        return True
    else:
        return False

def get_size(s):
    return size[get_root(s)]

def update_size(x, y, s):
    size[get_root(s)] = x + y

n, m = map(int, input().split())
c = (n * (n - 1)) // 2
root = [i for i in range(n)]
rank = [1 for _ in range(n)]
size = [1 for _ in range(n)]
ans = [c]
v = [list(map(int, input().split())) for _ in range(m)]
for i in range(m - 1, -1, -1):
    u = v[i]
    u[0] -= 1
    u[1] -= 1
    if not same(u[0], u[1]):
        x = get_size(u[0])
        y = get_size(u[1])
        unite(u[0], u[1])
        update_size(x, y, u[0])
        c -= x * y
    ans.append(c)
for i in range(m - 1, -1, -1):
    print(ans[i])
n,m = map(int,input().split())

a = []
for i in range(m):
    a.append(int(input()))

d = [a[0]-1]
for j in range(1,m):
    d.append(a[j]-a[j-1]-2)

d.append(n-a[m-1]-1)

mm = max(d)

fiblist = [0] * (mm+5)
fiblist[0] = 1
fiblist[1] = 1

for p in range(2,mm+5):
    fiblist[p] = (fiblist[p-1]+fiblist[p-2]) % 1000000007

#print(d)

if -1 in d:
    print(0)
else:
    ans = 1
    for k in range(m+1):
        ans = (ans * fiblist[d[k]]) % 1000000007

    print(ans)


### FIXED CODE ###

fiblist = [0] * 100001
fiblist[0] = 1
fiblist[1] = 1
for p in range(2,100001):
    fiblist[p] = (fiblist[p-1]+fiblist[p-2]) % 1000000007

n,m = map(int,input().split())

if m == 0:
    print(fiblist[n])
else:
    a = []
    for i in range(m):
        a.append(int(input()))

    d = [a[0]-1]
    for j in range(1,m):
        d.append(a[j]-a[j-1]-2)

    d.append(n-a[m-1]-1)




#print(d)

    if (-1 in d) or (-2 in d):
        print(0)
    else:
        ans = 1
        for k in range(m+1):
            ans = (ans * fiblist[d[k]]) % 1000000007

        print(ans)
K = int(input().split()[1])
As = [int(i) for i in input().split()]
As.sort(reverse=True)
print(bin(K))
bit_num = len(bin(K))-2
arr = [[int(s) for s in format(val,'b').zfill(bit_num)] for val in As]
arr = [sum(arr[i][j] for i in range(len(arr))) for j in range(len(arr[0]))]
ans = int("".join(["0" if i>len(arr)/2 else "1" for i in arr]), 2)
ans = ans if ans < K else K
print(sum([ans^i for i in As]))

### FIXED CODE ###

str_ = input().split()
x = int(str_[0])
t = int(str_[1])
print(x/t)
a,b = map(Decimal,input().split())
c = int(a*b)
print(c)

### FIXED CODE ###

from decimal import Decimal
a,b = map(Decimal,input().split())
c = int(a*b)
print(c)
import sys
sys.setrecursionlimit(4100000)
import collections
from math import factorial
n = int(input())
A = [str(input()) for _ in range(n)]
B = []
for a in A:
    B.append("".join(sorted(a)))
B = sorted(B)
C = collections.Counter(B)
ans = 0
for c in C.keys():
    if C[c] >= 2:
        ans += factorial(C[c]) / factorial(2) / factorial(C[c]-2)

print(int(ans))

### FIXED CODE ###

import sys
sys.setrecursionlimit(4100000)
import collections
from math import factorial
from operator import mul
from functools import reduce
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

n = int(input())
A = [str(input()) for _ in range(n)]
for i in range(len(A)):
    A[i] = "".join(sorted(A[i]))
A = sorted(A)
temp = A[0]
counter = 1
ans = 0
for i in range(1,len(A)):
    if temp != A[i]:
        if counter >= 2:
            # ans += factorial(counter) / factorial(2) / factorial(counter-2)
            ans += cmb(counter,2)
        temp = A[i]
        counter = 1
    else:
        counter += 1
if counter >= 2:
    # ans += factorial(counter) / factorial(2) / factorial(counter-2)
    ans += cmb(counter,2)
print(int(ans))
N = input()

tmp = 0
for i in range(len(N)):
    tmp += int(N[i])

if int(N) % tmp == 0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

D, N = map(int, input().split())
if D == 0:
    if N == 100:
        print(101)
    else:
        print(N)
    
else:
    if N == 100:
        print((100 ** D) * (N + 1))
    else:
        print((100 ** D) * N)
N = int(input())
X = int(input(),2)

def popcount(n):
    return bin(n).count('1')


def f(n):
    if n== 0:
        return 1
    count = 1
    while n!=0:
        n = n%popcount(n)
        count += 1
    return count


X_popcount = popcount(X)
X_mod_p = X%(X_popcount+1)
X_mod_m = X%(X_popcount-1)
for i in range(N):
    X_i = X ^ (1<<(N-i-1))
    if X_i == 0:
        ans = 0
    elif X>>(N-i-1)&1 == 1:
        if X_popcount == 1:
            ans = 1
        else:
            ans = f((X_mod_m-pow(2, N-i-1, X_popcount-1))%(X_popcount-1))
    else:
        ans = f((X_mod_p+pow(2, N-i-1, X_popcount+1))%(X_popcount+1))
    print(ans)

### FIXED CODE ###

N = int(input())
X = int(input(),2)

def popcount(n):
    return bin(n).count('1')


def f(n):
    if n== 0:
        return 1
    count = 1
    while n!=0:
        n = n%popcount(n)
        count += 1
    return count


X_popcount = popcount(X)
X_mod_p = X%(X_popcount+1)
if X_popcount != 1:
    X_mod_m = X%(X_popcount-1)
for i in range(N):
    X_i = X ^ (1<<(N-i-1))
    if X_i == 0:
        ans = 0
    elif X>>(N-i-1)&1 == 1:
        if X_popcount == 1:
            ans = 1
        else:
            ans = f((X_mod_m-pow(2, N-i-1, X_popcount-1))%(X_popcount-1))
    else:
        ans = f((X_mod_p+pow(2, N-i-1, X_popcount+1))%(X_popcount+1))
    print(ans)
# -*- coding: utf-8 -*-
 
import math
import itertools
import sys
import copy

# 入力
N, W = map(int, input().split())
H = []
H.append([0,0])
for _ in range(N) :
  S = str(input())
  H.append(list(map(int, S.split())))
#index
Hw = 0
Hv = 1

#print (H)
#Vmax = (10**3) * N
Vmax = (60) * N

#合計価値viのときの最小重量
dp = [[sys.maxsize for _ in range(Vmax+1)] for _ in range(N+1)]


for i in range(1, N+1) :
  if i == 1 : 
    dp[i][H[i][Hv]] = H[i][Hw]
  else :
    dp[i][H[i][Hv]] = min(H[i][Hw], dp[i][H[i][Hv]])
    for j in range(Vmax+1) :
      if dp[i-1][j] != sys.maxsize and (j + H[i][Hv]) <= Vmax+1 :
        dp[i][j + H[i][Hv]] = min(dp[i-1][j + H[i][Hv]], dp[i][j] + H[i][Hw])
  #print (dp[i][:])
  out = copy.deepcopy(dp[i][:])
  line = ""
  for x in range(len(out)) :
      if out[x] == sys.maxsize :
        line += "_" + " "
      else :    
        line += str(out[x]) + " "
  print(line)

for k in range(Vmax) :
  if dp[N][Vmax-k] <= W :
    print(Vmax-k)
    exit()




### FIXED CODE ###

# -*- coding: utf-8 -*-
 
import math
import itertools
import sys
import copy
 
# 入力
N, W = map(int, input().split())
H = []
H.append([0,0])
for _ in range(N) :
  S = str(input())
  H.append(list(map(int, S.split())))
#index
Hw = 0
Hv = 1
 
#print (H)
Vmax = (10**3) * N
#Vmax = (60) * N
 
#合計価値viのときの最小重量
dp = [[sys.maxsize for _ in range(Vmax+1)] for _ in range(N+1)]

for i in range(1, N+1) :
  #Niのvの反映
  dp[i][H[i][Hv]] = min(H[i][Hw], dp[i][H[i][Hv]])
  #VjのときにNiを選んだ場合/選ばない場合
  for j in range(Vmax+1) :
    if dp[i-1][j] != sys.maxsize :
      #Niを選ばないとき
      dp[i][j] = min(dp[i-1][j], dp[i][j])
      #Niを選ぶとき
      if (j + H[i][Hv]) <= Vmax+1 :
        dp[i][j + H[i][Hv]] = min(dp[i-1][j] + H[i][Hw], dp[i][j + H[i][Hv]])
        
  #print (dp[i][:])
  """
  out = copy.deepcopy(dp[i][:])
  line = ""
  for x in range(len(out)) :
      if out[x] == sys.maxsize :
        line += "_" + "\t"
      else :    
        line += str(out[x]) + "\t"
  print(line)
  """

for k in range(Vmax) :
  if dp[N][Vmax-k] <= W :
    print(Vmax-k)
    exit()
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*i+j*j+k*k+i*j+j*k+k*i;
				if v<10050:
					ans[v]+=1
for i in range(n):
	print(ans[i+1])

### 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*i+j*j+k*k+i*j+j*k+k*i;
			if v<10050:
				ans[v]+=1
for i in range(n):
	print(ans[i+1])