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

import sys


def input():
    return sys.stdin.readline()[:-1]


def dfs(tree: dict, count: list) -> list:
    res = [0] * (N + 1)

    stack = [1]
    while stack:
        label = stack.pop(0)
        res[label] = count[label]
        if tree[label] != []:
            for next_label in tree[label]:
                count[next_label] += count[label]
            stack = tree[label] + stack

    return res


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

tree = {}
for i in range(1, N + 1):
    tree[i] = []
for i in range(N - 1):
    a, b = map(int, input().split())
    tree[a] += [b]

count = [0] * (N + 1)
for i in range(Q):
    p, x = map(int, input().split())
    count[p] += x

ans = dfs(tree, count)
print(*ans[1:])


### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline()[:-1]


def dfs(tree: dict, count: list) -> list:
    res = [0] * (N + 1)

    stack = [1]
    while stack:
        label = stack.pop()
        res[label] = count[label]
        if tree[label] != []:
            for next_label in tree[label]:
                count[next_label] += count[label]
            stack += tree[label]

    return res


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

tree = {}
for i in range(1, N + 1):
    tree[i] = []
for i in range(N - 1):
    a, b = map(int, input().split())
    tree[a] += [b]

count = [0] * (N + 1)
for i in range(Q):
    p, x = map(int, input().split())
    count[p] += x

ans = dfs(tree, count)
print(*ans[1:])
### BUGGY CODE ###

n, w = map(int, input().split())
weights, values = zip(*[tuple(map(int, input().split())) for _ in range(n)])
UV = 10**5
INF = 10**10
dp = [INF]*(UV+1)
dp[0] = 0

for i in range(1, n+1):
    for j in reversed(range(1, UV+1)):
        if j-values[i-1] < 0:
            continue
        dp[j] = min(dp[j], dp[j-values[i-1]]+weights[i-1])

ans = 0
for j in reversed(range(UV+1)):
    if dp[j] <= w:
        ans = j
        break
print(ans)

### FIXED CODE ###

n, w = map(int, input().split())
weights, values = zip(*[tuple(map(int, input().split())) for _ in range(n)])
UV = 10**5
INF = float('inf')
dp = [[0]+[INF]*UV for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, UV+1):
        dp[i][j] = dp[i-1][j]
        if 0 <= j-values[i-1]:
            dp[i][j] = min(dp[i][j], dp[i-1][j-values[i-1]]+weights[i-1])

ans = 0
for i in range(UV+1):
    if dp[-1][i] <= w:
        ans = max(ans, i)
print(ans)
### BUGGY CODE ###

from fractions import gcd
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(N):
    tmp_arr = A[:i] + A[i+1:]
    ans_tmp = reduce(gcd,tmp_arr)
    if ans < ans_tmp:
        ans = ans_tmp
print(ans)

### FIXED CODE ###

from fractions import gcd
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
L = [A[0]]
R = [A[-1]]
for i in range(N-1):
    L.append(gcd(L[i],A[i+1]))
    R.append(gcd(R[(i)],A[-(i+2)]))
ans = []    
for i in range(N):
    if i == 0:
        ans.append(R[N - 2])
    elif i <= N - 2:
        ans.append(gcd(L[i - 1],R[N - i - 2]))
    else:
        ans.append(L[N - 2])

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

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

minv = 9999
for i in range(len(a)):
        t = 0
        s = i
        e = s + 1
        for j in range(len(a) - 1):
                if s >= len(a):
                        s = len(a) - s
                if e >= len(a):
                        e = len(a) - e
                if s > e:
                        t = t + abs((k - a[s]) + a[e])
                else:
                        t = t + abs(a[e] - a[s])

                s = s + 1
                e = e + 1
        if minv > t:
                minv = t
print(minv)

### FIXED CODE ###

k, n = map(int, input().split())
a = list(map(int, input().split()))
ma = min(a)
a = [x - ma for x in a]
a.append(k)
md = 0
for i in range(len(a) - 1):
    if md < (a[i+1] - a[i]):
        md = a[i+1] - a[i]
print(k - md)
### BUGGY CODE ###

s = list(input())

dp = [[0 for _ in range(13)]for _ in range(len(s)+1)]
MOD = 10**9+7
if s[-1] == '?':
	for i in range(10):
		dp[1][i] = 1
else:
	dp[1][int(s[-1])] = 1

