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

# from sys import stdin #入力の高速化(0.2秒ぐらい早くなる)
A, B, Q = list(map(int, input().split()))
# もし神社(寺)が1つしかなかった場合に両端に仮想の神社を建築して処理の一貫性を保つ。かりにこれが選ばれても最大のコストなので最終的に最適になることはない。
INF = 10 ** 18

# S = [-INF] + list(map(int, (stdin.readline() for _ in [0] * A))) + [INF]
# T = [-INF] + list(map(int, [stdin.readline() for _ in [0] * B])) + [INF]
S = [-INF] + [int(input()) for _ in range(A)]+[INF]
T = [-INF] + [int(input()) for _ in range(B)]+[INF]

from bisect import bisect_right
# from bisect import bisect_left as bisect_right #これでも通ったりする。
from itertools import product

for q in range(Q):  # 各問に答える
    x = int(input())  # 位置の指定
    s_idx, t_idx = bisect_right(S, x), bisect_right(T, x)
    ans = INF
    # 左右の神社と寺のの組み合わせ
    for s, t in product(S[s_idx - 1:s_idx + 1], T[t_idx - 1:t_idx + 1]):
        t_root = abs(t - x) + abs(s - t)  # 寺から最初に回るルート
        s_root = abs(s - x) + abs(s - t)
        ans = min(ans, t_root, s_root)
    # 最小をとって終わり
    print(ans)

'''
bisect_right

ソートされた順序を保ったまま x を a に挿入できる点を探し当てます。リストの中から検索する部分集合を指定するには、パラメータの lo と hi を使います。デフォルトでは、リスト全体が使われます。x がすでに a に含まれている場合、挿入点は既存のどのエントリーよりも後(右)になります。戻り値は、list.insert() の第一引数として使うのに適しています。a はすでにソートされているものとします。


In[3]: A
Out[3]: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

In[4]: bisect.bisect_right(A, 2.5)
Out[4]: 3

In[5]: bisect.bisect_right(A, 3)
Out[5]: 4
'''


### FIXED CODE ###

A, B, Q = list(map(int, input().split()))
# もし神社(寺)が1つしかなかった場合に両端に仮想の神社を建築して処理の一貫性を保つ。かりにこれが選ばれても最大のコストなので最終的に最適になることはない。
INF = 10 ** 18

S = [-INF] + [int(input()) for _ in range(A)]+[INF]
T = [-INF] + [int(input()) for _ in range(B)]+[INF]

from bisect import bisect_right
from itertools import product


for q in range(Q):  # 各問に答える
    x = int(input())  # 位置の指定
    s_idx, t_idx = bisect_right(S, x), bisect_right(T, x)
    ans = INF
    # 左右の神社と寺のの組み合わせ
    for s, t in product(S[s_idx - 1:s_idx + 1], T[t_idx - 1:t_idx + 1]):
        t_root = abs(t - x) + abs(s - t)  # 寺から最初に回るルート
        s_root = abs(s - x) + abs(s - t)
        ans = min(ans, t_root, s_root)
    # 最小をとって終わり
    print(ans)

'''
bisect_right

ソートされた順序を保ったまま x を a に挿入できる点を探し当てます。リストの中から検索する部分集合を指定するには、パラメータの lo と hi を使います。デフォルトでは、リスト全体が使われます。x がすでに a に含まれている場合、挿入点は既存のどのエントリーよりも後(右)になります。戻り値は、list.insert() の第一引数として使うのに適しています。a はすでにソートされているものとします。


In[3]: A
Out[3]: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

In[4]: bisect.bisect_right(A, 2.5)
Out[4]: 3

In[5]: bisect.bisect_right(A, 3)
Out[5]: 4
'''
### BUGGY CODE ###

S = input()
length_substring_S = len(S)
test_str_list = ['dream', 'dreamer', 'erase', 'eraser']
flag = True

while flag == True:
  for i in range(len(test_str_list)):
    if S[0:length_substring_S].endswith(test_str_list[i]):
      length_substring_S -= len(test_str_list[i])
      flag = True
      break
    flag = False

if length_substring_S == 0:
  print('YES')
else:
  print('NO')

### FIXED CODE ###

S = input()
length_substring_S = len(S)
test_str_list = ['dream', 'dreamer', 'erase', 'eraser']
flag = True

