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

#!/usr/bin/env python3
import sys
INF = float("inf")
import math


class SegmentTree(object):
    # セグメント木

    def __init__(self, N):
        # 単位元
        self.idelem = 0
        # 比較関数
        self.func = max

        self.N0 = 2**(math.ceil(math.log2(N)))
        self.tree = [self.idelem]*(2*self.N0)

    def update(self, k, x):
        k += self.N0-1
        self.tree[k] = x
        while k > 1:
            k = (k-1)//2
            self.tree[k] = self.func(self.tree[2*k+1], self.tree[2*k+2])

    def query(self, l, r):
        l += self.N0-1
        r += self.N0-1
        s = self.idelem
        while l < r:
            if r % 2 == 0:
                r -= 1
                s = self.func(s, self.tree[r])

            if l % 2 == 0:
                s = self.func(s, self.tree[l])
                l += 1
            l //= 2
            r //= 2
        return s

    def __str__(self):
        return str(self.tree[self.N0-1:-1])


def solve(N: int, h: "List[int]", a: "List[int]"):

    seg = SegmentTree(N+1)

    for i in range(N):
        temp = a[i] + seg.query(0, h[i])
        seg.update(h[i], temp)
    print(seg.query(0, N+1))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    h = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, h, a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")
import math


class SegmentTree(object):
    # セグメント木

    def __init__(self, N):
        # 単位元
        self.idelem = 0
        # 比較関数
        self.func = max

        self.N0 = 1
        while self.N0 < N:
            self.N0 *= 2
        self.tree = [self.idelem]*(2*self.N0)

    def update(self, k, x):
        k += self.N0-1
        self.tree[k] = x
        while k > 1:
            k = (k-1)//2
            self.tree[k] = self.func(self.tree[2*k+1], self.tree[2*k+2])

    def query(self, l, r):
        l += self.N0-1
        r += self.N0-1
        s = self.idelem
        while l < r:
            if r % 2 == 0:
                r -= 1
                s = self.func(s, self.tree[r])

            if l % 2 == 0:
                s = self.func(s, self.tree[l])
                l += 1
            l //= 2
            r //= 2
        return s

    def __str__(self):
        return str(self.tree[self.N0-1:-1])


def solve(N: int, h: "List[int]", a: "List[int]"):

    seg = SegmentTree(N+1)

    for i in range(N):
        temp = a[i] + seg.query(0, h[i])
        seg.update(h[i], temp)
    print(seg.query(0, N+1))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    h = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, h, a)


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

K,S= map(int,input().split())
cnt=0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i+j+k  == S:
                cnt+=1
print(cnt)

### FIXED CODE ###

# ABC 051 B - Sum of Three Integers　
k, s = map(int, input().split())
cnt =0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if 0<= z <= k: 
            cnt+=1
print(cnt)
### BUGGY CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))
a = np.array(A)
# l = int(((N*N)+1)/2)
b = []
for i in range(int(((N*N)+1)/2)):
    b.append(1)
    b.append(-1)
# b = b[:-1]
c = (np.array(b[:-1])).reshape(N,N)
# print(b)
# c = (np.delete(b, 2*l-1, axis=None)).reshape(N,N)
# print(c)
# d = c.reshape(N,N)
inv = ( np.triu(c) - np.tril(c) + np.eye(N) )
# g = np.eye(N)
x = (np.dot(inv,a))
ans = list(map(str, list(map(int, list(x)))))
print(" ".join(ans))

### FIXED CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))
a = np.array(A)
# l = int(((N*N)+1)/2)
b = []
for i in range(N):
    if i%2==0:
        b.append(1)
    else:
        b.append(-1)
c = np.dot(np.array(b),a)
x = [c]
for j in range(1,N):
    x_j = 2*a[j-1] - x[j-1]
    x.append(x_j)
ans = list(map(str, list(map(int, list(x)))))
print(" ".join(ans))
### BUGGY CODE ###

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

maxs = 0
for i in range(len(h)):
  
  cnt = 0
  for j in range(i+1, len(h)):
    if h[j-1] < h[j]:
      break
      
    cnt += 1
  maxs = max(maxs, cnt)
  
