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

class RangeUpdate:
    def __init__(self, n):
        self.p = Bit(n + 1)
        self.q = Bit(n + 1)

    def add(self, s, t, x):
        t += 1
        self.p.add(s, -x * s)
        self.p.add(t, x * t)
        self.q.add(s, x)
        self.q.add(t, -x)

    def sum(self, s, t):
        t += 1
        return self.p.sum(t) + self.q.sum(t) * t - \
            self.p.sum(s) - self.q.sum(s) * s


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


def main():
    import sys
    input = sys.stdin.buffer.readline
    N, Q = (int(i) for i in input().split())
    C = [int(i) for i in input().split()]
    Query = [([int(i) for i in input().split()], j) for j in range(Q)]
    Query.sort(key=lambda p: p[0][1])
    lastappend = [0]*(N+1)
    bit = RangeUpdate(N)

    for i, a in enumerate(C, start=1):
        if i <= Query[0][0][1]:
            lastappend[a] = i
    for la in lastappend[1:]:
        if la != 0:
            bit.add(la, la, 1)
    pre = Query[0][0][1]
    ans = []
    for (le, ri), j in Query:
        if pre <= N and pre < ri:
            for i in range(pre+1, ri+1):
                pre_i = lastappend[C[i-1]]
                if pre_i != 0:
                    bit.add(pre_i, pre_i, -1)
                lastappend[C[i-1]] = i
                bit.add(i, i, 1)
            pre = ri
        ans.append((j, bit.sum(le, ri)))
    ans.sort()
    for _, a in ans:
        print(a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

SHIFT = 1 << 20


def main():
    N, Q = (int(i) for i in input().split())
    C = [int(i) for i in input().split()]
    Query = []
    for j in range(Q):
        le, ri = (int(i) for i in input().split())
        Query.append(ri << 40 | le << 20 | j)
    Query.sort()

    # Query復元
    for i in range(Q):
        j = Query[i] % (SHIFT)
        Query[i] >>= 20
        le = Query[i] % (SHIFT)
        Query[i] >>= 20
        ri = Query[i]
        Query[i] = (le, ri, j)
    Query.append((-1, -1, -1))

    def sum(tree, i):
        s = 0
        while i > 0:
            s += tree[i]
            i -= i & -i
        return s

    def add(tree, i, x):
        while i <= N:
            tree[i] += x
            i += i & -i

    lastappend = [-1] * (N + 1)
    bit = [0] * (N + 1)
    idx = 0  # Queryのindex
    ans = [0]*Q

    for i, a in enumerate(C, start=1):
        if lastappend[a] != -1:
            add(bit, lastappend[a], -1)
        lastappend[a] = i
        add(bit, i, 1)
        while i == Query[idx][1]:
            (le, ri, j) = Query[idx]
            ans[j] = sum(bit, ri) - sum(bit, le-1)
            idx += 1

    print(*ans, sep="\n")


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

N = int(input())
s = input()
count = 0

while 'WR' in s:
    w_i = s.find('W')
    r_i = s.rfind('R')
    s = s[:w_i] + 'R' + s[w_i + 1:]
    s = s[:r_i] + 'W' + s[r_i + 1:]
    count += 1

print(count)


### FIXED CODE ###

N = int(input())
s = input()
r_count = s.count('R')
new_s = s[:r_count]
print(new_s.count('W'))
### BUGGY CODE ###

from operator import mul
from functools import reduce
from bisect import bisect_left


def solve(a):
    a.sort()
    max_cmb = cmb(a[1], a[0])
    ans = [a[1], a[0]]
    for ai in a[2:]:
        divided_ai = ai//2
        ak = a[bisect_left(a, divided_ai)]
        q = cmb(ai, ak)
        if a[1] <= ai//2:
            aj = a[bisect_left(a, divided_ai)-1]
            p = cmb(ai, aj)
            if q < p and max_cmb < p:
                ans = [ai, aj]
                max_cmb = p
            elif max_cmb < q:
                ans = [ai, ak]
                max_cmb = q
            else:
                pass

        else:
            if max_cmb < q:
                ans = [ai, ak]
                max_cmb = q

    return str(ans[0]) + ' '+str(ans[1])


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


if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    print(solve(a))


### FIXED CODE ###

from bisect import bisect_left
from sys import stdin



def solve(a):
    a.sort()
    mid = a[n-1]/2
    ai = a[bisect_left(a, mid)-1]
    aj = a[bisect_left(a, mid)]
    am = ai if abs(mid-ai) <= abs(mid-aj) else aj

    print(a[n-1], am)


if __name__ == '__main__':
    n = int(input())
    a = list(map(int, stdin.readline().split()))
    solve(a)
### BUGGY CODE ###

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

ans = 1
for a in A:
    ans *= a

if ans > 1000000000000000000:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

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

ans = 1
for a in A:
    ans *= a
    if  ans > 1000000000000000000:
        break

if 0 in A:
    print(0)
elif ans > 1000000000000000000:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

L,R = map(int,input().split())
a = []
for i in range(L,min(R,L+2019*2)+1):
    a.append(i%2019)
ans = 10**10
b = len(a)
for i in range(b):
    for j in range(b):
        if i<=j:
            break
        ans=min(ans,(a[i]*a[j])%2019)
print(ans)

### FIXED CODE ###

L,R = map(int,input().split())
a = [i for i in range(L,min(L+2019,R)+1)]
b = len(a)
ans = 10**10
for i in range(b):
    for j in range(b):
        if i==j:
            break
        ans = min(ans,a[i]*a[j]%2019)
print(ans)
### BUGGY CODE ###

import math
import sys

X,Y,Z,K=map(int,input().split())

x=sorted(list(map(int,input().split())),reverse=True)
y=sorted(list(map(int,input().split())),reverse=True)
z=sorted(list(map(int,input().split())),reverse=True)



"""
if X*Y*Z<=3000:
    ans=[]
    for i in range(X):
        for j in range(Y):
            for k in range(Z):  ans.append(x[i]+y[j]+z[k])
    ans.sort()
    for i in range(min(3000,X*Y*Z)):
        print(ans[i])
    sys.exit()
"""

yz=[]
for i in range(Y):
    yz=yz+[ y[i]+z[j] for j in range(Z)]

yz.sort(reverse=True)

if len(yz)>K:
    yz=yz[:K]


n=len(yz)
ans=[]

for i in range(X):
    tmp=[yz[j]+x[i] for j in range(len(yz))]
    ans =ans+tmp

ans.sort(reverse=True)


for i in range(K):
    print(ans[i])


### FIXED CODE ###

import math
import sys

X,Y,Z,K=map(int,input().split())

x=sorted(list(map(int,input().split())),reverse=True)
y=sorted(list(map(int,input().split())),reverse=True)
z=sorted(list(map(int,input().split())),reverse=True)



"""
if X*Y*Z<=3000:
    ans=[]
    for i in range(X):
        for j in range(Y):
            for k in range(Z):  ans.append(x[i]+y[j]+z[k])
    ans.sort()
    for i in range(min(3000,X*Y*Z)):
        print(ans[i])
    sys.exit()
"""

ans=[]
for i in range(min(X,K)):
    tmp1=math.ceil(K/(i+1))
    for j in range(min(Y,tmp1)):
        tmp2=math.ceil(tmp1/(j+1))
        for k in range(min(Z,tmp2)):
            ans.append(x[i]+y[j]+z[k])

ans.sort(reverse=True)
for i in range(K):
    print(ans[i])
### BUGGY CODE ###

import collections
n = int(input())

d = {}
ans = []

for i in range(n):
    a = input()
    if a in d:
        d[a] += 1
    else:
        d[a] = 1

ans = [j[0] for j in d.items() if j[1] == max(d.values())]

ans.sort()

print('\n'.join(map(str, ans)))

### FIXED CODE ###

n = int(input())

d = {}

for i in range(n):
    a = input()
    if a in d:
        d[a] += 1
    else:
        d[a] = 1

m = max(d.values())
d = sorted(d.items())

for j in d:
    if j[1] == m:
        print(j[0])
### BUGGY CODE ###

from collections import deque

N = int(input())
ABC = [list(map(int, input().split())) for _ in range(N - 1)]
Q, K = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(Q)]

