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

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

for a in A:
    ans *= a
if ans > 10 ** 18:
        print(str(-1))
else:
    print(ans)

### FIXED CODE ###

import sys

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

if A[0] == 0:
    print(0)
    sys.exit()

for a in A:
    ans *= a
    if ans > 10 ** 18:
        print(str(-1))
        break
else:
    print(ans)
### BUGGY CODE ###

import queue

def resolve():
    # ★get input
    h, w = map(int, input().split())

    grid = [["" for i in range(w)] for j in range(h)]

    for i in range(h):
        line = list(input())
        for j in range(w):
            grid[i][j] = line[j]

    # ★exec
    # BFSにて最短経路を求める
    # 準備
    distance = [[-1 for i in range(w)] for j in range(h)]
    que = queue.Queue()

    # スタート地点の情報を設定
    # 多点スタートの設定
    for i in range(h):
        for j in range(w):
            if grid[i][j] == "#":
                que.put([i, j])
                distance[i][j] = 0

    # BFS開始
    while not que.empty():

        now = que.get()

        # 上下左右のマスを確認
        for move_y, move_x in ((1, 0), (-1, 0), (0, 1), (0, -1)):

            # 盤の範囲外なら何もしない
            target = [now[0] + move_y, now[1] + move_x]
            if not h > target[0] >= 0 or not w > target[1] >= 0:
                continue

            # 黒塗りされているなら何もしない
            if grid[target[0]][target[1]] == '#':
                continue

            # 距離が設定済みなら何もしない
            if not distance[target[0]][target[1]] == -1:
                continue

            # キューに追加
            que.put(target)

            # 最短距離を設定
            distance[target[0]][target[1]] = distance[now[0]][now[1]] + 1

    # 距離が最大の点 = 答えになる。
    ans = 0
    for i in range(h):
        ans = max(ans, max(distance[i]))

    print(ans)


if __name__ == "__main__":
    resolve()


### 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 ###

a,b,x = map(int, input().split())
count = 0
for i in range(a, b+1):
    if i % x == 0:
        count += 1
print(count)

### FIXED CODE ###

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

ans = b//x - a//x
if a % x == 0:
    ans += 1
print(ans)
### BUGGY CODE ###

from collections import deque

s = deque(input())
q = int(input())

for i in range(q):
    a,b,c, *_ = input().split() + [None, None]
    
    if(a == '1'):
        s.reverse()
    else:
        if(b == '1'):
            s.appendleft(c)
        else:
            s.append(c)

print(*s, sep='')


### FIXED CODE ###

from collections import deque

revFlag = False

s = deque(input())
q = int(input())

for i in range(q):
    a,b,c, *_ = input().split() + [None, None]
    
    if(a == '1'):
        revFlag = not revFlag
        
    else:
        b = int(b)
        if(revFlag):
            b = (int(b)%2)+1
        
        if(b == 1):
            s.appendleft(c)
        else:
            s.append(c)
            
    #print(_,*s, sep="")

if(revFlag):
    s.reverse()
    
print(*s, sep='')
### BUGGY CODE ###

import copy

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

ls = []

for i in range(M):
    L, R = map(int,input().split())
    l = [k+L for k in range(R-L+1)]
    ls.append(l)
    
if M == 1:
    print(len(l))
else:
    for i in range(M-1):
        l_set = set(ls[i]) & set(ls[i+1])
        if len(l_set) == 0:
            break
        ls[i+1] = copy.deepcopy(l_set)

    print(len(l_set))

### FIXED CODE ###

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

Ls, Rs = [0 for _ in range(M)],  [0 for _ in range(M)]

for i in range(M):
    L, R = map(int,input().split())
    Ls[i] = L
    Rs[i] = R
    
L_prime = max(Ls)
R_peime = min(Rs)

if L_prime > R_peime:
    print(0)
else:
    print(R_peime - L_prime + 1)