while flag == True:
  flag = False
  for i in range(len(test_str_list)):
    if S[0:length_substring_S].endswith(test_str_list[i]):
      length_substring_S -= len(test_str_list[i])
      flag = True
      break

if length_substring_S == 0:
  print('YES')
else:
  print('NO')
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
L.sort()
cnt = 0

import bisect
for i in range(N):
  for j in range(i+1,N-1):
    insert = bisect.bisect_left(L[j+1:],L[i]+L[j])
    cnt += insert
        
print(cnt)

### FIXED CODE ###

N = int(input())
L = list(map(int,input().split()))
L.sort()
cnt = 0

import bisect
for i in range(N):
  for j in range(i+1,N-1):
    insert = bisect.bisect_left(L,L[i]+L[j]) -j -1
    cnt += insert
        
print(cnt)
### BUGGY CODE ###

N, M = [int(nm) for nm in input().split()]
A = [-1]
for m in range(M):
  A.append(int(input()))
A.append(N+1)

import math
total_case = 1
for m in range(M+1):
  a1 = A[m]
  a2 = A[m+1]
  safe_stairs = a2 - a1 - 1
  if safe_stairs == 0:
    print(0)
    break
  howmany_jump1 = safe_stairs - 1
  mx_jump2 = howmany_jump1 // 2
  #２のジャンプは０回～（mx_jump2）回
  case = 0
  for j2 in range(mx_jump2 + 1):
    jump2 = j2
    jump1 = howmany_jump1 - (j2 * 2)
    
    factorial_jump12 = 1
    for p in range(2, jump1+jump2+1):
      factorial_jump12 *= p
    
    factorial_jump1 = 1
    for q in range(2, jump1+1):
      factorial_jump1 *= q
    
    factorial_jump2 = 1
    for r in range(2, jump2+1):
      factorial_jump2 *= r
    
    c = factorial_jump12 // (factorial_jump1 * factorial_jump2)
    case += c
  total_case *= case
else:
  ans = total_case % (10**9 + 7)
  print(ans)

### FIXED CODE ###

N, M = [int(nm) for nm in input().split()]
if M != 0:
  a = int(input())

C = [1, 0] # [-2段目, -1段目]
C += [0]*(N+10) # C = [-2段目, -1段目, 0段目, 1段目, 2段目, ...]
for n in range(0, N+1):
  if M == 0:
    C[n+2] = (C[n] + C[n+1]) % 1000000007
  else: # M > 0:
    if n != a:
      C[n+2] = (C[n] + C[n+1]) % 1000000007
    else: # n == a:
      C[n+2] = 0
      M -= 1
      if M > 0:
        a = int(input())

ans = C[N+2]  % 1000000007
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
ab = []
for i in range(n):
  a,b = map(int,input().split())
  ab.append([-a,b])
ab.sort()
ab.reverse()
#print(ab)
here = 0
ans = 0
pool = [0 for _ in range(10**4+1)]
maxi = 0
cnt = 0
for i in range(m+1):
  while True:
    if here == n:
      break
    elif ab[here][0] == -i:
      add = ab[here][1]
      pool[add] += 1
      if add > maxi:
        maxi = add
      here += 1
      cnt += 1
    else:
      break
  if cnt != 0:
    cnt -= 1
    for j in range(10**4):
      '''
      if pool[10**4-j] != 0:
        ans += 10**4-j
        print(10**4-j,i)
        pool[10**4-j] -= 1
        break
      '''
    ans += maxi
    pool[maxi] -= 1
    if pool[maxi] == 0:
      if cnt == 0:
        maxi = 0
      else:
        while True:
          maxi -= 1
          if pool[maxi] != 0:
            break
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
ab = []
for i in range(n):
  a,b = map(int,input().split())
  ab.append([-a,b])
ab.sort()
ab.reverse()
#print(ab)
here = 0
ans = 0
pool = []
import heapq
for i in range(m+1):
  while True:
    if here == n:
      break
    elif ab[here][0] == -i:
      heapq.heappush(pool,-ab[here][1])
      here += 1
    else:
      break
  try:
    #print(pool)
    ans -= heapq.heappop(pool)
    #print(pool)
  except:
    pass
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-


def sieve(ks):
    rejected_set = {x for x in ks for i in range(
        1, x) for j in range(i, x) if i + j + 2 * i * j == x}
    return {2} | {2 * y + 1 for y in (ks - rejected_set)}