print(maxs)
    

### FIXED CODE ###

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

maxs = 0
cnt = 0
index = 1
for i in range(1, len(h)):
  if h[i-1] >= h[i]:
    cnt += 1
  else:
    maxs = max(cnt, maxs)
    cnt = 0

print(max(maxs, cnt))
### BUGGY CODE ###

n,w = map(int,input().split())
box = []
v = []
for i in range(n):
  W,V = map(int,input().split())
  box.append([W,V])
  v.append(V)
vmax = n*max(v)
inf = float('inf')
dp = [[inf for i in range(vmax+1)] for j in range(n+1)]
dp[0][0] = 0
for i in range(1,n+1):
  for j in range(vmax+1):
    if j >= box[i-1][1]:
      dp[i][j] = min(dp[i-1][j-box[i-1][1]] + box[i-1][0],dp[i-1][j])
    else:
      dp[i][j] = min(dp[i][j],dp[i-1][j])
ans = []
for i in range(vmax+1):
  if dp[n][i] <= w:
    ans.append(i)
print(max(ans))

### FIXED CODE ###

n,w = map(int,input().split())
box = []
v = []
for i in range(n):
  W,V = map(int,input().split())
  box.append([W,V])
  v.append(V)
vmax = n*max(v)
inf = float('inf')
dp = [[inf for i in range(vmax+1)] for j in range(n+1)]
dp[0][0] = 0
for i in range(1,n+1):
  for j in range(vmax+1):
    if j >= box[i-1][1]:
      dp[i][j] = min(dp[i-1][j-box[i-1][1]] + box[i-1][0],dp[i-1][j])
    else:
      dp[i][j] = min(dp[i][j],dp[i-1][j])
ans = []
for i in range(vmax+1):
  if dp[n][i] <= w:
    ans.append(i)
print(max(ans))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
d = {}
for i in range(N):
  if A[i] in d:
    d[A[i]] += 1
  else:
    d[A[i]] = 1
#print(A, d)

for i in range(N):
  ans = 0
  for k, v in d.items():
    if k == A[i]:
      ans+= (v-1)*max(v-2,0)/2
    else:
      ans+= v * (v-1)/ 2
  print(int(ans))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
d = {}
d_sum = {}
for i in range(N):
  if A[i] in d:
    d[A[i]] += 1
    d_sum[A[i]] += d[A[i]] - 1
  else:
    d[A[i]] = 1
    d_sum[A[i]] = 0
#print(A, d,d_sum)
#print(sum(A), sum(d.values()))
ans = sum(d_sum.values())
for i in range(N):
  print(ans - (d[A[i]] - 1))
### BUGGY CODE ###

import itertools
import sys
input = sys.stdin.readline

n,m = map(int, input().split())
xs,ys,zs = [], [], []
for _ in range(n):
  a,b,c = map(int, input().split())
  xs.append(a)
  ys.append(b)
  zs.append(c)

ans = 0
for com in itertools.combinations(range(n), m):
  x = sum(xs[c] for c in com)
  y = sum(ys[c] for c in com)
  z = sum(zs[c] for c in com)
  ans = max(abs(x)+abs(y)+abs(z),ans)
print(ans)

### FIXED CODE ###

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

n,m = map(int, input().split())
xs = []
for _ in range(n):
  x,y,z = map(int, input().split())
  xs.append([x, y, z, x+y+z, x+y-z, x-y+z, x-y-z, -x+y+z, -x+y-z, -x-y+z, -x-y-z])

ans = 0
xs.sort(key=itemgetter(3))
tot = abs(sum(xs[i][0] for i in range(m))) + abs(sum(xs[i][1] for i in range(m))) + abs(sum(xs[i][2] for i in range(m)))
ans = max(ans, tot)

xs.sort(key=itemgetter(4))
tot = abs(sum(xs[i][0] for i in range(m))) + abs(sum(xs[i][1] for i in range(m))) + abs(sum(xs[i][2] for i in range(m)))
ans = max(ans, tot)

