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


import sys
import itertools


class Treasure:
    def __init__(self, value, weight):
        self.value = value
        self.weight = weight



def solv(treasures, w_limit):
    tvw = (0, 0)
    for ts in t_combinations(treasures):
        w = t_sum_weight(ts)
        if w <= w_limit:
            v = t_sum_value(ts)
            if tvw[0] < v:
                 tvw = (v, w)
            elif tvw[0] == v:
                 if w < tvw[1]:
                     tvw = (v, w)
    return tvw


def t_combinations(t):
    l = len(t)
    for x in range(1, l+1):
        for y in itertools.combinations(t, x):
            yield y


def t_sum_weight(ts):
    return sum(map(lambda x: x.weight, ts))


def t_sum_value(ts):
    return sum(map(lambda x: x.value, ts))


def rightest(tss):
    return reduce(lambda a, b: take_right(a, b), tss)


def take_right(a, b):
    if t_sum_weight(a) <= t_sum_weight(b):
        return a
    else:
        return b


case = 0

while True:
    weight_limit = int(sys.stdin.readline())
    case += 1
    if weight_limit == 0:
        exit()
    n = int(sys.stdin.readline())
    treasures = []
    for i in range(n):
        v, w = map(int, sys.stdin.readline().split(','))
        treasures.append(Treasure(v, w))
    value, weight = solv(treasures, weight_limit)
    print 'Case ' + str(case) + ':'
    print value
    print weight

### FIXED CODE ###


import sys
import itertools


class Treasure:
    def __init__(self, value, weight):
        self.value = value
        self.weight = weight



def solv(treasures, w_limit):
    dp = []
    dp.append(0)
    for n in range(w_limit):
        dp.append(-1)
    for i in treasures:
        for j in range(w_limit - i.weight, -1, -1):
            if dp[j] >= 0:
                dp[j + i.weight] = max(dp[j + i.weight], dp[j] + i.value)
    p = 0
    q = 0
    for i in range(w_limit + 1):
        if dp[i] > p:
            p = dp[i]
            q = i
    return (p, q)






case = 0

while True:
    weight_limit = int(sys.stdin.readline())
    case += 1
    if weight_limit == 0:
        exit()
    n = int(sys.stdin.readline())
    treasures = []
    for i in range(n):
        v, w = map(int, sys.stdin.readline().split(','))
        treasures.append(Treasure(v, w))
    value, weight = solv(treasures, weight_limit)
    print 'Case ' + str(case) + ':'
    print value
    print weight
### BUGGY CODE ###

# coding: utf-8
from itertools import count

def merge(A, left, mid, right, counter):
  n1, n2 = mid - left, right - mid
  L, R = [None]*(n1+1), [None]*(n2+1)
  for i in range(n1):
    L[i] = A[left + i]
  for i in range(n2):
    R[i] = A[mid + i]
  L[n1] = R[n2] = float("inf")
  i = j = 0
  for k in range(left, right):
    next(counter)
    if L[i] <= R[j]:
      A[k] = L[i]
      i = i + 1
    else:
      A[k] = R[j]
      j = j + 1

def mergeSort(A, left, right, counter):
  if left+1 < right:
    mid = (left + right)//2;
    mergeSort(A, left, mid, counter)
    mergeSort(A, mid, right, counter)
    merge(A, left, mid, right, counter)

N = int(input())
A = [int(i) for i in input().split()]
counter = count(0)
mergeSort(A, 0, len(A), counter)
print(*A)
print(next(counter))

### FIXED CODE ###

def merge(A, left, mid, right):
  global counter
  n1, n2 = mid - left, right - mid
  L, R = list(A[left:left+n1]+[float("inf")]), list(A[mid:mid+n2]+[float("inf")])
  i = j = 0
  for k in range(left, right):
    if L[i] <= R[j]:
      A[k] = L[i]
      i += 1
    else:
      A[k] = R[j]
      j += 1
  counter += right - left
def mergeSort(A, left, right):
  if left+1 < right:
    mid = (left + right)//2;
    mergeSort(A, left, mid)
    mergeSort(A, mid, right)
    merge(A, left, mid, right)

N = int(input())
A = [int(i) for i in input().split()]
counter = 0
mergeSort(A, 0, len(A))
print(*A)
print(counter)
### BUGGY CODE ###

