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

def main():
    D, N = list(map(int, input().split()))
    mod = 100 ** D
    cnt = 0
    i = 1
    while True:
        if i == mod:
            continue
        if i % mod == 0:
            cnt += 1
        if cnt == N:
            print(i)
            break
        i += 1


if __name__ == "__main__":
    main()


### FIXED CODE ###

D, N = map(int, input().split())
if N < 100:
    print(N * (100**D))
else:
    print(101 * (100**D))
### BUGGY CODE ###

import numpy as np
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
hh = input().split()
h = np.array([int(x) for x in hh])
d = np.inf
dp = np.ones(N) * d
dp[0] = 0
cc = np.arange(1, N)
for i in cc:
  c =  np.arange(1, min(i, K)+1)
  j = i - min(i, K)
  dp[i] = min(dp[j:i]+np.abs(h[i]-h[j:i]))
print(int(dp[N-1]))

### FIXED CODE ###

import sys
import numpy as np

# inputを高速化する。
input = sys.stdin.readline

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

# dpの配列を作る。
dp = np.zeros(n, dtype=int)
# hの配列を作る。
h = np.array(h)


for i in range(1, n):
    # start は負になることはない。
    start = max(0, i-k)
    # 行列として足し算できるのでforを使う必要がない。
    dp[i] = min(dp[start: i] + np.abs(h[i] - h[start: i]))

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

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

def mod_nCr(n,k,mod):
    a = 1
    for i in range(n-k+1,n+1):
        a = a*i%mod
    b = 1
    for i in range(1,k+1):
        b = b*pow(i,mod-2,mod)%mod
    return a*b%mod

mod = 10**9+7
ans = 0
for i in range(k-1,n)[::-1]:
    ans += a[i]*mod_nCr(i,k-1,mod)
    ans %= mod
a.reverse()
for i in range(k-1,n)[::-1]:
    ans -= a[i]*mod_nCr(i,k-1,mod)
    ans %= mod
print(ans%mod)

### FIXED CODE ###

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

def mod_nCr(n,k,mod):
    r = min(k,n-k)
    return fact[n]*factinv[k]*factinv[n-k]%mod

