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

def yakusu(n):
    max_yakusu = int(n**0.5)
    arr = [1]

    while n > 1:
        for i in range(2,max(n+1,max_yakusu+1)):
            if n % i == 0:
                while n % i == 0:
                    arr.append(i)
                    n = int(n/i)
                break
    return arr

def gcd(x,y):
    if y == 0:
       return x
    else:
       return gcd(y, x % y)

A,B = [int(x) for x in input().split()]
koyaku = gcd(A,B)

koyaku_insu = set(yakusu(koyaku))


print(len(koyaku_insu))

### FIXED CODE ###

def prime_factorize(n):
    a = [1]
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
  
def gcd(x,y):
    if y == 0:
       return x
    else:
       return gcd(y, x % y)
 
A,B = [int(x) for x in input().split()]
koyaku = gcd(A,B)
 
koyaku_insu = list(set(prime_factorize(koyaku)))
 
 
print(len(koyaku_insu))
### BUGGY CODE ###

from math import factorial

def P(n, r):
    return factorial(n)//factorial(n-r)

def C(n, r):
    return P(n, r)//factorial(r)


ans = 0
H,W,A,B = map(int, input().split())
MOD = int(1e9)+7

for i in range(min(H-A, W-B)):
    ans += C(H-A+B-1, B+i)*C(A+W-B-1, A+i)
#     print(ans)
    ans %= MOD
    
print(ans)

### FIXED CODE ###

MOD = 10**9 + 7
MAX = 2*10**5
fac = [0]*MAX  # fac[n]:  (n!) mod p
finv = [0]*MAX  # finv[n]: (n!)^-1 mod p
inv = [0]*MAX  # inv[n]:  (n)^-1 mod -p


def comb_init():
    global fac, finv, inv
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i-1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD//i) % MOD
        finv[i] = finv[i-1] * inv[i] % MOD


def comb(n: int, r: int) -> int:
    global fac, finv
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD


H, W, A, B = map(int, input().split())
comb_init()
ans = 0

for i in range(H-A):
    x = comb(B-1+i, i)
    a = H-1-i
    b = W-1-B
    x *= comb(a+b, a)
    x %= MOD
    ans += x
ans %= MOD
print(ans)
### BUGGY CODE ###

N, Q = [int(i) for i in input().split()]

H, W = [N] * N, [N] * N
revd = 0
for _ in range(Q):
    t, x = [int(i) for i in input().split()]
    if t == 1:
        revd += H[x] - 2
        for y in range(2, H[x]):
            W[y] = min(W[y], x)
        H[x] = 0
    else:
        revd += W[x] - 2
        for y in range(2, W[x]):
            H[y] = min(H[y], x)
        W[x] = 0

ans = (N - 2)*(N - 2) - revd
print(ans)

### FIXED CODE ###

class SegTree():
    def __init__(self, initial, operation, identity):
        n = len(initial)
        self.initial = initial
        self.operation = operation
        self.identity = identity
        self.num = 1 << (len(bin(n - 1)) - 2)
        self.tree = [identity] * (2 * self.num - 1)
        for i in range(n):
            self.tree[i + self.num - 1] = self.initial[i]
        for i in reversed(range(self.num - 1)):
            self.tree[i] = min(self.tree[2*i + 1], self.tree[2*i + 2])
    
    def update(self, k, x):
        k += self.num - 1
        self.tree[k] = x
        while k >= 1:
            k = (k - 1) // 2
            self.tree[k] = self.operation(self.tree[2*k + 1], self.tree[2*k + 2])
    
    def query(self, l, r):
        res = self.identity
        l += self.num - 1
        r += self.num - 1
        while l < r:
            if l % 2 == 0:
                res = self.operation(res, self.tree[l])
                l += 1
            if r % 2 == 0:
                res = self.operation(res, self.tree[r - 1])
            l = (l - 1) // 2
            r = (r - 1) // 2
        return res

N, Q = [int(i) for i in input().split()]