for i in range(1,len(s)):
	if s[-i-1] != '?':
		num = (int(s[-i-1]) * (10**i)) % 13
		for j in range(13):
			dp[i+1][j] = dp[i][(13-num+j)%13]
			dp[i+1][j] % MOD
	else:
		num = (10**i) % 13
		a = 0
		for j in range(10):
			for k in range(13):
				dp[i+1][k] += dp[i][(13-a+k)%13]
				dp[i+1][k] % MOD
			a += num

print(dp[len(s)][5] % MOD)

### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

print(dp[len(S)][5])
### BUGGY CODE ###

import heapq
N, M = [int(x) for x in input().split()]
AB_list = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: int(x[0]))
h = []
ans = 0
for i in range(1, M+1):
    while(len(AB_list) > 0 and AB_list[0][0] <= i):
        tmp = AB_list.pop(0)
        heapq.heappush(h, -1 * tmp[1])
    # print(AB_list, h)
    if (len(h)):
        ans += -1 * heapq.heappop(h)
print(ans)


### FIXED CODE ###

import heapq
N, M = [int(x) for x in input().split()]
AB_list = [[] for _ in range(M)]
for _ in range(N):
    A, B = list(map(int, input().split()))
    if (A > M): continue
    AB_list[A-1].append(B)
h = []
ans = 0
for i in range(M):
    for B in AB_list[i]:
        heapq.heappush(h, -B)
    # print(AB_list, h)
    if (len(h)):
        ans += -heapq.heappop(h)
print(ans)
### BUGGY CODE ###

from operator import itemgetter
import sys
input = sys.stdin.readline

N, M = map(int,input().split()) # 複数の数字を変数に格納
List = [list(map(int,input().split())) for i in range(N)] # [[1,2],[3,4],[5,6]]

List.sort(key=itemgetter(0))
List_S = []
 
result = 0
p = 0
 
for i in range(1,M+1):
    add = 0
    for j in range(p,N):
        if List[j][0] <= i:
            List_S.append(List[j][1])
            p += 1
        else:
            break
        add = 1
    if len(List_S) != 0:
        if add == 1:
            List_S.sort()
        result += List_S.pop()
 
print(result)


### FIXED CODE ###

from operator import itemgetter
import sys
input = sys.stdin.readline

N, M = map(int,input().split()) # 複数の数字を変数に格納
List = [list(map(int,input().split())) for i in range(N)] # [[1,2],[3,4],[5,6]]

List.sort(key=itemgetter(0))
List_S = [0]
 
result = 0
p = 0

for i in range(1, M+1):
    add = 0
    add_list = []
    while p < N and List[p][0] == i:
        if List_S[len(List_S)-1] < List[p][1]:            
            List_S.append(List[p][1])
        else:
            add_list.append(List[p][1])
            add += 1
        p += 1
            
    if len(List_S) != 1:
        result += List_S.pop()
        if add > 0:
            List_S.extend(add_list)
            List_S.sort()
 
print(result)
### BUGGY CODE ###

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

def eratosthenes(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i*2, n+1, i):
            is_prime[j] = False
    
    return [i for i in range(n+1) if is_prime[i]]


pairwise = True
setwise = True
for x in eratosthenes(10**6):
    cnt = 0
    for a in A:
        if a % x == 0:
            cnt += 1
    
    if cnt >= 2:
        pairwise = False
    
    if cnt == N:
        setwise = False
    
if pairwise:
    print('pairwise coprime')
elif setwise:
    print('setwise coprime')
else:
    print('not coprime')
        

### FIXED CODE ###

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

def eratosthenes(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i*2, n+1, i):
            is_prime[j] = False
    
    return [i for i in range(n+1) if is_prime[i]]

primecount = {}
primenum = [-1] * (A_MAX+1)
for p in eratosthenes(A_MAX):
    primecount[p] = 0
    for i in range(p, A_MAX+1, p):
        primenum[i] = p
    
for a in A:
    while a > 1:
        p = primenum[a]
        while a % p == 0:
            a //= p
        primecount[p] += 1

primecount[1] = 1
cnt = max(primecount.values())

if cnt == 1:    
    print('pairwise coprime')
elif cnt < N:
    print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###

import bisect

n = int(input())
l = sorted([int(i) for i in input().split()])
ans = 0
for d in range(n):
    for e in range(d+1, n):
        a, b = l[d], l[e]
        idx = bisect.bisect_right(l, a + b)
        for c in l[e+1:idx]:
            if not c < a + b:
                break
            ans += 1
print(ans)


### FIXED CODE ###

import bisect

