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

from math import gcd
N = int(input())
A = list(map(int,input().split()))

g = 0
for a in A:
    g = gcd(g,a)
if g > 1:
    print('not coprime')
    exit()

MAXN = 10**6+10
sieve = [0,0] + [1]*MAXN
p = 2
primes = set()
while p*p <= MAXN:
    if sieve[p]:
        primes.add(p)
        for q in range(2*p,MAXN+1,p):
            sieve[q] = 0
    p += 1
for i in range(p,MAXN+1):
    if sieve[i]:
        primes.add(i)

for a in A:
    dels = set()
    for p in primes:
        if p > a: continue
        while a%p==0:
            a //= p
            dels.add(p)
    if a > 1:
        print('setwise coprime')
        exit()
    for p in dels:
        primes.remove(p)
print('pairwise coprime')

### FIXED CODE ###

from math import gcd
N = int(input())
A = list(map(int,input().split()))

g = 0
for a in A:
    g = gcd(g,a)
if g > 1:
    print('not coprime')
    exit()

sa = set()
for a in A:
    if a==1: continue
    if a in sa:
        print('setwise coprime')
        exit()
    sa.add(a)

MAXN = 10**6+10
sieve = [0,0] + [1]*MAXN
p = 2
small_primes = []
while p*p <= MAXN:
    if sieve[p]:
        small_primes.append(p)
        for q in range(2*p,MAXN+1,p):
            sieve[q] = 0
    p += 1

st = set()
for a in A:
    for p in small_primes:
        found = False
        while a%p==0:
            a //= p
            found = True
        if found:
            if p in st:
                print('setwise coprime')
                exit()
            st.add(p)
        if a==1: break
    else:
        if a in st:
            print('setwise coprime')
            exit()
        st.add(a)

print('pairwise coprime')
### BUGGY CODE ###

N, W = map(int, input().split())
items = [[0, 0]]
v_max = 0
for _ in range(N):
    w, v = map(int, input().split())
    items.append([w, v])
    v_max = max(v_max, v)

dp = [[float("inf") for _ in range(N * v_max + 1)] for _ in range(N + 1)]

for i in range(N + 1):
    dp[i][0] = 0

for i in range(1, N + 1):
    for j in range(N * v_max + 1):
        if j - items[i][1] >= 0:
            dp[i][j] = min(dp[i - 1][j - items[i][1]] + items[i][0], dp[i - 1][j])
        else:
            dp[i][j] = dp[i - 1][j]

ans = 0
for j in range(len(dp[N])):
    if dp[N][j] <= W:
        ans = max(ans, j)
print(ans)

### FIXED CODE ###

N, W = map(int, input().split())
items = [[0, 0]]
v_total = 0
for _ in range(N):
    w, v = map(int, input().split())
    items.append([w, v])
    v_total += v

dp = [[float("inf")] * (v_total + 1) for _ in range(N + 1)]

for i in range(N + 1):
    dp[i][0] = 0

ans = 0
for i in range(1, N + 1):
    for j in range(v_total + 1):
        if j - items[i][1] >= 0:
            dp[i][j] = min(dp[i - 1][j - items[i][1]] + items[i][0], dp[i - 1][j])
        else:
            dp[i][j] = dp[i - 1][j]

        if i == N and dp[i][j] <= W:
            ans = max(ans, j)

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

def main():
    H, W, D = map(int, input().split())
    M = [0 for _ in range(100000)]
    for i in range(H):
        for j, v in enumerate(list(map(int, input().split()))):
            M[v] = (i, j)
    Q = int(input())
    P = []
    ans = []
    for _ in range(Q):
        L, R = map(int, input().split())
        if L == R:
            ans.append(0)
            continue
        while True:
            P.append(M[L])
            if L == R:
                break
            L += D
        m = 0
        for i in range(len(P) - 1):
            m += abs(P[i][0] - P[i + 1][0]) + abs(P[i][1] - P[i + 1][1])
        ans.append(m)
    for a in ans:
        print(a)


main()


### FIXED CODE ###

