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

# standard input
S = input()
Q = int(input())
Query = []
num_reverse = 0

S_r = ''.join(reversed(S))

rev = False

for _ in range(Q):

    q = tuple(map(str, input().split()))

    if q[0] == '1':
        rev = (not rev)

    else:
        if (rev and q[1] == '1') or (not rev and q[1] == '2'):
            S = S + q[2]
            S_r = q[2] + S_r
        else:
            S = q[2] + S
            S_r = S_r + q[2]

if rev:
    print(S_r)
else:
    print(S)


### FIXED CODE ###

# standard input
S = input()
Q = int(input())
Query = []
num_reverse = 0

L = ''
R = ''

rev = False

for _ in range(Q):

    q = tuple(map(str, input().split()))

    if q[0] == '1':
        rev = (not rev)

    else:
        if (rev and q[1] == '1') or (not rev and q[1] == '2'):
            R = R + q[2]
        else:
            L = q[2] + L 

if rev:
    print( R[::-1] + S[::-1] + L[::-1])
else:
    print( L + S + R )
### BUGGY CODE ###

def solve():
    K = int(input())
    S = input()
    N = len(S)

    MOD = 10**9+7
    n = N+K
    fac = [1]*(n+1)
    rev = [1]*(n+1)
    
    for i in range(1,n+1):
        fac[i] = i*fac[i-1]%MOD
        rev[i] = pow(fac[i], MOD-2, MOD)
    
    comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD

    ans = 0
    for i in range(K+1):
        ans += pow(26, K-i, MOD) * pow(25, i, MOD) * comb(N+i-1, i)
        ans %= MOD
    print(ans)


solve()


### FIXED CODE ###

MOD = 10**9+7
K = int(input())
S = input()
N = len(S)

n = N+K
fac = [1]*(n+1)
rev = [1]*(n+1)
 
for i in range(1,n+1):
  fac[i] = i*fac[i-1]%MOD
  rev[i] = pow(fac[i], MOD-2, MOD)
 
comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD

ans = 0
for i in range(K+1):
    ans += pow(26, K-i, MOD) * pow(25, i, MOD) * comb(N+i-1, i)
    ans %= MOD
print(ans)
### BUGGY CODE ###

s = input()
q = int(input())
for i in range(q):
  z = input()
  if z[0] == '1':
    s = s[::-1]
  elif z[2] == '1':
    s = z[4] + s
  else:
    s = s + z[4]
print(s)

### FIXED CODE ###

from collections import deque
s = input()
q = int(input())
d = deque()
for i in s:
  d.append(i)
rv = 0
lst = [1, 0]
for i in range(q):
  z = input()
  if z[0] == '1':
    rv = lst[rv]
  elif z[2] == '1':
    if rv == 1:
      d.append(z[4])
    else:
      d.appendleft(z[4])
  else:
    if rv == 0:
      d.append(z[4])
    else:
      d.appendleft(z[4])
if rv == 1:
  print(''.join(d)[::-1])
else:
  print(''.join(d))
### BUGGY CODE ###

n = int(input())

for i in range(1,n+1):
    ans = 0
    for x in range(1,int(n**0.5+1)):
        for y in range(1,int((n-x**2)**0.5+1)):
            if (x+y)**2 - 4*(x**2 + y**2 + x*y - i) >= 0:
                z1 = (((x+y)**2 - 4*(x**2 + y**2 + x*y - i))**0.5) -(x+y)
                z2 = -(((x+y)**2 - 4*(x**2 + y**2 + x*y - i))**0.5) -(x+y)
                if z1//1 == z1 and z1 > 0:
                    ans += 1
                elif z2//1 == z2 and z2 > 0:
                    ans += 1
    print(ans)

### FIXED CODE ###

n = int(input())

a = [0]*(10**4)

for x in range(1,10**2):
    for y in range(1,10**2):
        for z in range(1,10**2):
            s = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if s <= 10**4:
                a[s-1] += 1

for i in range(n):
    print(a[i])
### BUGGY CODE ###

n, w = map(int, input().split())

weights = [0]*n
values = [0]*n

for i in range(n):
    weights[i], values[i] = map(int, input().split())

dp = [[0 for _ in range(w+1)] for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, w+1):
        if j < weights[i-1]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], values[i-1]+dp[i-1][j-weights[i-1]])

print(dp[-1][-1])

### FIXED CODE ###

n, w = map(int, input().split())