H, W = SegTree([N]*N, min, N), SegTree([N]*N, min, N)
revd = 0
for _ in range(Q):
    t, x = [int(i) for i in input().split()]
    if t == 1:
        h = H.query(x, N + 1)
        w = W.query(h, N + 1)
        revd += h - 2
        W.update(h, min(x, w))
    else:
        w = W.query(x, N + 1)
        h = H.query(w, N + 1)
        revd += w - 2
        H.update(w, min(x, h))

ans = (N - 2)*(N - 2) - revd
print(ans)
### BUGGY CODE ###

import queue
n,m = map(int,input().split())
 
l = []
for i in range(n):
    ab = list(map(int,input().split()))
    l.append(ab)
l.sort()
q = []
ans = 0
cnt = 0
for i in range(1,m+1):
    while cnt < n and l[cnt][0] == i:
        q.append(-l[cnt][1])
        q.sort()
        cnt += 1
    
    if len(q) != 0:
        ans +=-q.pop(0)
 
print(ans)

### FIXED CODE ###

import heapq
def heapify(x):
    for i in reversed(range(n//2)):
        _siftup(x, i)
 
n,m = map(int,input().split())
 
l = []
for i in range(n):
    ab = list(map(int,input().split()))
    l.append(ab)
l.sort()
q = []
ans = 0
cnt = 0
for i in range(1,m+1):
    while cnt < n and l[cnt][0] == i:
        heapq.heappush(q,-l[cnt][1])
        cnt += 1
    
    if len(q) != 0:
        ans += -heapq.heappop(q)
 
print(ans)
### BUGGY CODE ###


def cmd():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))

    DP = [10000] * N
    DP[0] = 0

    if K > N:
        K = N

    for k in range(1,K):
        tmp = []
        for s in range(k):
            tmp.append(DP[s] + abs(h[k]-h[s]))
            DP[k] = min(tmp)

    for i in range(N-K):
        tmp = []
        for j in range(K):
            tmp.append(DP[i+j] + abs(h[i+K] - h[i+j]))
            DP[i+K] = min(tmp)
            
    print(DP[N-1])

if __name__ == "__main__":
    cmd()


### FIXED CODE ###


def cmd():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))

    DP = [10000] * N
    DP[0] = 0

    if K > N:
        K = N

    for k in range(1,K):
        tmp = []
        for s in range(k):
            tmp.append(DP[s] + abs(h[k]-h[s]))
            DP[k] = min(tmp)

    for i in range(N-K):
        tmp = []
        for j in range(K):
            tmp.append(DP[i+j] + abs(h[i+K] - h[i+j]))
            DP[i+K] = min(tmp)
            
    print(DP[N-1])

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

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
S = input()

R = S.count("R")
G = S.count("G")
B = S.count("B")

cnt = 0
for l, r in combinations(range(N), 2):
	if l%2 != r%2:
		continue
	m = (l+r)//2
	if len(set([S[l], S[m], S[r]])) == 3:
		cnt += 1

print(R*G*B - cnt)

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
N = INT()
S = list(input())
 
r = S.count("R")
g = S.count("G")
b = S.count("B")
 
 
A = list(range(len(S)))
cnt = 0
for x, y in combinations(A, 2):
	if (x+y)//2 == (x+y)/2:
		z = (x+y)//2
		if S[x] != S[y] and S[x] != S[z] and S[y] != S[z]:
			cnt += 1
 
print(r*g*b-cnt)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

n = int(input())
ab = [[int(item) for item in input().split()] for _ in range(n-1)]

e = [[] for _ in range(n)]
for a, b in ab:
    e[a-1].append(b-1)
    e[b-1].append(a-1)

shortest = []
def get_path(start, end, par, path):
    global shortest
    if end in e[start]:
        shortest = path + [end]
        return True
    for item in e[start]:
        if item != par:
             get_path(item, end, start, path + [item])

def tree_count(start, par, a, b):
    count = 0
    for item in e[start]:
        if start == a and item == b:
            continue
        if start == b and item == a:
            continue
        if item != par:
            count += 1
            count += tree_count(item, start, a, b)
    return count

get_path(0, n-1, -1, [0])
cut_l = (len(shortest)-1) // 2
p = tree_count(0, -1, shortest[cut_l], shortest[cut_l+1])
q = tree_count(n-1, -1, shortest[cut_l], shortest[cut_l+1])

