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

S = input()
Q = int(input())
query = []
for _ in range(Q):
    q = list(input().split())
    if len(q) != 1:
        q = [int(x) for x in q[:2]] + [q[2]]
    else:
        q = list(map(int, q)) + [0, '']
    query.append(q)

S = list(S)
forward = 1
for t, f, c in query:
    if t == 1:
        forward *= -1
    else:
        if f == 1:
            if forward == 1:
                S.insert(0, c)
            else:
                S.append(c)
        else:
            if forward == 1:
                S.append(c)
            else:
                S.insert(0, c)
if forward == -1:
    S = list(reversed(S))
print(''.join(S))


### FIXED CODE ###

S = input()
Q = int(input())
query = [list(input().split()) for _ in range(Q)]
forward = 1
f = ''
b = ''
for i in range(Q):
    if query[i][0] == '1':
        forward *= -1
    else:
        if query[i][1] == '1':
            if forward == 1:
                f += query[i][2]
            else:
                b += query[i][2] 
        else:
            if forward == 1:
                b += query[i][2] 
            else:
                f += query[i][2]
S = ''.join(list(reversed(f))) + S + b

if forward == -1:
    ans = ''.join(list(reversed(S)))
else:
    ans = S
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for i in [0] * N ]

for i in range(N):
  print(max(A[:i] + A[i+1:]))

### FIXED CODE ###

N = int(input())
A = [int(input()) for i in [0] * N ]
M = max(A)
m = sorted(A)[-2]
for i in A:
  if i == M:
    print(m)
  else:
    print(M)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

mod = 10**9+7


def main():
    N = int(input())
    X = list(map(int, input().split()))
    D = [0 for i in range(N)]

    for i in range(N-1):
        D[i] = X[i+1] - X[i]

    import math
    n = math.factorial(N-1)

    ans = 0
    r = 0
    for i in range(1, N):
        r += n // i
        ans += D[i-1] * r
        ans %= mod
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import math
input = sys.stdin.readline

mod = 10**9+7


def main():
    N = int(input())
    r1 = [1]
    for i in range(N-1):
        r1.append(r1[i] * (i+1) % mod)
    r2 = [1]
    for i in range(N-1):
        r2.append(r2[i] * (N-1-i) % mod)

    X = list(map(int, input().split()))
    D = [0 for i in range(N)]
    for i in range(N-1):
        D[i] = X[i+1] - X[i]

    ans = 0
    r = 0
    for i in range(N):
        r += r1[i] * r2[N-i-2]
        ans += D[i] * r
        ans %= mod
    print(ans)


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

#C
N, K = map(int, input().split())
A = list(map(int, input().split()))
p=[]
for i in range(N-K+1):
    ans=1
    for x in range(K):
        ans=ans*A[i+x]
    p.append(ans)

for j in range(len(p)-1):
    if p[j]<p[j+1]:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

#C
N, K = map(int, input().split())
A = list(map(int, input().split()))
p=[]
for i in range(N-K):
    if A[i+K]>A[i]:
        p.append(1)
    else:
        p.append(0)

for j in range(len(p)):
    if p[j]==1:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

N = int(input())
a = [int(i) for i in input().split()]
b =[]

for i in range(1,N+1):
    b.append(a.index(i) + 1)

print(*b, sep=' ')

### FIXED CODE ###

N = int(input())
a = [int(i) for i in input().split()]
b = sorted(a)
c = []

dic = dict(zip(a , b))

for i in range(1,N+1):
    c.append(dic[i])

print(*c)
### BUGGY CODE ###

from fractions import gcd
from functools import lru_cache

M = 10 ** 9 + 7

@lru_cache(maxsize=None)
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

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

lcm_ = A[0]
for a in A[1:]:
    lcm_ = lcm_ * a // gcd(lcm_, a)

ans = 0
for a in A:
    m = modinv(a, M)
    ans = (ans + lcm_ * m) % M

print(ans)

### FIXED CODE ###

from fractions import gcd

M = 10 ** 9 + 7