S = list(input())
Quve = S
count = 0
flag = 0
Quve.append("")
while(flag ==0):
    tmp = count
    for i in range(len(Quve)-1):
        if ((Quve[i]=="0") & (Quve[i+1]=="1")) | ((Quve[i]=="1") & (Quve[i+1]=="0")):
            del Quve[i]
            del Quve[i]
            count += 2
            break
    if (tmp == count):
        flag = 1
print(count)


### FIXED CODE ###

#TLE
# 0と1を数えて少ないほうの2倍を取れば勝ち
S = list(input())
count0 = 0
count1 = 0
for i in range(len(S)):
    if S[i]=='0':
        count0 += 1
    else:
        count1 += 1
print(2*min(count0,count1))
### BUGGY CODE ###

def make_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
n=int(input())
ans=[0]*n
count=[0]*n

a=list(map(int,input().split()))
for i in range(n,0,-1):
    if count[i-1]%2!=a[i-1]:
        ans[i-1]=1
        b=make_divisors(i)
        for j in b:
            count[j-1]+=1
print(sum(ans))
kai=[]
for i in range(n):
    if ans[i]==1:
        kai.append(i+1)
print(*kai)

### FIXED CODE ###

def make_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
n=int(input())
ans=[0]*n
count=[0]*n

a=list(map(int,input().split()))
for i in range(n,0,-1):
    if count[i-1]%2!=a[i-1]:
        ans[i-1]=1
        b=make_divisors(i)
        for j in b:
            count[j-1]+=1
print(sum(ans))
kai=[]
for i in range(n):
    if ans[i]==1:
        kai.append(i+1)
print(*kai)
### BUGGY CODE ###

N = input()
A = input().split()
ans = 1
for i in A:
    ans = ans * int(i)
    if ans == 0:
        break
        
if ans > 10 ** 18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

N = input()
A = list(map(int, input().split()))
A.sort()
ans = 1
for i in A:

    ans = ans * i
    if ans == 0:
        break
    if ans > 1000000000000000000:
        ans = -1
        break

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

H,W = map(int , input().split())
sh,sw = map(int , input().split())
eh,ew = map(int , input().split())
mv_a_pts = [[-1,0],[1,0],[0,-1],[0,1]]
mv_b_pts = []
for h in range(-2,3,1):
  for w in range(-2,3,1):
    if h != 0 or w != 0:
      mv_b_pts.append([h,w])
maze = []
warp_cnts = [[None]*(W) for j in range(H)]
for i in range(H):
  maze.append(input())

def mv_a(h,w):
  mv_b_tgs.append([h,w])
  warp_cnts[h][w] = cnt
  for vh,vw in mv_a_pts:
    tgh = h + vh
    tgw = w + vw
    if 0 <= tgh <= H-1 and 0 <= tgw <= W-1 :
      if warp_cnts[tgh][tgw] is None and maze[tgh][tgw] != "#":
        mv_a(tgh,tgw)

def mv_b(h,w):
  for vh,vw in mv_b_pts:
    tgh = h + vh
    tgw = w + vw
    if 0 <= tgh <= H-1 and 0 <= tgw <= W-1 :
      if warp_cnts[tgh][tgw] is None and maze[tgh][tgw] != "#":
        mv_a_tgs.append([tgh,tgw])


mv_b_tgs=[]
mv_a_tgs = [[sh-1,sw-1]]
cnt = 0
while len(mv_a_tgs)>0:
  while len(mv_a_tgs):
    tg = mv_a_tgs.pop()
    mv_a(tg[0],tg[1])
  while len(mv_b_tgs):
    wp = mv_b_tgs.pop()
    mv_b(wp[0],wp[1])
  cnt+=1
print(-1 if warp_cnts[eh-1][ew-1] is None else warp_cnts[eh-1][ew-1])

### FIXED CODE ###

from collections import deque
 
 
walk = [(1, 0), (-1, 0), (0, 1), (0, -1)]
warp = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),
        (-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2),
        (0, -2), (0, -1), (0, 1), (0, 2),
        (1, -2), (1, -1), (1, 0), (1, 1), (1, 2),
        (2, -2), (2, -1), (2, 0), (2, 1), (2, 2),]
 
 
def get_warped(walked, map_):
    warped = deque()
    while walked:
        h, w = walked.popleft()
        for i, j in warp:
            h2 = h + i
            w2 = w + j
            if -1 < h2 < H and -1 < w2 < W and map_[h2][w2] == '.':
                warped.append((h2, w2))
                map_[h2][w2] = map_[h][w] + 1
    return warped, map_
 
 