xs.sort(key=itemgetter(5))
tot = abs(sum(xs[i][0] for i in range(m))) + abs(sum(xs[i][1] for i in range(m))) + abs(sum(xs[i][2] for i in range(m)))
ans = max(ans, tot)

xs.sort(key=itemgetter(6))
tot = abs(sum(xs[i][0] for i in range(m))) + abs(sum(xs[i][1] for i in range(m))) + abs(sum(xs[i][2] for i in range(m)))
ans = max(ans, tot)

xs.sort(key=itemgetter(7))
tot = abs(sum(xs[i][0] for i in range(m))) + abs(sum(xs[i][1] for i in range(m))) + abs(sum(xs[i][2] for i in range(m)))
ans = max(ans, tot)

xs.sort(key=itemgetter(8))
tot = abs(sum(xs[i][0] for i in range(m))) + abs(sum(xs[i][1] for i in range(m))) + abs(sum(xs[i][2] for i in range(m)))
ans = max(ans, tot)

xs.sort(key=itemgetter(9))
tot = abs(sum(xs[i][0] for i in range(m))) + abs(sum(xs[i][1] for i in range(m))) + abs(sum(xs[i][2] for i in range(m)))
ans = max(ans, tot)

xs.sort(key=itemgetter(10))
tot = abs(sum(xs[i][0] for i in range(m))) + abs(sum(xs[i][1] for i in range(m))) + abs(sum(xs[i][2] for i in range(m)))
ans = max(ans, tot)

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

# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
S = input().rstrip()
T = input().rstrip()

chars1 = set()
for t in T:
    chars1.add(t)
chars2 = set()
for s in S:
    chars2.add(s)

for c in chars1:
    if c not in chars2:
        print(-1)
        sys.exit()

idx = S.index(T[0])
ans = idx+1
for i in range(1,len(T)):
    S = S[idx+1:] + S[:idx+1]
    idx = S.index(T[i])
    ans += idx+1

print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
#ABC138 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

s = input()
t = input()
n = len(s)
m = len(t)
f = [False]*26
f2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(n):
    f[alpha.index(s[i])] = True
for i in range(m):
    f2[alpha.index(t[i])] = True
for i in range(26):
    if not f[i] and f2[i]:
        print(-1)
        quit()
ans = 0
inde = s.index(t[0])
ans += inde+1
for i in range(1,m):
    s = s[inde+1:] + s[:inde+1]
    inde = s.index(t[i])
    ans += inde+1
print(ans)
### BUGGY CODE ###

n = int(input())
ans = 0
for a in range (1,n):
  for b in range (1,n):
    if n > (a * b):
        ans += 1
    else:
        break

print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
for a in range (1,n):
    for b in range(a, n, a):
        ans += 1
print(ans)
### BUGGY CODE ###

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

import math
N = int(input())
l = math.factorial(N)
t = make_divisors(l)
print(len(t)%(10**9+7))


### FIXED CODE ###

N= int(input())

m = 10**9+7
pri_num = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
dic = {}

for i in range(2,N+1):
    for pri in pri_num:
        while i>0:
            if i % pri == 0:
                if pri in dic:
                    dic[pri] +=1
                else:
                    dic[pri]=1
                i = i//pri

            else:
                break

count = 1
for val in dic.values():
    count = (count*(val+1))%m
print(count)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
 
MOD = 10**9 + 7
 
from functools import reduce
from fractions import gcd
def lcm(x,y):return x*y//gcd(x,y)
def lcmm(l):return reduce(lcm,l)
 
x = lcmm(A)
 