def number_of_primes(n):
    return len({p for p in sieve(set(range(1, n + 1))) if p <= n})


def main():
    raw_args = []
    while True:
        try:
            raw_args.append(input())
        except EOFError as e:
            break
    for n in map(int, raw_args):
        print(number_of_primes(n))

if __name__ == "__main__":
    main()

### FIXED CODE ###

#!/usr/bin/env python3

"""Enumerates primes in an interval.

Verification: [0009](https://onlinejudge.u-aizu.ac.jp/status/users/hamukichi/submissions/1/0009/judge/4571021/Python3)
"""


import math
import sys


def segment_sieve(begin, end):
    """Enumerates the prime numbers in [`begin`, `end`).

    Returns (as a tuple):

    - `is_prime`: a list of bool values.
      If an integer `i` is a prime number, then `is_prime[i - begin]` is True.
      Otherwise `is_prime[i -begin]` is False.
    - `primes`: a list of prime numbers in [`begin`, `end`).
    """

    assert 1 < begin <= end
    sqrt_end = math.ceil(math.sqrt(end))
    is_prime_small = [True for i in range(sqrt_end)]
    is_prime_small[0] = False
    is_prime_small[1] = False
    is_prime = [True for i in range(end - begin)]
    for i in range(2, sqrt_end):
        if is_prime_small[i]:
            for j in range(2 * i, sqrt_end, i):
                is_prime_small[j] = False
            for k in range(max(2, (begin + i - 1) // i) * i, end, i):
                is_prime[k - begin] = False
    primes = [i for i, cond in enumerate(is_prime, begin) if cond]
    return is_prime, primes


def main():
    ns = [int(n) for n in sys.stdin.readlines()]
    max_n = max(ns)
    begin = 2
    is_prime, _ = segment_sieve(begin, max_n + 1)
    for n in ns:
        print(sum(is_prime[:n + 1 - begin]))


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

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

dp = [int(1e8) for i in range(H+1)]
dp[0] = 0

for h in range(1,H+1):
  cand = []
  for n in range(1,N+1):
    if h - AB[n][0] < 0:
        cand.append(dp[0] + AB[n][1])
    else:
        cand.append(dp[h-AB[n][0]] + AB[n][1])
  dp[h] = min(cand)
print(dp[H])

### FIXED CODE ###

import sys

input = sys.stdin.readline
H, N = map(int, input().split())
magic = [list(map(int, input().split())) for _ in range(N)]

max_damage = max(damage for damage, cost in magic)
dp = [0] * (H + max_damage)

for x in range(1, H + max_damage):
    dp[x] = min(dp[x - damage] + cost for damage, cost in magic)

ans = min(dp[H:])

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

n=int(input())
a=list(map(int,input().split()))
for i in range(1,n+1):
  print(a.count(i))

### FIXED CODE ###

import collections
n=int(input())
c=collections.Counter(list(map(int,input().split())))
for i in range(1,n+1):
  print(c[i])
### BUGGY CODE ###

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)
S = str(input())
N = len(S)
M = 13
#c = [0]*(N)
#for i in range(N):
#    c[i] = (10**i)%M
#    c[i] = pow(10,i,M)
#print(c)
#c.reverse()
#print(c)
"""
dp = [[0]*M for _ in range(N+1)]
i = int(0)
for j in range(M):
    dp[0][j] = 1
for s in S:
    if s == "?":
        for l in range(10):
            m = l * c[i] % M
            dp[i+1][(M - m) % M] += dp[i][j]
    else:
        m = int(s) * c[i] % M
        dp[i][(M - m) % M] +=dp[i][j]
    i +=1
"""
dp = [[0]*M for _ in range(N)]
c = (10**(N-1))%M
if S[0] == "?":
    for l in range(10):
        dp[0][l*c%M] += 1
else:
    m = int(S[0]) * c%M
    dp[0][m] = 1
S = S[1:]
i = int(1)
for s in S:
    c = (10 ** (N - 1-i)) % M
    if s == "?":
        for j in range(13):
            for l in range(10):
                dp[i][j] += dp[i-1][(j-l*c)%13]
    else:
        st = int(s)
        for j in range(13):
            dp[i][j] = dp[i-1][(j-st*c)%13]
    i +=1

"""
dp = [[0]*M for _ in range(N)]
if S[0] == "?":
    for l in range(10):
        m = l * c[0]%M
        dp[0][m] += 1
else:
    m = int(S[0]) * c[0]%M
    dp[0][m] = 1

for i in range(1,N):
    if S[i] == "?":
        for j in range(M):
            for l in range(10):
                m = l*c[i]%M
                dp[i][j] += dp[i-1][(M+j-m)%M]
    else:
        for j in range(M):
            m = int(S[i])*c[i]%M
            dp[i][j] = dp[i-1][(M+j-m)%M]
"""
#print(dp)
print(dp[-1][5]%mod)



### FIXED CODE ###

import sys
 
 
def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    s = str(input().rstrip('\n'))
    ls = [[0] * 13 for _ in range(len(s))]
    for i in range(len(s)):
        if i == 0:
            if s[-i-1] == "?":
                for j in range(10):
                    ls[i][j] += 1
            else:
                ls[i][int(s[-i-1])] += 1
        else:
            mult = pow(10, i, 13)
            if s[-i-1] == "?":
                for j in range(13):
                    for k in range(10):
                        ls[i][(k * mult + j) % 13] += ls[i-1][j]
            else:
                st = int(s[-i-1])
                for j in range(13):
                    ls[i][(st * mult + j) % 13] += ls[i-1][j]
        for j in range(13):
            ls[i][j] = ls[i][j] % mod
    print(ls[-1][5])
 
 
if __name__ == '__main__':
    solve()
### BUGGY CODE ###

N = int(input())
row = input()
L = [""]*N
for i in range(N):
  L[i] = row[i]

count = 0
while(1):
  while(1):
    if len(L) == 0:
      break
    if L[0] == "R":
      del L[0]
    elif L[-1] == "W":
      del L[-1]
    else:
      break
      
  if len(L) == 0:
    break
  else:
    left = L[0]
    right = L[-1]
    L[0] = right
    L[-1] = left
    count = count + 1
    
print(count)

### FIXED CODE ###

N = int(input())
stone = input()

R_count = 0
W_count = 0
for i in range(len(stone)):
  if stone[i] == "R":
    R_count = R_count + 1
  else:
    W_count = W_count + 1

W = 0
R = R_count
try_num_prev = -1
for i in range(N):
  if R_count == 0 or W_count == 0:
    try_num = 0
    break
  
  if W <= R:
    try_num = R
  else:
    try_num = W
  
  #print(try_num_prev, try_num)
  if try_num_prev >= 0 and try_num_prev < try_num:
    try_num = try_num_prev
    break
  else:
    try_num_prev = try_num
    if stone[i] == "R":
      R = R - 1
    else:
      W = W + 1
    
print(try_num)
### BUGGY CODE ###

import sys

def wfs(queue, S, step, goal):
    next_queue = []
    for q in queue:
        if q == goal:
            return step+1

        i, j = q[0], q[1]
        S[i][j] = '#'

        if S[i+1][j] == '.':
            next_queue.append([i+1, j])
        if S[i-1][j] == '.':
            next_queue.append([i-1, j])
        if S[i][j+1] == '.':
            next_queue.append([i, j+1])
        if S[i][j-1] == '.':
            next_queue.append([i, j-1])

    if len(next_queue) == 0:
        return -1
    else:
        return wfs(next_queue, S, step+1, goal)


def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    S = []
    init = 0
    for _ in range(H):
        s = [c for c in input().strip()]
        init += s.count('#')
        S.append(['#'] + s + ['#'])
    S = [['#'] * (W+2)] + S + [['#'] * (W+2)]
    minstep = wfs([[1,1]], S, 0, [H, W])
    if minstep == -1:
        print(-1)
    else:
        print(H*W - minstep - init)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

def wfs(queue, S, step, goal):
    next_queue = set()
    for q in queue:
        if q == goal:
            return step+1

        i, j = q[0], q[1]
        S[i][j] = '#'

        if S[i+1][j] == '.':
            next_queue.add((i+1, j))
        if S[i-1][j] == '.':
            next_queue.add((i-1, j))
        if S[i][j+1] == '.':
            next_queue.add((i, j+1))
        if S[i][j-1] == '.':
            next_queue.add((i, j-1))

    if len(next_queue) == 0:
        return -1
    else:
        next_queue = list(set(next_queue))
        return wfs(next_queue, S, step+1, goal)


def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    S = []
    black = 0
    for _ in range(H):
        s = [c for c in input().strip()]
        black += sum([c == '#' for c in s])
        S.append(['#'] + s + ['#'])
    S = [['#'] * (W+2)] + S + [['#'] * (W+2)]
    init = set([(1, 1)])
    minstep = wfs(init, S, 0, (H, W))
    if minstep == -1:
        print(-1)
    else:
        print(H*W - minstep - black)


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

def main():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1

    print(N)
    for k in range(2, N):
        ans = 0
        for i in range(N):
            ans += sum(1 for j in range(i + 1, N)
                       if min(j - i, abs(i - X) + abs(j - Y) + 1) == k)
        print(ans)


main()


### FIXED CODE ###

def main():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1

    print(N)
    dist = [0] * (N + 1)

    for i in range(N):
        for j in range(i + 1, N):
            d = min(j - i, abs(i - X) + abs(j - Y) + 1)
            dist[d] += 1

    for k in range(2, N):
        print(dist[k])


main()
### BUGGY CODE ###

import bisect
n,m = (int(i) for i in input().split())
a = []
a2 = []
for i in range(m):
 tmp1,tmp2 = (int(i) for i in input().split())
 a.append([tmp1,tmp2])
 a2.append(tmp1)
query = sorted(a, key=lambda x: x[0])
start = sorted(a2)
query2 = query[0:bisect.bisect_right(start,1)]
cand = []
for c,b in enumerate(query2):
  if [b[1],n] in a:
    print('POSSIBLE')
    exit()
print('IMPOSSIBLE')

### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
n,m = (int(i) for i in input().split())
uf = UnionFind(n-1)
for i in range(m):
  a,b = (int(i) for i in input().split())
  if a == 1 or b ==n: uf.union(a-1,b-1)

if uf.same_check(0,n-1): print('POSSIBLE')
else:print('IMPOSSIBLE')
### BUGGY CODE ###

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

pre_list = []
# set start point
for iidx, i in enumerate(C):
    for tidx, t in enumerate(i):
        if t == '#':
            pre_list.append((iidx, tidx))
            C[iidx][tidx] = 0

# bfs 
count = 0
 
while len(pre_list) > 0:
    count += 1
    next_list = []
    for y,x in pre_list:
        for i,j in ((1,0),(0,-1),(0,1),(-1,0)):
            if y+i < 0 or x+j < 0 or y+i >= H or x+j >= W:
                continue
            if C[y+i][x+j] == '.':
                C[y+i][x+j] = "count"
                next_list.append((y+i,x+j))
    pre_list = next_list
print(count-1)


### FIXED CODE ###

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

state = []
# 初期状態
for h in range(H):
    for w in range(W):
        if field[h][w] == "#":
            state.append([w, h])

tmp = []
ret = 0
while len(state) > 0:
    tmp = list()
    ret += 1
    for x, y in state:
        for nx, ny in ((1,0), (-1,0), (0,1), (0,-1)):
            nx += x
            ny += y
            if nx < 0 or ny < 0 or nx >= W or ny >= H:
                continue

            if field[ny][nx] == ".":
                field[ny][nx] = "#"
                tmp.append([nx, ny])
    state = tmp

print(ret-1)
### BUGGY CODE ###

n=input()
s=input()

import re

cnt=0
for i in range(0,1000):
  t="{0:03d}".format(i)
  reg=r'.*'+re.escape(t[0])+r'.*'+re.escape(t[1])+r'.*'+re.escape(t[2])
  if re.search(reg,s):
    cnt+=1

print(cnt)
  

### FIXED CODE ###

n=input()
s=input()

cnt=0
for i in range(0,1000):
  pos=0
  t="{0:03d}".format(i)
  for j in range(int(n)):
    if s[j] == t[pos]:
      pos+=1
    if pos == 3:
      cnt+=1
      break

print(cnt)
### BUGGY CODE ###

s=input()

d=[0]*2019
dp=0
d[0]+=1
l=len(s)

for i in range(l-1,-1,-1):
	dp = (dp+int(s[i])*(10**(l-1-i)))%2019
	d[dp]+=1
res=0

for a in d:
	res+=a*(a-1)//2
	
print(res)

### FIXED CODE ###

s = list(input())
mods = [0]*(len(s))
countRemainder = [0] * 2019
cnt = 0


m = 1
mod = 0
for i in range(len(s)):
    mod += int(s[len(s) - i - 1]) * m

    mod %= 2019
    m *= 10
    m %= 2019

    countRemainder[mod] += 1

countRemainder[0] += 1

for i in range(2019):
    cnt += int(countRemainder[i] * (countRemainder[i] - 1) / 2)

print(cnt)
### BUGGY CODE ###

n = int(input())
s = list(input())

ans=0
for i in range(n):
    for j in range(i,n):
        for k in range(j,n):
            if (j-i)!=(k-j) and s[i]!=s[j] and s[i]!=s[k] and s[j]!=s[k]:
                ans +=1

print(ans)


### FIXED CODE ###

n = int(input())
s = input()
r_count = s.count('R')
g_count = s.count('G')
b_count = s.count('B')

count=0
for i in range(n):
    a = s[i]
    for j in range(i+1,n):
        if (2*j-i)>(n-1):
            continue
        b=s[j]
        c=s[2*j-i]
        if a!=b and b!=c and a!=c:
            count+=1
print(r_count*g_count*b_count-count)
### BUGGY CODE ###

a = int(input())
b = map(int, input().split())
b_list = list(b)
count = 0
for i in range(len(b_list)):
    if b_list[i] == min(b_list[:i+1]):
        count += 1
        
print(count)

### FIXED CODE ###

a = int(input())
b_list = list(map(int, input().split()))
count = 0
mini=a
for i in range(len(b_list)):
    if b_list[i] <= mini:
        count += 1
        mini = b_list[i]
        
print(count)
### BUGGY CODE ###

from sys import stdin
from sys import setrecursionlimit

setrecursionlimit(10 ** 7)

n,m,k = map(int,stdin.readline().rstrip().split())
mod = 998244353
point = 0

def combination(n,r,mod=mod):
    r=min(r,n-r)
    up,down=1,1
    for i in range(r):
        up=up*(n-i)%mod
        down=down*(i+1)%mod
    return up*pow(down,mod-2,mod)%mod

col = m
for i in range(n-1,-1,-1):
    now = col
    now *= combination(n-1,i)
    if i <= k:
        point += now%mod
    col *= m-1
    col %= mod

print(point%mod)

### FIXED CODE ###

from sys import stdin
from sys import setrecursionlimit

setrecursionlimit(10 ** 7)

n,m,k = map(int,stdin.readline().rstrip().split())
mod = 998244353
wariate = 1
point = 0

def prepare(n, MOD=mod):
    facts = [1]*(n+1)
    for i in range(1, n+1):
        facts[i] = facts[i-1]*i%MOD
    invs = [1]*(n+1)
    invs[n] = pow(facts[n], MOD-2, MOD)
    for i in range(0, n)[::-1]:
        invs[i] = invs[i+1] * (i+1) % MOD
    return facts, invs
facts, invs = prepare(n, mod)
for i in range(n-1,-1,-1):
    now = m
    if i != n-1:
        wariate *= m-1
        wariate %= mod
    now *= wariate%mod

    now *= facts[n-1]*invs[n-1-i]*invs[i]
    if i <= k:
        point += now%mod

print(point%mod)
### BUGGY CODE ###

from collections import Counter

N, K = map(int, input().split())
counter = Counter(list(map(int, input().split())))
ans = 0
if len(counter.keys()) > K:
    for i in range(len(counter.keys()) - K):
        ans += counter.most_common()[0 - i - 1][1]

print(ans)


### FIXED CODE ###

import collections

N, K = map(int, input().split())
arr = list(map(int, input().split()))
ans = 0
cnt = collections.defaultdict(int)
for num in arr:
    cnt[num] += 1

vals = sorted(cnt.values())

if len(cnt) > K:
    for i in range(len(cnt) - K):
        ans += vals[i]

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

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

re = 1
for i in range(1, M // N + 1):
    if M % i == 0:
        a = M // i
        if a >= N:
            re = i
        else:
            break
print(re)  

### FIXED CODE ###

def factorize(n):
    fct = []  
    b, e = 2, 0  
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def divisorize(fct):
    b, e = fct.pop() 
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]

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

if M == 1:
    print(1)
else:
    re = 1
    fa = factorize(M)
    div_list = divisorize(fa)

    for i in range(len(div_list)):
        num = 1
        for j in range(len(div_list[-1 - i])):
            l = div_list[-1-i][j]
            num *= l[0] ** l[1]
        d = M // num 
        if d >= N and num > re:
            re = num
    print(re)