def get_walked(candidate, map_):
    walked = deque()
    while candidate:
        h, w = candidate.popleft()
        walked.append((h, w))
        for i, j in walk:
            h2 = h + i
            w2 = w + j
            if -1 < h2 < H and -1 < w2 < W and map_[h2][w2] == '.':
                candidate.append((h2, w2))
                map_[h2][w2] = map_[h][w]
    return walked, map_
 
H, W = map(int, input().split())
s_h, s_w = [i-1 for i in map(int, input().split())]
d_h, d_w = [i-1 for i in map(int, input().split())]
map_ = [list(input()) for i in range(H)]
 
candidate = deque([(s_h, s_w)])
map_[s_h][s_w] = 0
 
while candidate:
    walked, map_ = get_walked(candidate, map_)
    candidate, map_ = get_warped(walked, map_)
 
for h in range(H):
    for w in range(W):
        if map_[h][w] == '.':
            map_[h][w] = -1
 
print(map_[d_h][d_w])
### BUGGY CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i&-i
        return s
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i&-i
n, q = map(int, input().split())
c = list(map(int, input().split()))
last = [-1]*n
foradd = [[] for i in range(n)]
for i in range(n):
    if last[c[i]-1] != -1: foradd[last[c[i]-1]].append(i)
    last[c[i]-1] = i
forsum = [[] for i in range(n)]
for i in range(q):
    l, r = map(int, input().split()); l -= 1; r -= 1
    forsum[l].append([r, i])
bit = Bit(n); ans = [-1]*q
for i in range(n-1, -1, -1):
    for j in foradd[i]: bit.add(j, 1)
    for j in forsum[i]: ans[j[1]] = j[0]-i+1-bit.sum(j[0])
print(*ans, sep="\n")

### FIXED CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i&-i
        return s
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i&-i
n, q = map(int, input().split())
c = list(map(int, input().split()))
last = [-1]*n
foradd = [[] for i in range(n)]
for i in range(n):
    if last[c[i]-1] != -1: foradd[last[c[i]-1]].append(i)
    last[c[i]-1] = i
forsum = [[] for i in range(n)]
for i in range(q):
    l, r = map(int, input().split()); l -= 1; r -= 1
    forsum[l].append([r, i])
bit = Bit(n); ans = [-1]*q
for i in range(n-1, -1, -1):
    for j in foradd[i]: bit.add(j, 1)
    for j in forsum[i]: ans[j[1]] = j[0]-i+1-bit.sum(j[0])
print(*ans, sep="\n")
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import deque

N, M , K = [int(x) for x in input().split()]
AB = []
G_F = [deque([]) for _ in range(N)]
G_B = [deque([]) for _ in range(N)]
for _ in range(M):
    AB = [int(x) for x in input().split()]
    G_F[AB[0] - 1].append(AB[1] - 1)
    G_F[AB[1] - 1].append(AB[0] - 1)
CD = []
for _ in range(K):
    CD = [int(x) for x in input().split()]

    G_B[CD[0] - 1].append(CD[1] - 1)
    G_B[CD[1] - 1].append(CD[0] - 1)

ans = 0
from collections import deque
G_F = deque(G_F)
G_B = deque(G_B)

# グラフの作成(無向グラフでは#を消す)

time = 0
arrive_time = [-1] * (N) # 到着時刻

# 深さ優先探索
def dfs(v, graph):
    global time
    time += 1
    stack = [v]
    arrive_time[v] = time
    while stack:
        v = stack[-1]
        if graph[v]:
            w = graph[v].popleft()
            if arrive_time[w] < 0:
                time += 1
                arrive_time[w] = time
                stack.append(w) 
        else:
            stack.pop()          
    return arrive_time
import copy
ans = [0] * N
for i in range(N - 1):
    for j in range(i + 1, N):
        arrive_time = [-1] * N
        if j in G_B[i] or j in G_F[i]:
            continue
        graph = copy.deepcopy(G_F)
        arrive_time = dfs(i, graph)
        if arrive_time[j] > 0:
            ans[i] += 1
            ans[j] += 1

print(*ans)




### FIXED CODE ###

import sys
input = sys.stdin.readline
 
n,m,k = map(int,input().split())
ab = [set() for _ in range(n)]
cd = [[] * n for _ in range(n)]

 
#Union Find
 
#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True
 
#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]
 