ans = sum(x//a for a in A)
ans %= MOD
 
print(ans)

### FIXED CODE ###

from functools import reduce
from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
 
MOD = 10 ** 9 + 7
 
lcm = reduce(lambda x,y: x*(y//gcd(x,y)), A)
lcm %= MOD

coef = sum(pow(a, MOD-2, MOD) for a in A)
ans = lcm * coef % MOD

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

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def solve(S: str):
    ## 1の位からi+1文字のうち13で割ったもののあまりがjであるものの数
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0]=1
    for i in range(1,N+1):
        if S[N-i]=="?":
            for j in range(0,10):
                addmod = (j*10**(i-1))%13
                for k in range(0,13):
                    modmod = (k+addmod)%13
                    dp[i][modmod] += dp[i-1][k]%MOD
        else:
            addmod = (int(S[N-i])*10**(i-1))%13
            for k in range(0,13):
                modmod = (k+addmod)%13
                dp[i][modmod] = dp[i-1][k]%MOD

    print(dp[N][5]%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def solve(S: str):
    ## 1の位からi+1文字のうち13で割ったもののあまりがjであるものの数
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0]=1
    list10 = range(0,10)
    list13 = range(0,13)
    keta =1
    for i in range(1,N+1):
        if S[N-i]=="?":
            for j in list10:
                addmod = j*keta%13
                for k in list13:
                    modmod = (k+addmod)%13
                    dp[i][modmod] += dp[i-1][k]%MOD
        else:
            addmod = (int(S[N-i])*keta)%13
            for k in list13:
                modmod = (k+addmod)%13
                dp[i][modmod] = dp[i-1][k]%MOD
        keta*=10
        keta%=13
    print(dp[N][5]%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

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

#!/usr/bin/env python3
import sys

sys.setrecursionlimit(1000000)

n, m, *a = map(int, open(0).read().split())
dp = [0] * (n + 1)
ok = [True] * (n + 1)

for i in a:
    ok[i] = False


def count(n):
    if ok[n]:
        if n < 2:
            return 1
        if dp[n] != 0:
            return dp[n]
        dp[n] = (count(n - 1) + count(n - 2)) % (10**9 + 7)
        return dp[n]
    else:
        return 0


print(count(n))


### FIXED CODE ###

#!/usr/bin/env python3
import sys

sys.setrecursionlimit(1000000)


memo = [0]*(10**5+1)
def count(n):
    if n < 2:
        return 1
    if memo[n] != 0:
        return memo[n]
    memo[n] = count(n-1) + count(n-2)
    return memo[n]


n, m, *a = map(int, open(0).read().split())
if sum(a[i + 1] == a[i] + 1 for i in range(m - 1)) > 0:
    print(0)
    exit()

a.append(n + 1)
c = -1
ans = 1
for i in a:
    ans = ans * count(i - c - 2) % (10**9 + 7)
    c = i
print(ans)
### BUGGY CODE ###

S = input()
N = int(input())
is_inversed = False
for i in range(N):
    Q = input()
    if Q[0] == '1':
        is_inversed = not (is_inversed)
    else:
        if (Q[2] == '1' and is_inversed) or (Q[2] == '2' and not (is_inversed)):
            S = S + Q[4]
        else:
            S = Q[4] + S

if is_inversed:
    print(S[::-1])
else:
    print(S)

### FIXED CODE ###

from collections import deque
S = deque(input())
N = int(input())
is_inversed = False
for i in range(N):
    Q = input()
    if Q[0] == '1':
        is_inversed = not (is_inversed)
    else:
        if (Q[2] == '1' and is_inversed) or (Q[2] == '2' and not (is_inversed)):
            S.append(Q[4])
        else:
            S.appendleft(Q[4])
if is_inversed:
    print(''.join(list(S)[::-1]))
else:
    print(''.join(S))
### BUGGY CODE ###

N, K =map(int, input().split())
bordor = []
while(K >= 1):
  bordor.insert(0, K)
  K / 2
  
print(bordor)

### FIXED CODE ###

import math
N, K =map(int, input().split())
k = K
bordor = []
Ans = 0
while(K >= 1):
  bordor.append(K)
  K = K / 2
  
for i in range(len(bordor) - 1):
  if bordor[i] <= N:
    Ans += (math.ceil(bordor[i]) - math.ceil(bordor[i + 1])) * (1 / (2 ** (i + 1)))
    
 
  elif bordor[i] > N >= bordor[i + 1]:
    Ans += (N + 1 - math.ceil(bordor[i + 1])) * (1 / (2 ** (i + 1)))
    
if bordor[-1] != 1:
  Ans += 1 / (2 ** len(bordor))

if N >= k:
  Ans += (N - k + 1)
Ans = Ans / N  

print(Ans)
### BUGGY CODE ###

n, m = map(int, input().split())
cards = list(map(int, input().split()))

for i in range(m):
    b, c = map(int, input().split())
    cards += ([c] * b)
    cards = sorted(cards, reverse=True)[:n]

print(sum(cards))

### FIXED CODE ###

import numpy as np
 
n, m = map(int, input().split())
 
cards = list(map(int, input().split()))
cards = np.array(cards, np.int64)
cards.sort()

bc = [list(map(int, input().split())) for _ in range(m)]
bc = np.array(bc, np.int64)

B = bc[:,0]
C = bc[:,1]
 
#並び替えた配列のidxをnparrayで取得
idx = C.argsort()
B = B[idx][::-1]
C = C[idx][::-1]
 
p = 0
for b,c in zip(B,C):
    cards[p:p+b] = np.maximum(cards[p:p+b], c)
    p += b

print(sum(cards))
### BUGGY CODE ###

K,S=map(int,input().split())
cnt=0
for i in range(K+1):
    for t in range(K+1):
        for s in range(K+1):
            if i+t+s==S:
                cnt+=1
            else:
                continue
print(cnt)

### FIXED CODE ###

K,S=map(int,input().split())
cnt=0
for i in range(K+1):
    for t in range(K+1):
        s=S-i-t
        if 0<=s<=K:
            cnt+=1
        else:
            continue
print(cnt)
### BUGGY CODE ###

a = input().split()
k = int(a[0])
s = int(a[1])
count = 0
for n1 in range(k+1):
    for n2 in range(k+1):
        for n3 in range(k+1):
            if n1+n2+n3==s:
                count += 1

print(count)

### FIXED CODE ###

a = input().split()
k = int(a[0])
s = int(a[1])
count = 0
for n1 in range(k+1):
    for n2 in range(k+1):
        if 0<=(s - n1 - n2)<=k:
            count += 1

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

s=list(input())
mod=10**9+7
for i in range(len(s)):
    if s[i]=='?':
        s[i]=-1
    else:
        s[i]=int(s[i])

dp=[[0]*13 for i in range(len(s)+1)]
s.reverse()
y=[]

for i in range(len(s)):
    if s[i]!=-1:
        x=(s[i]*10**i)%13
        if i==0:
            dp[i+1][x]=1
        else:
            for j in range(13):
                dp[i+1][(j+x)%13]+=(dp[i][j])
    else:
        for j in range(10):
            y.append((j*10**i)%13)
        if i==0:
            for k in range(len(y)):
                dp[i+1][y[k]]+=1
                    
        for k in range(13):
            for l in range(len(y)):
                dp[i+1][(k+(y[l]))%13]+=(dp[i][k])
        y=[]
print(dp[len(s)][5]%mod)
            
        
        


     

    


### FIXED CODE ###

s=list(input())
mod=10**9+7
for i in range(len(s)):
    if s[i]=='?':
        s[i]=-1
    else:
        s[i]=int(s[i])

dp=[[0]*13 for i in range(len(s)+1)]
s.reverse()
dp[0][0]=1
y=[]
x=1
for i in range(len(s)):
    if s[i]!=-1:
        z=s[i]*x

        for j in range(13):
            dp[i+1][(j+z)%13]+=dp[i][j]%mod
    else:
        for j in range(10):
            y.append(x*j)

        for k in range(13):
            for l in range(len(y)):
                dp[i+1][(k+y[l])%13]+=dp[i][k]%mod
        y=[]
    x=(x*10)%13
        
print(dp[len(s)][5]%mod)
### BUGGY CODE ###

import math
from math import floor
A,B,N = map(int,input().split())
maxi = 0
Npower = 0
diff = 0
S = N
while S/10 >= 1:
    Npower += 1
    S /=10
if Npower >= 7 and Npower < 11:
    print(N-10**6-10**5-10**4-10**3-10**2)
    for i in range(0,10**6+10**5):
        maxi = max(floor((A*i)/B)-A*floor(i/B),maxi)
    for i in range(N-10**6-10**5-10**4-10**3-10**2,N+1):
        maxi = max(floor((A*i)/B)-A*floor(i/B),maxi)
else:
    for i in range(0,N+1):
        maxi = max(floor((A*i)/B)-A*floor(i/B),maxi)
print(max(maxi,0))

### FIXED CODE ###

import math
from math import floor
A,B,N = map(int,input().split())
def f(x):
  return floor(A*x/B) - A*floor(x/B)
print(f(min(B-1,N)))
### BUGGY CODE ###

N = int(input())
A=list(map(int,input().split()))
L=[0]*65
MOD=(10**9+7)
for i in range(N):
    t=str(format(A[i],"b"))
    for j in range(len(t)):
        L[j]+=int(t[-j-1])

for i in range(len(L)):
    L[i]=L[i]*(N-L[i])
    L[i]*=2**i
print(sum(L)%MOD)




### FIXED CODE ###

N = int(input())
A=list(map(int,input().split()))
L=[0]*65
MOD=(10**9+7)
for i in range(N):
    t=str(format(A[i],"b"))
    for j in range(len(t)):
        L[j]+=int(t[-j-1])

for i in range(len(L)):
    L[i]=L[i]*(N-L[i])
    L[i]*=2**i
    L[i]%=MOD
print(sum(L)%MOD)
### BUGGY CODE ###

s = str(input())
n = int(input())

for _ in range(n):
    q = input()

    # 反転の場合
    if q[0] == "1":
        s = s[::-1]
        continue

    q = q.split()

    if q[1] == "1":
        s = q[2] + s

    if q[1] == "2":
        s = s + q[2]

print(s)


### FIXED CODE ###

s = str(input())
n = int(input())

stat = 0
front = ""
back = ""

for _ in range(n):
    q = input()

    # 反転の場合
    if q[0] == "1":
        stat = (stat + 1) % 2
        continue

    judge = int(q[2])
    if stat == 1:
        if judge == 1:
            judge = 2
        elif judge == 2:
            judge = 1

    if judge == 1:
        front = q[4] + front 

    if judge == 2:
        back = back + q[4]

s = front + s + back
if stat == 1:
    s = s[::-1]

print(s)
### BUGGY CODE ###

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

#素数
def primes(n):
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1, int(n**0.5)//3+1):
        if sieve[i]:
            k = 3*i+1|1
            sieve[k*k//3::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2, 3] + [3*i+1|1 for i in range(1, n//3-correction) if sieve[i]]

primes=primes(int(1000))
points=[0]*1000001

from math import gcd
pairprime_flag=True
allgcd=A[0]
allprime=set()

for a in A:
    allgcd=gcd(allgcd,a)
    for i in primes:
        if a%i==0:
            if points[i]==1:
                pairprime_flag=False
            points[i]=1
            while a%i==0:
                a//=i
        if a==1:
            break
    if a!=1:
        if points[a]!=0:
            pairprime_flag=False
        else:
            points[a]=1

if pairprime_flag:
    print('pairwise coprime')
elif allgcd==1:
    print('setwise coprime')
else:
    print('not coprime')


### FIXED CODE ###

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

#素数
def primes(n):
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1, int(n**0.5)//3+1):
        if sieve[i]:
            k = 3*i+1|1
            sieve[k*k//3::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2, 3] + [3*i+1|1 for i in range(1, n//3-correction) if sieve[i]]

primes=primes(int(1000))
points=[0]*1000001

from math import gcd
pairprime_flag=True
allgcd=A[0]
allprime=set()

for a in A:
    allgcd=gcd(allgcd,a)
    if pairprime_flag:
        for i in primes:
            if a%i==0:
                if points[i]==1:
                    pairprime_flag=False
                points[i]=1
                while a%i==0:
                    a//=i
            if a==1:
                break
        if a!=1:
            if points[a]!=0:
                pairprime_flag=False
            else:
                points[a]=1

if pairprime_flag:
    print('pairwise coprime')
elif allgcd==1:
    print('setwise coprime')
else:
    print('not coprime')