weights = [0]*n
values = [0]*n

for i in range(n):
    weights[i], values[i] = map(int, input().split())

dp = [[0 for _ in range(w+1)] for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, w+1):
        if j < weights[i-1]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], values[i-1]+dp[i-1][j-weights[i-1]])

print(dp[-1][-1])
### BUGGY CODE ###

# unfinished
INF = 1 << 64


def find_max(a):
    n = len(a)
    odd_a = [a[i] for i in range(n) if i % 2 == 0]
    even_a = [a[i] for i in range(n) if i % 2 == 1]

    cum_odd_a = [0]
    sum_odd_a = 0
    for odd_a_elem in odd_a:
        cum_odd_a.append(cum_odd_a[-1] + odd_a_elem)
        sum_odd_a += odd_a_elem

    cum_even_a = [0]
    sum_even_a = 0
    for even_a_elem in even_a:
        cum_even_a.append(cum_even_a[-1] + even_a_elem)
        sum_even_a += even_a_elem

    max_sum_half_a = -INF

    if n % 2 == 0:  # nが偶数である場合
        # 奇数と偶数の境目
        for i in range(n // 2 + 1):
            odd_part_sum = cum_odd_a[i]
            even_part_sum = sum_even_a - cum_even_a[i]
            sum_half_a = odd_part_sum + even_part_sum

            if sum_half_a > max_sum_half_a:
                max_sum_half_a = sum_half_a
    else:  # nが奇数である場合
        # 奇数と偶数の境目
        for i in range(n // 2 + 1):
            odd_part_sum_1 = cum_odd_a[i]

            # 偶数と奇数の境目
            for j in range(i, n // 2 + 1):
                even_part_sum = cum_even_a[j] - cum_even_a[i]
                odd_part_sum_2 = sum_odd_a - cum_odd_a[j + 1]

                sum_half_a = odd_part_sum_1 + even_part_sum + odd_part_sum_2

                if sum_half_a > max_sum_half_a:
                    max_sum_half_a = sum_half_a

    return max_sum_half_a


def main():
    _ = int(input())
    a = list(map(int, input().split()))

    print(find_max(a))


main()


### FIXED CODE ###

def find_max(a):
    n = len(a)

    if n <= 3:
        return max(a)

    dp = [[-(1 << 64)] * (2 + n % 2) for _ in range(n)]

    for i in range(2 + n % 2):
        dp[i][i] = a[i]
        dp[i + 1][i] = a[i]

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

    return dp[-1][1 + n % 2]


def main():
    _ = int(input())
    a = list(map(int, input().split()))

    print(find_max(a))


main()
### BUGGY CODE ###

import sys

def prime_calc(n):
    if n < 2:
        return False
    else:
        i = 2
        while n > i:
            if n % i == 0:
                return False
            else:
                i += 1
    return True

def prime(n):
    cnt = 0
    for i in range(0, n+1):
        ans = prime_calc(i)
        if ans is True:
            cnt = cnt + 1

    return cnt

def main():
    l = []
    
    for line in sys.stdin:
        l.append(int(line))

    for line in l:
        print(prime(line))

if __name__ == "__main__":
    main()


### FIXED CODE ###

import math
import sys

sup = 1000000

is_prime = [0] * sup

count = [0] * sup

def setup():
    is_prime[2] = 1
    for n in range(3,sup,2):
        flag = True
        for i in range(3, int(math.floor(math.sqrt(n) + 1)), 2):
            if n % i == 0:
                flag = False
                break
        if flag:
            is_prime[n] = 1

def precount():
    for n in range(2, sup):
        count[n] = count[n-1] + is_prime[n]

def main():
    setup()
    precount()

    l = []

    for line in sys.stdin:
        l.append(int(line))

    for line in l:
         print(count[line])

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

from collections import Counter

def Get_nC2(n):
    return int(n*(n-1) / 2)


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

c = Counter(A_i)
cnt_dict = {}

for a_i in A_i:
    if a_i in cnt_dict:
        print(cnt_dict[a_i])
        continue
        
    tmp = c.copy()
    tmp[a_i] = tmp[a_i] - 1
    total = sum(list(map(Get_nC2, tmp.values())))
    cnt_dict[a_i] = total
    print(total)


### FIXED CODE ###

from collections import Counter

def Get_nC2(n):
    return int(n*(n-1) / 2)


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

c = Counter(A_i)


total = sum(list(map(Get_nC2, c.values())))

for a_i in A_i:
    result =  total - Get_nC2(c[a_i]) + Get_nC2(c[a_i]-1)
    print(result)
### BUGGY CODE ###

from itertools import *
from bisect import *
from operator import *
import math

def comb(n, r):
    return math.factorial(n) / (math.factorial(r) * math.factorial(n-r))

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

a_item = sorted(a)
a_max = a_item[-1]
a_item = a_item[:-1]
bisect_l_item = bisect_left(a_item, a_max//2)
#import pdb; pdb.set_trace()
if bisect_l_item >= n - 1:
    bisect_l = a_item[bisect_l_item - 1]
else:
    bisect_l = a_item[bisect_l_item]
bisect_r = a_item[bisect_l_item - 1]
#print(bisect_l_item, bisect_l, bisect_r)
idea_l = comb(a_max, bisect_l)
idea_r = comb(a_max, bisect_r)

if idea_l >= idea_r:
    print(a_max, bisect_l)
else:
    print(a_max, bisect_r)


### FIXED CODE ###

from itertools import *
from bisect import *
from operator import *
import math

def comb(n, r):
    return math.factorial(n) / (math.factorial(r) * math.factorial(n-r))

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

a_item = sorted(a)
a_max = a_item[-1]
a_item = a_item[:-1]
bisect_l_item = bisect_left(a_item, a_max//2)
#import pdb; pdb.set_trace()
if bisect_l_item >= n - 1:
    bisect_l = a_item[bisect_l_item - 1]
else:
    bisect_l = a_item[bisect_l_item]

bisect_r = a_item[bisect_l_item - 1]
if abs(bisect_r - a_max/2) <= abs(bisect_l - a_max/2):
    print(a_max, bisect_r)
else:
    print(a_max, bisect_l)
#print(bisect_l_item, bisect_l, bisect_r)
#idea_l = comb(a_max, bisect_l)
#idea_r = comb(a_max, bisect_r)
### BUGGY CODE ###

N,M = map(int,input().split())
ls = [0 for _ in range(N)]
flg = 1
for i in range(M):
    a,b = map(int,input().split())
    if ls[a-1] == 0 and ls[b-1] == 0:
        ls[a-1]=flg
        ls[b-1]=flg
        flg+=1
    elif ls[a-1] == 0:
        ls[a-1] = ls[b-1]
    elif ls[b-1] == 0:
        ls[b-1] = ls[a-1]
    else:
        x = ls.count(ls[a-1])
        y = ls.count(ls[b-1])
        if x >= y:
            check = ls[a-1]
        else:
            check = ls[b-1]
        ls[a-1] = check
        ls[b-1] = check
import collections
c = collections.Counter(ls)
plan = c.most_common()
ans = 0
if plan[0][0] == 0 and M != 0:
    ans = plan[1][1]
elif M ==0:
    ans =1    
else:
    ans = plan[0][1]
print(ans)

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m = map(int,input().split())
uf = UnionFind(n)
for i in range(m):
    a,b = map(int,input().split())
    uf.union(a-1,b-1)
ans = 0
for j in range(n):
    check = uf.size(j)
    if ans < check:
        ans = check
print(ans)
### BUGGY CODE ###

n = int(input())
an = [int(num)  for num in input().split()]

sum = 0
for i in range(len(an)):
  for j in range(i+1,len(an)):
    sum +=  an[i]*an[j]
    sum = sum%1000000007
print(sum)

### FIXED CODE ###

n = int(input())
an = [int(num)  for num in input().split()]

an_total = sum(an)
answer = 0
for i in range(len(an)-1):
  an_total -= an[i]
  answer +=  an[i] * an_total
print(answer%1000000007)
### BUGGY CODE ###

n,k = map(int, input().split())
over = n+1
while over > n:
  over = n
  n = abs(n-k)
print(over)

### FIXED CODE ###

n,k = map(int, input().split())
if n % k == 0:
  print(0)
elif n % k <= k - (n % k):
  print(n % k)
else:
  print(k - (n % k))
### BUGGY CODE ###

"""
セグメント木で行きたいところだけど、集合の管理が必要になるため、時間がかかりすぎてしまう。
と思いきや、文字の種類は26種類しかないので、問題ない。
"""
def main():
    import sys
    input = sys.stdin.readline
    class segTree:
        def __init__(self,n):
            if bin(n).count("1") == 1:
                self.leaves = 2**(n.bit_length()-1)
            else:
                self.leaves = 2**n.bit_length()
            self.identity = set()
            self.tree = [set()]*(self.leaves*2)

        def update(self,i,x):
            i = i+self.leaves
            self.tree[i] = set(x)
            i >>= 1
            while i > 0:
                self.tree[i] = self.tree[i*2]|self.tree[i*2+1]
                i >>= 1

        def query(self,l,r):
            #[l:r)のクエリ結果を返す
            l = l + self.leaves
            r = r + self.leaves
            res = self.identity
            while l < r:
                if l&1:
                    res = res|self.tree[l]
                    l += 1
                if r&1:
                    r -= 1
                    res = res|self.tree[r]
                l >>= 1
                r >>= 1
            return len(res)


    N = int(input())
    S = list(input())
    Q = int(input())
    seg = segTree(N)
    for i in range(N):
        seg.update(i,S[i])

    for _ in range(Q):
        q,a,b = input().split()
        if q == "1":
            a = int(a)
            seg.update(a-1,b)
        else:
            a = int(a)
            b = int(b)
            print(seg.query(a-1,b))
main()

### FIXED CODE ###

"""
セグメント木で行きたいところだけど、集合の管理が必要になるため、時間がかかりすぎてしまう。
と思いきや、文字の種類は26種類しかないので、問題ない。
"""
def main():
    import sys
    input = sys.stdin.readline
    from collections import Counter
    class BIT:
        def __init__(self,n):
            self.size = n
            self.tree = [Counter([]) for _ in range(n+1)]
        
        def change(self,i,x,y):
            while i <= self.size:
                if x in self.tree[i]:
                    self.tree[i][x] -= 1
                if y not in self.tree[i]:
                    self.tree[i][y] = 1
                else:
                    self.tree[i][y] += 1
                i += i&-i
    
        def sum(self,i):
            s = Counter([])
            while i > 0:
                s += self.tree[i]
                i -= i&-i
            cnt = 0
            return s


    N = int(input())
    S = list(input())
    Q = int(input())
    bit = BIT(N)
    for i in range(N):
        bit.change(i+1," ",S[i])

    for _ in range(Q):
        q,a,b = input().split()
        if q == "1":
            x = S[int(a)-1]
            S[int(a)-1] = b
            bit.change(int(a),x,b)
        else:
            a = int(a)
            b = int(b)
            count = bit.sum(b) - bit.sum(a-1)
            ans = 0
            for v in count.values():
                if v > 0:
                    ans += 1
            print(ans)
main()
### BUGGY CODE ###

from operator import itemgetter
n,m=map(int,input().split())
wa=0
ac=0
ig=0
l=[(input().split()) for _ in range(m)]
l=sorted(l, key=itemgetter(0))

for t in l:
  c,r=t[0],t[1]
  if c == ig:
    continue
  
  if [c,'AC'] not in l:
    continue
  
  if r == 'WA':
    wa+=1
  elif r == 'AC':
    ac+=1
    ig=c
    
print(ac,wa)

### FIXED CODE ###

n,m=map(int,input().split())
l=[[] for _ in range(n)]
for _ in range(m):
  a,b=input().split()
  l[int(a)-1].append(b)
  
wacnt=0
accnt=0

for rl in l:
  cnt = 0
  for r in rl:
    if r == 'WA':
      cnt+=1
    elif r == 'AC':
      wacnt+=cnt
      accnt+=1
      break
      
print(accnt, wacnt)
### BUGGY CODE ###

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

pnt = [q*(-1)+k for _ in range(n)]
for i in range(n):
    pnt[i] += a.count(i+1)
    if pnt[i] > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

import sys
input = sys.stdin.readline

n, k, q = map(int, input().split())
t = k - q
a = [0 for _ in range(n)]

for i in range(q):
    a[int(input())-1] += 1

for i in range(n):
    pnt = a[i] + t
    if pnt > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

from itertools import permutations

N, C = list(map(int, input().split()))
D =[list(map(int, input().split())) for _ in range(C)] 

remains = {0: [], 1: [], 2: []} 
for i in range(1, N+1):
    line = list(map(int, input().split()))
    for j in range(N):
        remains[(i+j+1)%3].append(line[j])

INF = 65535

def recolor(x, y): 
    return D[x-1][y-1]

answer = INF 
for choice in permutations(range(1, C+1), 3): 
    _answer = 0 
    for i, c in enumerate(choice):
        _answer += sum([recolor(r, c) for r in remains[i] if c != r]) 
    answer = min(answer, _answer)

print(answer)

### FIXED CODE ###

from itertools import permutations
from collections import defaultdict

N, C = list(map(int, input().split()))
D =[list(map(int, input().split())) for _ in range(C)]

remains = {0: defaultdict(int), 1: defaultdict(int), 2: defaultdict(int)}
for i in range(1, N+1):
    line = list(map(int, input().split()))
    for j in range(N):
        remains[(i+j+1)%3][line[j]] += 1

INF = float('inf')

def recolor(x, y, count):
    return D[x-1][y-1] * count

answer = INF
for choice in permutations(range(1, C+1), 3):
    _answer = 0
    for i, c in enumerate(choice):
        _answer += sum([recolor(r, c, remains[i][r]) for r in remains[i] if c != r])
    answer = min(answer, _answer)

print(answer)
### BUGGY CODE ###

from collections import Counter
n = int(input())
A = []
l = []

for i in range(n):
    a = int(input())
    A.append(a)
    if a not in l:
        l.append(a)

d = Counter(A)
ans = len(l)
for i in range(len(l)):
    if d[l[i]]%2 == 0:
        ans -= 1
print(ans)

### FIXED CODE ###

n = int(input())
A = []

for i in range(n):
    a = int(input())
    A.append(a)
A.sort()
i = 0
ans = 0
while True:
    cnt = 0
    while A[i + cnt] == A[i]:
        cnt += 1
        if i + cnt == n:
            break
    if cnt%2 == 1:
        ans += 1
    i += cnt
    if i == n:
        break
print(ans)
### BUGGY CODE ###

n = int(raw_input())
d = {}
for _ in range(n-1):
  v,u = map(int, raw_input().split())
  if v in d:
    d[v].append(u)
  else:
    d[v] = [u]

  if u in d:
    d[u].append(v)
  else:
    d[u] = [v]

visited = [False] * (n+1)
# 0 == fennec, 1 == sunuke
q = [(1,1,0), (n,n,1)]

count_f = 0
count_s = 0

while len(q) > 0:
  cur, prev, sunuke = q.pop(0)
  # print cur,prev,sunuke

  if visited[cur]:
    continue

  visited[cur] = True
  if sunuke:
    count_s += 1
  else:
    count_f += 1

  for v in d[cur]:
    q.append([v, cur, sunuke])

if count_f > count_s:
  print 'Fennec'
else:
  print 'Snuke'

### FIXED CODE ###

n = int(raw_input())
d = {}
for _ in range(n-1):
  v,u = map(int, raw_input().split())
  if v in d:
    d[v].append(u)
  else:
    d[v] = [u]

  if u in d:
    d[u].append(v)
  else:
    d[u] = [v]

# -1: not yet, 0: fennec, 1: sunuke
visited = [-1] * (n+1)
visited[1] = 0
visited[n] = 1

# 0 == fennec, 1 == sunuke
q = [(1,1), (n,n)]

# 0: fennec
# 1: sunuke
count = [1,1]

while len(q) > 0:
  cur, prev = q.pop(0)

  for v in d[cur]:
    if v == prev: continue
    if visited[v] != -1: continue

    chara = visited[prev]
    visited[v] = chara
    count[chara] += 1

    q.append([v, cur])


if count[0] > count[1]:
  print 'Fennec'
else:
  print 'Snuke'

# TLE
# while len(q) > 0:
#   cur, prev, sunuke = q.pop(0)
#   # print cur,prev,sunuke

#   if visited[cur]:
#     continue

#   visited[cur] = True
#   if sunuke:
#     count_s += 1
#   else:
#     count_f += 1

#   for v in d[cur]:
#     q.append([v, cur, sunuke])

# if count_f > count_s:
#   print 'Fennec'
# else:
#   print 'Snuke'
### BUGGY CODE ###

N = int(input())
NN = [[0]*10 for _ in range(11)]
for i in range(11,100):
    As = str(i)[0]
    Ae = str(i)[-1]
    cnt = 0
    for j in range(1,N+1):
        if str(j)[-1]== As and str(j)[0] == Ae:
            cnt +=1
    NN[int(As)][int(Ae)] = cnt


ans = 0
for i in range(1,N+1):
    ans += NN[int(str(i)[0])][int(str(i)[-1])]

print(ans)


### FIXED CODE ###

N = int(input())
NN = [[0]*10 for _ in range(11)]
for i in range(11,100):
    As = str(i)[0]
    Ae = str(i)[-1]
    cnt = 0
    for j in range(1,N+1):
        if str(j)[-1]== As and str(j)[0] == Ae:
            cnt +=1
    NN[int(As)][int(Ae)] = cnt


ans = 0
for i in range(1,N+1):
    ans += NN[int(str(i)[0])][int(str(i)[-1])]

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

x = input()
y = input()

lcs = [[''] * (len(y) + 1) for _ in range(len(x) + 1)]
for i_x in range(len(x)):
    for i_y in range(len(y)):
        if x[i_x] == y[i_y]:
            lcs[i_x+1][i_y+1] = lcs[i_x][i_y] + x[i_x]
        elif len(lcs[i_x+1][i_y]) > len(lcs[i_x][i_y+1]):
            lcs[i_x+1][i_y+1] = lcs[i_x+1][i_y]
        else:
            lcs[i_x+1][i_y+1] = lcs[i_x][i_y+1]

print(lcs[-1][-1])


### FIXED CODE ###

x = input()
y = input()
lx = len(x)
ly = len(y)

chars = [[''] * (ly + 1) for _ in range(lx + 1)]
length = [[0] * (ly + 1) for _ in range(lx + 1)]
prev = [[0b00] * (ly + 1) for _ in range(lx + 1)]

for i_x in range(lx):
    for i_y in range(ly):
        if x[i_x] == y[i_y]:
            length[i_x+1][i_y+1] = length[i_x][i_y] + 1
            chars[i_x+1][i_y+1] = x[i_x]
            prev[i_x+1][i_y+1] = 0b11
        elif length[i_x+1][i_y] > length[i_x][i_y+1]:
            length[i_x+1][i_y+1] = length[i_x+1][i_y]
            prev[i_x+1][i_y+1] = 0b01
        else:
            length[i_x+1][i_y+1] = length[i_x][i_y+1]
            prev[i_x+1][i_y+1] = 0b10

lcs = [''] * length[-1][-1]
i_x, i_y = lx, ly
i = 1
while i_x and i_y:
    if prev[i_x][i_y] == 0b11:
        lcs[-i] = chars[i_x][i_y]
        i += 1
    i_x, i_y = i_x - ((prev[i_x][i_y] & 0b10) >> 1), i_y - (prev[i_x][i_y] & 0b01)

print(''.join(lcs))
### BUGGY CODE ###

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

for x in range(n):
    print(k.count(x+1))


### FIXED CODE ###

import collections

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

c = collections.Counter(k)

for x in range(n):
    print(c[x+1])
### BUGGY CODE ###

s = input()

dp = [[0] * 13 for _ in range(len(s)+1)]
dp[0][0] = 1

mul = 1

for i in range(len(s)):
    x = s[-(i+1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i+1][(mul*k + j)%13] += dp[i][j]
                dp[i+1][(mul*k + j)%13] %= 10**9 + 7
    else:
        k = int(x)
        for j in range(13):
            dp[i+1][(mul*k + j)%13] += dp[i][j]
            dp[i+1][(mul*k + j)%13] %= 10**9 + 7
    mul = mul * 10 % 13

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


### FIXED CODE ###

s = input()

dp = [[0] * 13 for _ in range(len(s)+1)]
dp[0][0] = 1

mul = 1

for i in range(len(s)):
    x = s[-(i+1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i+1][(mul*k + j)%13] += dp[i][j]
                dp[i+1][(mul*k + j)%13] %= 10**9 + 7
    else:
        k = int(x)
        for j in range(13):
            dp[i+1][(mul*k + j)%13] += dp[i][j]
            dp[i+1][(mul*k + j)%13] %= 10**9 + 7
    mul = mul * 10 % 13

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

from math import *
A,B,N=[int(i) for i in input().split()]
f = lambda k:floor(A*k/B)
k=0
mx=f(k)
while k<=B-1 and k<=N:
    if f(k)>mx:
        mx=f(k)
    k+=1
print(mx)


### FIXED CODE ###

from math import *
A,B,N=[int(i) for i in input().split()]
f = lambda k:floor(A*k/B)
if B-1 < N:
    print(f(B-1))
else:
    print(f(N))