G = [[0] * N for _ in range(N)]
for a, b, c in ABC:
  G[a - 1][b - 1] = c
  G[b - 1][a - 1] = c

D = [-1] * N
D[K - 1] = 0

q = deque()
q.append(K - 1)
while q:
  n = q.popleft()
  for i in range(N):
    if G[n][i] != 0 and D[i] < 0:
      q.append(i)
      D[i] = D[n] + G[n][i]

for x, y in XY:
  print(D[x - 1] + D[y - 1])

### FIXED CODE ###

from collections import deque

N = int(input())
ABC = [list(map(int, input().split())) for _ in range(N - 1)]
Q, K = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(Q)]

G = [[] * N for _ in range(N)]
for a, b, c in ABC:
  G[a - 1].append((b - 1, c))
  G[b - 1].append((a - 1, c))

D = [-1] * N
D[K - 1] = 0

q = deque()
q.append(K - 1)
while q:
  n = q.popleft()
  for i, c in G[n]:
    if D[i] < 0:
      q.append(i)
      D[i] = D[n] + c

for x, y in XY:
  print(D[x - 1] + D[y - 1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

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

ans = 0
count = 0

num_list.sort()

for index_1, num_1 in enumerate(num_list):
  for index_2, num_2 in enumerate(num_list):
    if index_1 != index_2:
      if num_1 % num_2 == 0:
        break
      else:
        count += 1
  
  if count == n - 1:
    ans += 1

  count = 0

print(ans)

### FIXED CODE ###

import collections
 
n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr)
s=set()
cnt=collections.Counter(arr)
 
for i in range(n):
 if arr[i] in s:
   continue
 if cnt[arr[i]]>=2:
   s.add(arr[i])
 for j in range(2,10**6//arr[i]+1):
   s.add(arr[i]*j)
ans=0
for i in range(n):
 if arr[i] in s:
   continue
 ans+=1
 
print(ans)
### BUGGY CODE ###

import sys
import bisect
A,B,Q = [int(n) for n in input().split()]
# N = int(input())
INF = 10 **18
s = [0]*A
t = [0]*B
x = [0]*Q
s = [-INF] + [int(input()) for n in range(A)] + [INF]
t = [-INF] + [int(input()) for n in range(B)] + [INF]
x = [int(input()) for n in range(Q)]
def binary_search(arry, target):
    result = None
    left = 0
    right = len(arry) - 1

    while left <= right:
        mid = (left + right) // 2
        if arry[mid] == target:
            result = mid
            break
        elif arry[mid] > target:
            right = mid - 1
        else:
            left = mid + 1

    if result == None:
        result = mid
        if(mid+1 < len(arry)):
            result = mid+1 if (abs(arry[mid+1] - target) < abs(arry[mid] - target)) else result
        if(mid-1 >= 0):
            result = mid-1 if (abs(arry[result] - target) > abs(arry[mid-1] - target)) else result
        return result
    else:
        return result+1

for q in x:
    mostntera = binary_search(s,q)
    # print(mostntera)
    tera0 = s[mostntera]
    tera1 = s[mostntera-1] if q-tera0<0 else s[mostntera+1]
    # print(tera0,tera1)
    mostnzin = binary_search(t,q)
    zin0 = t[mostnzin]
    zin1 = t[mostnzin-1] if q-zin0<0 else t[mostnzin+1]
    # print(zin0,zin1)
    ans = INF
    for a in [tera0, tera1]:
        for b in [zin0,zin1]:
            d1,d2 = abs(q-a) +abs(a-b), abs(q-b) + abs(a-b)
            ans = min(ans,d1,d2)
    print(ans)


### FIXED CODE ###

import sys
import bisect
A,B,Q = [int(n) for n in input().split()]
# N = int(input())
INF = 10 **18
s = [0]*A
t = [0]*B
s = [-INF] + [int(input()) for n in range(A)] + [INF]
t = [-INF] + [int(input()) for n in range(B)] + [INF]

for i in range(Q):
    x = int(input())
    b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
    res = INF
    for S in [s[b - 1], s[b]]:
        for T in [t[d - 1], t[d]]:
            d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
            res = min(res, d1, d2)
    print(res)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = [0]
for i in range(n):
    x = 0
    x += b[i] + a[i]
    b.append(x)
b.sort()
check = 1000000000000
ans = 0
for i in range(n+1):
    if b[i] != check:
        y = b.count(b[i])
        ans += y * (y - 1) //2
        check = b[i]
print(ans)
    



### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = [0]
for i in range(n):
    x = 0
    x += b[i] + a[i]
    b.append(x)
b.sort()
check = b[0]
count = 1
ans = 0
for i in range(1,n+1):
    if b[i] == check:
        count += 1
    else:
        ans += count * (count - 1) // 2
        check = b[i]
        count = 1
ans += count * (count - 1) // 2            
print(ans)
### BUGGY CODE ###

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

def kurikaeshi(x, n, mod):
    if n == 1:
        return x
    elif n %2 == 0:
        return kurikaeshi(x, n//2, mod)**2%mod
    elif n %2 == 1:
        return kurikaeshi(x, n//2, mod)**2*x%mod
    
    
def combination(n, a, mod):
    bunbo = 1
    bunshi = 1
    for i in range(a):
        bunshi *= n-i
        bunbo *= a-i
        
    return bunshi*(kurikaeshi(bunbo, mod-2, mod)%mod)
        
        
mod = 10*9+7
answer = kurikaeshi(2, n, mod)
answer -= 1
answer -= combination(n, a, mod)
answer -= combination(n, b, mod)
print(answer%mod)

### FIXED CODE ###

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

def kurikaeshi(x, n, mod):
    if n == 1:
        return x%mod
    elif n %2 == 0:
        return kurikaeshi(x, n//2, mod)**2%mod
    elif n %2 == 1:
        return kurikaeshi(x, n//2, mod)**2*x%mod
    
    
def combination(n, a, mod):
    bunbo = 1
    bunshi = 1
    for i in range(a):
        bunshi *= n-i
        bunshi = bunshi%mod
        bunbo *= a-i
        bunbo = bunbo%mod
        
    return bunshi*pow(bunbo, mod-2, mod)%mod
        
        
mod = 1000000007
answer = pow(2, n, mod)
answer -= 1
answer -= combination(n, a, mod)
answer -= combination(n, b, mod)
print(answer%mod)
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]

# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    """
    BFSを用いて、全マス目を黒くする回数を求める

    Args:
        black_cells: 「開始時の黒マス」の座標が入ったキュー（複数座標あり）
        dist: 「開始時の黒マス」からの距離の入ったリスト  [[-1, -1, 0], ...]
        　　　（白マスの初期値は0）

    Returns:
        g: 操作を繰り返した数
    """
    d = 0
    while black_cells:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]

# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    """
    BFSを用いて、全マス目を黒くする回数を求める

    Args:
        black_cells: 「開始時の黒マス」の座標が入ったキュー（複数座標あり）
        dist: 「開始時の黒マス」からの距離の入ったリスト  [[-1, -1, 0], ...]
        　　　（白マスの初期値は0）

    Returns:
        g: 操作を繰り返した数
    """
    d = 0
    while black_cells:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)
### BUGGY CODE ###

N = int(input())

lst = [[0, 0] for _ in range(N)]
d = 0
for i in range(N):
  x, y = map(int, input().split())
  lst[i][0] = x
  lst[i][1] = y
  
  for j in range(i):
    #print(lst[j], [x, y])
    d = max(d, abs(lst[j][0] - x)+abs(lst[j][1] - y))
  
print(d)

### FIXED CODE ###

N = int(input())

lst = [[0, 0, 0, 0] for _ in range(N)]
p = [0] * N
m = [0] * N

for i in range(N):
  x, y = map(int, input().split())
  lst[i][0] = x
  lst[i][1] = y
  p[i] = x+y
  m[i] = x-y
  
d = max( max(p) - min(p), max(m) - min(m) )
print(d)
### BUGGY CODE ###

primes = [0, 0] + [1] * 9999999
for i in range(2, 3163):
    if primes[i]:
        for j in range(i*i, 10000001, i):
            primes[j] = 0

while True:
    n = int(input())
    if n == 0:
        break
    while not (primes[n-8] and primes[n-6] and primes[n-2] and primes[n]):
        n -= 1
    print(n)

### FIXED CODE ###

import bisect


primes = [0, 0] + [1] * 9999999
for i in range(2, 3163):
    if primes[i]:
        for j in range(i*i, 10000001, i):
            primes[j] = 0

values = [i for i, v in enumerate(primes) if v]
while True:
    n = int(input())
    if n == 0:
        break
    index = bisect.bisect(values, n)
    for i in range(2, index)[::-1]:
        if all(primes[values[i]-j] for j in [0, 2, 6, 8]):
            print(values[i])
            break
### BUGGY CODE ###

import sys
a, b = map(int, input().split())
OKs = []
 
if min(a, b) == 1:
  print(1)
  sys.exit()
  
for i in range(2, min(a, b) + 1):
  if a % i != 0:
    continue
  if b % i != 0:
    continue  
  for ok in OKs:
    if i % ok == 0:
      break
  else:
    OKs.append(i)
print(len(OKs) + 1)

### FIXED CODE ###

a, b = map(int, input().split())
from collections import defaultdict

def comdiv(n):
  end = int(n**0.5) + 2
  dic = defaultdict(lambda: 0)
  for i in range(2, end):
    while n % i == 0:
      n //= i
      dic[i] += 1
  else:
    if n > 1:
      dic[n] = 1
  return dic

A = comdiv(a).keys()
B = comdiv(b).keys()
C = set(A) & set(B)
print(len(C) + 1)
### BUGGY CODE ###

import sys,queue,math,copy,itertools,bisect,collections
LI = lambda : [int(x) for x in sys.stdin.readline().split()]

X,Y,Z,K = LI()
A = LI()
B = LI()
C = LI()

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

h = A[0] + B[0] + C[0]
l = 0
while h > l+1:
    m = (h+l) // 2

    num = 0
    for a in A:
        j = len(C) - 1
        for i in B:
            while i + C[j] < m - a:
                j -= 1
                if j < 0: break
            else:
                num += j + 1
                continue
            break
    if num > K:
        l = m
    else:
        h = m

ans = []
for a in A:
    j = len(C) - 1
    for i in B:
        while i + C[j] < l - a:
            j -= 1
            if j < 0: break
        else:
            for k in range(j+1):
                ans.append(a+i+C[k])
            continue
        break
ans.sort(reverse=True)
print (*ans[:K],sep='\n')



### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections
LI = lambda : [int(x) for x in sys.stdin.readline().split()]

X,Y,Z,K = LI()
A = LI()
B = LI()
C = LI()

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

h = A[0] + B[0] + C[0]
l = 0
while h > l+1:
    m = (h+l) // 2

    num = 0
    for a in A:
        j = len(C) - 1
        for i in B:
            while i + C[j] < m - a:
                j -= 1
                if j < 0: break
            else:
                num += j + 1
                continue
            break
    if num > K:
        l = m
    else:
        h = m

ans = []
cnt = 0
for a in A:
    j = len(C) - 1
    last_cnt = cnt
    for i in B:

        while i + C[j] <= l - a:
            j -= 1
            if j < 0: break
        else:
            for k in range(j+1):
                ans.append(a+i+C[k])
                cnt += 1
            continue
        break
ans.sort(reverse=True)
for _ in range(K-len(ans)):
    ans.append(l)
print (*ans[:K],sep='\n')
### BUGGY CODE ###

import sys
input=sys.stdin.readline

def main():
    H,W = map(int, input().split())
    
    S = []
    for _ in range(H):
        S.append(input().strip()+"#")

    u = [[0]*W for _ in range(H)]
    d = [[0]*W for _ in range(H)]
    l = [[0]*W for _ in range(H)]
    r = [[0]*W for _ in range(H)]
    for y in range(H):
        for x in range(W):
            if S[y][x] == "#":
                u[y][x] = l[y][x] = 0
            else:
                u[y][x] = 1 if y == 0 else u[y-1][x] + 1
                l[y][x] = 1 if x == 0 else l[y][x-1] + 1
    for y in range(H-1,-1,-1):
        for x in range(W-1,-1,-1):
            if S[y][x] == "#":
                d[y][x] = r[y][x] = 0
            else:
                d[y][x] = 1 if y == H-1 else d[y+1][x] + 1
                r[y][x] = 1 if x == W-1 else r[y][x+1] + 1

    ans = 0
    for y in range(H):
        for x in range(W):
            ans = max(ans, u[y][x] + d[y][x] + l[y][x] + r[y][x] - 3)
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline

def main():
    H,W = map(int, input().split())
    
    S = []
    for _ in range(H):
        S.append(input().strip())
 
    u = [[0]*W for _ in range(H)]
    d = [[0]*W for _ in range(H)]
    l = [[0]*W for _ in range(H)]
    r = [[0]*W for _ in range(H)]
    for y in range(H):
        for x in range(W):
            if S[y][x] == "#":
                u[y][x] = l[y][x] = 0
            else:
                u[y][x] = 1 if y == 0 else u[y-1][x] + 1
                l[y][x] = 1 if x == 0 else l[y][x-1] + 1
    for y in range(H-1,-1,-1):
        for x in range(W-1,-1,-1):
            if S[y][x] == "#":
                d[y][x] = r[y][x] = 0
            else:
                d[y][x] = 1 if y == H-1 else d[y+1][x] + 1
                r[y][x] = 1 if x == W-1 else r[y][x+1] + 1
 
    ans = 0
    for y in range(H):
        for x in range(W):
            ans = max(ans, u[y][x] + d[y][x] + l[y][x] + r[y][x] - 3)
            
    print(ans)

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

from collections import deque

S = input()
a = len(S)

for i in range(int(10**5/2)):
    S = S.replace("01","",1)
    S = S.replace("10","",1)

b = len(S)

print(a-b)

### FIXED CODE ###

from collections import deque

S = input()

print(len(S) - abs(S.count("0") - S.count("1")))
### BUGGY CODE ###

n = int(input())
Ai = list(map(int, input().split()))
sum_ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        sum_ans += Ai[i] * Ai[j]
    sum_ans = sum_ans % (10**9 + 7)

print(sum_ans)

### FIXED CODE ###

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

sum_ans = sum(Ai)
ans = 0
mod = 1000000007

for i in range(n-1):
    sum_ans -= Ai[i]
    ans += sum_ans * Ai[i]
    ans %= mod

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

import math

n = int(input())

if n < 6:
    for _ in range(n):
        print(0)
else:
    for _ in range(5):
        print(0)
    for i in range(6, n + 1):
        cnt = 0
        f = int(math.sqrt(n)) + 1
        for x in range(1, f):
            for y in range(1, f):
                for z in range(1, f):
    #                 print(i, x, y, z)
                    if (x ** 2) + (y ** 2) + (z ** 2) + (x * y) + (y * z) + (z * x) == i:
                        cnt += 1

        print(cnt)

### FIXED CODE ###

import math

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

f = int(math.sqrt(n)) + 1
for x in range(1, f):
    for y in range(1, f):
        for z in range(1, f):
            v = (x ** 2) + (y ** 2) + (z ** 2) + (x * y) + (y * z) + (z * x)
            if v < n + 1:
                ans[v] += 1
            
for i in range(n):
    print(ans[i+1])