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

N,K = map(int,input().split())
H = [int(x) for x in input().split()]
dp = [0]*N
dp[0] = 0
dp[1] = abs(H[1]-H[0])
for i in range(2,N):
    L = [dp[j]+abs(H[i]-H[j]) for j in range(max(0,i-K),i)]
    dp[i] = min(L)
print(dp[N-1])

### FIXED CODE ###

N,K = map(int,input().split())
H = [int(x) for x in input().split()]

def main(N,K,H):
    dp = [0]*N
    for i in range(1,N):
        L = [dp[j]+abs(H[i]-H[j]) for j in range(max(0,i-K),i)]
        dp[i] = min(L)
    print(dp[-1])
main(N,K,H)
### BUGGY CODE ###

N,K = input().split()
N1 = int(N)
K1 = int(K)
for i in range (1000000):
    if K1**(i-1) <= N1 and N1 < K1**i:
        print(i)

### FIXED CODE ###

N,K = input().split()
N1 = int(N)
K1 = int(K)
for i in range (1000):
    if K1**(i-1) <= N1 and N1 < K1**i:
        print(i)
        break
### BUGGY CODE ###

n, m = map(int, input().split())
p = [[] for _ in range(n)]
py = [list(map(int, input().split())) for _ in range(m)]
for _p, _y in py:
    p[_p-1].append(_y)
for i in range(n):
    p[i] = sorted(p[i])

for _p, _y in py:
    print("{:06}{:06}".format(_p, p[_p-1].index(_y) + 1))


### FIXED CODE ###

import time
import numpy as np

# def solve(n, m, py):
"""
n, m = map(int, input().split())
py = [list(map(int, input().split())) for _ in range(m)]
"""

n, m = map(int, input().split())
py = [list(map(int, input().split())) for _ in range(m)]
p = [[] for _ in range(n)]
start = time.time()
for _p, _y in py:
    p[_p - 1].append(_y)
# print(time.time() - start)
for i in range(n):
    p[i] = np.argsort(np.argsort(p[i]))

# print(time.time() - start)
counter = [0 for _ in range(n)]
for _p, _y in py:
    # print("{:06}{:06}".format(_p, p[_p - 1].index(_y) + 1))
    # t = "{:06}{:06}".format(_p, p[_p - 1].index(_y) + 1)
    # print(counter[_y])
    t = "{:06}{:06}".format(_p, p[_p - 1][counter[_p - 1]] + 1)
    print(t)
    counter[_p - 1] += 1
### BUGGY CODE ###

N = int(input())
A = []
for _ in range(N):
    A.append([x - 1 for x in map(int, reversed(input().split()))])

num_game_left = N * (N - 1) // 2
num_days = 0
left_players = set(range(N))
while 0 < num_game_left:
    game_players = set()
    for i in left_players:
        if i in game_players:
            continue
        j = A[i][-1]
        if A[j][-1] == i:
            game_players.add(i)
            game_players.add(j)
    num_game_left -= len(game_players) // 2

    if not game_players:
        break

    num_days += 1
    for i in game_players:
        A[i].pop()
        if not A[i]:
            left_players.remove(i)

if num_game_left == 0:
    print(num_days)
else:
    print(-1)

### FIXED CODE ###

N = int(input())
A = []
for _ in range(N):
    A.append([x - 1 for x in map(int, input().split())])

game = []
for p1 in range(N):
    p2 = A[p1][0]
    if A[p2][0] == p1 and p1 < p2:
        game.append((p1, p2))

cursors = [0] * N
days = 0
while game:
    days += 1
    new_game = []
    for p1, p2 in game:
        cursors[p1] += 1
        if cursors[p1] < N - 1:
            p3 = A[p1][cursors[p1]]
            if cursors[p3] < N - 1 and A[p3][cursors[p3]] == p1:
                new_game.append((p1, p3))
        cursors[p2] += 1
        if cursors[p2] < N - 1:
            p3 = A[p2][cursors[p2]]
            if cursors[p3] < N - 1 and A[p3][cursors[p3]] == p2:
                new_game.append((p2, p3))
    game = new_game

if all(c == N - 1 for c in cursors):
    print(days)
else:
    print(-1)
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int,input().split()))
    Q = int(input())
    B = [list(map(int,input().split())) for _ in range(Q)]
    dict = {}

    for i in range(1,10**5+1):
    #for i in range(1,6):
        dict[i] = 0

    for i in range(N):
        dict[A[i]] += 1

    for i in range(Q):
        dict[B[i][1]] += dict[B[i][0]]
        dict[B[i][0]] = 0
        #print(dict)
        sum = 0
        for i in range(1,10**5+1):
        #for i in range(1,6):
            if dict[i] != 0:
                sum += dict[i]*i
        print(sum)