if p > q:
    print("Fennec")
else:
    print("Snuke")

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

n = int(input())
e = [[] for _ in range(n)]

for i in range(n-1):
    a, b = [int(item) for item in input().split()]
    e[a-1].append(b-1)
    e[b-1].append(a-1)

shortest = []
def get_path(start, end, par):
    if end in e[start]:
        shortest.append(end)
        return True
    for item in e[start]:
        if item != par:
             if get_path(item, end, start):
                 shortest.append(item)
                 return True

def tree_count(start, par, a, b):
    count = 0
    for item in e[start]:
        if start == a and item == b:
            continue
        if start == b and item == a:
            continue
        if item != par:
            count += 1
            count += tree_count(item, start, a, b)
    return count

get_path(0, n-1, -1)
shortest.append(0)
shortest = shortest[::-1]
cut_l = (len(shortest)-1) // 2
p = tree_count(0, -1, shortest[cut_l], shortest[cut_l+1])
q = n - p - 2 
if p > q:
    print("Fennec")
else:
    print("Snuke")
### BUGGY CODE ###


H,N = map(int,input().split())
magicL =[]
for x in range(N):
    magic = list(int(i) for i in input().split())
    magicL.append(magic)
magicE = []
for x in range(N):
    magicE.append(magicL[x][0]/magicL[x][1])
c = list(zip(magicE,magicL))
mel , ml = zip(*c)
dp =[[10000000000 for x in range(N+1)]for y in range(H+1)]
dp[0][0] = 0
for i in range(len(dp[0])-1):
    for w in range(H+1):
        dp[w][i+1] = min(dp[w][i],dp[w][i+1])
        dp[min(w+ml[i][0],H)][i+1] = min(dp[min(w+ml[i][0],H)][i+1],dp[w][i+1]+ml[i][1])
print(dp[H][N])


### FIXED CODE ###

H,N = map(int,input().split())
magicL =[]
for x in range(N):
    magic = list(int(i) for i in input().split())
    magicL.append(magic)
 
ml = magicL
dp = [10**9 for i in range(H +1)]
dp [0] = 0
for i in range(N):
    for w in range(H +1):
        dp[min(w+ml[i][0],H)] = min(dp[min(w+ml[i][0],H)],dp[w]+ml[i][1])
print(dp[H])
### BUGGY CODE ###

n=int(input())
a=[list(map(int,input().split()))for _ in range(n)]
b=[i.copy() for i in a]
c=[n*[1]for _ in range(n)]
for k in range(n):
  for i in range(n):
    for j in range(n):
      b[i][j]=min(b[i][j],b[i][k]+b[k][j])
      if a[i][j]==a[i][k]+a[k][j]:
        if i!=j and i!=k and j!=k:
          c[i][j]=0
if a!=b:exit(print(-1))
ans=0
for i in range(n):
  for j in range(i):
    if c[i][j]:ans+=a[i][j]
print(ans)

### FIXED CODE ###

n=int(input())
a=[list(map(int,input().split()))for _ in range(n)]
b=[[j for j in i]for i in a]
c=[n*[1]for _ in range(n)]
for k in range(n):
  for i in range(n):
    for j in range(n):
      b[i][j]=min(b[i][j],b[i][k]+b[k][j])
      if a[i][j]==a[i][k]+a[k][j]:
        if i!=j and i!=k and j!=k:
          c[i][j]=0
if a!=b:exit(print(-1))
ans=0
for i in range(n):
  for j in range(i):
    if c[i][j]:ans+=a[i][j]
print(ans)
### BUGGY CODE ###

n,s=map(int,input().split())
a = list(map(int,input().split()))
mod = 998244353
dp = [[[0 for i in range(3)] for i in range(s+1)]for i in range(n+1)]
dp[0][0][0]=1