def main():
    H, W, D = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    Q = int(input())
    ans = []

    x = [0 for _ in range(90001)]
    y = [0 for _ in range(90001)]
    dp = [0 for _ in range(90001)]

    for i, row in enumerate(A):
        for j, a in enumerate(row):
            x[a] = j
            y[a] = i
    for i in range(D + 1, H * W + 1):
        dp[i] = dp[i - D] + abs(x[i] - x[i - D]) + abs(y[i] - y[i - D])

    for _ in range(Q):
        L, R = map(int, input().split())
        ans.append(dp[R] - dp[L])
    for a in ans:
        print(a)


main()
### BUGGY CODE ###

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

for i in range(N):
  if i != 0:
    tmp = A[:i]+A[i+1:]
  else:
    tmp = A[1:]
  print(max(tmp))

### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
A_max = max(A)
A_max_count = A.count(A_max)
if A_max_count != N:
  a_ = A[:]
  a_ = sorted(a_,reverse = True)
  A_next_max = a_[A_max_count]
else:
  A_next_max = A_max_count

for i in range(N):
  tmp = A[i]
  if tmp != A_max:
    print(A_max)
  else:
    if A_max_count == 1:
      print(A_next_max)
    else:
      print(A_max)
### BUGGY CODE ###

N, Q = map(int, input().split(" "))
 
ns= [list(map(int, input().split(" ")))  for _ in range(N-1)]
vs = [list(map(int, input().split(" ")))  for _ in range(Q)]
 
flags = [True]+[False]*(N-1)
dic = [[] for _ in range(N)]
rlt = [0]*N
 
for i in range(N-1):
  dic[ns[i][1]-1] += [ns[i][0]-1]
  dic[ns[i][0]-1] += [ns[i][1]-1]
  
for j in range(Q):
  rlt[vs[j][0]-1] += vs[j][1]
  
for k in range(N):
  for l in dic[k]:
    if flags[l]:
      continue
    else:
      rlt[l] += rlt[k]
      flags[l] = True
    
print(" ".join(map(str, rlt)))

### FIXED CODE ###

N, Q = map(int, input().split(" "))
 
ns= [list(map(int, input().split(" ")))  for _ in range(N-1)]
vs = [list(map(int, input().split(" ")))  for _ in range(Q)]

dic = [[] for _ in range(N)]
rlt = [0]*N


for i in range(N-1):
  dic[ns[i][0]-1] += [ns[i][1]-1]
  
for j in range(Q):
  rlt[vs[j][0]-1] += vs[j][1]
  
for k in range(N):
  for l in dic[k]:
    rlt[l] += rlt[k]
    
print(" ".join(map(str, rlt)))
### BUGGY CODE ###

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

A = []

for i in range(Q):
    A.append(int(input()))

res = [K]*N

for i in range(Q):
    res = list(map(lambda x: x-1,res))
    temp = A[i]-1
    res[temp] = res[temp] + 1

for i in range(N):
    if res[i] > 0:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

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

A = []

for i in range(Q):
    A.append(int(input()))

points = [K-Q]*N

for i in range(Q):
    points[A[i]-1] += 1

for i in range(N):
    if points[i] > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
cost=[0]
for i in range(1,n):
  wk=-1
  for j in range(1,min(i,k)+1):
    if wk==-1:
      wk=cost[i-j]+abs(h[i]-h[i-j])
    else:
      wk=min(wk,cost[i-j]+abs(h[i]-h[i-j]))
  cost.append(wk)
print(cost[n-1])

### FIXED CODE ###

from numba import jit
n,k=map(int,input().split())
h=list(map(int,input().split()))
@jit
def jitcalc(n,k,h):
  cost=[0]
  for i in range(1,n):
    wk=[]
    for j in range(1,min(k,i)+1):
      wk.append(cost[i-j]+abs(h[i]-h[i-j]))
    cost.append(min(wk))
  print(cost[n-1])
jitcalc(n,k,h)
### BUGGY CODE ###

n, k = [int(x) for x in input().split()]

while n > abs(n-k):
    n = abs(n-k)
    if k == 1:
        n = 0
        break
    
    if n%k == 0:
        n = 0
        break

print(n)

### FIXED CODE ###

n, k = [int(x) for x in input().split()]

while n > abs(n-k):
    if k == 1:
        n = 0
        break
    elif n%k == 0:
        n = 0
        break

    if n > k:
        n = n%k
    else:
        n = abs(n-k)    
    

print(n)
### BUGGY CODE ###

N = int(input())