main()


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int,input().split()))
    Q = int(input())
    B = [list(map(int,input().split())) for _ in range(Q)]
    dict = {}

    for i in range(1,10**5+1):
    #for i in range(1,6):
        dict[i] = 0

    for i in range(N):
        dict[A[i]] += 1

    sum = 0
    for i in range(1,10**5+1):
        #for i in range(1,6):
        if dict[i] != 0:
            sum += dict[i]*i

    for i in range(Q):
        sum = sum +(dict[B[i][0]]*B[i][1] - dict[B[i][0]]*B[i][0])

        dict[B[i][1]] += dict[B[i][0]]
        dict[B[i][0]] = 0
        #print(dict)
        print(sum)

main()
### BUGGY CODE ###

N, K = list(map(int, input().split()))
H = list(map(int, input().split()))
# 最小なものにコストを書き換えたいので初期値は大きく取る
dp = [float('inf')] * N

# 最初はコスト０
dp[0] = 0
for i in range(1, N):
    dp[i] = min(dp[j] + abs(H[i] - H[j]) for j in range(max(i - K, 0), i))
print(int(dp[i]))


### FIXED CODE ###

def test():
    N, K = map(int, input().split())
    H = list(map(int, input().split()))
    dp = [float('inf')]*N
    dp[0] = 0
 
    for i in range(1, N):
        dp[i] = min(dp[j] + abs(H[i] - H[j]) for j in range(max(i-K, 0), i))
 
    print(dp[-1])
 
if __name__ == '__main__':
    test()
### BUGGY CODE ###

L, R = map(int, input().split())

R = min(R, L+2019*2) # 長さを制限しても同じ
MOD = 2019
ans = 2020

for i in range(L, R): # iはLからR-1まで
    for j in range(i+1, R+1): # jはi+1からRまで
        n = ((i%MOD) * (j%MOD))%MOD
        if n < ans:
            ans = n

print(ans)



### FIXED CODE ###

L, R = map(int, input().split())

R = min(R, L+(2019)) # 長さを制限しても同じ
MOD = 2019
ans = 2018

for i in range(L, R): # iはLからR-1まで
    for j in range(i+1, R+1): # jはi+1からRまで
        n = (i*j)%MOD
        ans = min(n, ans)

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

def sol():
    h,w=map(int,input().split())
    l=[]
    d=set()
    for i in range(h):
        s=list(input())
        for j in range(w):
            if s[j]=="#": d.add((i,j))
        l.append(s)
    ans=-1
    for i in range(2000):
        if len(d)==0: break
        ans+=1
        t=set()
        for j in d:
            if 0<=j[0]+1<h and l[j[0]+1][j[1]]==".":
                l[j[0]+1][j[1]]="#"
                t.add((j[0]+1,j[1]))
            if 0<=j[0]-1<h and l[j[0]-1][j[1]]==".":
                l[j[0]-1][j[1]]="#"
                t.add((j[0]-1,j[1]))
            if 0<=j[1]+1<w and l[j[0]][j[1]+1]==".":
                l[j[0]][j[1]+1]="#"
                t.add((j[0],j[1]+1))
            if 0<=j[1]-1<w and l[j[0]][j[1]-1]==".":
                l[j[0]][j[1]-1]="#"
                t.add((j[0],j[1]-1))
        d=t
    print(ans)
 
if __name__ == "__main__":
    sol()

### FIXED CODE ###

def sol():
    h,w=map(int,input().split())
    l=[]
    d=set()
    for i in range(h):
        s=list(input())
        for j in range(w):
            if s[j]=="#": d.add((i,j))
        l.append(s)
    ans=-1
    for i in range(2000):
        if len(d)==0: break
        ans+=1
        t=set()
        for j in d:
            if 0<=j[0]+1<h and l[j[0]+1][j[1]]==".":
                l[j[0]+1][j[1]]="#"
                t.add((j[0]+1,j[1]))
            if 0<=j[0]-1<h and l[j[0]-1][j[1]]==".":
                l[j[0]-1][j[1]]="#"
                t.add((j[0]-1,j[1]))
            if 0<=j[1]+1<w and l[j[0]][j[1]+1]==".":
                l[j[0]][j[1]+1]="#"
                t.add((j[0],j[1]+1))
            if 0<=j[1]-1<w and l[j[0]][j[1]-1]==".":
                l[j[0]][j[1]-1]="#"
                t.add((j[0],j[1]-1))
        d=t
    print(ans)

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