mod = 10**9+7
fact = [1,1]
inv = [0,1]
factinv = [1,1]
for i in range(2,n+1):
    fact.append(fact[-1]*i%mod)
    inv.append((-inv[mod%i]*(mod//i))%mod)
    factinv.append((factinv[-1]*inv[-1])%mod)
    
ans = 0
for i in range(k-1,n)[::-1]:
    ans += a[i]*mod_nCr(i,k-1,mod)
    ans %= mod
a.reverse()
for i in range(k-1,n)[::-1]:
    ans -= a[i]*mod_nCr(i,k-1,mod)
    ans %= mod
print(ans%mod)
### BUGGY CODE ###

import math

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

for _ in range(K):
  H[H.index(max(H))] = 0

ans = 0
for i in H:
  ans += i
  
print(ans)

### FIXED CODE ###

import math

N, K = map(int,input().split())
H = list(map(int,input().split()))
H.sort(reverse = True)

for i in range(K):
  H[min(i, N-1)] = 0

ans = 0
for i in H:
  ans += i
  
print(ans)
### BUGGY CODE ###

import sys
def main():
  input = sys.stdin.readline
  sys.setrecursionlimit(10**7)
  n,k = map(int,input().split())
  sl = [0]*n
  dl = [0]*n
  tree = [[] for i in range(n)]
  mod = 10**9+7

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

  def perm(n, k = 1):
    pdt = 1
    if n != int(n) or k != int(k):
      raise ValueError("perm() not defined for float object")
    elif k < 0:
      pdt = 0
    elif n < 0:
      pdt = 0
    else:
      for x in range(n, n-k, -1):
        pdt *= x
    return pdt

  def dfs(x,depth,k):
    sl[x] = 1
    dl[depth] += 1
    child = 0
    ans = 1
    for i in tree[x]:
      if sl[i] == 0:
        ans *= dfs(i,depth+1,k)
        ans %= mod
        child += 1
    if depth == 0:
      ans *= perm(k-1,child)
      ans %= mod
    else:    
      ans *= perm(k-2,child)
      ans %= mod
    return ans

  print(dfs(0,0,k)*k%mod)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
mod = 10**9+7

def main():
  
  n,k = map(int,input().split())
  sl = [0]*(n+1)
  tree = [[] for i in range(n+1)]
  
  for i in range(n-1):
    a,b = map(int,input().split())
    tree[a] += (b,)
    tree[b] += (a,)

  def dfs(x,depth,k):
    sl[x] = 1
    child = 0
    ans = 1
    for i in tree[x]:
      if sl[i] == 0:
        ans *= dfs(i,depth+1,k)
        child += 1
    if depth == 0:
      for x in range(k-1, k-1-child, -1):
        ans = ans * x % mod   
    else:    
      for x in range(k-2, k-2-child, -1):
        ans = ans * x % mod
    ans %= mod
    return ans

  print(dfs(1,0,k)*k%mod)

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

n=int(input())
S=input()
RGB=[[] for i in range(3)]
for i in range(n):
    if S[i]=="R":
        RGB[0].append(i)
    elif S[i]=="G":
        RGB[1].append(i)
    else:
        RGB[2].append(i)
L=[len(RGB[0]),len(RGB[1]),len(RGB[2])]
m=L.index(max(L))
A=[]
for i in range(3):
    if i==m:
        continue
    else:
        A.append(i)
C=RGB[A[0]]
D=RGB[A[1]]
E=RGB[m]

ans=0
for i in range(L[A[0]]):
    for j in range(L[A[1]]):
        r=C[i]
        g=D[j]
        d=abs(r-g)
        cnt=0
        if d%2==0:
            if (r+g)//2 in E:
                cnt+=1
        if r<g:
            if g+d in E:
                cnt+=1
            if r-d in E:
                cnt+=1
        if r>g:
            if r+d in E:
                cnt+=1
            if g-d in E:
                cnt+=1
        ans+=L[m]-cnt
print(ans)

### FIXED CODE ###

n=int(input())
S=input()
RGB=[[] for i in range(3)]
for i in range(n):
    if S[i]=="R":
        RGB[0].append(i)
    elif S[i]=="G":
        RGB[1].append(i)
    else:
        RGB[2].append(i)
L=[len(RGB[0]),len(RGB[1]),len(RGB[2])]
m=L.index(max(L))
A=[]
for i in range(3):
    if i==m:
        continue
    else:
        A.append(i)
C=RGB[A[0]]
D=RGB[A[1]]
E=RGB[m]

ans=0
for i in range(L[A[0]]):
    for j in range(L[A[1]]):
        r=C[i]
        g=D[j]
        d=abs(r-g)
        cnt=0
        if d%2==0:
            if (r+g)//2 in E:
                cnt+=1
        u=max(r,g)+d
        l=min(r,g)-d
        if 0<=u<=n-1:
            if u in E:
                cnt+=1
        if 0<=l<=n-1:
            if l in E:
                cnt+=1
        ans+=L[m]-cnt
print(ans)
### BUGGY CODE ###

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

p = {}
for i in range(H):
    for j in range(W):
        p[A[i][j]] = (i, j)

d = [[float('inf')]*(H*W) for _ in range(H*W)]

for i in range(1, H*W+1):
    for j in range(1, H*W+1):
        dist = abs(p[i][0]-p[j][0]) + abs(p[i][1]-p[j][1])
        d[i-1][j-1] = dist
        d[j-1][i-1] = dist


dp = [[float('inf')]*(H*W) for _ in range(H*W)]
for i in range(H*W):
    dp[i][i] = 0
    for j in range(i+D, H*W, D):
        dp[i][j] = dp[i][j-D] + d[j][j-D]

for _ in range(Q):
    L, R = map(lambda x:int(x)-1, input().split())
    print(dp[L][R])

### FIXED CODE ###

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

p = {}
for i in range(H):
    for j in range(W):
        p[A[i][j]-1] = (i, j)

d = [0]*(H*W)
for i in range(D, H*W):
    d[i] = d[i-D] + abs(p[i][0]-p[i-D][0]) + abs(p[i][1]-p[i-D][1])

for _ in range(Q):
    L, R = map(lambda x:int(x)-1, input().split())
    print(d[R]-d[L])
### BUGGY CODE ###

N,K,Q = map(int,input().split())
A = [int(input()) for x in range(Q)]
for i in range(N):
  z = 0
  for j in range(Q):
    if A[j] == i + 1:
      z += 1
  if z > Q - K:
    print('Yes')
  else:
    print('No')
 
    


### FIXED CODE ###

N,K,Q = map(int,input().split())
A = [int(input()) for x in range(Q)]
ans = [K - Q] * N


for j in range(Q):
  ans[A[j] - 1] += 1
  
for i in range(N):
  print('Yes' if ans[i] > 0 else 'No')
### BUGGY CODE ###

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

B = []
for a in A:
    B.append(a)
    B = B[::-1]

print(' '.join(B))

### FIXED CODE ###

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

B = ['_' for _ in range(N)]
if N % 2 == 0:
    for i, a in enumerate(A):
        if i % 2 == 0:
            B[N//2 + i//2] = a
        else:
            B[N//2 - (i+1)//2] = a
else:
    for i, a in enumerate(A):
        if i % 2 == 0:
            B[N//2 - i//2] = a
        else:
            B[N//2 + (i+1)//2] = a

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

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

### FIXED CODE ###

k,s=map(int,input().split())
cnt=0
for i in range(k+1):
  for j in range(k+1):
    h = s-i-j
    if 0<=h and h <=k:
      cnt+=1
print(cnt)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

# 上限は1000
N = ri()
S = list(rs())
answer = set()

for i in range(len(S)-2):
    se2 = set()
    for j in range(i+1, len(S)-1):
        if j in se2:
            continue
        se2.add(j)
        se = set(S[j+1:])
        x = S[i]
        y = S[j]
        for z in se:
            answer.add((x, y, z))

print(len(answer))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

# 上限は1000
N = ri()
S = list(rs())
answer = set()
se1 = set()
for i in range(len(S)-2):
    x = S[i]
    if x in se1:
        continue
    se1.add(x)
    se2 = set()
    for j in range(i+1, len(S)-1):
        y = S[j]
        if y in se2:
            continue
        se2.add(y)
        se = set(S[j+1:])
        for z in se:
            answer.add((x, y, z))

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

import sys
import math
from functools import reduce

# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SR(): return sys.stdin.readline().rstrip()

ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii_uppercase2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'

# リストを改行区切りで出力する
p2D = lambda x: print(*x, sep="\n")
p2E = lambda x: print(''.join(x))
p2S = lambda x: print(*x, sep=" ")

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

N = II()
S = input()

ans = 0
for i in range(1, N-2):
    for j in range(2, N):
        if j < i:
            continue
        for k in range(3, N+1):
            if k < j:
                continue
            if S[i-1] != S[j-1] and S[i-1] != S[k-1] and S[k-1] != S[j-1] and j-i != k-j:
                    ans+=1
print(ans)

### FIXED CODE ###

import sys
import math
from functools import reduce

# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SR(): return sys.stdin.readline().rstrip()

ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii_uppercase2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'

# リストを改行区切りで出力する
p2D = lambda x: print(*x, sep="\n")
p2E = lambda x: print(''.join(x))
p2S = lambda x: print(*x, sep=" ")

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

N = int(input())
S = input()
ans = S.count("R") * S.count("G") * S.count("B")
for i in range(N-2):
  for j in range(i+1,N-1):
    k=2*j-i
    if k>=N:
      continue
    if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
      ans-=1
print(ans)
### BUGGY CODE ###

import math

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

ans = 0
for x in range(1, N+1):
    term1 = math.floor(A*x/B)
    term2 = A * math.floor(x/B)
    temp = term1 - term2

    # print("x: {}, temp: {}, term1: {}, term2: {}".format(x, temp, term1, term2))

    ans = max(ans, temp)

print(ans)


### FIXED CODE ###

import math

DEBUG = False

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

if DEBUG:
    ans = 0
    for x in range(1, N+1):
        term1 = math.floor(A*x/B)
        term2 = A * math.floor(x/B)
        temp = term1 - term2
        print("x: {}, temp: {}, term1: {}, term2: {}".format(x, temp, term1, term2))
        ans = max(ans, temp)
    print(ans)

print(math.floor(A*min(B-1, N)/B)-A*math.floor(min(B-1, N)/B))
### BUGGY CODE ###

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

if a == b:
    if a % n == 0:
        print('OK')
    else:
        print('NG')
else:
    while a < b:
        if a % n ==0:
            print('OK')
        else:
            a += 1
            if a % n == 0:
                print('OK')
                break
            elif a == b:
                print("NG")

### FIXED CODE ###

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

if a == b:
    if a % n == 0:
        print('OK')
    else:
        print('NG')
elif a % n == 0:
    print('OK')
else:
    while a < b:
        a += 1
        if a % n == 0:
            print('OK')
            break
        elif a == b:
            print("NG")
### BUGGY CODE ###

def main():
  def prime_factorize(n):
    a = []
    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 prime_dict(a):
    import collections
    c = collections.Counter(prime_factorize(a))
    return c

  ans = 0
  n = int(input())
  a = tuple(map(int, input().split()))
  ov = 10**9+7
  c = {}
  for i in a:
    d = prime_dict(i)
    for k in d.keys():
      m = 0
      if k in c:
        if d[k] < c[k]:
          continue
      c[k] = d[k]
  lcm = 1
  for k,v in c.items():
    lcm *= k**v
  for i in a:
    ans += lcm//i%ov
  print(ans%ov)
if __name__ == "__main__":
  main()

### FIXED CODE ###

def main():
  from functools import reduce
  from fractions import gcd
  ans = 0
  n = int(input())
  b = tuple(map(int, input().split()))
  ov = 10**9+7
  def lcm(x,y):
    return (x * y) // gcd(x, y)
  def lcm_list(a):
    return reduce(lcm, a, 1)
  l = lcm_list(b)
  for i in range(n):
    ans += l//b[i]
  print(ans%ov)
if __name__ == "__main__":
  main()
### BUGGY CODE ###

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

n_pears = 0
used_ball = [False] * N

for i in reversed(range(0, len(A))):
    if used_ball[i]:
        continue
    for j in reversed(range(0, i)):
        if used_ball[j]:
            continue
        if not ((A[i] + A[j]) & (A[i] + A[j] - 1)):
            n_pears += 1
            used_ball[j] = True
            break

print(n_pears)

### FIXED CODE ###

import math
from collections import Counter


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

n_pears = 0
counter = Counter(A)

for i in reversed(range(0, len(A))):
    if counter[A[i]] <= 0:
        continue
    counter[A[i]] -= 1
    Aj = 2 ** int(math.log2(A[i]) + 1) - A[i]
    if counter[Aj] > 0:
        n_pears += 1
        counter[Aj] -= 1

print(n_pears)
### BUGGY CODE ###

import sys
#input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
mod = 10**9+7
N = int(input())
p = list(map(float, input().split()))
dp = [[0]*(N+1) for _ in range(N)]
dp[0][0] = 1-p[0]
dp[0][1] = p[0]
for i in range(1, N):
    for j in range(N+1):
        if j == 0:
            dp[i][j] = dp[i-1][j]*(1-p[i])
        else:
            dp[i][j] = dp[i-1][j-1]*p[i]+dp[i-1][j]*(1-p[i])
print(sum(dp[-1][(N+1)//2:]))








### FIXED CODE ###

import sys
#input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
mod = 10**9+7
N = int(input())
p = list(map(float, input().split()))
dp = [[0]*(N+1) for _ in range(N)]
dp[0][0] = 1-p[0]
dp[0][1] = p[0]
for i in range(1, N):
    for j in range(N+1):
        if j == 0:
            dp[i][j] = dp[i-1][j]*(1-p[i])
        else:
            dp[i][j] = dp[i-1][j-1]*p[i]+dp[i-1][j]*(1-p[i])
print(sum(dp[-1][(N+1)//2:]))
### BUGGY CODE ###

import heapq
import copy

N,M = map(int,input().split())

baito = []
for i in range(N):
    baito.append(list(map(int, input().split())))

baito.sort(key=lambda x: x[0])

que = []
ans = 0
for i in range(1, M+1):
    tmp = copy.copy(baito)
    for val in baito:
        if val[0] <= i:
            heapq.heappush(que, val[1]*-1)
            tmp.pop(0)
        else:
            break
    baito = tmp
    if len(que) != 0:
        ans += heapq.heappop(que)*-1

print(ans)

### FIXED CODE ###

import heapq

N,M = map(int,input().split())

baito = [[] for i in range(M+1)]
for i in range(N):
    A,B = map(int,input().split())
    if A <= M:
        baito[A].append(B)

que = []
ans = 0
for i in range(1, M+1):
    if len(baito[i]) != 0:
        for val in baito[i]:
            heapq.heappush(que, val*-1)
    if len(que) != 0:
        ans += heapq.heappop(que)*-1

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

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

# M回の握手の幸福度最大化
# X以上になる握手を全て採用したときに、M通りを越える
# Xの最大値を求める

import bisect

ok=-1
ng=(10**10)*m+1

# x以上の握手をm通り以上作れるか
def isOk(x,m):
  cnt=0
  # 左手をループする
  for i in range(len(A)):
    left=A[i]
    minright=x-left
    # minright以上の数を数える
    cnt+=n-bisect.bisect_left(A,minright)
    if cnt>=m:
      return True
  return cnt>=m

while abs(ok-ng)>1:
  mid=abs(ok+ng)//2
  if isOk(mid,m):
    ok=mid
  else:
    ng=mid

x=ok
# x以上となる幸福度を足し合わせる
# 足し合わせた握手がMを越える場合、xぴったりを足し過ぎている

# 効率化のため累積和を作成
Asum=[0]+A
for i in range(1,len(Asum)):
  Asum[i]=Asum[i-1]+Asum[i]
  
# Aの添字i以降を全て足すときは、
# Asum[-1]-Asum[i]

ans=0
cnt=0
for i in range(len(A)):
  left=A[i]
  minright=x-left
  start=bisect.bisect_left(A,minright)
  cnt+=n-start
  ans+=left*(n-start)+(Asum[-1]-Asum[start])
  
if cnt>m:
  ans-=(cnt-m)*x
  
print(ans)


### FIXED CODE ###

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

# M回の握手の幸福度最大化
# X以上になる握手を全て採用したときに、M通りを越える
# Xの最大値を求める

import bisect

ok=-1
ng=(10**10)+2

# x以上の握手をm通り以上作れるか
def isOk(x,m):
  cnt=0
  # 左手をループする
  for i in range(len(A)):
    left=A[i]
    minright=x-left
    # minright以上の数を数える
    cnt+=n-bisect.bisect_left(A,minright)
    if cnt>=m:
      return True
  return cnt>=m

while abs(ok-ng)>1:
  mid=abs(ok+ng)//2
  if isOk(mid,m):
    ok=mid
  else:
    ng=mid

x=ok
# x以上となる幸福度を足し合わせる
# 足し合わせた握手がMを越える場合、xぴったりを足し過ぎている

# 効率化のため累積和を作成
Asum=[0]+A
for i in range(1,len(Asum)):
  Asum[i]=Asum[i-1]+Asum[i]
  
# Aの添字i以降を全て足すときは、
# Asum[-1]-Asum[i]

ans=0
cnt=0
for i in range(len(A)):
  left=A[i]
  minright=x-left
  start=bisect.bisect_left(A,minright)
  cnt+=n-start
  ans+=left*(n-start)+(Asum[-1]-Asum[start])
  
if cnt>m:
  ans-=(cnt-m)*x
  
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-


class Node():
    def __init__(self, loc=None, left=None, right=None):
        self.loc = loc
        self.l = left
        self.r = right

class Point():
    def __init__(self, id, xy):
        self.id = int(id)
        self.x = int(xy[0])
        self.y = int(xy[1])

if __name__ == '__main__':

    n = int(input())
    P = [Point(i, input().split(" ")) for i in range(n)]
    q = int(input())
    Q = [list(map(int, input().split(" "))) for _ in range(q)]
    T = [None] * n

    def make2DTree(l, r, depth):
        global np
        if l >= r:
            return None

        mid = (l + r) // 2
        t = np
        np += 1
        if depth % 2 == 0:
            P[l:r] = sorted(P[l:r], key=lambda p: p.x)
        else:
            P[l:r] = sorted(P[l:r], key=lambda p: p.y)

        T[t] = Node(loc=mid)
        T[t].l = make2DTree(l, mid, depth + 1)
        T[t].r = make2DTree(mid + 1, r, depth + 1)

        return t

    def find(v, sx, tx, sy, ty, depth, ans):
        x = P[T[v].loc].x
        y = P[T[v].loc].y

        if (sx <= x <= tx) and (sy <= y <= ty):
            ans.append(P[T[v].loc].id)

        if depth % 2 == 0:
            if T[v].l is not None and sx <= x:
                find(T[v].l, sx, tx, sy, ty, depth + 1, ans)
            if T[v].r is not None and x <= tx:
                find(T[v].r, sx, tx, sy, ty, depth + 1, ans)

        else:
            if T[v].l is not None and sy <= y:
                find(T[v].l, sx, tx, sy, ty, depth + 1, ans)
            if T[v].r is not None and y <= ty:
                find(T[v].r, sx, tx, sy, ty, depth + 1, ans)

    np = 0
    root = make2DTree(0, n, 0)

    for sx, tx, sy, ty in Q:
        ans = []
        find(root, sx, tx, sy, ty, 0, ans)
        ans.sort()
        if ans:
            print("\n".join(map(str, ans)))
        print("")



### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
from operator import itemgetter
from bisect import bisect_left, bisect_right

if __name__ == '__main__':

    P = [tuple(map(int, input().split())) + (i,)
         for i in range(int(input()))]  # (x,y,i)
    P.sort()
    root = int(math.sqrt(len(P)))
    low = [x for x, y, i in P[::root]]
    high = [x for x, y, i in P[root - 1::root]] + [float('inf')]

    # disjoint subsets (ordered by y) of P
    P = [sorted(P[i:i + root], key=itemgetter(1))
         for i in range(0, len(P), root)]
    P = [([y for x, y, i in Pi], Pi)
         for Pi in P]  # ([y in subsets], [subsets])
    q = int(input())
    Q = [list(map(int, input().split(" "))) for _ in range(q)]

    for sx, tx, sy, ty in Q:
        ret = []
        for i in range(bisect_left(high, sx), bisect_right(low, tx)):
            k, v = P[i]
            for i in range(bisect_left(k, sy), bisect_right(k, ty)):
                if sx <= v[i][0] <= tx:
                    ret.append(v[i][2])
        if ret:
            ret.sort()
            print('\n'.join(map(str, ret)))
        print()
### BUGGY CODE ###

a,b,n=map(int,input().split())
ans=0
for i in range(1,n+1):
    t=int((a*i)/b)-a*int(i/b)
    ans=max(ans,t)
print(ans)

### FIXED CODE ###

a,b,n=map(int,input().split())
def f(x):
    return int(a*x/b)-a*int(x/b)
print(f(min(b-1,n)))
### BUGGY CODE ###

n, k = map(int, input().split())
ns = list(map(int, input().split()))
min_num = float('inf')
for i in range(n - k+1):
    l = ns[i:i + k]
    if l[-1] < 0:
        min_num = min(min_num, abs(l[0]))
    elif l[0] < 0 and l[-1] >= 0:
        min_num = min(min_num, abs(l[0]) * 2 + l[-1])
        min_num = min(min_num, abs(l[0]) + l[-1] * 2)
    else:
        min_num = min(min_num, l[-1])
print(min_num)

### FIXED CODE ###

n, k = map(int, input().split())
ns = list(map(int, input().split()))
min_num = float('inf')
for i in range(n - k+1):
    l = ns[i]
    r = ns[i+k-1]
    min_num = min(min_num, abs(l) + abs(r-l), abs(r) + abs(l-r))
print(min_num)
### BUGGY CODE ###

import numpy as np
n,x,y=map(int,input().split())
def dist(i,j):
  if i>=j:
    d=0
  else:
    d=min(abs(j-i),abs(y-j)+1+abs(x-i),abs(y-i)+1+abs(x-j))
  return d
for l in range(2,n+1):
  distmap=np.array([dist(k,l) for k in range(1,n+1) for l in range(2,n+1)])
[print(np.count_nonzero(distmap==m)) for m in range(1,n)]

### FIXED CODE ###

n,x,y=map(int,input().split())
def dist(i,j):
  if i>=j:
    d=0
  else:
    d=min(abs(j-i),abs(y-j)+1+abs(x-i),abs(y-i)+1+abs(x-j))
  return d
distmap=[0]*n
for l in range(2,n+1):
  for k in range(1,l):
    distmap[dist(k,l)]+=1
print('\n'.join(map(str,distmap[1:])))
### BUGGY CODE ###

N,P = map(int,input().split())
k = 1
c = int(P**(1/N))+2
for i in range(c,1,-1):
    if P%(i**N)==0:
        k=i
        break
print(k)

### FIXED CODE ###

N,P = map(int,input().split())
r = round(P**(1/N))
for i in range(r,0,-1):
    if P%(i**N)==0:
        print(i)
        exit()