Harryxun/stf_run huggingface dataset:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions

import copy

# import heapq
# from collections import deque
# import decimal

# sys.setrecursionlimit(100001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, m = ns()
    s = list(input())
    t = list(input())

    gcd = n * m // fractions.gcd(n, m)

    s_idx = [gcd // n * i for i in range(n)]
    t_idx = [gcd // m * i for i in range(m)]

    ans = [-1] * (gcd + 1)
    for i, si in enumerate(s_idx):
        ans[si] = s[i]
    for i, ti in enumerate(t_idx):
        if ans[ti] != -1 and ans[ti] != t[i]:
            print(-1)
            exit(0)
    print(gcd)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions

import copy

# import heapq
# from collections import deque
# import decimal

sys.setrecursionlimit(10000001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    def euclid(a, b):
        if b == 0:
            return a
        else:
            return euclid(b, a % b)

    def multiple(a, b):
        return a * b // euclid(a, b)

    n, m = ns()
    s = list(input())
    t = list(input())

    gcd = multiple(n, m)

    s_idx = [gcd // n * i for i in range(n)]
    t_idx = [gcd // m * i for i in range(m)]
    t_set = set(t_idx)

    for idx in s_idx:
        if idx in t_set:
            if s[idx * n // gcd] != t[idx * m // gcd]:
                print(-1)
                exit(0)

    print(gcd)


if __name__ == '__main__':
    main()
nums = list(map(int, input().split()))
sums = [sum(nums[i:i+3]) for i in range(len(nums)-1)]
poyo = [abs(x-753) for x in sums]
print(min(poyo))

### FIXED CODE ###

s = input()
list = [int(c) for c in s]
num = []
ans = 753
for i in range(len(list)-2):
	num.append((list[i] * 100) + (list[i+1] * 10) + list[i+2])
	if(num[i] >= 753):
		if(ans >= (num[i] - 753)):
			ans = num[i] - 753
	else:
		if(ans > (753 - num[i])):
			ans = 753 - num[i]
print(ans)
a, b, c, d = map(int,input().split())
print('Yes' if a <= b <= c <= d else 'No')

### FIXED CODE ###

k = int(input())
a = "ACL"
print(a * k)
n=int(input())
a=[int(_) for _ in input().split()]
b=[int(_) for _ in input().split()]

d_a={}
d_b={}

for i in range(n):
    d_a[i]=0
    d_b[i]=0

for i in range(n):
    d_a[a[i]]+=1
    d_b[b[i]]+=1

diff=0

for i in range(n):
    if d_a[i]+d_b[i]>n:
        print("No")
        exit()
    diff = max(diff,abs(d_a[i]-d_b[(i-1)%n]))
print("Yes")
# for i in range(n):
#     print(a[i],end=" ")
# print()
for i in range(n):
    print(b[(i-diff)%n],end=" ")
print()

### FIXED CODE ###

n=int(input())
a=[int(_) for _ in input().split()]
b=[int(_) for _ in input().split()]

d_a={}
d_b={}

for i in range(-1,n):
    d_a[i]=0
    d_b[i]=0

for i in range(n):
    d_a[a[i]-1]+=1
    d_b[b[i]-1]+=1

diff=0
c,d=0,0
for i in range(n):
    if d_a[i]+d_b[i]>n:
        print("No")
        exit()
    c+=d_a[i]
    d+=d_b[i-1]
    diff = max(diff,c-d)
print("Yes")
# for i in range(n):
#     print(a[i],end=" ")
# print()
for i in range(n):
    print(b[(i-diff)%n],end=" ")
print()
N_str, q_str = raw_input().split()
N = int(N_str)
q = int(q_str)
A =[]
B =[]
total =0

for i in N:
    t = raw_input().split()
    A.append([t[0],int(t[1])])

while A:
    name, time = A.pop(0)
    if time <= q:
        total += time
        B.append(name+" "+ str(total))
       
    else:
        time -= q
        total += q
        A.append([name, time])

print '\n'.join(B)

### FIXED CODE ###

N_str, q_str = raw_input().split()
N = int(N_str)
q = int (q_str)
A =[]
B =[]
total =0

for i in range(N):
    t = raw_input().split()
    A.append([t[0],int(t[1])])

while A:
    name, time = A.pop(0)
    if time <= q:
        total += time
        B.append(name+" "+ str(total))
       
    else:
        time -= q
        total += q
        A.append([name, time])

print '\n'.join(B)
n, m, k = map(int, input().split())
clusterN = [1] * n
clusterI = [-1] * n
out = [0] * n
def cluster(x):
  if clusterI[x] >= 0:
    minI = cluster(clusterI[x])
    clusterI[x] = minI
    return minI
  else:
    return x

def unite(x, y):
  CX = cluster(x)
  CY = cluster(y)
  if CX != CY:
    if clusterI[CX] > clusterI[CY]:
      x, y = y, x
    clusterN[CX] += clusterN[CY]
    clusterI[CY] = CX
    

for _ in range(m):

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

  unite(a-1, b-1)
  out[a-1] -= 1
  out[b-1] -= 1

for _ in range(k):

  a, b = map(int, input().split())
  if cluster(a-1) == cluster(b-1):
    out[a-1] -= 1
    out[b-1] -= 1
out = [out[i] + clusterN[cluster(i)] - 1 for i in range(n)]
print(*out)

### FIXED CODE ###

n, m, k = map(int, input().split())
clusterN = [1] * n
clusterI = list(range(n))
out = [0] * n
def generateC(x):
  if clusterI[x] != x:
    minI = generateC(clusterI[x])
    clusterI[x] = minI
    return minI
  else:
    return x

def unite(x, y):
  CX = generateC(x)
  CY = generateC(y)
  if CX != CY:
    if CX > CY:
      CX, CY = CY, CX
      x, y = y, x
    clusterN[CX] += clusterN[CY]
    clusterI[CY] = CX
    generateC(y)
    

for _ in range(m):
  a, b = map(int, input().split())

  unite(a-1, b-1)
  out[a-1] -= 1
  out[b-1] -= 1

for _ in range(k):

  a, b = map(int, input().split())
  if generateC(a-1) == generateC(b-1):
    out[a-1] -= 1
    out[b-1] -= 1
out = [out[i] + clusterN[generateC(i)] - 1 for i in range(n)]
print(*out)
import fractions
n= int(input())
a =list(map(int, input().split()))

a0 = min(a)
b0 = a0

if(n==1):
    print(1)
    exit()

for i in a:
    b0 = (b0 * i) // fractions.gcd(b0,i)
b0 = b0 / a0
count = 0
for i in a:
    count += a0*b0 // i
    count = count % (10**9 + 7)

print(count)

### FIXED CODE ###

from fractions import gcd
 
n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
l = 1
for i in a:
    l = i * l // (gcd(i, l))
 
cnt = 0
for i in a:
    cnt += l // i
print(cnt % mod)
s=input()
cnt=0
for i in range(len(s)//2):
  if s[i]!=s[(i*(-1))-1]
  cnt+=1
print(cnt)

### FIXED CODE ###

s=input()
cnt=0
for i in range(len(s)//2):
  if s[i]!=s[(i*(-1))-1]:
    cnt+=1
print(cnt)
from bisect import bisect_left,bisect,bisect_right

n,m=map(int,input().split())
a=list(map(int,input().split()))
d=[]
cb=[[0]*2 for i in range(m)]
for i in range(m):
    bi,ci=map(int,input().split())
    cb[i]=[ci,bi]

a.sort()
cb.sort(reverse=True)

asum=0
isum=0
isumm=0
for i in range(m):
    isum+=cb[i][1]
#    print(i,isum,a[isum-1])
    if a[isum-1]<cb[i][0]:
        asum+=cb[i][0]*cb[i][1]
        isumm=isum
        continue
    else:
        ii=bisect(a,cb[i][0])
        asum+=cb[i][0]*(ii-isumm)
#        print(ii,isum,asum)
        asum+=sum(a[ii:isum])
        isumm=isum
        break
    
if isum<n:
    asum+=sum(a[isum:])
        
print(asum)


### FIXED CODE ###

import sys
from bisect import bisect_left,bisect,bisect_right

icase=0
if icase==0:
    n,m=map(int,input().split())
    a=list(map(int,input().split()))
    d=[]
    cb=[[0]*2 for i in range(m)]
    for i in range(m):
        bi,ci=map(int,input().split())
        cb[i]=[ci,bi]
elif icase==1:
    n,m=3,2
    a=[1, 4, 5]
    cb=[[5, 1], [3, 2]]
elif icase==3:
    n,m=3,2
    a=[100, 100, 100]
    cb=[[99, 3], [99, 3]]
elif icase==2:
    n,m=10,3
    a=[1, 4, 5, 5, 7, 8, 13, 33, 52, 100]
    cb=[[30, 4], [10, 3], [4, 1]]
elif icase==4:
    n,m=11,3
    a=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
    cb=[[1000000000, 4], [1000000000, 3], [1000000000, 3]]
elif icase==5:
    f=open(r"C:\Users\nishi\999atcoder\ABCD040-151\ABC127D\testcase_13_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    ll=f.readline()
    a=list(map(int,ll.split()))
    d=[]
    cb=[[0]*2 for i in range(m)]
    for i in range(m):
        ll=f.readline()
        bi,ci=map(int,ll.split())
        cb[i]=[ci,bi]
    f.close()
    ans=99913215738299
elif icase==6:
    f=open(r"C:\Users\nishi\999atcoder\ABCD040-151\ABC127D\testcase_12_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    ll=f.readline()
    a=list(map(int,ll.split()))
    d=[]
    cb=[[0]*2 for i in range(m)]
    for i in range(m):
        ll=f.readline()
        bi,ci=map(int,ll.split())
        cb[i]=[ci,bi]
    f.close()
    ans=95821339675952

a.sort()
cb.sort(reverse=True)

if cb[0][0]<=a[0]:
    print(sum(a))
    sys.exit()
    
asum=0
isum=0
isumm=0
for i in range(m):
    isum+=cb[i][1]
    if isum>n:
        if a[-1]<=cb[i][0]:
#        print("A",i)
            asum+=cb[i][0]*(n-isumm)
            print(asum)
            sys.exit()
#    isum=min(isum,n)
#    print(i,isum,a[isum-1])
        else:
#        print("C",i)
            ii=bisect_right(a,cb[i][0])
            asum+=cb[i][0]*(ii-isumm)
#        print(ii,isumm,asum)
#        asum+=sum(a[ii:isum])
            asum+=sum(a[ii:])
            print(asum)
            sys.exit()
    if a[isum-1]<=cb[i][0]:
        asum+=cb[i][0]*cb[i][1]
#        asum+=cb[i][0]*(isum-isumm)
#        print("B",i,isum,asum)
        isumm=isum
        continue
    else:
#        print("C",i)
        ii=bisect_right(a,cb[i][0])
        asum+=cb[i][0]*(ii-isumm)
#        print(ii,isumm,asum)
#        asum+=sum(a[ii:isum])
        asum+=sum(a[ii:])
        print(asum)
        sys.exit()
#        isumm=isum
#        break
    isumm=isum
    
#if isumm<n:
asum+=sum(a[isumm:])
        
print(asum)
x = input()

def temp(num):
  if num >= 30:
    print('Yes')
  else:
    print('No')
    
temp(x)

### FIXED CODE ###

x = int(input())

if x >= 30:
  print('Yes')
else:
  print('No')
n,m=[int(i) for i in input().split()]
x=[int(i) for i in input().split()]
x.sort()
a=[]
if m==1:
    print("0")
else:
    for i in range(m-1):
        a.append(x[i+1]-x[i])
    a.sort(reverse=True)
    result=0
    for i in range(n-1):
        result+=a[i]
    print(max(x)-min(x)-result)

### FIXED CODE ###

n,m=[int(i) for i in input().split()]
x=[int(i) for i in input().split()]
x.sort()
a=[]
if m==1 or n>=m:
    print("0")
else:
    for i in range(m-1):
        a.append(x[i+1]-x[i])
    a.sort(reverse=True)
    if n==1:
        print(max(x)-min(x))
    else:
        result=0
        for i in range(n-1):
            result+=a[i]
        print(max(x)-min(x)-result)
n, m = map(int, input().split())
needs = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
usable = {}
for a in map(int, input().split()):
    na = needs[a]
    if na in usable:
        usable[na] = max(usable[na], a)
    else:
        usable[na] = a
use_keys = sorted(usable.keys())

dp = [-9] * (n + 1)
dp[0] = 0
for d in range(2, min(8, n + 1)):
    for u in use_keys:
        du = d - u
        if du < 0:
            break
        dp[d] = max(dp[d], dp[du] + 1)
for d in range(8, n + 1):
    for u in use_keys:
        dp[d] = max(dp[d], dp[d - u] + 1)

ans = ''
remain = n
rk = [(str(a), needs[a]) for a in sorted(usable.values(), reverse=True)]
for d in range(dp[n] - 1, -1, -1):
    for a, na in rk:
        if dp[remain - na] == d:
            ans += a
            remain -= na
            break

print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
needs = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
usable = {}
for a in map(int, input().split()):
    na = needs[a]
    if na in usable:
        usable[na] = max(usable[na], a)
    else:
        usable[na] = a
use_keys = sorted(usable.keys())

dp = [-9] * (n + 1)
dp[0] = 0
for d in range(2, min(8, n + 1)):
    for u in use_keys:
        du = d - u
        if du < 0:
            break
        dp[d] = max(dp[d], dp[du] + 1)
for d in range(8, n + 1):
    for u in use_keys:
        dp[d] = max(dp[d], dp[d - u] + 1)

ans = ''
remain = n
rk = [(str(a), needs[a]) for a in sorted(usable.values(), reverse=True)]
for d in range(dp[n] - 1, -1, -1):
    for a, na in rk:
        ra = remain - na
        if ra < 0:
            continue
        if dp[ra] == d:
            ans += a
            remain = ra
            break

print(ans)
import collections

h,w = map(int,input().split())
maze = []
ans = 0
dy_dx = [[0,1],[1,0],[0,-1],[-1,0]]
for i in range(h):
    s = input()
    a = []
    for j in range(w):
        a.append(s[j])
    maze.append(a)
for i in range(h):
    for j in range(w):
        if maze[i][j] != '#':
            next = collections.deque()
            dist = []
            checked = []
            curmax = 0
            for k in range(h):
                a = [0]*w
                b = [0]*w
                dist.append(a)
                checked.append(b)
            next.append([i,j])
            while len(next) != 0:
                cur = next.popleft()
                checked[cur[0]][cur[1]] = 1
                for l in range(4):
                    if (0 <= cur[0]+dy_dx[l][0] <= h-1) and (0 <= cur[1]+dy_dx[l][1] <= w-1):
                        if checked[cur[0]+dy_dx[l][0]][cur[1]+dy_dx[l][1]] == 0:
                            if maze[cur[0]+dy_dx[l][0]][cur[1]+dy_dx[l][1]] == '.':
                                dist[cur[0]+dy_dx[l][0]][cur[1]+dy_dx[l][1]] = dist[cur[0]][cur[1]]+1
                                next.append([cur[0]+dy_dx[l][0],cur[1]+dy_dx[l][1]])
                                curmax = max(curmax,dist[cur[0]+dy_dx[l][0]][cur[1]+dy_dx[l][1]])
        ans = max(ans,curmax)
print(ans)

### FIXED CODE ###

from collections import deque

h,w = map(int,input().split())
maze = []
ans = 0
dy_dx = [[0,1],[1,0],[0,-1],[-1,0]]
for i in range(h):
    maze.append(input())
flag = True
check = '.'*w
for i in range(h):
    if maze[i] != check:
        flag = False
        break
if flag:
    print(h+w-2)
else:
    for i in range(h):
        for j in range(w):
            if maze[i][j] == '.':
                ne = deque([[i,j]])
                dist = [[0]*w for k in range(h)]
                checked = [[0]*w for k in range(h)]
                while len(ne) != 0:
                    cur = ne.popleft()
                    checked[cur[0]][cur[1]] = 1
                    for l in range(4):
                        t = cur[0]+dy_dx[l][0]
                        u = cur[1]+dy_dx[l][1]
                        if (0 <= t <= h-1) and (0 <= u <= w-1):
                            if checked[t][u] == 0:
                                if maze[t][u] == '.':
                                    dist[t][u] = dist[cur[0]][cur[1]]+1
                                    ne.append([t,u])
                                    ans = max(ans,dist[t][u])
    print(ans)
N, A, B = map(int, input())

if N * A <= B:
  print(N*A)
else:
  print(B)

### FIXED CODE ###

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

if N * A <= B:
  print(N*A)
else:
  print(B)
import fractions
import sys

input = sys.stdin.readline

mp = 1000###max prime
mod = 10 ** 9 + 7
def prime_factorize(n):
    a = [0] * mp
    while n % 2 == 0:
        a[2] += 1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a[f] += 1
            n //= f
        else:
            f += 2
    if n != 1:
        a[n] += 1
    return a

def lcm(x,y):
    return x * y // fractions.gcd(x,y)

def fact_mul(x,y):
    ret = [0] * mp
    for i in range(mp):
        ret[i] = x[i] + y[i]
    return ret

def fact_div(x,y):
    ret = [0] * mp
    for i in range(mp):
        ret[i] = x[i] - y[i]
    return ret

def cal_mod(x):
    ret = 1
    for i in range(mp):
        ret *= (i**x[i]) % mod
        ret %= mod
    return ret


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


l = A[0]###A全体の最大公約数

for i in range(1,N):
    l = lcm(l,A[i])

B0_fact = [0] * mp
l_fact = prime_factorize(l)

A_fact = [0] * N
for i in range(N):
    A_fact[i] = prime_factorize(A[i])

for i in range(mp):
    B0_fact[i] = max(0,l_fact[i]-A_fact[0][i])

ans = cal_mod(B0_fact)

#print(A_fact)
#print(B0_fact)
for i in range(1,N):
    Bi = fact_div(fact_mul(A_fact[0],B0_fact),A_fact[i])
    ans += cal_mod(Bi)
    ans %= mod

print(ans)

### FIXED CODE ###

###提出 #10048385

n = int(input())
a = list(map(int, input().split()))
from fractions import gcd
from functools import reduce
def lcm(x,y):
  return (x*y)//gcd(x,y)
mod = 10**9+7
l = reduce(lcm, a) % mod
ans = 0
for i in range(n):
  ans += l * pow(a[i], mod - 2, mod)
  ans %= mod
print(ans)

#頭良すぎて草
from collections import defaultdict
n = int(input())
d = defaultdict(int)
for i in range(1, n+1):
  s = str(i)
  d[(i[0], i[1])]+=1
ans = 0
for i, j in d.items():
  ans+=j*d[i[::-1]]
print(ans)

### FIXED CODE ###

from collections import defaultdict
n = int(input())
d = defaultdict(int)
for i in range(1, n+1):
  s = str(i)
  d[(s[0], s[-1])]+=1
ans = 0
x = list(d.keys())
for i in x:
    ans+=d[i[::-1]]*d[i]
print(ans)
i = 1
x = int(input())
for y in x:
    if x == 0:
        break
    if i == 10000:
        break
    print(f 'Case {i}: {y}')
    i += 1



### FIXED CODE ###

case_num = 1

while True:
    tmp_num = int(input())
    if tmp_num == 0:
        break
    else:
        print("Case %d: %d" % (case_num,tmp_num))
        case_num += 1
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
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()))

n, q = LI()
ans = (n-2) * (n-2)
min_x_list = [-n]
min_x_idx = [0]
min_y_list = [-n]
min_y_idx = [0]
idx = 1
for _ in range(q):
    a, b = LI()
    min_x = -min_x_list[-1]
    min_y = -min_y_list[-1]
    if a == 1:
        if min_x > b:
            min_x_list.append(-b)
            min_x_idx.append(idx)
            idx += 1
            ans -= min_y - 2
        else:
            r = br(min_x_list, -b)
            i = min_x_idx[r]
            ans -= -min_y_list[i-1] - 2

    elif a == 2:
        if min_y > b:
            min_y_list.append(-b)
            min_y_idx.append(idx)
            idx += 1
            ans -= min_x - 2
        else:
            r = br(min_y_list, -b)
            i = min_y_idx[r]
            ans -= -min_x_list[i-1] - 2

print(ans)


### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
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()))

n, q = LI()
ans = (n-2) * (n-2)
min_x_list = [-n]
min_x_idx = [0]
min_y_list = [-n]
min_y_idx = [0]
idx = 1
for _ in range(q):
    a, b = LI()
    min_x = -min_x_list[-1]
    min_y = -min_y_list[-1]
    if a == 1:
        if min_x > b:
            min_x_list.append(-b)
            min_x_idx.append(idx)
            idx += 1
            ans -= min_y - 2
        else:
            r = br(min_x_list, -b)
            i = min_x_idx[r]
            r = br(min_y_idx, i)
            ans -= -min_y_list[r-1] - 2

    elif a == 2:
        if min_y > b:
            min_y_list.append(-b)
            min_y_idx.append(idx)
            idx += 1
            ans -= min_x - 2
        else:
            r = br(min_y_list, -b)
            i = min_y_idx[r]
            r = br(min_x_idx, i)
            ans -= -min_x_list[r-1] - 2
print(ans)
a,b,c = int(input.split())
if a + b == c:
  print("Yes")
elif a + c == b:
  print("Yes")
elif b + c ==a:
  print("Yes")
else:
  print("No")
  

### FIXED CODE ###

a,b,c = list(map(int,input().split()))
if a + b == c:
  print("Yes")
elif a + c == b:
  print("Yes")
elif b + c ==a:
  print("Yes")
else:
  print("No")
N,A,B=map(int,raw_input().split())
print(sum([i for i in range(1,N+1) if A<=sum(map(int,str(i)))<=B]))

### FIXED CODE ###

N,A,B=map(int,input().split())
print(sum([i for i in range(1,N+1) if A<=sum(map(int,str(i)))<=B]))
import numpy as np


def solve(N, M):
    _p, _y = 0, 0
    py = []
    ans = np.zeros(M,dtype=object)
    rank = [1]*(M+1)

    for i in range(M):
        _p, _y = map(int, input().split())
        py.append((_y, _p, i))
    py.sort()

    for pyi in py:
        pi = pyi[1]
        ans[pyi[2]] = str(pi).zfill(6) + str(rank[pi]).zfill(6)
        rank[pi] += 1

    return ans


if __name__ == "__main__":
    N, M = map(int, input().split())
    ans = solve(N, M)
    for a in ans:
        print(a)


### FIXED CODE ###

import numpy as np


def solve(N, M, py):
    ans = np.zeros(M, dtype=object)
    rank = [1]*(N+1)

    py.sort()

    for pyi in py:
        pi = pyi[1]
        ans[pyi[2]] = str(pi).zfill(6) + str(rank[pi]).zfill(6)
        rank[pi] += 1

    return ans


if __name__ == "__main__":
    _p, _y = 0, 0
    py = []

    N, M = map(int, input().split())
    for i in range(M):
        _p, _y = map(int, input().split())
        py.append((_y, _p, i))

    ans = solve(N, M, py)
    for a in ans:
        print(a)
def partition(A, p, r):
    x = A[r]
    i = p-1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i+1

n = int(input())
A = list(map(int, input().split()))
i = partition(A, 0, n)
A[i] = "["+str(A[i])+"]"
print(*A)

### FIXED CODE ###

def partition(A, p, r):
    x = A[r]
    i = p-1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i+1

n = int(input())
A = list(map(int, input().split()))
i = partition(A, 0, n-1)
A[i] = "["+str(A[i])+"]"
print(*A)
i,x = map(int,input().split())

print(case i : x)

### FIXED CODE ###

i = 1

while True:

 x=int(input())
 if x==0:
  break
 print("Case {0}: {1}".format(i,x))
 i+=1
from collections import defaultdict
dic = defaultdict(int)

n, m = map(int, input().split())
ar_a = map(int, input().split())
for i in range(m):
  b, c = map(int, input().split())
  dic[c] += b

ar = []
for c in sorted(dic.keys(), reverse=True):
  cnt = dic[c]
  ar += [c] * cnt
  if len(ar) >= n:
    break

if len(ar) < n:
  ar += [0] * (n-len(ar))

sum = 0
for x, y in zip(ar, sorted(ar_a)):
  sum += max([x,y])
print(sum)


### FIXED CODE ###

dic = {}

n, m = map(int, input().split())
ar_a = map(int, input().split())
for i in range(m):
  b, c = map(int, input().split())
  if c not in dic:
    dic[c] = 0
  dic[c] += b

ar = []
for c in sorted(dic.keys(), reverse=True):
  cnt = dic[c]
  if cnt > n:
    cnt = n
  ar += [c] * cnt
  if len(ar) >= n:
    break

if len(ar) < n:
  ar += [0] * (n-len(ar))

sum = 0
for x, y in zip(ar, sorted(ar_a)):
  sum += max([x,y])
print(sum)
n = int(input())
lst = list(map(int, input().split()))
ans = 1
for a in lst: 
    ans *= a
	if ans > 1000000000000000000:
		print(-1);
		return;
if(ans>1000000000000000000): 
    print(-1)
else:
    print(ans)


### FIXED CODE ###

n = int(input())
lst = list(map(int, input().split()))
lst.sort()
ans = 1
for a in lst: 
    ans *= a
    if ans > 1e18:
        print(-1)
        break
else:
    print(ans)
a, b, c = map(int, input().split())
if a + b + 2 * (a * b) ** 0.5 < c
    print("Yes")
else:
    print("No")

### FIXED CODE ###

a, b, c = map(int, input().split())
if c - a - b > 0 and 4 * a * b < ((c - a - b) ** 2):
    print("Yes")
else:
    print("No")
from decimal import *


def target(x):
    x = Decimal(x)
    return (A * x).divmod(B) - A * (x.divmod(B))


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

left = 1
right = N

while right - left > 1:
    mid = left + (right - left) // 2
    y = target(mid)
    prv = target(mid - 1)
    nxt = target(mid + 1)
    if prv <= y <= nxt:
        left = mid
    else:
        right = mid


print(target(right))


### FIXED CODE ###

def target(x):
    return (A * x) // B - A * (x // B)


A, B, N = map(int, input().split())
print(target(min(B - 1, N)))