def xgcd(a, b):
    x0, x1 = 1, 0
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
    return x0 % M

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

lcm_ = A[0]
for a in A[1:]:
    lcm_ = lcm_ * a // gcd(lcm_, a)

ans = 0
for a in A:
    m = xgcd(a, M)
    ans = ans + lcm_ * m

print(ans % M)
### BUGGY CODE ###

N = int(input())
S = input()
Q = int(input())
*k, = map(int, input().split())

lc = [1 if s=="C" else 0 for s in S]
ld = [1 if s=="D" else 0 for s in S]

ac = [0]*(N+1)
for i in range(1, N+1):
    ac[i] = ac[i-1] + lc[i-1]

ans = 0

for a in k:
    ans = 0
    for i, s in enumerate(S):
        if s!="M":
            continue
        for j in range(max(i-a, 0), i):
            ans += ld[j]*(ac[min(a+j, N)]-ac[i])
    print(ans)

### FIXED CODE ###

N = int(input())
S = input()
Q = int(input())
*k, = map(int, input().split())

acd = [0]*(N+1)
acm = [0]*(N+1)
acc = [0]*(N+1)
acmc = [0]*(N+2)

for i in range(1, N+1):
    acd[i] = acd[i-1] + (S[i-1]=="D")
    acm[i] = acm[i-1] + (S[i-1]=="M")
    acc[i] = acc[i-1] + (S[i-1]=="C")

ans = 0
for i in range(1, N+1):
    if S[i-1]=="M":
        ans += acd[i-1]*(acc[N]-acc[i])

for i in range(1, N)[::-1]:
    acmc[i] += acmc[i+1]
    if S[i-1]=="M":
        acmc[i] += acc[N]-acc[i]

for i in k:
    v = 0
    for j in range(1, N+1):
        if S[j-1]=="D":
            v += (acm[min(N, i+j-1)]-acm[j]) * (acc[N]-acc[min(N, i+j-1)]) + acmc[min(i+j, N)]
    print(ans-v)
### BUGGY CODE ###

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

n, q = map(int, input().split())
c = list(map(int, input().split()))
lr = []
for i in range(q):
    l, r = map(int, input().split())
    lr.append((l, r, i))

# 1-indexed
left_index_dict = {}
d = defaultdict(int)

for i, ci in enumerate(c):
    index = d[ci]
    if index in left_index_dict:
        left_index_dict[index].append(i+1)
    else:
        left_index_dict[index] = [i+1]
    d[ci] = i + 1

lr.sort()

index = list(left_index_dict.keys())
index.sort()
i = 0

N = n
bit = [0] * (N+1)

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

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

ans = [0] * q

for l, r, _i in lr:
    while i < len(index) and index[i] < l:
        for j in left_index_dict[index[i]]:
            add(j, 1)
        i += 1
    ans[_i] = sum(r) - sum(l-1)

for ansi in ans:
    print(ansi) 
    



    


### FIXED CODE ###

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

n, q = map(int, input().split())
c = list(map(int, input().split()))
lr = []
for i in range(q):
    l, r = map(int, input().split())
    lr.append((l, r, i))

# 1-indexed
left_index_dict = {}
d = defaultdict(int)

for i, ci in enumerate(c):
    index = d[ci]
    if index in left_index_dict:
        left_index_dict[index].append(i+1)
    else:
        left_index_dict[index] = [i+1]
    d[ci] = i + 1

lr.sort(key=lambda x:x[0])

index = list(left_index_dict.keys())
index.sort()
i = 0

N = n
bit = [0] * (N+1)

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

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

ans = [0] * q

for l, r, _i in lr:
    while i < len(index) and index[i] < l:
        for j in left_index_dict[index[i]]:
            add(j, 1)
        i += 1
    ans[_i] = sum(r) - sum(l-1)

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