n = int(input())
l = sorted([int(i) for i in input().split()])
ans = 0
for d in range(n):
    for e in range(d+1, n):
        a, b = l[d], l[e]
        idx = bisect.bisect_left(l, a + b)
        ans += max(idx - e - 1, 0)
print(ans)
### BUGGY CODE ###

n=int(input())
a=[]
b=[]
ans=0
for i in range(n):
  s=list(input())
  s.sort()
  a.append(str(s))
a.sort()
for i in range(n-1):
  for j in range(i+1,n):
    if a[i]==a[j]:
      ans+=1
    #print(a[i],a[j],ans)
  




print(ans)

### FIXED CODE ###

n=int(input())
a=[]
ans=0
for i in range(n):
  s=list(input())
  s.sort()
  a.append(str(s))
a.sort()
y=''
w=0
c=[]
for x in a:
  if y==x:
    w+=1
  else:
    c.append(w)
    w=1
  y=x
c.append(w)
c=c[1:]
for x in c:
  ans+=x*(x-1)//2
print(ans)
### BUGGY CODE ###

k = int(input())
x = 7%k
s = []
if k%2 == 0:
  print(-1)

else:
  while s.count(x) == 0:
    s.append(x)
    if x == 0:
      print(len(s))
      break
    x = (10*x + 7)%k

  
  if s[-1] != 0:
    print(-1)


### FIXED CODE ###

k = int(input())
x = 7%k
s = []

for i in range(k):
  if x == 0:
    print(i+1)
    exit()
  s.append(x)
  x = (10*x + 7)%k

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

N=int(input())
s=[sorted(list(input())) for i in range(N)]
count=0
for i in range(N-1):
    for j in range(i+1,N):
        if s[i]==s[j]:
            count+=1
print(count)

### FIXED CODE ###

N=int(input())
S = ["".join(sorted(input())) for _ in range(0, N)]
d={}
result=0
for s in S:
    if s in d.keys():
        result+=d[s]
        d[s]+=1
    else:
        d[s]=1
print(result)
### BUGGY CODE ###

import fractions
n = int(input())
ans = 0
for i in range(1,n + 1):
    for j in range(1, n + 1):
        f = fractions.gcd(i, j)
        for k in range(1, n + 1):
            ans += fractions.gcd(f, k)
print(ans)

### FIXED CODE ###

from math import gcd
n = int(input())
ans = 0
for i in range(1,n + 1):
    for j in range(1, n + 1):
        f = gcd(i, j)
        for k in range(1, n + 1):
            ans += gcd(f, k)
print(ans)
### BUGGY CODE ###

def main():
  import sys
  input=sys.stdin.readline
  h,w,k=map(int,input().split())
  sx,sy,tx,ty=map(int,input().split())
  calc=lambda x,y:x*1000007+y
  b=[[-1]*(w+2)]
  for i in range(h):
    s=input()
    bb=[-1]
    for j in s:
      if j==".":bb.append(0)
      else:bb.append(-1)
    bb.append(-1)
    b.append(bb)
  b.append([-1]*(w+2))
  from collections import deque
  d=deque()
  d.append(calc(sx,sy))
  s=set()
  while d:
    x,y=divmod(d.popleft(),1000007)
    if calc(x,y)in s:
      s.discard(calc(x,y))
      continue
    if x==tx and y==ty:
      exit(print(b[x][y]))
    for i in range(1,k+1):
      if b[x-i][y]<=b[x][y] and b[x-i][y]!=0:break
      d.append(calc(x-i,y))
      if b[x-i][y]!=0:
        s.add(calc(x-i,y))
      b[x-i][y]=b[x][y]+1
    for i in range(1,k+1):
      if b[x+i][y]<=b[x][y] and b[x+i][y]!=0:break
      d.append(calc(x+i,y))
      if b[x+i][y]!=0:
        s.add(calc(x+i,y))
      b[x+i][y]=b[x][y]+1
    for j in range(1,k+1):
      if b[x][y-j]<=b[x][y] and b[x][y-j]!=0:break
      d.append(calc(x,y-j))
      if b[x][y-j]!=0:
        s.add(calc(x,y-j))
      b[x][y-j]=b[x][y]+1
    for j in range(1,k+1):
      if b[x][y+j]<=b[x][y] and b[x][y+j]!=0:break
      d.append(calc(x,y+j))
      if b[x][y+j]!=0:
        s.add(calc(x,y+j))
      b[x][y+j]=b[x][y]+1
  print(-1)