from itertools import product

def add_magic_move(enable_to_move_list):
  ret = list(enable_to_move_list)
  for h, w in enable_to_move_list:
    for target_h, target_w in product([h-1, h, h+1], [w-1, w, w+1]):
      if -1 < target_h < H and -1 < target_w < W and (target_h, target_w) not in enable_to_move_list:
        s[target_h][target_w] = '.'
        ret += [(target_h, target_w)]
  return ret
    

def get_enable_to_move_list(h, w, enable_to_move_list):
  if (h, w) in enable_to_move_list:
    return enable_to_move_list
  enable_to_move_list += [(h, w)]
  targets = ((h+1, w), (h-1, w), (h, w+1), (h, w-1))
  for h, w in targets:
    if -1 < h < H and -1 < w < W and s[h][w] == '.':
      enable_to_move_list = get_enable_to_move_list(h, w, enable_to_move_list)
  return enable_to_move_list

H, W = map(int, input().split())
s_h, s_w = [i-1 for i in map(int, input().split())]
d_h, d_w = [i-1 for i in map(int, input().split())]
s = [list(input()) for i in range(H)]

enable_to_move_list = get_enable_to_move_list(s_h, s_w, [])
i = 0
while True:
  if (d_h, d_w) in enable_to_move_list:
    break
  tmp = add_magic_move(enable_to_move_list)
  i += 1
  for h, w in list(set(tmp) - set(enable_to_move_list)):
  	enable_to_move_list = get_enable_to_move_list(h, w, enable_to_move_list)
  if not set(tmp) ^ set(enable_to_move_list):
    i = -1
    break

print(i)

### FIXED CODE ###

from collections import deque
 
 
walk = [(1, 0), (-1, 0), (0, 1), (0, -1)]
warp = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),
        (-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2),
        (0, -2), (0, -1), (0, 1), (0, 2),
        (1, -2), (1, -1), (1, 0), (1, 1), (1, 2),
        (2, -2), (2, -1), (2, 0), (2, 1), (2, 2),]
 
 
def get_warped(walked, map_):
    warped = deque()
    while walked:
        h, w = walked.popleft()
        for i, j in warp:
            h2 = h + i
            w2 = w + j
            if -1 < h2 < H and -1 < w2 < W and map_[h2][w2] == '.':
                warped.append((h2, w2))
                map_[h2][w2] = map_[h][w] + 1
    return warped, map_
 
 
def get_walked(candidate, map_):
    walked = deque()
    while candidate:
        h, w = candidate.popleft()
        walked.append((h, w))
        for i, j in walk:
            h2 = h + i
            w2 = w + j
            if -1 < h2 < H and -1 < w2 < W and map_[h2][w2] == '.':
                candidate.append((h2, w2))
                map_[h2][w2] = map_[h][w]
    return walked, map_
 
H, W = map(int, input().split())
s_h, s_w = [i-1 for i in map(int, input().split())]
d_h, d_w = [i-1 for i in map(int, input().split())]
map_ = [list(input()) for i in range(H)]
 
candidate = deque([(s_h, s_w)])
map_[s_h][s_w] = 0
 
while candidate:
    walked, map_ = get_walked(candidate, map_)
    candidate, map_ = get_warped(walked, map_)
 
for h in range(H):
    for w in range(W):
        if map_[h][w] == '.':
            map_[h][w] = -1
 
print(map_[d_h][d_w])
### BUGGY CODE ###

N = int(input())
S = input()

L = []
flag1 = [0,1,2,3,4,5,6,7,8,9]

for i in range(N-2):
    x = int(S[i])
    if x in flag1:
        flag1[x] == 99999
    else:
        continue

    for j in range(i+1, N-1):
        for k in range(j+1, N):
            L.append(S[i] + S[j] + S[k])

print(len(set(L)))

### FIXED CODE ###

N = int(input())
S = list(map(int, list(input())))

cnt = 0

for i in range(10):
    for j in range(10):
        for k in range(10):
            pin = [i, j, k]
            x = 0

            for a in S:
                if a == pin[x]:
                    x += 1
                    if x == 3:
                        cnt += 1
                        break

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

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