for i in range(1,n+1):
    for j in range(s+1):
        dp[i][j][0] += dp[i-1][j][0]
        dp[i][j][0] %= mod
        dp[i][j][1] += (dp[i-1][j][1]+dp[i-1][j][0])%mod
        dp[i][j][1] %= mod
        dp[i][j][2] += (dp[i-1][j][2]+dp[i-1][j][1]+dp[i-1][j][0])%mod
        dp[i][j][2] %= mod
        if j-a[i-1]>=0:
            dp[i][j][1] += (dp[i-1][j-a[i-1]][1]+dp[i-1][j-a[i-1]][0])%mod
            dp[i][j][1] %= mod
            dp[i][j][2] += (dp[i-1][j-a[i-1]][0]+dp[i-1][j-a[i-1]][1])%mod
            dp[i][j][2] %= mod

#tmp = [[dp[i][j][2]for j in range(s+1)]for i in range(n+1)]
#print(tmp)

print(dp[n][s][2])


### FIXED CODE ###

import sys
import math
def input():
    return sys.stdin.readline()[:-1]
n,s=map(int,input().split())
a = list(map(int,input().split()))
mod = 998244353
dp0 = [[0 for i in range(s+1)]for i in range(n+1)]
dp1 = [[0 for i in range(s+1)]for i in range(n+1)]
for i in range(1,n+1):
    for j in range(s+1):
        if j==0:
            b=1
        else:
            b=0
        dp0[i][j] += (dp0[i-1][j]+b)
        dp0[i][j] %= mod
        dp1[i][j] += (dp1[i-1][j]+dp0[i-1][j]+b)
        dp1[i][j] %= mod
        if j+a[i-1]<=s:
            dp0[i][j+a[i-1]] += (dp0[i-1][j]+b)
            dp0[i][j+a[i-1]] %= mod
            dp1[i][j+a[i-1]] += (b+dp0[i-1][j])
            dp1[i][j+a[i-1]] %= mod

        dp0[i][j]%=mod
        dp1[i][j]%=mod

print(dp1[n][s])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(3*10**5)

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

mod = 10**9 + 7

data = [[] for i in range(n)]

def solve(pre,now):
    # output [部分木の頂点数,親の側の頂点数]
    data_now = []
    for nex in G[now]:
        if nex == pre:continue
        data_nex = solve(now,nex)
        data_now.append(n-data_nex[-1])

    data_now.append(n-1-sum(data_now))
    data[now] = data_now
    return data_now

solve(-1,0)

ans = 0
for i in range(n):
    now = pow(2,n-1,mod)-1

    for x in data[i]:

        now -= pow(2,x,mod)-1
        now %= mod
    ans += now

#print(ans)

x = pow(2,n,mod)
x = pow(x,mod-2,mod)
print(ans*x%mod)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
n = int(input())
G = [[] for _ in range(n)]
mod = 10**9 + 7

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

stack = [0]
depth = [-1]*n
depth[0] = 0
while stack:
    v = stack.pop()
    d = depth[v]
    for nv in G[v]:
        if depth[nv] >= 0:continue
        depth[nv] = depth[v] + 1
        stack.append(nv)

d_to_i = [[] for _ in range(n)]

for i in range(n):
    d_to_i[depth[i]].append(i)

data = [[] for _ in range(n)]

for d in range(n-1,-1,-1):
    for v in d_to_i[d]:
        for nv in G[v]:
            if depth[nv] < depth[v]:continue
            if data[nv]:
                data[v].append(n-data[nv][-1])
        if data[v]:
            data[v].append(n-1-sum(data[v]))
        else:
            data[v].append(n-1)

ans = 0
two = [1]
for i in range(n):
    two.append(two[-1]*2%mod)
for i in range(n):
    now = two[n-1]-1
    for x in data[i]:
        now -= two[x]-1
        now %= mod
    ans += now

#print(ans)