if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
input=sys.stdin.readline
h,w,k=map(int,input().split())
si,sj,ti,tj=map(int,input().split())
si-=1
sj-=1
ti-=1
tj-=1
b=[input()for _ in range(h)]
ans=[[-1]*w for _ in range(h)]
ans[si][sj]=0
from collections import deque
d=deque()
d.append((si,sj))
while d:
  x,y=d.popleft()
  if x==ti and y==tj:
    exit(print(ans[x][y]))
  for dx,dy in [[1,0],[-1,0],[0,-1],[0,1]]:
    for i in range(1,k+1):
      xx=x+dx*i
      yy=y+dy*i
      if not(0<=xx<h and 0<=yy<w) or b[xx][yy]=="@":break
      if 0<=ans[xx][yy]<=ans[x][y]:break
      if ans[xx][yy]==-1:d.append((xx,yy))
      ans[xx][yy]=ans[x][y]+1
print(-1)
### BUGGY CODE ###

n = int(input())
N = [i for i in range(n)]
A = list(map(int,input().split()))
ans = 0
for i in range(n):
  for j in range(i+1,n):
    if N[j]-N[i] == A[i] + A[j]:
      ans += 1
print(ans)



### FIXED CODE ###

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

X = dict()
ans = 0
for i in range(N):
    L = i + A[i]
    if L not in X:
        X[L] = 1
    else:
        X[L] += 1

for i in range(N):
    R = i - A[i]
    if R in X:
        ans += X[R]
        
print(ans)
### BUGGY CODE ###

from collections import defaultdict
from queue import Queue
n, m = list(map(int, input().split()))
MX = int(1e6)
edge = defaultdict(set)
edge2 = defaultdict(set)
kenedge = defaultdict(set)
dist = [MX for i in range(n)]
reached = [False for i in range(n)]

for loop in range(m):
    a, b = list(map(int, input().split()))
    edge[a-1].add(b-1)

for i in range(n):
    step1 = set()
    for ii in edge[i]:
        edge2[i] |= edge[ii]

for i in range(n):
    step2 = set()
    for ii in edge2[i]:
        kenedge[i] |= edge[ii]

s, t = list(map(int, input().split()))
s = s-1
t = t-1
dist[s] = 0

q = Queue()
q.put(s)
while not q.empty():
    node = q.get()
    reached[node] = True
    for next_node in kenedge[node]:
        if not reached[next_node]: q.put(next_node)
        dist[next_node] = min(dist[next_node], dist[node] + 1)

if dist[t] == MX:
    print(-1)
else:
    print(dist[t])



### FIXED CODE ###

from collections import defaultdict
from queue import Queue

n, m = list(map(int, input().split()))
MX = int(1e6)
edge = defaultdict(set)
dist = [[MX, MX, MX] for i in range(n)]
reached = [[False, False, False] for i in range(n)]

for loop in range(m):
    a, b = list(map(int, input().split()))
    edge[a-1].add(b-1)

s, t = list(map(int, input().split()))
s = s-1
t = t-1
dist[s][0] = 0

q = Queue()
q.put((s, 0))
while not q.empty():
    node, step = q.get()
    next_step = (step + 1) % 3
    for next_node in edge[node]:
        if reached[next_node][next_step]: continue
        q.put((next_node, next_step))
        reached[next_node][next_step] = True
        if step == 2:
            dist[next_node][next_step] = min(dist[next_node][next_step], dist[node][step] + 1)
        else:
            dist[next_node][next_step] = min(dist[next_node][next_step], dist[node][step])

if dist[t][0] == MX:
    print(-1)
else:
    print(dist[t][0])
### BUGGY CODE ###

def main():
  N = int(input())
  As = list(map(int, input().split()))
  for i in range(1, N+1):
    print(As.count(i))

if __name__ == "__main__":
  main()

### FIXED CODE ###

def main():
  N = int(input())
  As = list(map(int, input().split()))
  
  ans_list = [0] * N
  
  for i in As:
    ans_list[i - 1] += 1
   
  for i in range(N):
    ans = ans_list[i]
    print(ans)

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

n = int(input())
a = list(map(int, input().split()))
s = [0]
s.extend([sum(a[0:i+1]) for i in range(n)])
s_uniq = list(set(s))
result = 0

for s_uniq_i in s_uniq:
    count = s.count(s_uniq_i)
    if count >= 2:
        result += count * (count-1) // 2

print(result)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
s = [0]
for i in range(n):
    s.append(s[-1] + a[i])
s.sort()
result = 0