A = []

for _ in range(N):
    A.append(int(input()))

color_base = []

for i, a in enumerate(A):
    for j, color in enumerate(color_base):
        if a > color :
            color_base[j] = a
            break
    else :
        color_base.append(a)

print(len(color_base))


### FIXED CODE ###

import bisect

N = int(input())

A = [int(input()) for _ in range(N)]

colors = []

for i in range(N-1, -1, -1):
    target = bisect.bisect_right(colors, A[i])

    if target == len(colors):
        colors.append(A[i])
    else:
        colors[target] = A[i]

print(len(colors))
### BUGGY CODE ###

import copy
N = int(input())
numList = list(map(int, input().split()))
medIndex = int((N-1)/2)

for i in range(0,N):
	numListCopy = copy.deepcopy(numList)
	numListCopy.pop(i)
	numListCopy.sort()
	print(numListCopy[medIndex])

### FIXED CODE ###

import copy
N = int(input())
numList = list(map(int, input().split()))
numListCopy = copy.deepcopy(numList)
numList = sorted(numList)
medIndex = int((N)/2)
med1 = numList[medIndex-1]
med2 = numList[medIndex]


for i in range(0,N):
	if numListCopy[i] <= med1:
		print(med2)
	elif med2 <= numListCopy[i]:
		print(med1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(500000)

N, Q = map(int, input().split())
G = [set() for _ in range(N)]
cnt = [0]*N
visited = [0]*N


def dfs(start_node):
    for i in G[start_node]:
        if visited[i]==0:
            visited[i]=1
            cnt[i] += cnt[start_node]
            dfs(i)

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

for i in range(Q):
    node, x = map(int, input().split())
    node -= 1
    cnt[node] += x

visited[0]=1
dfs(0)

ans = map(str, cnt)
print(' '.join(ans))

### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)

N, Q = map(int, input().split())
G = [set() for _ in range(N)]
cnt = [0]*N
visited = [0]*N

def dfs(start_node):
    for i in G[start_node]:
        if visited[i]==0:
            visited[i]=1
            cnt[i] += cnt[start_node]
            dfs(i)

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

for i in range(Q):
    node, x = map(int, input().split())
    node -= 1
    cnt[node] += x

visited[0]=1
#dfs(0)
st = [0]
while st:
    v = st.pop()
    for u in G[v]:
        if visited[u]: continue
        visited[u] = 1
        cnt[u] += cnt[v]
        st.append(u)    

ans = map(str, cnt)
print(' '.join(ans))
### BUGGY CODE ###

N, M = map(int,input().split())
ans = 0
while True:
    if 1 <= N and 2 <= M:
        N -= 1
        M -= 2
        ans += 1
        continue
    if N == 0 and 4 <= M:
        M -= 4
        ans += 1
    else:
        break
print(ans)

### FIXED CODE ###

N, M = map(int,input().split())
ans = 0
if M - 2*N < 0:
    print(M//2)
else:
    print(N+((M-2*N)//4))
### BUGGY CODE ###

from collections import Counter

N = int(input())
c = Counter()
for i in range(N):
    k = input()
    v = c.setdefault(k, 0)
    c[k] = v + 1
ans = sorted([k for k,n in c.items() if n == max(c.values())])
[print(k) for k in ans]


### FIXED CODE ###

from collections import Counter

N = int(input())
c = Counter()
l = 0
for i in range(N):
    k = input()
    v = c.setdefault(k, 0)
    c[k] = v + 1
    if l < c[k]:
        l = c[k]
ans = sorted([k for k, n in c.items() if n==l])
[print(k) for k in ans]
### BUGGY CODE ###

import numpy as np
def osilate(acc):
    acc = np.array(acc)
    flag = 1
    ans = 0
    while len(acc) > 0:
        #print(acc)
        a = acc[0]
        if flag > 0:
            if a <= 0:
                ans += 1-a
                acc = acc + (1-a)
        if flag < 0:
            if a >= 0:
                ans += 1+a
                acc = acc - (1+a)
        acc = acc[1:]
        flag = flag * (-1)
    return ans

n = int(input())
seq = [int(i) for i in input().split()]
acc = []
tmp = 0
for i in seq:
    tmp += i
    acc.append(tmp)
acc_rev = [-i for i in acc]

print(min(osilate(acc),osilate(acc_rev)))


### FIXED CODE ###

def osilate(seq):
    flag = 1
    acc = 0
    ans = 0
    #while loop O(n)
    for i in range(len(seq)):
        a = seq[i]
        acc += a
        flag = i%2

        if flag == 0:
            if acc <= 0:
                ans += 1-acc
                acc = 1
        if flag == 1:
            if acc >= 0:
                ans += 1+acc
                acc = -1
        #print(seq, acc, acc)
        flag = flag * (-1)
    return ans

n = int(input()) #(1)
seq = [int(i) for i in input().split()] #O(N)

seq_rev = [-i for i in seq]  # O(N)
print(min(osilate(seq),osilate(seq_rev))) #O(2N)
### BUGGY CODE ###

def prime_number(x):
    if x==2 or x==3:
        return True
    else:
        if x%2==0 or x%3==0:
            return False
        else:
            divisor_lst = [1,x]
            for i in range(1,x+1):
                if i%2!=0 and i%3!=0:
                    if i not in divisor_lst and x%i==0:
                        return False
                        break
            else:
                return True

n = int(input())

if prime_number(n):
    print(n-1)
else:
    i = 1
    j = n//i
    divisor_lst = []
    while i<=j:
        i += 1
        j = n//i
        if n%i==0:
            divisor_lst.append([i,j])

    n_x = divisor_lst[-1][0]
    n_y = divisor_lst[-1][1]
    print(n_x+n_y-2)

### FIXED CODE ###

n = int(input())

need_lst = []
for i in range(1,int(n**(1/2)+1)):
    if n%i==0:
        need = i+n//i
        need_lst.append(need-2)

print(min(need_lst))
### BUGGY CODE ###

n,k = map(int,input().split())
mp = list(map(int,input().split()))
save = []

s_queue = [[1,0]]
while(len(s_queue)>0):
    i,cnt = s_queue.pop()
    if(cnt==k):
        break
    if(mp[i-1] in save):
        last=mp[i-1]
        break
    save.append(mp[i-1])
    s_queue.append([mp[i-1],cnt+1])


ls = len(save)

if(k<=ls):
    print(save[k-1])
else:
    for i in range(ls):
        if(save[i]==last):
            si = i
    k -= si
    save = save[si:]
    ls = len(save)
    amari = k%ls
    print(save[amari-1])


### FIXED CODE ###

n,k = map(int,input().split())
mp = list(map(int,input().split()))
save = []
isSaved = [False]*(n+1)
s_queue = [[1,0]]
while(len(s_queue)>0):
    i,cnt = s_queue.pop()
    if(cnt==k):
        break
    if(isSaved[i]):
        last=mp[i-1]
        break
    nexti = mp[i-1]
    isSaved[i] = True
    save.append(nexti)
    s_queue.append([nexti,cnt+1])


ls = len(save)

if(k<=ls):
    print(save[k-1])
else:
    for i in range(ls):
        if(save[i]==last):
            si = i
    k -= si
    save = save[si:]
    ls = len(save)
    amari = k%ls
    print(save[amari-1])
### BUGGY CODE ###

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

def func(k):
    ans = 0
    D = 0
    M = 0
    DM = 0
    for i in range(k):
        if S[i] == "D":
            D += 1
        elif S[i] == "M":
            M += 1
            DM += D
        elif S[i] == "C":
            ans += DM
    for i in range(k,N):
        if S[i-k] == "D":
            D -= 1
            DM -= M
        elif S[i-k] == "M":
            M -= 1
        if S[i] == "D":
            D += 1
        elif S[i] == "M":
            M += 1
            DM += D
        elif S[i] == "C":
            ans += DM
    return ans
for i in K:
    print(func(i))

### FIXED CODE ###

N = int(input())
S = list(input())
Q = int(input())
K = list(map(int,input().split()))
DP = [[0,0,0]]
C = []
for i in range(N):
    q = DP[i][:]
    if S[i] == "D":
        q[0] += 1
    elif S[i] == "M":
        q[1] += 1
        q[2] += q[0]
    elif S[i] == "C":
        C.append(i+1)
    DP.append(q)

for k in K:
    ans = 0
    for c in C:
        if c < k:
            ans += DP[c][2]
        else:
            ans += DP[c][2] - DP[c-k][2] - DP[c-k][0]*(DP[c][1] - DP[c-k][1])
    print(ans)
### BUGGY CODE ###

import numpy as np
N=int(input())
P= np.array([int(x) for x in input().split()])
cnt=0
for i in range(N):
  if np.amin(P[:i+1])==P[i]:
    cnt+=1
print(cnt)

### FIXED CODE ###

N=int(input())
P=[int(x) for x in input().split()]
cnt=0
tmp=P[0]
for i in range(N):
  if P[i]<=tmp:
    cnt+=1
    tmp=P[i]
print(cnt)
### BUGGY CODE ###

def solve():

    N,M=map(int,input().split()) #N個の問題,M回の提出
    A_list=[]#正解問題番号を入れる
    W_list=[0]*N
    WA=0
    PS=[list(map(str,input().split())) for i in range(M) ]
    ans=0
    pena=0
    for x in range(M):
        if PS[x][0] not in A_list:
            if PS[x][1]=='AC':
                A_list.append(PS[x][0])
                ans+=1
                WA+=W_list[int(PS[x][0])-1]
            else:
                #pena+=1
                W_list[int(PS[x][0])-1]+=1
    
    #print(ans,pena)
    print(ans,WA)
solve()


### FIXED CODE ###

n, m = map(int, input().split())
AC = [0] * (n+1) #その問題で既に AC が出たか
b = [0] * (n+1) #その問題で WA が出た回数

WA = 0

for i in [0]*(m):

    s = input().split()

    if AC[int(s[0])] == 0:
        if s[1] == "AC":
            AC[int(s[0])] = 1
            WA += b[int(s[0])]
        else:
            b[int(s[0])] += 1

print(sum(AC), WA)
### BUGGY CODE ###

N = int(input())
S = input().strip()
qn = int(input())
qs = list(map(int, input().split()))
dp = [[0,0,0] for _ in range(N+1)]
As = [0]*qn
for i, c in enumerate(S):
    i += 1
    dp[i][0] = dp[i-1][0] + (c=="D")
    dp[i][2] = dp[i-1][2] + (c=="M")
    dp[i][1] = dp[i-1][1] + (c=="M")*dp[i-1][0]
    if c != "C":
        continue
    for j, q in enumerate(qs):
        ll = max(i-q, 0)
        As[j] += dp[i-1][1] - dp[ll][1] - dp[ll][0]*(dp[i-1][2]-dp[ll][2])
for a in As:
    print(a)


### FIXED CODE ###

N = int(input())
S = input().strip()
qn = int(input())
qs = list(map(int, input().split()))
dd,mm,cc = [0],[0],[0]
As = [0]*qn
d=m=dm=0
for i, w in enumerate(S):
    i += 1
    if w=="D":
        d+=1
    elif w == "M":
        m+=1
        dm+=d
    elif w == "C":
        for j, q in enumerate(qs):
            ll = max(i-q, 0)
            As[j] += dm - cc[ll] - dd[ll]*(m-mm[ll])
    dd.append(d)
    mm.append(m)
    cc.append(dm)
for a in As:
    print(a)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
n,w=map(int,input().split())
l=[[]]
for i in range(n):
  l.append(list(map(int,input().split())))
dp=[[-1 for i in range(w+2)] for j in range(n+2)]
def knap(x,y):
  if dp[x][y]!=-1:
    return dp[x][y]
  if x==n+1:
    res=0
  elif y<l[x][0]:
    res=knap(x+1,y)
  else:
    res=max(knap(x+1,y),knap(x+1,y-l[x][0])+l[x][1])
  dp[x][y]=res
  return res
knap(1,w)
print(dp[1][w])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
def knapsack(N,W,weight,value):
  #初期化
  inf=float("inf")
  dp=[[-inf for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1): dp[0][i]=0

  #DP
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
        dp[i+1][w]=max(dp[i][w-weight[i]]+value[i], dp[i][w])
      else: #入る可能性はない
        dp[i+1][w]=dp[i][w]
  return dp[N][W]
n1,w1=map(int,input().split())
lw=[]
lv=[]
for i in range(n1):
  w,v=map(int,input().split())
  lw.append(w)
  lv.append(v)
print(knapsack(n1,w1,lw,lv))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,k = map(int,input().split())
inf = 10**10
parent = [inf]*n
q = {}
for i in range(n):
    a,b = map(int,input().split())
    if a not in q.keys():
        parent[i] = a
        q[a] = 0
    q[a] += b
parent.sort()
cnt = 0
for p in parent:
    cnt += q[p]
    if cnt >= k:
        print(p)
        break


### FIXED CODE ###

import sys
input = sys.stdin.readline
n,k = map(int,input().split())
inf = 10**10
parent = [inf]*n
q = {}
for i in range(n):
    a,b = map(int,input().split())
    if a not in q.keys():
        parent[i] = a
        q[a] = 0
    q[a] += b
parent.sort()
cnt = 0
for p in parent:
    cnt += q[p]
    if cnt >= k:
        print(p)
        break
### BUGGY CODE ###


import sys
sys.setrecursionlimit(10**9)

def main():
    S = [int(s) for s in input()]
    N = len(S)
    K = 2019

    V = [0] * (N+1)
    for i in reversed(range(N)):
        rev_i = (N-1)-i
        V[rev_i+1] = V[rev_i] + S[i] * (10**(rev_i+1))
        # print(V)

    dic = {} # value:count
    U = []
    for v in V:
        u = v % K
        if u in dic:
            dic[u] += 1
        else:
            dic[u] = 1
            U.append(u)

    ans = 0
    for u in U:
        u_count = dic[u]
        ans += u_count * (u_count-1) // 2

    # print(S)
    # print(V)
    # print(dic)
    print(ans)

if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

def main():
    S = [int(s) for s in input()]
    N = len(S)
    K = 2019

    V = [0] * (N+1)
    for i in reversed(range(N)):
        rev_i = (N-1)-i
        V[rev_i+1] = V[rev_i] + S[i] * (pow(10,rev_i+1,K))
        # print(V)

    dic = {} # value:count
    U = set()
    for v in V:
        u = v % K
        if u in U:
            dic[u] += 1
        else:
            dic[u] = 1
            U.add(u)

    ans = 0
    for u in U:
        u_count = dic[u]
        ans += u_count * (u_count-1) // 2

    # print(S)
    # print(V)
    # print(dic)
    print(ans)

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

H,W = map(int,input().split())
S = list(input() for i in range(H))
Grid1 = [[0]*W for i in range(H)]
#print(S)
ans = 0
for i in range(H):
    cou = 0
    l = 0
    ws = [0]*W
    for j in range(W):
        #print(i,j,S[i][j])
        if S[i][j] == ".":
            cou += 1
        else:
            for x in range(l,j):
                ws[x] = cou
            ws[j] = 0
            l = j+1
            cou = 0
        for x in range(l,j+1):
            ws[x] = cou
    Grid1[i] = ws

for i in range(W):
    cou = 0
    l = 0
    ws = [0]*H
    for j in range(H):
        #print(i,j,S[i][j])
        if S[j][i] == ".":
            cou += 1
        else:
            for x in range(l,j):
                ws[x] = cou
            ws[j] = 0
            l = j+1
            cou = 0
        for x in range(l,j+1):
            ws[x] = cou
    for j in range(H):
        ans =max(Grid1[j][i] +ws[j], ans)

print(ans-1)

### FIXED CODE ###

H,W = map(int,input().split())
S = list(input() for i in range(H))
Grid1 = [[0]*W for i in range(H)]
for i in range(H):
    cou = 0
    l = 0
    for j in range(W):
        if S[i][j] == ".":
            cou += 1
        else:
            for x in range(l,j):
                Grid1[i][x] = cou
            l = j+1
            cou = 0
    for x in range(l,j+1):
        Grid1[i][x] = cou    
for i in range(W):
    cou = 0
    l = 0
    for j in range(H):
        #print(i,j,S[i][j])
        if S[j][i] == ".":
            cou += 1
        else:
            for x in range(l,j):
                Grid1[x][i] += cou
            l = j+1
            cou = 0
    for x in range(l,j+1):
        Grid1[x][i] += cou

print(max(max(Grid1[i]) for i in range(H))-1)
### 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 -= int(B / 20)
else:
    mx = math.floor(A / B * p) - math.floor(p / B) * A
    while mx == 0:
        p -= int(N / 20)

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