a_list = []
c_list = []
for i in range(M):
    a, _ = list(map(int, input().split()))
    a_list.append(a)
    c = 0
    for one in list(map(int, input().split())):
        c |= 1<<(one-1)
    c_list.append(c)

INF = 1001001001


dp = [INF]*(1<<N)
dp[0] = 0
for s in range(1<<N):
    for i in range(M):
        t = c_list[i] | s
        cost = a_list[i]+dp[s]
        dp[t] = min(dp[t], cost)

if dp[-1]==INF:
    print(-1)
else:
    print(int(dp[-1]))


### FIXED CODE ###

INF = 1000000000

N, M = list(map(int, input().split()))
a_list = []
c_list = []
for i in range(M):
    a, _ = list(map(int, input().split()))
    a_list.append(a)
    c = 0
    for one in list(map(int, input().split())):
        c |= 1<<(one-1)
    c_list.append(c)

dp = [INF]*(1<<N)
dp[0] = 0
for s in range(1<<N):
    for i in range(M):
        t = c_list[i] | s
        cost = a_list[i]+dp[s]
        dp[t] = min(dp[t], cost)

if dp[-1]==INF:
    print(-1)
else:
    print(int(dp[-1]))
### BUGGY CODE ###

n = int(input())
x = [int(i) for i in input().split()]
a = x.copy()
x.sort()
for i in a:
    if x.index(i) < n//2:
        print(x[int(n//2)])
    else:
        print(x[int(n//2)-1])

### FIXED CODE ###

n = int(input())
x = [int(i) for i in input().split()]
y = x.copy()
y.sort()
y_e = y[n//2]
y_o = y[n//2 - 1]
for xx in x:
    if xx >= y_e:
        print(y_o)
    else:
        print(y_e)
### BUGGY CODE ###

def main():
    N = int(input())
    H = list(map(int, input().split()))
    A = list(map(int, input().split()))
    dp = [0] * H[0] + [A[0]] * (N - H[0] + 1)
    for a, h in zip(A[1:], H[1:]):
        t = dp[h] = dp[h] + a
        for j in range(h + 1, N + 1):
            if dp[j] < t:
                dp[j] = t

    return max(dp)


print(main())


### FIXED CODE ###

class SegTree:
    def __init__(self, a, func):
        self.n = 2**(len(a) - 1).bit_length()
        self.f = func
        self.d = [0] * (2 * self.n - 1)
        self.d[self.n - 1:self.n - 1 + len(a)] = a
        for i in reversed(range(self.n - 1)):
            self.d[i] = self.f(self.d[2 * i + 1], self.d[2 * i + 2])

    def update(self, i, v):
        i += self.n - 1
        self.d[i] = v
        while i:
            i = (i - 1) // 2
            self.d[i] = self.f(self.d[2 * i + 1], self.d[2 * i + 2])

    def query(self, l, r):
        assert l <= r
        l += self.n
        r += self.n
        s = self.d[l - 1]
        while l < r:
            if l & 1:
                s = self.f(s, self.d[l - 1])
                l += 1
            if r & 1:
                r -= 1
                s = self.f(s, self.d[r - 1])
            l //= 2
            r //= 2
        return s

def main():
    N = int(input())
    H = list(map(int, input().split()))
    A = list(map(int, input().split()))
    S = SegTree([0] * N, max)

    for h, a in zip(H, A):
        S.update(h - 1, S.query(0, h - 1) + a)
    return S.query(0, N)

print(main())
### BUGGY CODE ###

N = int(input())
Ln = list(map(int,input().split(' ')))
Ln.sort(reverse=True)

count = 0

def binary_area_search(target_list: list, target_item: int) -> int:
    '''
    @params
    target_list: [1,3,5](ACC)
    target_item: 2

    @return
    return index
    '''
    low = 0
    high = len(target_list) - 1
    while low <= high:
        mid = (low + high) //2
        guess = target_list[mid]
        if guess > target_item:
            if mid == 0:
                return 0
            if target_item > target_list[mid-1]:
                return mid 
            high = mid -1
        else:
            if mid == len(target_list) - 1:
                return None
            if target_list[mid+1] > target_item:
                return mid + 1 
            low = mid + 1
    return None

for a in range(N):
    a_l = Ln[a]
    '''
    N^2*logN
    '''
    for b in range(a+1, N):
        num_b = N - b - 1
        flag = True
        b_l = Ln[b]
        c_threshold = a_l - b_l
        c_list = Ln[b+1:N]
        c_list.sort()
        c_idx = binary_area_search(c_list,c_threshold)
        if c_idx is not None:
            count += len(c_list) - c_idx
    '''
    N^2
    '''
    '''
    current_min = N-1
    b = a +1
    while b <= current_min:
        c_idx = current_min
        bc = Ln[b] + Ln[c_idx]
        if a_l < bc:
            count += (current_min - b)
            b += 1
            continue
        current_min -= 1
    '''
print(count)

### FIXED CODE ###

N = int(input())
Ln = list(map(int,input().split(' ')))
Ln.sort(reverse=True)

count = 0
for a in range(N):
    a_l = Ln[a]
    current_min = N-1
    b = a +1
    while b <= current_min:
        c_idx = current_min
        bc = Ln[b] + Ln[c_idx]
        if a_l < bc:
            count += (current_min - b)
            b += 1
            continue
        current_min -= 1
    '''
    for b in range(a+1, N):
        if b >= current_min:
            break
        for c in range(b+1,N):
            c_idx = current_min
            bc = Ln[b] + Ln[c_idx]
            if a_l < bc:
                count += (current_min - b)
                break
            current_min -= 1
    '''
print(count)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

N,M = map(int,readline().split())
A = [0]+list(map(int,readline().split()))
B = tuple(map(int,read().split()))

for i in range(1,N):
    A[i] += A[i-1]

ticket_sum = [0]*(N*N)
left_init = list(range(1,N))+[0,0]
right_init = list(range(-1,N))
for n in range(M):
    arr = B[n::M]
    # 安いチケットから入れていく -> 連結成分上で採用される
    left = left_init[:]
    right = right_init[:]
    for i in sorted(range(N), key=arr.__getitem__):
        l = left[i-1]
        r = right[i+1]
        left[r] = l; right[l] = r
        # [l,i] x [i,r] に arr[i] を加える
        x = arr[i]
        ticket_sum[l*N+i]+=x
        if i<N-1:
            ticket_sum[(i+1)*N+i]-=x
        if r<N-1:
            ticket_sum[l*N+r+1]-=x
        if i<N-1 and r<N-1:
            ticket_sum[(i+1)*N+r+1]+=x

del B

# 2d累積和
for i in range(N,N*N):
    ticket_sum[i] += ticket_sum[i-N]
for i in range(N*N):
    if i%N:
        ticket_sum[i] += ticket_sum[i-1]

answer = 0
for i in range(N):
    x = A[i]
    for y,t in zip(A[i:],ticket_sum[N*i+i:N*i+N]):
        happy = x-y+t
        if answer < happy:
            answer = happy

print(answer)


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

INF=10**10

N,M = map(int,readline().split())
A = [0,0]+list(map(int,readline().split()))
B = [[INF]*M]+[list(map(int,line.split())) for line in readlines()]

for i in range(1,N+1):
    A[i] += A[i-1]

answer = 0
INF = 10**12
diff = [INF]+[0]*N
left = [list(range(-1,N)) for m in range(M)]
arr = [INF,2,1,2]
for i in range(1,N+1):
    for m in range(M):
        p=i; prev_val=0
        q=left[m][p]
        x = B[i][m]
        while prev_val<=x:
            diff[p] += x-prev_val
            diff[q] -= x-prev_val
            p=q; q=left[m][p]
            prev_val=B[p][m]
        left[m][i]=p
    # 出発地点ごとの収入
    ticket_sum = list(itertools.accumulate(diff[::-1]))[::-1]
    for start in range(1,i+1):
        happy = ticket_sum[start] + A[start]-A[i]
        if answer < happy:
            answer = happy

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

#!/usr/bin/env python
import bisect
from collections import defaultdict
import math

def judge(start, end, S):
    for i in range(start, end):
        s = S[i:i+2]
        if tuple(s) == ("#", "#"):
            return False
    return True

def main():
    N, A, B, C, D = map(int, input().split())
    S = list(input().strip())

    is_ok = judge(A-1, C-1, S)
    if not is_ok:
        print("No")
        return
    is_ok = judge(B-1, D-1, S)
    if not is_ok:
        print("No")
        return

    if C > D:
        for i in range(B-1, D):
            if S[i] != "#":
                new_S = list(S)
                new_S[i] = "#"
                is_ok = judge(A-1, C-1, new_S)
                if is_ok:
                    print("Yes")
                    return
        print("No")
    else:
        print("Yes")

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python
import bisect
from collections import defaultdict
import math

def judge(start, end, S):
    for i in range(start, end):
        s = S[i:i+2]
        if tuple(s) == ("#", "#"):
            return False
    return True

def main():
    N, A, B, C, D = map(int, input().split())
    S = list(input().strip())

    is_ok = judge(A-1, C-1, S)
    if not is_ok:
        print("No")
        return
    is_ok = judge(B-1, D-1, S)
    if not is_ok:
        print("No")
        return

    if C > D:
        for i in range(B-1, D):
            if S[i] != "#" and S[i-1] != "#" and S[i+1] != "#":
                print("Yes")
                return
        print("No")
    else:
        print("Yes")

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

N, M = list(map(int,input().split()))
a = [int(input()) for i in range(M)]

b = [0]*(N+1)
b[0] = 1

if 1 not in a:
    b[1] = 1

for i in range(2,N+1):
    if i not in a:
        for j in range(1,3):
            if b[i-j] != 0:
                b[i]+= b[i-j]

print(b[N]%1000000007)

### FIXED CODE ###

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

b = [0]*(N+2)
b[0] = 1

for i in range(M):
    b[int(input())] = -1

for i in range(N):
    if b[i] != -1:
        if b[i+1] != -1:
            b[i+1] += b[i]
        if b[i+2] != -1:
            b[i+2] += b[i]

print(b[N]%1000000007)
### BUGGY CODE ###

s=input()
t=input()
set_s = {x for x in s}
set_t = {x for x in t}
if len(set_t-set_s)>0:
    print(-1)
else:
    cnt=1
    a=0
    s_ = s
    for x in t:
        idx = s_.find(x)
        if idx==-1:
            cnt+=1
            s_=s
            a=0
            idx = s_.find(x)
        a+=idx+1
        s_=s_[idx+1:]
    print((cnt-1)*len(s)+a)

### FIXED CODE ###

s=input()
t=input()
set_s = {x for x in s}
set_t = {x for x in t}
if len(set_t-set_s)>0:
    print(-1)
else:
    n=len(s)
    letters='abcdefghijklmnopqrstuvwxyz'
    l=[[-1 for i in range(n)] for j in range(26)]
    for i in range(26):
        letter = letters[i]
        if s[-1]==letter:
            l[i][-1]=n-1
        for j in range(1,n):
            idx=n-1-j
            if s[idx]==letter:
                l[i][idx]=idx
            else:
                l[i][idx]=l[i][idx+1]
    cnt=1
    a=0
    for x in t:
        id = ord(x)-97
        if a>=n or l[id][a]==-1:
            cnt+=1
            a=0
            a=l[id][a]+1
        else:
            a=l[id][a]+1
    print((cnt-1)*n+a)
### BUGGY CODE ###

#coding:utf8
import random

def is_prime3(q,k=50):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

A,B=map(int,input().split())
C=[1]
for i in range(2,min(A,B)+1):
    if A % i == 0 and B % i == 0:
        C.append(i)

ans=[]

for j in C:
    if is_prime3(j):
        ans.append(j)

print(len(ans)+1)
        



### FIXED CODE ###

import fractions
import collections
   
A,B = map(int,input().split())
gcd = fractions.gcd(A,B)

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

c = collections.Counter(prime_factorize(gcd))
print(len(list(c.keys()))+1)
### BUGGY CODE ###

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

import math

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

MOD = 10 ** 9 + 7

total = 2 ** n - 1
ans = total - combinations_count(n, a) - combinations_count(n, b)
print(ans % MOD)



### FIXED CODE ###

from functools import reduce

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

MOD = 10 ** 9 + 7

def f(A):
    num = reduce(lambda x, y: x * y % MOD, range(N, N - A, -1))
    den = reduce(lambda x, y: x * y % MOD, range(1, A + 1))
    return num * pow(den, MOD - 2, MOD) % MOD

answer = pow(2, N, MOD) - 1 - f(A) - f(B)
answer %= MOD
print(answer)
### BUGGY CODE ###

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

a=[]

for i in range(1,n):
    if h[i-1]>h[i]:
        a.append(h[i-1])
        h[i-1]=h[i-1]-1        
        if h[i-1]-1>h[i]:
            print('No')
            sys.exit()
    for j in a:
        if h[i]<=(j-2):
            print('No')
            sys.exit()

print('Yes')

### FIXED CODE ###

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

for i in range(n-1):
    if h[i+1]>h[i]:
        h[i+1]-=1
    elif h[i+1]<h[i]:
        print('No')
        sys.exit()

print('Yes')