count = 1
for i in range(n):
    if s[i] == s[i+1]:
        count += 1
    else:
        result += count * (count - 1) // 2
        count = 1
result += count * (count - 1) // 2

print(result)
### BUGGY CODE ###

N = int(input())
s = list(input() for _ in range(N))

l = list(map(sorted,s))
cnt = 0
for i in range(len(l)):
    for j in range(i,len(l)):
        if(i != j):
            #print(i,",",j)
            if(l[i] == l[j]):
                cnt += 1
print(cnt)

### FIXED CODE ###

d,a = {},0
for i in range(int(input())):
    k = ''.join(sorted(input()))
    d[k] = d.get(k,-1)+1
    a+= d[k]
print(a)
### BUGGY CODE ###

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
d[~w+a*w+b]=1
q=[(a-1,b-1)]
for s,t in q:
 p=d[s*w+t]+1
 for y,x in(-1,0),(0,-1),(0,1),(1,0):
  for z in range(k):
   i,j=s+y*~z,t+x*~z
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[i*w+j]<p:break
   q+=[(i,j)];d[i*w+j]=p
print(d[~w+f*w+g]%I-1)

### FIXED CODE ###

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)
### BUGGY CODE ###


def green_bin(s):
    anagram_num = 0

    for i in range(len(s)):
        sorted_si = sorted(s[i])

        for j in range(i + 1, len(s)):
            sorted_sj = sorted(s[j])

            if sorted_si == sorted_sj:
                anagram_num += 1

    return anagram_num


if __name__ == '__main__':
    N = int(input())
    s = []
    for n in range(N):
        sn = input()
        s.append(sn)
    print(green_bin(s))


### FIXED CODE ###


def green_bin(s, N):
    anagram_num = 0
    sorted_s_sub = []
    sorted_s = []
        
    for i in range(N):
        sorted_si = sorted(s[i])
        sorted_s_sub.append(''.join(sorted_si))

    sorted_s = sorted(sorted_s_sub)

    i = 0
    item_count = []
    while i < N:
        item = sorted_s[i]
        j = i + 1
        count = 1
        while j < N:
            if item == sorted_s[j]:
                count += 1
                j += 1
            else:
                break
        item_count.append(count)
        i += count  # count だけ進める
    
    for count in item_count:
        
        anagram_num += int(count * (count - 1) / 2)

    return anagram_num


if __name__ == '__main__':
    N = int(input())
    s = []
    for n in range(N):
        sn = input()
        s.append(sn)
    print(green_bin(s, N))
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
a=A[:]
for _ in range(K):
    t=[0]*(N+1)
    for i in range(N):
        ti=a[i]
        t[max(0,i-ti)]+=1
        t[min(N,i+ti+1)]-=1
    a=[]
    for i in range(N):
        a.append(t[i])
        if i>0:
            a[i]+=a[i-1]
    if min(a)==N:
        break
print(*a)

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
a=A[:]
for _ in range(K):
    t=[0]*(N+1)
    for i in range(N):
        ti=a[i]
        t[max(0,i-ti)]+=1
        t[min(N,i+ti+1)]-=1
    a=[]
    for i in range(N):
        a.append(t[i])
        if i>0:
            a[i]+=a[i-1]
    if min(a)==N:
        break
print(*a)
### BUGGY CODE ###

N,M=map(int,input().split())
A=list(range(N))
ans=0
for i in range(M):
  L,R=map(int,input().split())
  for j in range(N):
    if A[j]+1<L or R<A[j]+1:
      A[j]=-1
for k in range(N):
  if A[k]!=-1:
    ans=ans+1
print(ans)

### FIXED CODE ###

N,M=map(int,input().split())
ans,L,R=0,0,N
for i in range(M):
  Ltmp,Rtmp=map(int,input().split())
  if L<Ltmp:
    L=Ltmp
  if R>Rtmp:
    R=Rtmp
if L<=R:
  ans=R-L+1
print(ans)
### BUGGY CODE ###

n = int(input())
x = {i for i in range(1,int((n/6)**0.5)+1)}
y = []
z = []
for i in range(1,n):
  if (i**2)+2*i > n-3:
    break
  else:
    y.append(i)
    z.append(i)
one = set()
three = set()
six = set()
for xi in x:
  for yi in y:
    for zi in z:
      k = ((xi+yi+zi)**2 +(xi**2)+(yi**2)+(zi**2))//2
      if xi==yi==zi:
        one.add(k)
      elif xi==yi or yi==zi or zi==xi:
        three.add(k)
      else:
        six.add(k)