import sys
sys.setrecursionlimit(1000000)
n, q = map(int, input().split())
edge = [set() for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    edge[a-1].add(b-1)
    edge[b-1].add(a-1)

cost = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    cost[p-1] += x

ans = [0] * n
def dfs(cur, c, root):
    # print(cur, c, root)
    ans[cur] = c
    for next in edge[cur]:
        if next != root:
            dfs(next, c + cost[next], cur)

dfs(0, cost[0], -1)
print(*ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

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

connect = [set() for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    connect[a-1].add(b-1)
    connect[b-1].add(a-1)

counter = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    counter[p-1] += x

ans = [0] * n
def dfs(me, parent, cum):
    cum += counter[me]
    ans[me] = cum
    for child in connect[me]:
        if child != parent:
            dfs(child, me, cum)

dfs(0, -1, 0)

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

n,k = map(int,input().split())
while(True):
    if n > abs(n-k):
        n=abs(n-k)
    else:
        break
print(n)

### FIXED CODE ###

n,k = map(int,input().split())
ans = min(n%k,k-(n%k))
print(ans)
### BUGGY CODE ###

n, a, b = map(int, input().split())
l = []
i = 0
res = 0

while i < n:
    save = i
    i += a
    if i < n:
        res += a
        i += b
    elif i > n:
        res += n - save

print(res)

### FIXED CODE ###

n, a, b = map(int, input().split())
k = a + b
i = 0
res = 0

y = n // k  
res += y * a

x = k * y

if x + a <= n:
    res += a
elif x + a > n:
    res += n - x
    
print(res)
### BUGGY CODE ###

from collections import deque
n, m = map(int, input().split())
p = list(map(int, input().split()))
paths = {}
for _ in range(m):
    x, y = map(int, input().split())
    if not x in paths.keys():
        paths[x] = [y]
    else:
        paths[x].append(y)
    if not y in paths.keys():
        paths[y] = [x]
    else:
        paths[y].append(x)

connected = [None]*(n+1)
path_id = 1
for i in range(1, n+1):
    if connected[i] is None:
        connected[i] = path_id
    else:
        continue
    que = deque(paths[i]) if i in paths.keys() else []
    while len(que) > 0:
        j = que.popleft()
        connected[j] = path_id
        for k in paths[j]:
            if connected[k] is None:
                que.append(k)
    path_id += 1
# print(connected)

ans = 0
for i in range(n):
    if connected[i+1] == connected[p[i]]:
        ans += 1
print(ans)


### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
p = list(map(int, input().split()))
paths = {}
for _ in range(m):
    x, y = map(int, input().split())
    if not x in paths.keys():
        paths[x] = [y]
    else:
        paths[x].append(y)
    if not y in paths.keys():
        paths[y] = [x]
    else:
        paths[y].append(x)

connected = [None]*(n+1)
path_id = 1
for i in range(1, n+1):
    if connected[i] is None:
        connected[i] = path_id
    else:
        continue

    if i in paths.keys():
        stack = deque(paths[i])
        cluster = set([i]+paths[i])
    else:
        stack = []
    while len(stack) > 0:
        j = stack.pop()
        connected[j] = path_id
        for k in paths[j]:
            if connected[k] is None and not k in cluster:
                stack.append(k)
                cluster.add(k)
    path_id += 1
# print(connected)

ans = 0
for i in range(n):
    if connected[i+1] == connected[p[i]]:
        ans += 1
print(ans)
### BUGGY CODE ###


n, k = map(int, raw_input().split())
hs = map(int, raw_input().split())
oo = max(hs) * n + 1


dp = [oo] * n
dp[n - 1] = 0
for i in range(n - 2, -1, -1):
    for j in range(1, k + 1):
        if i + j < n:
            dp[i] = min(dp[i], dp[i + j] + abs(hs[i] - hs[i + j]))
print(dp[0])


### FIXED CODE ###

n, k = map(int, raw_input().split())
hs = map(int, raw_input().split())
oo = max(hs) * n + 1


dp = [oo] * n
dp[n - 1] = 0
for i in range(n - 2, -1, -1):
    for j in range(1, k + 1):
        if i + j < n:
            dp[i] = min(dp[i], dp[i + j] + abs(hs[i] - hs[i + j]))
print(dp[0])
### BUGGY CODE ###

import math


def resolve():
    import sys
    input = sys.stdin.readline
    # row = [int(x) for x in input().rstrip().split(" ")]
    # n = int(input().rstrip())
    x = int(input().rstrip())

    def get_sieve_of_eratosthenes(n: int):
        candidate = [i for i in range(2, n + 1)]

        primes = []
        while len(candidate) > 0:
            prime = candidate[0]
            candidate = [num for num in candidate if num % prime != 0]
            primes.append(prime)
        return primes

    # xまでの素数
    primes = get_sieve_of_eratosthenes(x)

    ans = x
    if not x in primes:
        while True:
            if any([ans % prime == 0 for prime in primes]):
                ans += 1
                continue
            break

    print(ans)




if __name__ == "__main__":
    resolve()


### FIXED CODE ###

import math


def resolve():
    import sys
    input = sys.stdin.readline
    # row = [int(x) for x in input().rstrip().split(" ")]
    # n = int(input().rstrip())
    x = int(input().rstrip())

    def get_sieve_of_eratosthenes(n: int):
        candidate = [i for i in range(2, n + 1)]

        primes = []
        while len(candidate) > 0:
            prime = candidate[0]
            candidate = [num for num in candidate if num % prime != 0]
            primes.append(prime)
        return primes

    # xまでの素数
    primes = get_sieve_of_eratosthenes(x)

    ans = x
    if not x in primes:
        while True:
            if any([ans % prime == 0 for prime in primes]):
                ans += 1
                continue
            break

    print(ans)




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

A, B, Q = map(int, input().split())

INF = 10 ** 11 + 1
S = [-INF] + [int(input()) for _ in range(A)] + [INF]
T = [-INF] + [int(input()) for _ in range(B)] + [INF]
#X = [int(input()) for _ in range(Q)]

def bsr(a, v, lo=0, hi=None):
	if hi == None:
		hi = len(a) - 1
	if hi < lo:
		return lo
	mi = (lo + hi) // 2
	if v < a[mi]:
		return bsr(a, v, lo, mi - 1)
	else:
		return bsr(a, v, mi + 1, hi)

#print(S)
#print(T)
#print()

#for x in X:
for _ in range(Q):
	x = int(input())
	sr = bsr(S, x)
	sl = sr - 1
	tr = bsr(T, x)
	tl = tr - 1
	#print(sr, sl, tr, tl)
	#print(S[sr], S[sl], T[tr], T[tl])
	cost = []
	for m in [S[sr], S[sl]]:
		for n in [T[tr], T[tl]]:
			cost += [abs(x - m) + abs(m - n), abs(x - n) + abs(m - n)]
	#print(sr, sl, tr, tl, cost)
	print(min(cost))
	#break


### FIXED CODE ###

import bisect
A, B, Q = map(int, input().split())

INF = 10 ** 11 + 1
S = [-INF] + [int(input()) for _ in range(A)] + [INF]
T = [-INF] + [int(input()) for _ in range(B)] + [INF]
X = [int(input()) for _ in range(Q)]

"""
def bsr(a, v, lo=0, hi=None):
	if hi == None:
		hi = len(a) - 1
	if hi < lo:
		return lo
	mi = (lo + hi) // 2
	if v < a[mi]:
		return bsr(a, v, lo, mi - 1)
	else:
		return bsr(a, v, mi + 1, hi)
"""

def bsr(a, v):
	return bisect.bisect_right(a, v)

#print(S)
#print(T)
#print()

for x in X:
	sr = bsr(S, x)
	sl = sr - 1
	tr = bsr(T, x)
	tl = tr - 1
	#print(sr, sl, tr, tl)
	#print(S[sr], S[sl], T[tr], T[tl])
	cost = []
	for m in [S[sr], S[sl]]:
		for n in [T[tr], T[tl]]:
			cost += [abs(x - m) + abs(m - n), abs(x - n) + abs(m - n)]
	#print(sr, sl, tr, tl, cost)
	print(min(cost))
	#break
### BUGGY CODE ###

from scipy.special import comb
from collections import Counter, deque

D = deque(map(int, list(input())))
num_mod = {}
num_mod[0] = 1
value = 0

for i in range(len(D)):
    value = value + D.pop() * 10**i
    modulo = value % 2019
    #print(modulo)
    if modulo in num_mod.keys():
        num_mod[modulo] += 1
    else:
        num_mod[modulo] = 1

ans = [comb(i, 2, exact=True) for i in num_mod.values() if i > 1]
print(sum(ans))


### FIXED CODE ###

import sys
from collections import deque
def input():
    return sys.stdin.readline()[:-1]

S = deque(map(int, list(input())))
num = 0
dict = {}
dict[0] = 1
ans = 0

for i in range(len(S)):
    num += S.pop() * pow(10,i,2019)
    cand = num % 2019
    if cand in dict.keys():
        dict[cand] += 1
    else:
        dict[cand] = 1

for key in dict.keys():
    ans += dict[key] * (dict[key] - 1) // 2
print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
count = [0] * n
for i in range(1, n):
  count[i] += count[i-1]
  if s[i-1:1+i] == 'AC' :
    count[i] += 1
for i in range(q):
  l, r = map(int, input().split())
  print(count[r-1] - count[l-1])
### BUGGY CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))

INF = 10 ** 18

dp = [0] + [INF] * (N - 1)

for n in range(N):
	for k in range(1, K + 1):
		if N <= n + k:
			break
		dp[n + k] = min(dp[n + k], dp[n] + abs(H[n] - H[n + k]))
		#print(dp)
print(dp[N - 1])


### FIXED CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))

INF = 10 ** 18

h = H
dp = [0] * N

for n in range(1, N):
	l, r = max(0, n - K), n
	dp[n] = min([dpl + abs(hl - h[r]) for dpl, hl in zip(dp[l:r], h[l:r])])
	#print(dp)
print(dp[N - 1])
### BUGGY CODE ###

N, M=map(int, input().split())
lst=[list(map(int, input().split())) for _ in range(M)]
ok=[1 for _ in range(N)]
for L, R in lst:
  L, R=L-1, R-1
  for i in range(L):
    ok[i]=0
  for i in range(R+1, N):
    ok[i]=0
print(sum(ok))

### FIXED CODE ###

N, M=map(int, input().split())
lst=[list(map(int, input().split())) for _ in range(M)]
maxL, minR=-1, N
for L, R in lst:
  L, R=L-1, R-1
  maxL=max(maxL, L)
  minR=min(minR, R)
if minR>=maxL:
  print(minR-maxL+1)
else:
  print(0)
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

# a, b = MAP()
# n = INT()
# a, b, c = MAP()
count = 0
N = INT()
for i in range(1,N):
    # print(i)
    count += i
print(count)

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

# a, b = MAP()
# n = INT()
# a, b, c = MAP()
count = 0
N = INT()
# for i in range(1,N):
    # print(i)
    # count += i
# print(count)
a = N-1
ans = a * (a+1)//2
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [None]*n
dp[0], dp[1] = 0, abs(h[0]-h[1])
for i, hi in enumerate(h[2:], 2):
    di = 10**9
    m = i-k if i>k else 0
    for dj, hj in zip(dp[m:i], h[m:i]):
        d = dj + abs(hj-hi)
        if di > d:
            di = d
    dp[i] = di
print(dp[-1])

### FIXED CODE ###

def main():
    n, K = map(int, input().split())
    h = list(map(int, input().split()))
    inf = 10**10
    dp = [inf]*n
    dp[0] = 0
    for i, (di, hi) in enumerate(zip(dp[1:], h[1:]), 1):
        num = max(i-K, 0)
        for dk, hk in zip(dp[num:i], h[num:i]):
            a = dk+abs(hi-hk)
            if di > a:
                di = a
        dp[i] = di
    print(dp[n-1])

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

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

for _ in range(K):
    A_old = A
    A = [0] * (N)
    for idx_A, a in enumerate(A_old):
        A[max(0, idx_A-a)] += 1
        if idx_A+a+1 < N:
            A[idx_A+a+1] -= 1
    for idx_A in range(1, N):
        A[idx_A] += A[idx_A-1]
    if A_old == A:
        break
print(" ".join(map(str, A)))


### FIXED CODE ###

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

for _ in range(K):
    A_old = A
    A = [0] * (N)
    for idx_A, a in enumerate(A_old):
        A[max(0, idx_A-a)] += 1
        if idx_A+a+1 < N:
            A[idx_A+a+1] -= 1
    for idx_A in range(1, N):
        A[idx_A] += A[idx_A-1]
    if A_old == A:
        break
print(" ".join(map(str, A)))
### BUGGY CODE ###

MOD = 10**9 + 7


def main():
    from fractions import Fraction as F
    N = int(input())
    A = []
    cnt_zero = [0, 0]  # 片方が0のとき
    p = 0  # 両方0
    cA = {}
    for _ in range(N):
        a, b = (int(i) for i in input().split())
        if a == 0 and b == 0:
            p += 1
        elif a == 0:
            cnt_zero[0] += 1
        elif b == 0:
            cnt_zero[1] += 1
        else:
            A.append((F(a, b), F(b, a)))
            if F(a, b) not in cA.keys():
                cA[F(a, b)] = 0
            if -F(b, a) not in cA.keys():
                cA[-F(b, a)] = 0
            cA[F(a, b)] += 1

    used = set()
    ans = 1
    ans *= pow(2, cnt_zero[0], MOD) - 1 + pow(2, cnt_zero[1], MOD) - 1 + 1
    for a, b in A:
        if a in used or -b in used:
            continue
        ans *= pow(2, cA[a], MOD) - 1 + pow(2, cA[-b], MOD) - 1 + 1
        ans %= MOD
        used.add(a)
        used.add(-b)
    print((ans + p - 1) % MOD)


if __name__ == '__main__':
    main()


### FIXED CODE ###

MOD = 10**9 + 7
P = 7 ** 21 + 52


def F(a, b):
    return (a * pow(b, P-2, P)) % P


def main():
    from collections import Counter
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    T = [[int(i) for i in input().split()] for j in range(N)]
    cnt_zero = [0, 0]  # 片方が0のとき
    p = 0  # 両方0
    cA = Counter()
    B = []
    used = set()
    for a, b in T:
        if a == 0 and b == 0:
            p += 1
        elif a == 0:
            cnt_zero[0] += 1
        elif b == 0:
            cnt_zero[1] += 1
        else:
            x = F(a, b)
            y = -F(b, a) % P
            cA[x] += 1
            if x not in used and y not in used:
                B.append((x, y))
                used.add(x)
                used.add(y)

    ans = 1
    ans *= pow(2, cnt_zero[0], MOD) - 1 + pow(2, cnt_zero[1], MOD) - 1 + 1
    for a, b in B:
        ans *= pow(2, cA[a], MOD) - 1 + pow(2, cA[b], MOD) - 1 + 1
        ans %= MOD
    print((ans + p - 1) % MOD)


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

N = int(input())
for n in range(1, N+1):
    ans = 0
    for x in range(1, int(n**0.5)+1):
        for y in range(1, int(n**0.5)+1):
            v = x**2+y**2+1+x*y+y*1+1*x
            if v>n:
                break
            for z in range(1, int(n**0.5)+1):
                v = x**2+y**2+z**2+x*y+y*z+z*x
                if v>n:
                    break
                elif v==n:
                    ans += 1
    print(ans)

### FIXED CODE ###

def solve():
    N = int(input())
    f = lambda x,y,z:x*x+y*y+z*z+x*y+y*z+z*x
    MAX = 10000

    ans = [0]*(MAX+1)
    for x in range(1, 101):
        if f(x,0,0)>MAX:
            break
        for y in range(1, 101):
            if f(x,y,0)>MAX:
                break
            for z in range(1, 101):
                if f(x,y,z)>MAX:
                    break
                ans[f(x,y,z)]+=1
    for i in range(1, N+1):
        print(ans[i])

if __name__ == "__main__":
    solve()