### BUGGY CODE ###

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

cnt=[]
for a in set(A):
  cnt.append(A.count(a))
cnt.sort()
ans=0
while len(cnt)>k:
  ans+=cnt[0]
  cnt=cnt[1:]
print(ans)

### FIXED CODE ###

from collections import Counter
n,k=map(int,input().split())
A=list(map(int,input().split()))

cnt=sorted(Counter(A).values())
print(sum(cnt[:-k]))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np

n, m = map(int, input().split())
h = np.array(input().split())
good_tower = np.arange(1, n+1)

for i in range(m):
    way = np.array(input().split(), dtype='int')

    if h[way[0]-1] > h[way[1]-1]:
        good_tower = np.delete(good_tower, np.where(good_tower == way[1]))
    elif h[way[0]-1] < h[way[1]-1]:
        good_tower = np.delete(good_tower, np.where(good_tower == way[0]))
    elif h[way[0]-1] == h[way[1]-1]:
        good_tower = np.delete(good_tower, np.where(good_tower == way[0]))
        good_tower = np.delete(good_tower, np.where(good_tower == way[1]))

print(len(good_tower))

### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np

n, m = map(int, input().split())
h = np.array(input().split(), dtype='int')
bad_tower = np.zeros((n), dtype='int')

for i in range(m):
    a, b = map(int, input().split())
    ha = h[a-1]
    hb = h[b-1]

    if ha > hb:
        bad_tower[b-1] = 1
    elif ha < hb:
        bad_tower[a-1] = 1
    elif ha == hb:
        bad_tower[a-1] = 1
        bad_tower[b-1] = 1

ans = n - np.sum(bad_tower)

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

a, b, x = map(int, input().split(" "))
ad = 0
bd = 0
for i in range(x):
  if (a+i) % x == 0:
    ad = a + i
    break
for i in range(x):
  if (b-i) % x == 0:
    bd = b - i
    break
