Harryxun/stf_run huggingface dataset:
n=int(input())
mod=10**9+7
l=['A','C','G','T']
NG=['AGC','GAC','ACG']
NG2=['AAGC','ACGC','AGGC','ATGC','AGAC','AGCC','AGTC']
L=[]
for i1 in range(4):
  for i2 in range(4):
    for i3 in range(4):
      for i4 in range(4):
        L.append(l[i1]+l[i2]+l[i3]+l[i4])
dp=[[0 for i in range(256)] for j in range(n+1)]
for i in range(256):
  if L[i][1:4] in NG or L[i][0:3] in NG or L[i] in NG2:
    dp[4][i]=0
  else:
    dp[4][i]=1
for j in range(5,n+1):
  for i in range(256):
    if L[i][1:4] in NG or L[i][0:3] in NG or L[i] in NG2:
      dp[j][i]=0
    else:
      for i2 in range(256):
        if L[i2][1:4]==L[i][0:3]:
          dp[j][i]+=dp[j-1][i2]
    dp[j][i]%=mod
print(sum(dp[n])%mod)

### FIXED CODE ###

import sys
n=int(input())
if n==3:
  print(61)
  sys.exit()
mod=10**9+7
l=['A','C','G','T']
NG=['AGC','GAC','ACG']
NG2=['AAGC','ACGC','AGGC','ATGC','AGAC','AGCC','AGTC']
L=[]
for i1 in range(4):
  for i2 in range(4):
    for i3 in range(4):
      for i4 in range(4):
        L.append(l[i1]+l[i2]+l[i3]+l[i4])
dp=[[0 for i in range(256)] for j in range(n+1)]
for i in range(256):
  if L[i][1:4] in NG or L[i][0:3] in NG or L[i] in NG2:
    dp[4][i]=0
  else:
    dp[4][i]=1
for j in range(5,n+1):
  for i in range(256):
    if L[i][1:4] in NG or L[i][0:3] in NG or L[i] in NG2:
      dp[j][i]=0
    else:
      for i2 in range(256):
        if L[i2][1:4]==L[i][0:3]:
          dp[j][i]+=dp[j-1][i2]
    dp[j][i]%=mod
print(sum(dp[n])%mod)
M=pow(10,5)

prime_sieve=[-1 for i in range(M+1)]
prime_sieve[0]=1
prime_sieve[1]=1