x = two[n]
x = pow(x,mod-2,mod)
print(ans*x%mod)
### BUGGY CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
L = Counter(A)
anss = {}
for k,v in L.items():
    L[k] -= 1
    anss[k] = sum([i*(i-1)//2 for i in list(L.values()) if i >= 2])
    L[k] += 1
for i in A:
    print(anss[i])


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
L = Counter(A)
anss = {}
sum_ans = sum([i*(i-1)//2 for i in L.values() if i >= 2])
for k,v in L.items():
    anss[k] = sum_ans - (v*(v-1)//2) + ((v-1)*(v-2)//2)
for i in A:
    print(anss[i])
### BUGGY CODE ###



s = input()
l_s = len(s)
t = input()
l_t = len(t)

dp = list([0 for _ in range(l_t+1)] for _ in range(l_s+1))

for i in range(l_s):
    for j in range(l_t):
        #dp[i+1][j+1]  = ...
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i][j]+1 , dp[i+1][j] , dp[i][j+1])
        else:
            dp[i+1][j+1] = max(dp[i][j], dp[i+1][j] , dp[i][j+1])

ans = []
l = dp[-1][-1]
i = l_s
j = l_t
while l != 0:
    if s[i-1] == t[j-1]:
        ans.append(s[i-1])
        i -= 1
        j -= 1
        l -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        j -= 1

print("".join(ans[::-1]))




### FIXED CODE ###



s = input()
l_s = len(s)
t = input()
l_t = len(t)

dp = list([0 for _ in range(l_t+1)] for _ in range(l_s+1))

for i in range(l_s):
    for j in range(l_t):
        #dp[i+1][j+1]  = ...
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i][j]+1 , dp[i+1][j] , dp[i][j+1])
        else:
            dp[i+1][j+1] = max(dp[i][j], dp[i+1][j] , dp[i][j+1])

ans = []
l = dp[-1][-1]
i = l_s
j = l_t
while l != 0:
    if s[i-1] == t[j-1]:
        ans.append(s[i-1])
        i -= 1
        j -= 1
        l -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        j -= 1

print("".join(ans[::-1]))
### BUGGY CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
Q = [0]*(N-K+1)
for i in range(N-K+1):
    Q[i] = sum(p[i:i+K])
print(max(Q)/2+0.5*K)

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
ans = sum(p[:K])
tmp = ans
for i in range(K,N):
    tmp += p[i]-p[i-K]
    ans = max(ans,tmp)
print((ans+K)/2)
### BUGGY CODE ###

import bisect
import heapq
import sys
import queue


input = sys.stdin.readline
sys.setrecursionlimit(100000)


class V:
    def __init__(self, f):
        self.f = f
        self.v = None

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if self.v is None:
            self.v = n
        else:
            self.v = self.f(self.v, n)

    def get(self):
        return self.v


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def main():
    N = int(input())

    left = 0
    right = N - 1
    D = {}
    for _ in range(21):
        if left not in D:
            print(left)
            sys.stdout.flush()
            res = input()
            if res == "Vacant":
                return

            D[left] = 0 if res == "Male" else 1

        if right not in D:
            print(right)
            sys.stdout.flush()
            res = input()
            if res == "Vacant":
                return

            D[right] = 0 if res == "Male" else 1

        LD = D[left]
        RD = D[right]

        m = (left + right) // 2

        if m not in D:
            print(m)
            sys.stdout.flush()
            res = input()
            if res == "Vacant":
                return

            D[m] = 0 if res == "Male" else 1

        MD = D[m]

        if (m % 2 == left % 2 and MD == LD) or (m % 2 != left % 2 and MD != LD):
            left = m
        else:
            right = m


if __name__ == "__main__":
    main()


### FIXED CODE ###

import bisect
import heapq
import sys
import queue


input = sys.stdin.readline
sys.setrecursionlimit(100000)


class V:
    def __init__(self, f):
        self.f = f
        self.v = None

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if self.v is None:
            self.v = n
        else:
            self.v = self.f(self.v, n)

    def get(self):
        return self.v


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def main():
    N = int(input())

    left = 0
    right = N - 1
    D = {}
    c = 0
    for _ in range(21):
        if left not in D:
            print(left)
            sys.stdout.flush()
            res = input()
            c += 1
            if res == "Vacant" or c >= 20:
                return

            D[left] = res

        LD = D[left]
        m = (left + right) // 2

        if m not in D:
            print(m)
            sys.stdout.flush()
            res = input()
            c += 1
            if res == "Vacant" and c >= 20:
                return

            D[m] = res

        MD = D[m]

        if (m % 2 == left % 2 and MD == LD) or (m % 2 != left % 2 and MD != LD):
            left = m if left != m else m + 1
        else:
            right = m


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

n,k,q=map(int,input().split())
A=[int(input()) for _ in range(q)]

for i in range(1,n+1):
  if k-(q-A.count(i))<=0:
    print('No')
  else:
    print('Yes')


### FIXED CODE ###

import sys
import itertools
input = sys.stdin.readline
n,k,q=map(int,input().split())
A=[int(input()) for _ in range(q)]

ans=[k]*n
for i in range(q):
  ans[A[i]-1]+=1
for i in range(n):
  if ans[i]-q>0:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

import math
a,b,n=map(int,input().split())
l=[]
for i in range(n+1):
    ans= math.floor(a*i/b)-a*(math.floor(i/b))
    l.append(ans)
print(max(l))

### FIXED CODE ###

a,b,n=map(int,input().split())
s=0
if b<=n:
    x=b-1
    s=(a*x)//b-a*(x//b)
else:
    x=n
    s=(a*x)//b-a*(x//b)
print(s)
### BUGGY CODE ###

x=int(input())
for i in range(1,int(x**(1/2))+1):
    if x%i:continue

    ar,s=i,x//i
    pre=[]
    if (ar**5)%5==x%5:pre.append(ar)
    if  ((s**5)%5==x%5):pre.append(s)

    for a in pre:
        d=(x-a**5)//5//a
        if d==0:print(a,0);exit()
        for b in range(1,int(abs(d)**(1/2))+1):
            if d%b:continue
            if a**3+2*b*a**2+2*b**2*a+b**3==d//b:
                print(a+b,b);exit()
            if a**3-2*b*a**2+2*b**2*a-b**3==-(d//b):print(a-b,-b);exit()


### FIXED CODE ###

x=int(input())
for i in range(-120,121):
  for j in range(-120,121):
    if pow(i,5)-pow(j,5)==x:
      print(i,j);exit()
### BUGGY CODE ###

import numpy as np
n, k = map(int,input().split())
a = np.array([int(i) for i in input().split()])
best = 0
for i in range(k+1):
    aa = np.full_like(a, i)
    tmp = np.sum(a ^ aa)
    if best < tmp:
        best = tmp
print(best)

### FIXED CODE ###

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

# 最大値を取るf(x)のxを求める
# digitsは下位桁 < 上位桁で1になっているbitをカウントする
digits = [0] * 40
for i in range(40):
    for a in A:
        if (a >> i) & 1:
            digits[i] += 1

# Kを考慮してmax_xを求める方法がわからない
# 桁ごとに最適なbitはすでにわかっていて、他の桁のbitに影響を受けることはないので、
# 上位桁から見ていって、Kが1になっている部分ならフラグを立てる
# 上位桁から見てKが1のbitが出てから、K:1,max_x:0のフラグを立てたら、その桁より下位桁のbitはなんでもよくなる
check_K = True
max_x = 0
for i, d in enumerate(reversed(digits)):
    i = 40 - i - 1
    if check_K and K < pow(2, i):
        continue
    if d <= (N-d) and ((K >> i) & 1 == 1 or not check_K):
        max_x += 2 ** i
    elif (K >> i) & 1 == 1:
        check_K = False
    
#print(max_x)
ans = 0
for a in A:
    ans += a ^ max_x

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

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

dp = [0] * n
dp[0] = 0
# 足場を一つづつ見ていく
for i in range(1, n):
#    for j in range(max(0,i-k),i):
#        # 今の足場へのコストと、他の足場から来た場合のコストを比較
#        dp[i] = min(dp[i], dp[j] + abs(h[i]-h[j]))
    dp[i] = min(dp[j] + abs(h[j] - h[i]) for j in range(max(i-k,0),i))
print(dp[-1])

### FIXED CODE ###

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

dp = [0] * n
for i in range(1, n):
    dp[i] = min(dp[j] + abs(h[j] - h[i]) for j in range(max(i-k,0),i))
print(dp[-1])