for i in range(1,n+1):
  if i in set(one):
    print(1)
  elif i in set(three):
    print(3)
  elif i in set(six):
    print(6)
  else:
    print(0)

### FIXED CODE ###

n = int(input())
cnt = [0]*(10**4+50)

for i in range(1,105):
  for j in range(1,105):
    for k in range(1,105):
      v = (i**2)+(j**2)+(k**2)+i*j+j*k+k*i
      if v<10**4+50:
        cnt[v] += 1
for i in range(1,n+1):
  print(cnt[i])
### BUGGY CODE ###

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

if  N % 2 == 0:
    M =  N // 2
    even_A = [A[i* 2] for i in range(M)]
    odd_A = [A[i* 2 + 1] for i in range(M)]
    even_sum = []
    _sum = 0
    for a in even_A:
        _sum += a
        even_sum.append(_sum)
    odd_sum = []
    _sum = 0
    for a in odd_A:
        _sum += a
        odd_sum.append(_sum)
    ans = max(odd_sum[-1], even_sum[-1])
    for i in range(M):
            x = even_sum[i] + odd_sum[-1] - odd_sum[i]
            ans = max(ans, x)
    print(ans)
    exit()
M =  N // 2
# evenが元一つ多い
even_A = [A[i* 2] for i in range(M+1)]
odd_A = [A[i* 2 + 1] for i in range(M)]
even_sum = []
_sum = 0
for a in even_A:
    _sum += a
    even_sum.append(_sum)
odd_sum = []
_sum = 0
for a in odd_A:
    _sum += a
    odd_sum.append(_sum)
# 全て奇数
all_even = even_sum[-1] - min(even_A)

ans = all_even
for i in range(M):
        x = even_sum[i] + odd_sum[-1] - odd_sum[i]
        y = odd_sum[i] + even_sum[-1] - even_sum[i+1]
        ans = max(ans, x, y)
        for k in range(i+1, M):
           z = even_sum[i] + odd_sum[k] - odd_sum[i] + even_sum[-1] - even_sum[k+1]
           ans = max(ans, z)

print(ans)



### FIXED CODE ###

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

if  N % 2 == 0:
    M =  N // 2
    even_A = [A[i* 2] for i in range(M)]
    odd_A = [A[i* 2 + 1] for i in range(M)]
    even_sum = []
    _sum = 0
    for a in even_A:
        _sum += a
        even_sum.append(_sum)
    odd_sum = []
    _sum = 0
    for a in odd_A:
        _sum += a
        odd_sum.append(_sum)
    ans = max(odd_sum[-1], even_sum[-1])
    for i in range(M):
            x = even_sum[i] + odd_sum[-1] - odd_sum[i]
            ans = max(ans, x)
    print(ans)
    exit()
M =  N // 2
# evenが元一つ多い
even_A = [A[i* 2] for i in range(M+1)]
odd_A = [A[i* 2 + 1] for i in range(M)]
even_sum = []
_sum = 0
for a in even_A:
    _sum += a
    even_sum.append(_sum)
odd_sum = []
_sum = 0
for a in odd_A:
    _sum += a
    odd_sum.append(_sum)
# 全て奇数
all_even = even_sum[-1] - min(even_A)
diff_odd_even = [odd_sum[k] - even_sum[k+1] for k in range(M)]
diff_max_odd_even = []
diff_max = diff_odd_even[-1]
for k in range(M):
    diff_max = max(diff_max, diff_odd_even[-k-1])
    diff_max_odd_even.append(diff_max)
diff_max_odd_even.reverse()

ans = all_even
for i in range(M):
        x = even_sum[i] + odd_sum[-1] - odd_sum[i]
        y = odd_sum[i] + even_sum[-1] - even_sum[i+1]
        z = even_sum[i] + - odd_sum[i] + even_sum[-1] + diff_max_odd_even[i]
        ans = max(ans, x, y, z)
print(ans)
### BUGGY CODE ###

import math

A, B, N = map(int, input().split())
mx = 0
p = N
q = B

if B <= N:
    mx = math.floor(A / B * q) - math.floor(q / B) * A
    while mx == 0:
        q -= 1
else:
    mx = math.floor(A / B * p) - math.floor(p / B) * A
    while mx == 0:
        p -= 1

print(mx)

### FIXED CODE ###

import math

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

if N >= B-1:  # x = B-1のときに最大値
    beta = (B-1)/B
    print(math.floor(A * beta))

else:
    beta = N/B
    print(math.floor(A * beta))