primes=[]
for i in range(M+1):
  if prime_sieve[i]==-1:
    primes.append(i)
    for j in range(2,(M+1)//i+1):
      prime_sieve[i*j]=1
#print(prime_sieve)
rangesum=[0,0,0]
sum=0
for i in range(3,M+1):
  if prime_sieve[i]==-1:
    if prime_sieve[(i+1)//2]==-1:
       sum+=1
       #print(i,sum)
  rangesum.append(sum)

Q=int(input())
for i in range(Q):
  l,r=[int(x) for x in str(input()).split()]
  print(rangesum[r]-rangesum[l-1])


### FIXED CODE ###


M=pow(10,5)

prime_sieve=[-1 for i in range(M+1)]
prime_sieve[0]=1
prime_sieve[1]=1

primes=[]
for i in range(M+1):
  if prime_sieve[i]==-1:
    primes.append(i)
    for j in range(2,(M)//i+1):
      prime_sieve[i*j]=1
#print(prime_sieve)
rangesum=[0,0,0]
sum=0
for i in range(3,M+1):
  if prime_sieve[i]==-1:
    if prime_sieve[(i+1)//2]==-1:
       sum+=1
       #print(i,sum)
  rangesum.append(sum)

Q=int(input())
for i in range(Q):
  l,r=[int(x) for x in str(input()).split()]
  print(rangesum[r]-rangesum[l-1])
a, b, c = map(int, input().split())
A, B, C = sorted([a, b, c])
if (B - A) % 2 == (C - A) % 2 == 0:
    print((C - A) // 2 + (C - B) // 2)
else:
    print((C - A) // 2 + (C - B) // 2 + 2)

### FIXED CODE ###

s = input()
if s.count("a") == 1 and s.count("b") == 1 and s.count("c") == 1:
  print("Yes")
else:
  print("No")
l = list(input().sprit())
t = list(input().sprit())
c = 0
for i in range(0,2):
  if l[i] == t[i]:
    c = c+1
  else:
    continue

print(c)

### FIXED CODE ###

l = input()
t = input()
c = 0
for i in range(0,3):
  if l[i] == t[i]:
    c = c+1
  else:
    continue

print(c)
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

x, y = map(int, read().split())


def c(n, k):
    return 1 if(k <= 0 or n <= k) else c(n-1, k-1) + c(n-1, k)


if y > x:
    temp = y
    y = x
    x = temp

if ((x + y) % 3 != 0) or x > y * 2:
    print("0")
else:
    n = ((x + y) // 3)
    k = ((n - abs(x - y)) // 2)
    print(c(n, k))


### FIXED CODE ###

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

MOD = 10**9 + 7


def combination(n: int, r: int, mod=MOD):
    n1 = n+1
    r = min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod


x, y = map(int, read().split())

if ((x + y) % 3 != 0):
    print("0")
else:
    a = (2*y - x) // 3
    b = (x - a) // 2

    if a < 0 or b < 0:
        print(0)
    else:
        print(combination(a+b, a))
#!/usr/bin/python3
# -*- coding: utf-8 -*-
def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)
def list_euclid(int_list):
    ans = int_list[0]
    for i in range(1,len(int_list)):
        ans = euclid(ans, int_list[i])
        if ans == 1:
            return ans
    return ans
n = int(input())
a = list(map(int, input().split()))
a.sort()
max = 0
b_int = 0
min = 1
if n < 5:
    for i in range(0,n):
        if b_int == a[0]:
            p = a.pop(0)
            # a.append(p)
        else:
            p = a.pop(0)
            b_int = p
            x = list_euclid(a)
        if max < x:
            max = x
            a.append(p)
else:
    for i in range(0,n):
        if b_int == a[0]:
            p = a.pop(0)
            # a.append(p)
        else:
            if max == 0:
                p = a.pop(0)
                b_int = p
                k = len(a) // 2
                x = 0
                y = list_euclid(a[0:k])
                if y == 1:
                    x = 1
                else:
                    z = list_euclid(a[k:len(a)])
                    x = euclid(y, z)
                if max < x:
                    max = x
                a.append(p)
                min = p
            elif min <= max:
                break
            else:
                p = a.pop(0)
                b_int = p
                k = len(a) // 2
                x = 0
                y = list_euclid(a[0:k])
                if y == 1:
                    x = 1
                else:
                    z = list_euclid(a[k:len(a)])
                    x = euclid(y, z)
                if max < x:
                    max = x
                a.append(p)
print(max)



### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
import sys
def gcd(a, b): #最大公約数
  while b:
    a, b = b, a % b
  return int(a)
    
n = int(input())
a = list(map(int, input().split()))
if n==2:
  print(max(a))
  sys.exit(0)
elif n==3:
  lis = [gcd(a[0], a[1]), gcd(a[1], a[2]), gcd(a[2], a[0])]
  print(max(lis))
  sys.exit(0)
tmp_unused = gcd(a[0], a[1])
tmp_used = max(a[0], a[1])
#print("used=", tmp_used, "unused=", tmp_unused)
for i in range(2,n):
  #print(a[i])
  tmp_used = max(tmp_unused, gcd(tmp_used, a[i]))
  tmp_unused = gcd(tmp_unused, a[i])
  
  #print("used=", tmp_used, "unused=", tmp_unused)
print(tmp_used)
a, b, c = (int(i) for i in input().split())  
integers = [a, b, c]
integers = [a, b, c].sort()
print(integers[2]*10+integers[1]+integers[0])

### FIXED CODE ###

a, b, c = (int(i) for i in input().split())  
integers = [a, b, c]
integers.sort()
print(integers[2]*10+integers[1]+integers[0])
a = "abcdefghijklmnopqrstuvwxyz"
while 1:
    try:
        b += input().lower()
    except:
        break
for i in range(26):
    print(a[i],':',b.count(a[i]))


### FIXED CODE ###

a = "abcdefghijklmnopqrstuvwxyz"
b = ''
while 1:
    try:
        b += input().lower()
    except:
        break
for i in range(26):
    print(a[i],':',b.count(a[i]))
a = []
for i in range(5):
  a.append(int(input()))
a.sort()
j = int(input)
k = a[4] - a[0]
if k <= j:
  print("Yay!")
else:
  print(":(")

### FIXED CODE ###

a = []
for i in range(5):
  a.append(int(input()))
a.sort()
j = int(input())
k = a[4] - a[0]
if k <= j:
  print("Yay!")
else:
  print(":(")
x = int(3)
x^3 = y
print ("y")



### FIXED CODE ###

x = int(input())
print (x ** 3)
n, m = map(int, input().split())

edges = [ [] for _ in range(n) ]

for _ in range(m):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

INF = 10 ** 6

def dijkstra_travel(edges):
    dists = [ INF  for _ in range(n) ]
    paths = [ None for _ in range(n) ]

    dists[0] = 0
    paths[0] = 0

    def travel_adjacent(n):
        adjacent_nodes = list(
            map(
                lambda node: (node, paths[node]),
                edges[n],
            )
        )

        next_travel = []

        for node, path in adjacent_nodes:
            if path is None or dists[node] > dists[n] + 1:
                dists[node] = dists[n] + 1
                paths[node] = n
                next_travel.append(node)

        for x in next_travel:
            travel_adjacent(x)

    travel_adjacent(0)

    return paths[1:]

result = dijkstra_travel(edges)

if all(map(lambda x: x is not None, result)):
    print('Yes')

    for x in result:
        print(x + 1)

else:
    print('No')

### FIXED CODE ###

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

edges = [ [] for _ in range(n) ]

for _ in range(m):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

INF = 10 ** 6

def dijkstra_travel(edges):
    dists = [ INF  for _ in range(n) ]
    paths = [ None for _ in range(n) ]

    dists[0] = 0
    paths[0] = 0

    next_travel = [ 0 ]

    def travel_adjacent():
        n = next_travel.pop(0)

        adjacent_nodes = list(
            map(
                lambda node: (node, paths[node]),
                edges[n],
            )
        )

        for node, path in adjacent_nodes:
            if path is None or dists[node] > dists[n] + 1:
                dists[node] = dists[n] + 1
                paths[node] = n
                next_travel.append(node)


    while len(next_travel) > 0:
        travel_adjacent()

    return paths[1:]

result = dijkstra_travel(edges)

if all(map(lambda x: x is not None, result)):
    print('Yes')

    for x in result:
        print(x + 1)

else:
    print('No')
while True:
    a = input().split()
    h=int(a)
    w=int(b)
    if h ==0 and w==0:
        break
    else:
        print(w*"#")
        if h>=3 and h>=3:
            for i in range(h-2):
                print(1*"#"+(w-2)*"."+1*"#")

            print(w * "#")
        elif h==2:
            print(w * "#")
        print(" ")

### FIXED CODE ###

while True:
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        break
    for i in range(a):
        if i == 0 or i == a-1:
            print("#" * b)
        else:print("#"+"."*(b-2)+"#")
    print("")
n=int(input())
a=list(map(int,input().split()))
m=int(input())
for i in range(m):
  p,x=map(int,input().split())
  print(sum(a)-a[p]+x)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
m=int(input())
for i in range(m):
  p,x=map(int,input().split())
  print(sum(a)-a[p-1]+x)
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import math as mt

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

    maxn = 0
    
    elif N >= B:
        maxn = mt.floor(A*(B-1)/B) - A*mt.floor((B-1)/B)
    else:
        maxn = mt.floor(A*N/B) - A*mt.floor(N/B)
    
    print(maxn)


if __name__ == '__main__':
    main()

### FIXED CODE ###

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

import math as mt

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

    maxn = 0
    
    if N >= B:
        maxn = mt.floor(A*(B-1)/B) - A*mt.floor((B-1)/B)
    else:
        maxn = mt.floor(A*N/B) - A*mt.floor(N/B)
    
    print(maxn)


if __name__ == '__main__':
    main()
n = int(input())
a = list(map(int,input().split()))
inf = 1e14
dp_table = [inf for i in range(n)]
dp_table[0] = 0
dp_table[1] = abs(a[0] - a[1])
for i in range(2,len(a)):
    dp_table[i] = min(dp_table[i-2]+abs(a[i-2]-a[i]),dp_table[i-1]+abs(a[i-1]-a[i]))
    print(dp_table)
print(dp_table[-1])


### FIXED CODE ###

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

dp_table = [0 for i in range(n)]
dp_table[1] = abs(a[0] - a[1])
for i in range(2,len(a)):
    dp_table[i] = min(dp_table[i-2]+abs(a[i-2]-a[i]),dp_table[i-1]+abs(a[i-1]-a[i]))
print(dp_table[-1])
a,b,c=map(input().split())

print(a[0]+b[1]+c[2])

### FIXED CODE ###

a=input()
b=input()
c=input()

print(a[0]+b[1]+c[2])
n,k=map(int,input().split())
s=input()
s[k-1]=s[k-1].lower()
print("".join(s))


### FIXED CODE ###

n,k=map(int,input().split())
s=list(input())
s[k-1]=s[k-1].lower()
print("".join(s))
import itertools
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
p=list(map(int,input().split()))
sss=0
for c in itertools.product([0,1],n):
  for i in range(m):
    cnt=0
    for j in range(l[i][0]):
      if c[l[i][j+1]-1]==1:
        cnt+=1
    if cnt%2==p[i]:
      ans+=1
  if ans==m:
    sss+=1
print(sss)

### FIXED CODE ###

import itertools
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
p=list(map(int,input().split()))
sss=0
for c in itertools.product([0,1],repeat=n):
  ans=0
  for i in range(m):
    cnt=0
    for j in range(l[i][0]):
      if c[l[i][j+1]-1]==1:
        cnt+=1
    if cnt%2==p[i]:
      ans+=1
  if ans==m:
    sss+=1
print(sss)
N, K = map(int, input().split())
S = str()
if(S[K-1] = 'A'):
  S[K-1] = 'a'
elif(S[K-1] = 'B'):
  S[K-1] = 'b'
elif(S[K-1] = 'C'):
  S[K-1] = 'c'

### FIXED CODE ###

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

           
if(S[K-1] == "A"):
  S[K-1] = "a"
elif(S[K-1] == "B"):
  S[K-1] = "b"
elif(S[K-1] == "C"):
  S[K-1] = "c"
           
"".join(S)

S_1 = S[0]
for i in range(1,N):
  S_1 = S_1 + S[i]
print(S_1)
N=int(input())
list_A=[int(A) for A in input().split()]
list_A.insert(0,0)
list_A.insert(N+1,0)
money=0
for i in range(N+1):
  money+=abs(list_A[i+1]-list_B[i])
for i in range(1,N+1):
  Money=money-abs(list_A[i]-list_A[i-1])-abs(list_A[i+1]-list_A[i])+abs(list_A[i+1]-list_A[i-1])
  print(Money)
    

### FIXED CODE ###

N=int(input())
list_A=[int(A) for A in input().split()]
list_A.insert(0,0)
list_A.insert(N+1,0)
money=0
for i in range(N+1):
  money+=abs(list_A[i+1]-list_A[i])
for i in range(1,N+1):
  Money=money-abs(list_A[i]-list_A[i-1])-abs(list_A[i+1]-list_A[i])+abs(list_A[i+1]-list_A[i-1])
  print(Money)
import sys
input = sys.stdin.readlineN,M = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(M)]
 
root = list(range(N+1))
comp_size = [1] * (N+1)
 
def find_root(x):
  y = root[x]
  if x == y:
    return x
  z = find_root(y)
  root[x] = z
  return z
 
def merge(x,y):
  rx = find_root(x)
  ry = find_root(y)
  if rx == ry:
    return 0
  sx = comp_size[rx]
  sy = comp_size[ry]
  if sx > sy:
    root[ry] = rx
    comp_size[rx] += sy
  else:
    root[rx] = ry
    comp_size[ry] += sx
  return sx * sy
 
answer = []
x = N*(N-1)//2
for a,b in AB[::-1]:
  answer.append(x)
  x -= merge(a,b)
 
for a in answer[::-1]:
  print(a)
import sys
input = sys.stdin.readline

# 逆再生
# 連結成分がくっつくときに加点

N,M = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(M)]

root = list(range(N+1))
comp_size = [1] * (N+1)

def find_root(x):
  y = root[x]
  if x == y:
    return x
  z = find_root(y)
  root[x] = z
  return z

def merge(x,y):
  rx = find_root(x)
  ry = find_root(y)
  if rx == ry:
    return 0
  sx = comp_size[rx]
  sy = comp_size[ry]
  if sx > sy:
    root[ry] = rx
    comp_size[rx] += sy
  else:
    root[rx] = ry
    comp_size[ry] += sx
  return sx * sy

answer = []
x = N*(N-1)//2
for a,b in AB[::-1]:
  answer.append(x)
  x -= merge(a,b)
for a in answer[::-1]:
  print(a)

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
N,M = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(M)]
 
root = list(range(N+1))
comp_size = [1] * (N+1)
 
def find_root(x):
  y = root[x]
  if x == y:
    return x
  z = find_root(y)
  root[x] = z
  return z
 
def merge(x,y):
  rx = find_root(x)
  ry = find_root(y)
  if rx == ry:
    return 0
  sx = comp_size[rx]
  sy = comp_size[ry]
  if sx > sy:
    root[ry] = rx
    comp_size[rx] += sy
  else:
    root[rx] = ry
    comp_size[ry] += sx
  return sx * sy
 
answer = []
x = N*(N-1)//2
for a,b in AB[::-1]:
  answer.append(x)
  x -= merge(a,b)
for a in answer[::-1]:
  print(a)
import math

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

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

### FIXED CODE ###


def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

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

a,b = map(int,input().split())
print(lcm(a, b))
# ARC 77 D
MOD = 10**9 + 7
n = int(input())
A = list(map(int, input().split()))

fact = {i: None for i in range(n+1)}                 # n!
inverse = {i: None for i in range(1, n+1)}       # inverse of n in the field Z/(MOD)Z
fact_inverse = {i: None for i in range(n+1)}  # inverse of n! in the field Z/(MOD)Z

fact[0] = fact[1] = 1
fact_inverse[0] = fact_inverse[1] = 1
inverse[1] = 1
for i in range(2, n+1):
    fact[i] = i * fact[i-1] % MOD
    inverse[i] = - inverse[MOD % i] * (MOD // i) % MOD
    fact_inverse[i] = inverse[i] * fact_inverse[i-1] % MOD

def combination(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    else:
        return fact[n] * (fact_inverse[r] * fact_inverse[n-r] % MOD) % MOD

dup_num = sum(A) - n*(n+1)//2
dup_idx = []
for i, a in enumerate(A):
    if a == dup_num:
        dup_idx.append(i)
        
left, right = dup_idx[0], dup_idx[1]
        
for k in range(1, n+2):
    print((combination(n+1, k) - combination(n + 1 - (right - left + 1), k - 1)) % MOD)

### FIXED CODE ###

MOD = 10**9 + 7
n = int(input())
A = list(map(int, input().split()))

fact = {i: None for i in range(n+2)}                 # n!
inverse = {i: None for i in range(1, n+2)}       # inverse of n in the field Z/(MOD)Z
fact_inverse = {i: None for i in range(n+2)}  # inverse of n! in the field Z/(MOD)Z

fact[0] = fact[1] = 1
fact_inverse[0] = fact_inverse[1] = 1
inverse[1] = 1
for i in range(2, n+2):
    fact[i] = i * fact[i-1] % MOD
    inverse[i] = - inverse[MOD % i] * (MOD // i) % MOD
    fact_inverse[i] = inverse[i] * fact_inverse[i-1] % MOD

def combination(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    else:
        return fact[n] * (fact_inverse[r] * fact_inverse[n-r] % MOD) % MOD

dup_num = sum(A) - n*(n+1)//2
dup_idx = []
for i, a in enumerate(A):
    if a == dup_num:
        dup_idx.append(i)
        
left, right = dup_idx[0], dup_idx[1]
        
for k in range(1, n+2):
    print((combination(n+1, k) - combination(n + 1 - (right - left + 1), k - 1)) % MOD)
n,m=map(int,input().split())
food=[0 for i in range(m)]
for i in range(n):
  per=list(map(int,input().split()))
  for j in range(1,per[0]+1):
    food[per[j]]+=1
ans=0
for i in range(m):
  if food[i] == n:
    ans+=1
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
food=[0 for i in range(m)]
for i in range(n):
  per=list(map(int,input().split()))
  for j in range(1,per[0]+1):
    food[per[j]-1]+=1
ans=0
for i in range(m):
  if food[i] == n:
    ans+=1
print(ans)
n = int(input())
inp = map(int,input().split())
inp.reverse()
for i in range(n-1):
	print(inp[i]," ",sep="",end="")
print(inp[n-1])

### FIXED CODE ###

n = int(input())
inp = list(map(int,input().split()))
inp.reverse()
for i in range(n-1):
	print(inp[i]," ",sep="",end="")
print(inp[n-1])
a=[]
for i invrangr(6):
  a.append(int(input()))
if a[4]-a[0]>a[5]:
  print(":(")
else:
  print("Yay!")

### FIXED CODE ###

a=[]
for i in range(6):
  a.append(int(input()))
if a[4]-a[0]>a[5]:
  print(":(")
else:
  print("Yay!")
import math
a = [int(input()) for i in range(5)]
sum = 0
r =[]
for i in range(5):
  if a[i] % 10 =0:
    sum+=a[i]
  elif a[i] % 10 !=0:
    r.append(a[i]%10)
    sum+= (math.ceil(a[i]/10)*10)
print(sum-10+min(r))

### FIXED CODE ###

import math
a = []
for i in range(5):
    a.append(int(input()))
sum = 0
r =10
for i in range(5):
  if a[i] % 10 ==0:
    sum+=a[i]
  elif a[i] % 10 !=0:
    r = min(r,a[i]%10)
    sum+= (10*math.ceil(a[i]/10))
print(sum-10+r)
from math import factorial,sqrt,ceil,gcd
# from itertools import permutations as permus
# from collections import deque,Counter
# import re
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# import networkx as nx
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb

# slist = "abcdefghijklmnopqrstuvwxyz"
N,K = map(int,input().split())
arrA = list(map(int,input().split()))
ans = ceil((N-1)/(K-1))
print(ans)
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))


### FIXED CODE ###

from math import factorial,sqrt,ceil #,gcd
# from itertools import permutations as permus
# from collections import deque,Counter
# import re
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# import networkx as nx
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb

# slist = "abcdefghijklmnopqrstuvwxyz"
N,K = map(int,input().split())
arrA = list(map(int,input().split()))
ans = ceil((N-1)/(K-1))
print(ans)
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))
import sys
sys.setrecursionlimit(100002)
input=sys.stdin.readline
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(m):
    max(a)//=2
print(sum(a))


### FIXED CODE ###

import sys
import heapq
sys.setrecursionlimit(100002)
input=sys.stdin.readline
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
  a[i]=-a[i]
heapq.heapify(a)
for i in range(m):
  heapq.heappushpop(a,-(-a[0]//2))
print(-sum(a))
A,B=int(input().split())

if A+B < 10:
  print(A+B)
else:
  print("error")

### FIXED CODE ###

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

if A+B < 10:
  print(A+B)
else:
  print("error")
s = input()
t = input()

s_sort = sorted(s,reverse=True)
t_sort = sorted(t,reverse= True)

if s_sort < t_sort:
    print('Yes')
else:
    print('No

### FIXED CODE ###

s = input()
t = input()

s_sort = sorted(s)
t_sort = sorted(t,reverse= True)

if s_sort < t_sort:
    print('Yes')
else:
    print('No')
#n = a の本:m = b の本
n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
p = 0
i = 0
j = 0
while p < k:
    if a[i] < b[j]:
        p += 1
        i += 1
    elif a[i] > b[j]:
        p += 1
        j += 1
    else:
        if a[i+1] < b[j+1]:
            p += 1
            i += 1
        else:
            p += 1
            j += 1

print(p)

### FIXED CODE ###

n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = [0]*(n+1)
d = [0]*(m+1)
for i in range(n):
    c[i+1] = a[i]+c[i]
for i in range(m):
    d[i+1] = b[i]+d[i]
for i in range(m+1)[::-1]:
    if d[i] <= k:
        x = i
        break
ans = x
for i in range(1,n+1):
    while c[i] + d[x] > k:
        if x >= 1:
            x -= 1
        else:
            break
    if c[i] + d[x] <= k:
        ans = max(ans,i+x)
print(ans)