print(int((bd - ad) // x) + 1)


### FIXED CODE ###

a, b, x = map(int, input().split(" "))
if a % x == 0:
  print(int(b//x) - int(a//x) + 1)
else:
  print(int(b//x) - int(a//x))
### BUGGY CODE ###

n = int(input())
print(0)
s0 = str(input())
if s0 == 'Vacant':
    exit()
l = 0
r = n
while abs(l - r) > 1:
    m = (l + r) // 2
    print(m)
    s = str(input())
    if s == 'Vacant':
        exit()
    else:
        if s0 == s:
            l = m
        else:
            r = m
        s0 = s
else:
    print(l)
    s = str(input())


### FIXED CODE ###

n = int(input())
l = 0
r = n - 1
print(l)
s_l = str(input())
if s_l == 'Vacant':
    exit()
while abs(l - r) > 1:
    m = (l + r) // 2
    print(m)
    s_m = str(input())
    if s_m == 'Vacant':
        exit()
    else:
        if (m - l) % 2:
            if s_m != s_l:
                l = m
                s_l = s_m
            else:
                r = m
                s_r = s_m
        else:
            if s_m != s_l:
                r = m
                s_r = s_m
            else:
                l = m
                s_l = s_m
else:
    print(r)
    s = str(input())
### BUGGY CODE ###

import sys

input = sys.stdin.readline

def calc(n):
    for i in range(1,n):
        for j in range(1,n):
            for k in range(1,n):
                if (i+j+k)**2 - i*j - j*k - k*i == n:
                    if i == j == k:
                        return 1
                    else:
                        return 3
    return 0    

def main():
    ans = 0
    n = int(input())
    for i in range(1,n):
        print(calc(i))

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

input = sys.stdin.readline

def main():
    ans = [0]* 10010
    n = int(input())
    for x in range(1,101):
        for y in range(1,101):
            for z in range(1,101):
                v = (x+y+z)**2 - x*y - y*z - z*x
                if v <= n:
                    ans[v] += 1
    for i in range(1,n+1):
        print(ans[i])

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

from fractions import gcd
from functools import reduce
mod=1000000000+7
n=int(input())
a=[int(i) for i in input().split()]
l=reduce(lambda x,y:x//gcd(x,y)*y,a)
ans=sum(map(lambda x:l//x,a))
print(ans%mod)


### FIXED CODE ###

from fractions import gcd

def lcm(c,d):
    return c//gcd(c,d)*d
mod=10**9+7
n=int(input())
a=[int(i) for i in input().split()]
l=a[0]
for i in range(1,n):
    l=lcm(l,a[i])
ans=0
for i in range(n):
    ans+=l//a[i]
    #ans%=mod
print(ans%mod)
### BUGGY CODE ###

H, N = map(int, input().split())
A, B = [], []
for i in range(N):
	a, b = map(int, input().split())
	A.append(a)
	B.append(b)

# dp
INF = 1 << 30
dp = [INF] * (H + 1) # dp[i]: モンスターの体力を i 減らすため消耗する魔力の最小値
dp[0] = 0
for h in range(H + 1):
	for n in range(N):
		dp[h] = min(dp[h], B[n] + dp[max(h - A[n], 0)])

print(dp[H])

### FIXED CODE ###

H, N = map(int, input().split())
A, B = [], []
for i in range(N):
	a, b = map(int, input().split())
	A.append(a)
	B.append(b)

# dp
INF = 1 << 30
dp = [INF] * (H + 1) # dp[i]: モンスターの体力を i 減らすため消耗する魔力の最小値
dp[0] = 0
for h in range(H + 1):
	for n in range(N):
		dp[h] = min(dp[h], B[n] + dp[max(h - A[n], 0)])

print(dp[H])
### BUGGY CODE ###

A = input()

S = [0]


for n in range(1, len(A)+1):
    S.append(S[-1] + (int(A[-n])*(10**(n-1))))

result = 0

for i in range(len(S)):
    i = i + 1
    for j in range(len(S)-i):
        if S[-i] == S[-j]:
            continue
        if (S[-i] - S[j]) % 2019 == 0:
            result += 1


print(result)


### FIXED CODE ###

S = input()
 
res = [0] * 2019
res[0] = 1
 
d = 1
a = 0
 
for c in reversed(S):
    a += int(c) * d
    a %= 2019
    res[a] += 1
    d *= 10
    d %= 2019
 
ans = 0
for r in res:
    ans += r*(r-1) // 2
print(ans)
### BUGGY CODE ###

n = int(input())
s = 0

for p in range(1, int(n/2) + 1):
  t = (n - p) / p
  if t.is_integer():
    if (n // int(t)) == (n % int(t)):
      s += int(t)

print(s)


### FIXED CODE ###

import math
 
n = int(input())
s = 0
if n > 2:
  for p in range(1, int(math.sqrt(n)) + 1):
    t = (n - p) / p
    if t.is_integer():
      if (n // int(t)) == (n % int(t)):
        s += int(t)
  print(s)

else:
  print(0)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc164/tasks/abc164_d

from operator import mul
from functools import reduce
from collections import defaultdict

def combination(n, r):
    if not 0 <= r <= n: return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

S = input()

res = 0

T = [0]
x = 0
L = len(S)
for i, s in zip(range(L),reversed(S)):
    """ 累積和 """
    x = int(s)*pow(10,i) + x
    T.append(x)

reminder = [0]*2019
for i in range(L+1):
    reminder[T[i]%2019] += 1

for c in reminder:
    res += combination(c,2)

print(res)

### FIXED CODE ###

# https://atcoder.jp/contests/abc164/tasks/abc164_d

from operator import mul
from functools import reduce
from collections import defaultdict

def combination(n, r):
    if not 0 <= r <= n: return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

S = input()

res = 0

T = [0]
x = 0
L = len(S)
for i, s in zip(range(L),reversed(S)):
    """ 累積和 """
    x = (int(s)*pow(10,i,2019) + x)%2019
    T.append(x)

reminder = [0]*2019
for i in range(L+1):
    reminder[T[i]%2019] += 1

for c in reminder:
    res += combination(c,2)

print(res)
### BUGGY CODE ###

x,y,a,b,c = map(int, input().split())
p1 = list(map(int, input().split()))
p2 = list(map(int, input().split()))
p3 = list(map(int, input().split()))
ans1 = 0
ans2 = 0
p1.sort(reverse = True)
p2.sort(reverse = True)
p3.sort(reverse = True)
for i in range(0, max(x,y)):
  p3.append(0)
for i in range(0,x):
  p3.sort(reverse = True)
  ans1= ans1 + max(p1[i],p3[0])
  if(p3[0]>p1[i]):
    p3[0] = 0
for i in range(0,y):
  p3.sort(reverse = True)
  ans2= ans2 + max(p2[i],p3[0])
  if(p3[0]>p2[i]):
    p3[0] = 0
print(ans1+ans2)



### FIXED CODE ###

x,y,a,b,c = map(int, input().split())
p1 = list(map(int, input().split()))
p2 = list(map(int, input().split()))
p3 = list(map(int, input().split()))
p1.sort(reverse= True)
p2.sort(reverse= True)
ans =p1[:x]+p2[:y]+p3
ans.sort(reverse= True)
print(sum(ans[:x+y]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
    r,c,k=map(int,input().split())
    a=[list(map(int,input().split())) for _ in range(k)]
    dp=[[[0,0,0,0,0]for _ in range(c+1)]for _ in range(r+1)]
    b=[[0 for _ in range(c+1)] for _ in range(r+1)]
    for x,y,z in a:
        b[x][y]=z
    for i in range(1,r+1):
        for j in range(1,c+1):
            v=b[i][j]
            if b==0:
                dp[i][j][0]=max(dp[i][j-1][0],dp[i-1][j][0],dp[i-1][j][1],dp[i-1][j][2],dp[i-1][j][3])
                dp[i][j][1]=dp[i][j-1][1]
                dp[i][j][2]=dp[i][j-1][2]
                dp[i][j][3]=dp[i][j-1][3]
            else:
                dp[i][j][0]=max(dp[i][j-1][0],dp[i-1][j][0],dp[i-1][j][1],dp[i-1][j][2],dp[i-1][j][3])
                dp[i][j][1]=max(dp[i][j-1][1],dp[i][j-1][0]+v,dp[i-1][j][0]+v,dp[i-1][j][1]+v,dp[i-1][j][2]+v,dp[i-1][j][3]+v)
                dp[i][j][2]=max(dp[i][j-1][2],dp[i][j-1][1]+v)
                dp[i][j][3]=max(dp[i][j-1][3],dp[i][j-1][2]+v)
    print(max(dp[i][j]))

if __name__ == "__main__":
    main()

### FIXED CODE ###

r,c,k=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(k)]
dp=[[[0 for _ in range(c+1)]for _ in range(r+1)]for _ in range(5)]
for x,y,z in a:
    dp[4][x][y]=z
for i in range(1,r+1):
    for j in range(1,c+1):
        v=dp[4][i][j]
        dp[0][i][j]=max(dp[0][i][j-1],dp[0][i-1][j],dp[1][i-1][j],dp[2][i-1][j],dp[3][i-1][j])
        dp[1][i][j]=max(dp[1][i][j-1],dp[0][i][j-1]+v,dp[0][i-1][j]+v,dp[1][i-1][j]+v,dp[2][i-1][j]+v,dp[3][i-1][j]+v)
        dp[2][i][j]=max(dp[2][i][j-1],dp[1][i][j-1]+v)
        dp[3][i][j]=max(dp[3][i][j-1],dp[2][i][j-1]+v)
print(max([dp[i][r][c] for i in range(4)]))
### BUGGY CODE ###

K, S = map(int, input().split())
X = range(K + 1)
Y = range(K + 1)
Z = range(K + 1)
count = 0
for i in X:
    for p in Y:
        for o in Z:
            if (S - (i + p)) > K:
                break
            if (i + p + o) == S:
                count += 1
print(count)

### FIXED CODE ###

K, S = map(int, input().split())
X = range(K + 1)
Y = range(K + 1)
Z = range(K + 1)

count = 0

for i in X:
    for p in Y:
        if (S - (i + p)) in Z:
            count += 1

print(count)
### BUGGY CODE ###

s = input()
mod = 10 ** 9 + 7
# for _ in range(len(s) + 1):
#     l = []
#     for __ in range(13):
#         l.append(0)
#     dp.append(l)
dp = [[0 for _ in range(13)] for __ in range(len(s) + 1)]
dp[0][0] = 1
for i, si in enumerate(s[::-1]):
    if si == '?':
        for n in range(10):
            a = n * (10 ** i)
            for j in range(13):
                dp[i+1][(j + a) % 13] = (dp[i+1][(j + a) % 13] + dp[i][j]) % mod
    else:
        a = int(si) * (10 ** i)
        for j in range(13):
            dp[i+1][(j + a) % 13] = (dp[i+1][(j + a) % 13] + dp[i][j]) % mod
print(dp[len(s)][5])


### FIXED CODE ###

s = input()
mod = 10 ** 9 + 7
memo = [0] * (len(s) + 1)
memo[0] = 1
dp = [[0 for _ in range(13)] for __ in range(len(s) + 1)]
dp[0][0] = 1
for i, si in enumerate(s[::-1]):
    memo[i+1] = memo[i] * 10 % 13
    if si == '?':
        for n in range(10):
            a = n * memo[i]
            for j in range(13):
                dp[i+1][(j + a) % 13] = (dp[i+1][(j + a) % 13] + dp[i][j]) % mod
    else:
        a = int(si) * memo[i]
        for j in range(13):
            dp[i+1][(j + a) % 13] = (dp[i+1][(j + a) % 13] + dp[i][j]) % mod
print(dp[len(s)][5])
### BUGGY CODE ###

n,x,y = map(int,input().split())
dists = [0]*(n)
for i in range(n):
    for j in range(i):
        dist = min(abs(i-j),abs((i+1)-x)+1+abs((j+1)-y),abs((j+1)-x)+1+abs((i+1)-y))
        dists[dist] = dists[dist]+1
    
for i in range(len(dists) - 1):
    print(dists[i+1])

### FIXED CODE ###

n,x,y = map(int,input().split())
dists = [0]*(n)
for i in range(1,n+1):
    for j in range(1,i):
        dist = min(abs(i-j),abs(i-x)+1+abs(j-y),abs(j-x)+1+abs(i-y))
        dists[dist] = dists[dist]+1
    
for i in range(len(dists) - 1):
    print(dists[i+1])
### BUGGY CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
ans = 0

for n in range(N-K+1):
	tmp = sum(list(map(lambda x: (x+1)/2, p[n:n+K])))
	if ans < tmp:
		ans = tmp

print(ans)

### FIXED CODE ###

import numpy as np

N, K = map(int, input().split())
p = np.array(list(map(int, input().split())))
ans = tmp = np.sum((p[0:K]+1)/2)

for n in range(1, N-K+1):
	last = (p[n-1]+1)/2
	next = (p[n+K-1]+1)/2
	tmp = tmp - last + next
	if ans < tmp:
		ans = tmp

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

from collections import Counter
n,t = map(int, input().split())
a = list(map(int, input().split()))

benefit = []
for i in range(len(a)):
    if i != 0:
        b = a[i] - min(a[:i])
        if not b <= 0:
            benefit.append(a[i] - min(a[:i]))

ans = Counter(benefit)
for _, c in ans.most_common(1):
    print(c)
    exit(0)

### FIXED CODE ###

#ab = [tuple(map(int, input().split())) for _ in range(n)]
from collections import Counter
from collections import defaultdict
_,_ = map(int, input().split())
a = list(map(int, input().split()))

benefit, min = defaultdict(int), 0
for i in range(len(a)):
    if i == 0 or a[i] <= min:
        min = a[i]
    else:
        benefit[a[i]-min] += 1
print(benefit[max(benefit)])
exit(0)
### BUGGY CODE ###

import bisect

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
C.sort()
cnt = 0
for a in A:
  pos_b = bisect.bisect_right(B, a)
  for pb in range(pos_b, N):
    pos_c = bisect.bisect_right(C, B[pb])
    cnt += N-pos_c
print(cnt)

### FIXED CODE ###

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

nums = []
for idx in range(N):
  nums.append((1, A[idx]))
  nums.append((2, B[idx]))
  nums.append((3, C[idx]))
nums.sort(key=lambda x:(x[1], -x[0]))
sum_a = 0
sum_b = 0
sum_c = 0
for idx in range(3*N):
  if nums[idx][0] == 1:
    sum_a += 1
  elif nums[idx][0] == 2:
    sum_b += sum_a
  elif nums[idx][0] == 3:
    sum_c += sum_b
print(sum_c)
### BUGGY CODE ###

from numpy import*
M=10**9+7
m=lambda:map(int,input().split())
n,k=m()
a=matrix([list(m())for i in[0]*n],'O')
b=eye(n,n,0,'O')
while k:b=[b,b*a%M][k&1];a*=a;k>>=1
print(sum(b)%M)

### FIXED CODE ###

import numpy
M=10**9+7
n,k=map(int,input().split())
a=numpy.matrix([list(map(int,input().split()))for i in[0]*n],dtype='O')
b=numpy.eye(n,dtype='O')
while k:b=[b,b*a%M][k&1];a=a*a%M;k>>=1
print(b.sum()%M)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque

n,m = map(int,readline().split())
s = [set() for i in range(n)]
c = [set() for i in range(n)]
for i in range(m+n-1):
  a,b = map(int,readline().split())
  a -= 1
  b -= 1
  s[a].add(b)
  c[a].add(b)
  
class segment_():
    def __init__(self,n,ide_ele,segfunc):
        self.ide_ele = ide_ele
        self.num = 1 << n.bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        self.segfunc = segfunc
                
    def update(self, k, r):
        k += self.num
        self.seg[k] = r
        while k:
            k >>= 1
            self.seg[k] = self.segfunc(self.seg[k*2], self.seg[k*2+1])

S = segment_(n,set(),lambda a, b: a|b)
for i,ci in enumerate(c):
  S.update(i,ci)
  
p = set([int(i) for i in range(n)])
ans = [0]*n
root = deque()
root.append(-1)
cnt = 0
l = [1]*n

while root:
  if cnt == n:
    break
  now = root.popleft()
  if now >= 0:
    S.update(now,set())
    l[now] -= 1
  child = list(p-S.seg[1])
  for nex in child:
    cnt += 1
    ans[nex] = now+1
    root.append(nex)
    p.remove(nex)
  if now >= 0 and l[now] != 0:
    S.update(now,s[now])
print(*ans,sep='\n')

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque,defaultdict

n,m = map(int,readline().split())
c = [set() for i in range(n)]
d = defaultdict(int)
for i in range(m+n-1):
  a,b = map(int,readline().split())
  a -= 1
  b -= 1
  c[a].add(b)
  d[b] += 1
  
ans = [0]*n
root = deque()
for i in range(n):
  if d[i] == 0:
    root.append(i)
    break
cnt = 1

while True:
  now = root.popleft()
  for nex in c[now]:
    d[nex] -= 1
    if d[nex] == 0:
      cnt += 1
      ans[nex] = now+1
      root.append(nex)
  if cnt == n:
    break
print(*ans,sep='\n')
### 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 ###

import bisect
N,Q = map(int,input().split())
S = input()
lista = []
for j in range(N-1):
    if S[j:j+2] == 'AC':
        lista.append(j)
for i in range(Q):
    l,r = map(int,input().split())
    l,r = l-1,r-1
    lind = bisect.bisect_left(lista,l)
    rind = bisect.bisect_right(lista,r-1)
    print(rind-lind)
### BUGGY CODE ###

N = int(input())
S = input()
S = list(S)
S2 = list(S)
ans = 0
while True:
    cnt = 0
    newS = list(S2)
    i = 0
    while i < (len(S2)-1):
        if S2[i] == '#' and S2[i+1] == '.':
            newS = newS[0:i-cnt*2] + newS[i+2 - cnt*2:]
            ans += 1
            cnt += 1
            i += 1
        i += 1
    S2 = list(newS)
    if cnt == 0:
        break

print(ans)
        
    
    

### FIXED CODE ###

N = int(input())
S = input()

CW = 0

for s in S:
    if s == '.' : CW += 1
    
CB = 0
ans = (CB+CW)
for s in S:
    if s == '.' : CW -= 1
    if s == '#' : CB += 1
    ans = min(ans,CB+CW)
    
print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())

# total = 0
num = 0
for i in range(Q):
    tmp = input().split()

    if tmp[0] == "1":
        # total += 1
        num += 1

    elif tmp[0] == "2":
        num = num % 2
        dada = num + int(tmp[1])

        if dada == 2:
            S = S + tmp[2]

        else:
            S = tmp[2] + S
        # else:
            # S = S + tmp[2]



if num % 2 == 1:
    S = S[::-1]
print(S)

### FIXED CODE ###

S = input()
Q = int(input())

num = 0
mae = ""
usi = ""
for i in range(Q):
    tmp = input().split()

    if tmp[0] == "1":
        num += 1

    elif tmp[0] == "2":
        num = num % 2
        dada = num + int(tmp[1])

        if dada == 2:
            usi += tmp[2]
            # S = S + tmp[2]
            # print("usi: "+usi)
        else:
            mae = tmp[2] + mae
            # S = tmp[2] + S
            # print("mae: "+mae)


if num % 2 == 1:
    S = S[::-1]
    S = usi[::-1] + S + mae[::-1]
else:
    S = mae + S + usi
print(S)
### BUGGY CODE ###

import sys
N, K = map(int, input().split())
p = list(map(int, input().split()))

cnt = {}
x = 0
y = K
while len(p[x:y]) == K:
    cnt[x] = sum(p[x:y])
    x += 1
    y += 1

for x, v in cnt.items():
    if v == max(cnt.values()):
        output = p[x:x+K]
        print(sum(list(map(lambda x : x * 0.5 + 0.5, output))))
        sys.exit(0)

### FIXED CODE ###

N, K = map(int, input().split())
cnt = [int(x) * 0.5 + 0.5 for x in input().split()]

add = [0]
for i in cnt:
    add.append(add[-1]+i)

ans = [add[i+K]-add[i] for i in range(N-K+1)]

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

A, B, N = map(int, input().split())
c = 0
i = 1
x = B * i - 1
while x <= N:
    cc = (A * x) // B - A * (x // B)
    c = max(c, cc)
    i += 1
    x = B * i - 1
if c == 0:
    x = N
    c = (A * x) // B - A * (x // B)
print(c)

### FIXED CODE ###

A, B, N = map(int, input().split())
if N >= B - 1:
    x = B - 1
    c = (A * x) // B - A * (x // B)
else:
    x = N
    c = (A * x) // B - A * (x // B)
print(c)