#初期化
#根なら-size,子なら親の頂点
par = [-1]*n

for _ in range(m):
    a, b = [int(x) for x in input().split()]
    unite(a - 1, b - 1)
    ab[a - 1].add(b - 1)
    ab[b - 1].add(a - 1)

for i in range(k):
    c, d = [int(x) for x in input().split()]
    if same(c - 1, d - 1):
        cd[c - 1].append(d - 1)
        cd[d - 1].append(c - 1)

ans = [0] * n

for i in range(n):
    ans[i] = size(i) - 1 - len(cd[i]) - len(ab[i])

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

# D - Integer Cards
import heapq

n, m = map(int, input().split())
A = list(int(x) for x in input().split())

heapq.heapify(A)

for j in range(m):
    b, c = map(int, input().split())
    for i in range(b):
        a = heapq.heappop(A)
        if a<c:
            heapq.heappush(A, c)
        else:
            heapq.heappush(A, a)
            break

print(sum(A))

### FIXED CODE ###

# D - Integer Cards

import heapq
from collections import Counter

n, m = map(int, input().split())
A = list(int(x)*-1 for x in input().split())

C = Counter(A)
L = list(C.items())

for j in range(m):
    b, c = map(int, input().split())
    L.append((-c, b))

heapq.heapify(L)

ans = 0
for i in range(n):
    p, q = heapq.heappop(L)
    ans += p
    if q>1:
        heapq.heappush(L, (p, q-1))

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

import sys
import heapq
 
input = sys.stdin.readline
n, m = map(int, input().split())
A = list(map(int, input().split()))
heapq.heapify(A)
 
for _ in range(m):
    b, c = map(int, input().split())
    for i in range(b):
        heapq.heappushpop(A, c)
 
print(sum(A))

### FIXED CODE ###

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]
BC.sort(key=lambda x: -x[1])

maxi = n*2
extend = A.extend
[extend([ls[1]] * ls[0]) for ls in BC if len(A) <= maxi]
A.sort(reverse=True)

print(sum(A[:n]))
### BUGGY CODE ###

S=list(input())
c=0
while len(S)>1:
    before=len(S)
    for i in range(len(S)-1):
        #print(S[i]+S[i+1])
        if S[i]+S[i+1]=="01" or S[i]+S[i+1]=="10":
            c+=2
            S.pop(i)
            S.pop(i)
            break
    after=len(S)
    if before==after:
        break

#print(S)
print(c)


### FIXED CODE ###

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

def main():
    N, M, K = map(int, input().split())

    fac = [0] * N
    fac[0] = 1
    for i in range(N - 1):
        fac[i + 1] = fac[i] * (i + 1) % 998244353

    def mcomb(n, k, fac):
        if n == 0 and k == 0:
            return 1
        if n < k or k < 0:
            return 0
        return fac[n] * pow(fac[n - k], 998244351, 998244353) * pow(fac[k], 998244351, 998244353) % 998244353

    result = 0
    for i in range(K + 1):
        result += mcomb(N - 1, i, fac) * pow(M - 1, N - 1 - i, 998244353)
        result %= 998244353
    result *= M
    result %= 998244353
    print(result)


main()


### FIXED CODE ###

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

result = 0
n = 1
k = 1
for i in range(K + 1):
    result += n * pow(k, 998244353 - 2, 998244353) * pow(M - 1, N - 1 - i, 998244353)
    result %= 998244353
    n *= N - 1 - i
    n %= 998244353
    k *= i + 1
    k %= 998244353
result *= M
result %= 998244353
print(result)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
flag = [True] * n
for i in range(n):
    if not flag[i]: continue
    for j in range(i + 1, n):
        if a[j] % a[i] == 0:
            flag[j] = False
            if a[i] == a[j]:
                flag[i] = False
print(flag.count(True))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
flag = [True] * (a[-1] + 1)
memo = -1
for i in a:
    if memo == i:
        flag[i] = False
        continue
    memo = i
    tmp = 2 * i
    while tmp <= a[-1]:
        flag[tmp] = False
        tmp += i
ans = 0
for i in a:
    if flag[i]: ans += 1
print(ans)
### BUGGY CODE ###

n=int(input())
a=[int(i) for i in input().split()]
a.sort()
q=int(input())
bc=[]
for i in range(q):
    bc.append([int(i) for i in input().split()])

import collections
collect = collections.Counter(a)
#print(collect)

for i in bc:
    #if i[0] in collect.keys():
    if i[1] in collect.keys():
        collect[i[1]] += collect.pop(i[0],0)
    else:
        collect[i[1]] = collect.pop(i[0],0)
    ans=0
    for k in collect.keys():
        ans += (k * collect[k])
    print(ans)

### FIXED CODE ###

#sum を計算しておく
n=int(input())
a=[int(i) for i in input().split()]
a.sort()
q=int(input())
bc=[]
for i in range(q):
    bc.append([int(i) for i in input().split()])

import collections
collect = collections.Counter(a)

ans=0
for k,v in collect.items():
    ans += (k * v)
for i in bc:
    if i[0] in collect:
        if i[1] in collect:
            ans += ((i[1]-i[0]) * collect[i[0]])
            collect[i[1]] += collect.pop(i[0],0)
        else:
            ans += ((i[1]-i[0]) * collect[i[0]])
            collect[i[1]] = collect.pop(i[0],0)
    print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
x = n
r = 0
pre_x = x
while True:
	if k == 1 or n == 0:
		break
	pre_x = x
	x = abs(x - k)
	if pre_x < x:
		r = pre_x
		break
print(r)

### FIXED CODE ###

n, k = map(int, input().split())
x = n
r = 0
x = n - (n // k) * k
pre_x = x
while True:
	if k == 1 or n == 0:
		break
	pre_x = x
	x = abs(x - k)
	if pre_x < x:
		r = pre_x
		break
print(r)
### BUGGY CODE ###

import numpy as np
import collections
import math

s = input()[::-1]
length = len(s)
a = [0] * length
d = [0] * length

for i in range(length):
    a[i] = int(s[i]) * pow(10, i) % 2019
d[0] = a[0]

for i in range(length-1):
    d[i+1] = (d[i] + a[i+1]) % 2019
    
x = np.array([i for i in collections.Counter(d).values()])
x = x[np.where(x > 1)]

print(int(sum([math.factorial(x[i]) for i in range(x.shape[0])]) / 2) + d.count(0))

### FIXED CODE ###

import numpy as np

s = input()[::-1]
length = len(s)
a = np.zeros(length, dtype=int)
d = np.zeros(length, dtype=int)
ans = np.zeros(2019, dtype=int)
x = 10

a[0] = int(s[0])
d[0] = a[0]
ans[d[0]] += 1

for i in range(1, length):
    a[i] = int(s[i]) * x % 2019
    d[i] = (d[i-1] + a[i]) % 2019
    ans[d[i]] += 1
    x = x * 10 % 2019

ans_c = ans[np.nonzero(ans)]

print(int(sum([ans_c[i] * (ans_c[i]-1) for i in range(ans_c.shape[0])]) / 2) + ans[0])
### BUGGY CODE ###

def Comb(n,k):
    comb_ans=1
    for i in range(1,k+1):
        comb_ans*=(n-i+1)/i
    comb_ans=int(comb_ans)
    return comb_ans

N=int(input())
S=[str(sorted(input())) for i in range(N)]
T=set(S)
ans=0
for i in T:
    cnt=S.count(i)
    ans+=Comb(cnt,2)
#print(S)
#print(T)
print(ans)

### FIXED CODE ###

import collections
def Comb(n,k):
    comb_ans=1
    for i in range(1,k+1):
        comb_ans*=(n-i+1)/i
    comb_ans=int(comb_ans)
    return comb_ans

N=int(input())
S=[''.join(sorted(input())) for i in range(N)]
T=collections.Counter(S)
ans=0
for i in T.most_common():
    ans+=Comb(i[1],2)
#print(S)
#print(T)
print(ans)
### BUGGY CODE ###

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

r = s.count('R')
g = s.count('G')
b = s.count('B')

cnt = 0

for i in range(n-2):
    for j in range(i+1, n-1):
        k = 2*j - i
        if 2 <= k <= n-1:
            if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
                cnt += 1
print(r*g*b - cnt)

### FIXED CODE ###

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

r = s.count('R')
g = s.count('G')
b = s.count('B')

cnt = 0

for i in range(n-2):
    for j in range(i+1, n-1):
        k = 2*j - i
        if 2 <= k <= n-1:
            if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
                cnt += 1
        else:
            break
print(r*g*b - cnt)
### BUGGY CODE ###

import math
n = int(input())

a = int(math.sqrt(n))
for j in range(a,n):
	if n%j == 0 and n/j >0:
		print(int(n/j+j-2))
		break
	


### FIXED CODE ###

N = int(input())
a,b = 0,0
t = 10**13
for i in range(1,int(N**0.5)+1):
	if N%i == 0:
		if t >= N//i + i:
			t = N//i + i
			


print(t-2)
### BUGGY CODE ###

def rec(h,w,s):
    res = 0
    for dh,dw in [[1,0],[0,1]]:
        nh,nw = h+dh,w+dw
        if 0 <= nh < H and 0 <= nw < W and C[nh][nw].isdigit():
            res = max(res, rec(nh,nw,s+C[nh][nw]))
    return res if res > 0 else int(s)

while 1:
    W,H = map(int,raw_input().split())
    if W == 0: break
    C = [list(raw_input()) for _ in xrange(H)]
    ans = 0
    for h in xrange(H):
        for w in xrange(W):
           if C[h][w].isdigit():
               ans = max(ans, rec(h,w,C[h][w]))
    print ans

### FIXED CODE ###

while 1:
    W,H = map(int,raw_input().split())
    if W == 0: break
    C = [list(raw_input()) for _ in xrange(H)]
    dp = [[0]*W for _ in xrange(H)]
    ans = 0
    for h in xrange(H):
        for w in xrange(W):
            if C[h][w].isdigit():
                dp[h][w] = max(dp[h][w],int(C[h][w]))
                if w > 0: dp[h][w] = max(dp[h][w],int(str(dp[h][w-1])+C[h][w]))
                if h > 0: dp[h][w] = max(dp[h][w],int(str(dp[h-1][w])+C[h][w]))
    print max(max(i) for i in dp)
### BUGGY CODE ###

N,K,C = map(int,input().split())
S = str(input())
works1 = 0
works2 = 0
l1 = []
l2 = []
i = 0
while i < N and works1 < K:
  if S[i] == "o":
    l1.append(i+1)
    i = i+C+1
    works1 += 1
  else:
    i = i+1
i = N-1
while i > -1 and works2 < K:
    if S[i] == "o":
      l2.append(i+1)
      i = i-C-1
      works2 = works2+1
    else:
      i = i-1

for i in range(len(l1)):
  if l1[i] in l2 :
    print(l1[i])

### FIXED CODE ###

N,K,C = map(int,input().split())
S = str(input())
works1 = 0
works2 = 0
l1 = []
l2 = []
i = 0
while i < N and works1 < K:
  if S[i] == "o":
    l1.append(i+1)
    i = i+C+1
    works1 += 1
  else:
    i = i+1
i = N-1
while i > -1 and works2 < K:
    if S[i] == "o":
      l2.append(i+1)
      i = i-C-1
      works2 = works2+1
    else:
      i = i-1

for i in range(len(l1)):
  if l1[i] == l2[-i-1] :
    print(l1[i])
### BUGGY CODE ###

def gcd(a,b):
    if not b: return a
    return gcd(b,a%b)

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

N = int(input())
A = list(map(int,input().split()))
l = 1
ans, mod = 0, 1000000007

for x in A:
    l = lcm(l, x)

for x in A:
    ans = ans + l//x
    if ans > mod: ans = ans % mod
print(ans)


### FIXED CODE ###

def gcd(a,b):
    if not b: return a
    return gcd(b,a%b)

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

N = int(input())
A = list(map(int,input().split()))
l = 1
ans, mod = 0, 1000000007

for x in A:
    l = lcm(l, x)

for x in A:
    ans = ans + l//x
print(ans % mod)
### BUGGY CODE ###

N = int(input())
c = 0
n = 0
list = []
for l in range(1,N+1):
    list = []
    for i in range(1,N+1):
        if i*i > l:
            break;        
        for j in range(1,N-i):
            if i*i + j*j + i*j > l:
                break;
            for k in range(1,N-j):
                #print(i,j,k,l)
                if i*i + j*j + k*k + i*j +j*k + i*k > l:
                    break;
                if i*i + j*j + k*k + i*j +j*k + i*k == l:
                    list.append(1)
                    break;
    print(sum(list))

### FIXED CODE ###

N = int(input())
list = [0]*(N+1)
for i in range(1,100):  
    for j in range(1,100):
        a = i*i + j*j + i*j
        for k in range(1,100):
            a = i*i + j*j + k*k + i*j +j*k + i*k
            if a <= N:
                list[a] += 1
for i in range(1,N+1):
    print(list[i])