Harryxun/stf_run huggingface dataset:
N, M = map(int, input().split())
S = input()

steps = [[] for i in range(N)]
steps[0] = [0]
num_steps = 0
root = [0] + [-1]*N
pos = 1

while pos <= N:
  starts = steps[num_steps]
  if not starts:
    ans = -1
    break
  for start in starts:
    end = min(start+M+1, N+1)
    for i in range(pos, end):
      if S[i] == '0':
        steps[num_steps+1].append(i)
        root[i] = start
    
    pos = end
  
  num_steps += 1


if pos == N+1:
  pos = N
  ans = []
  while pos > 0:
    pre_pos = root[pos]
    ans.append(str(pos - pre_pos))
    pos = pre_pos
  
  ans = ans[::-1]
  ans = ' '.join(ans)


print(ans)

### FIXED CODE ###

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

steps = [[] for i in range(N+1)]
steps[0] = [0]
num_steps = 0
root = [0] + [-1]*N
pos = 1

while pos <= N:
  starts = steps[num_steps]
  if not starts:
    break
  for start in starts:
    end = min(start+M+1, N+1)
    for i in range(pos, end):
      if S[i] == '0':
        steps[num_steps+1].append(i)
        root[i] = start
    
    pos = end
  
  num_steps += 1


if root[N] == -1:
  ans = -1
else:
  pos = N
  ans = []
  while pos > 0:
    pre_pos = root[pos]
    ans.append(str(pos - pre_pos))
    pos = pre_pos
  
  ans = ans[::-1]
  ans = ' '.join(ans)


print(ans)
x,y=map(int,input().split())
a=0
b=0
if y == 2*x or y == 4*x:
  print("Yes")
else:
  count=0
  for i in range(0,x):
    for j in range(0,x):
      if (i+j)==x:
        if 2*i + 4 * j == y:
          count=1     
if count==0:
  print("No")
else:
  print("Yes")

### FIXED CODE ###

x,y=map(int,input().split())
count=0
if y == 2*x or y == 4*x:
    count=1
else:
  for i in range(x):
    for j in range(x):
      if (i+j)==x:
        if (2*i) + (4 * j) == y:
          count+=1     
if count<1:
  print("No")
else:
  print("Yes")
from math import gcd


def solve(n, ax):
    lcm = 1
    for ai in ax:
        lcm = lcm*ai//gcd(lcm, ai)
    m=lcm-1
    return sum(list(map(lambda x: (lcm-1)%x, ax)))


if __name__ == '__main__':
    n = int(input())
    ax = list(map(int, input().split()))
    print(solve(n, ax))


### FIXED CODE ###

from fractions import gcd


def solve(n, ax):
    lcm = 1
    for ai in ax:
        lcm = lcm*ai//gcd(lcm, ai)
    m = lcm-1
    return sum(list(map(lambda x: m % x, ax)))


if __name__ == '__main__':
    n = int(input())
    ax = list(map(int, input().split()))
    print(solve(n, ax))
import sys
import math
for line in sys.stdin:
        a =map(int,raw_input().split())
        b = a[0] + a[1]
        print int(math.log10(b)+1)

### FIXED CODE ###

import math
while True:
        try:
                a =map(int,raw_input().split())
                b = a[0] + a[1]
                print len(str(a[0]+a[1]))
        except EOFError:
                break
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
L = set([int(input()) - 1 for _ in range(M)])
ans = [0] * N

if 0 not in L:
    ans[0] = 1
    
if 1 not in L:
    ans[1] = ans[0] + 1

for i in range(2, N):
    if i in L:
        continue
    
    if ans[i - 2] != 0 or ans[i - 1] != 0:
        ans[i] = ans[i - 2] + ans[i - 1]
        
print(ans[-1] % (1000000007))

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
L = set([int(input()) - 1 for _ in range(M)])
ans = [0] * N

if 0 not in L:
    ans[0] = 1
    
if N > 1 and 1 not in L:
    ans[1] = ans[0] + 1

for i in range(2, N):
    if i in L:
        continue
    
    if ans[i - 2] != 0 or ans[i - 1] != 0:
        ans[i] = ans[i - 2] + ans[i - 1]
        
print(ans[-1] % (1000000007))
def method(input()):
    l = input().split(' ')
    square = int(l[0]) * int(l[1])
    length = 2 * int(l[0]) + 2* int(l[1])
    print(square length)

method(input(3 5))


### FIXED CODE ###

string = input()
a,b = map(int,string.split(' '))
print(a*b, 2*(a+b))
n = int(input())
l = map(int, input().split())
 
print (n)
print (l[::-1])

### FIXED CODE ###

input()
xs=reversed(input().split())
print(" ".join(xs))
import math

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

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

yaku_b = b - (b // c + b // d - b // lcm(c,d))
yaku_a = a-1 - ((a-1) // c + (a-1) // d - (a-1) // lcm(c,d))
print(yaku_b - yaku_a)

### FIXED CODE ###

from fractions import gcd
 
def lcm(x, y):
    return (x * y) // gcd(x, y)
 
a, b, c, d = map(int, input().split())
 
yaku_b = b - (b // c + b // d - b // lcm(c,d))
yaku_a = a-1 - ((a-1) // c + (a-1) // d - (a-1) // lcm(c,d))
print(yaku_b - yaku_a)
n = int(input())
l = list(map(int, input().split())) 
l2 =[]
i = len(l)
for i in range(len(l):
  if l[i] > l[i-1]:
    l[i] += 1
    i += 1

i = 0
l2 = [l[i] <= l[i+1] for i in range(len(l)-1)]

if all(l2):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

from sys import stdin
a, b, c = [int(x) for x in stdin.readline().rstrip().split()]

l = c - (a - b)

if l < 0:
  print(0)
else:
  print(l)
n = int(input())
r = int(input())

if n >= 10:
  print(r)
else:
  print(r+100*(10-n))

### FIXED CODE ###

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

if n >= 10:
  print(r)
else:
  print(r+100*(10-n))
from _collections import deque
N, M = map(int, input().split())
graph = [[] for _ in range(M)]
for i in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    graph[a].append(b)
    graph[b].append(a)
#print(graph)

queue = deque()
seen = [-1] * N
steps = [-1] * N
steps[0] = 0
parents = [-1] * N
queue.append(0)
while queue:
    node = queue.popleft()

    seen[node] = 1
    #print("now: "+str(node))
    for next in graph[node]:
        if seen[next] > -1:
            continue
        #print("next: " + str(next))
        queue.append(next)
        seen[next] = 1
        steps[next] = steps[node] + 1
        parents[next] = node

for a in parents[1:]:
    print(a+1)

### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for i in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    graph[a].append(b)
    graph[b].append(a)
#print(graph)

queue = deque()
seen = [-1] * N
steps = [-1] * N
steps[0] = 0
parents = [-1] * N
queue.append(0)
while queue:
    node = queue.popleft()

    seen[node] = 1
    #print("now: "+str(node))
    for next in graph[node]:
        if seen[next] > -1:
            continue
        #print("next: " + str(next))
        queue.append(next)
        seen[next] = 1
        steps[next] = steps[node] + 1
        parents[next] = node

print("Yes")
for a in parents[1:]:
    print(a+1)
def gcd(a,b):
  while b:
    a,b=b,a%b
  return a

def lcm(a,b):
  return a * b // gcd(a,b)

e=lcm(c,d)
a,b,c,d=map(int,input().split())
print((b-a+1)-(b//c-a//c)-(b//d-a//d)+(b//e-a//e))

### FIXED CODE ###

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

def lcm(a,b):
	return a * b // gcd (a, b)

a,b,c,d=map(int,input().split())
e=lcm(c,d)

cc=(b//c)-((a-1)//c)
dd=(b//d)-((a-1)//d)
cd=(b//e)-((a-1)//e)
print((b-a+1)-(cc+dd-cd))
n=int(input())
v=list(map(int,input().split()))
a=v[0::2]
b=v[1::2]
c=dict()
d=dict()

for i in a:
  if i in c:
    c[i]+=1
  else:
    c[i]=1
for j in d:
  if j in d:
    d[j]+=1
  else:
    d[j]=1

e=sorted([[c,v] for v,c in c.items()],reverse=True)
f=sorted([[c,v] for v,c in d.items()],reverse=True)

if e[0][1]!=f[0][1]:
  print(n-e[0][0]-f[0][0])
elif e[0][0]>f[0][0]:
  print(n-e[0][0]-f[1][0])
else:
  print(n-e[1][0]-f[0][0])

### FIXED CODE ###

from collections import defaultdict
n = int(input())
A = [int(x) for x in input().split()]
even = A[0::2]
odd = A[1::2]
EC = defaultdict(int)
EC[0] = 0
OC = defaultdict(int)
OC[0] = 0
for e in even:
  EC[e] += 1
for o in odd:
  OC[o] += 1
E = sorted([[v, k] for k, v in EC.items()], reverse=True)
O = sorted([[v, k] for k, v in OC.items()], reverse=True)
if E[0][1] != O[0][1]:
  print(n - E[0][0] - O[0][0])
elif E[1][0] >= O[1][0]:
  print(n - E[1][0] - O[0][0])
else:
  print(n - E[0][0] - O[1][0])

#sample code.
n = innput()
 
if "7" in n:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n = str(input())
m = "7"
if m in n:
  print("Yes")
else:
  print("No")
from bisect import bisect_left, bisect, insort

def dfs(v, p):
    i = bisect_left(dp, a[v])
    dp[i], old = a[v], dp[i]
    ans[v] = i
    if p != -1:
        ans[v] = max(ans[v], ans[p])
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)
    dp[i] = old

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    to = [[] for _ in range(n)]
    ans = [None]*n
    INF = 10**10
    for _ in range(n-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        to[u].append(v)
        to[v].append(u)
    dp = [INF]*n
    dp[0] = -INF
    dfs(0, -1)
    print("\n".join(list(map(str, ans))))

### FIXED CODE ###

from bisect import bisect_left
import sys
sys.setrecursionlimit(1000000)


def dfs(v, p):
    i = bisect_left(dp, a[v])
    dp[i], old = a[v], dp[i]
    ans[v] = bisect_left(dp, INF)-1
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)
    dp[i] = old

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    to = [[] for _ in range(n)]
    ans = [0]*n
    INF = 10**20
    for _ in range(n-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        to[u].append(v)
        to[v].append(u)
    dp = [INF]*(n+1)
    dp[0] = -INF
    dfs(0, -1)
    print("\n".join(list(map(str, ans))))
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
count = 0
for i in range(N-1):
    if A[i] <= A[i+2] : count += 1
if count > N * 0.8 : print(1)
ans = []
mini = min(A[0:L])
ans.append(mini)
for i in range(1,N-L+1) :
    if A[i+L-1] <= mini :
        mini = A[i+L-1]
    elif A[i-1] == mini :
        mini = min(A[i:i+L])
    ans.append(mini)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
s = input()
k = int(input())

if s[0] != "1":
  print(s[0])
elif s[1] != "1":
  print(s[1])
elif s[2] != "1":
  print(s[2])
elif s[3] != "1":
  print(s[3])

### FIXED CODE ###

s = input()
k = int(input())

for i in range(k):
  if s[i] != "1":
    print(s[i])
    exit()
print("1")
import math

def cal(n, i):
    numerator = math.factorial(n)
    denominator = math.factorial(i)*math.factorial(n-i)

    return numerator / denominator

N, K = map(int, input().split())
for i in range(1, K+1):
    if i > N-K+1:
        print(0)
    else:
        ans = cal(N-K+1, i)
        ans *= cal(K-1, i-1) % 1000000007
        print(int(ans))

### FIXED CODE ###

def cal(n, i):
    numerator = 1
    denominator = 1
    for j in range(1, i+1):
        numerator *= (n-j+1) 
        denominator *= j
    x = numerator // denominator
    return x

N, K = map(int, input().split())
for i in range(1, K+1):
    if i > N-K+1:
        print(0)
    else:
        ans = cal(N-K+1, i)
        ans *= cal(K-1, i-1)
        ans = ans % 1000000007
        print(int(ans))
x=int(input())
a=int(str(x)[-2:])
b=int(str(x)[:-2])
counter=0
while a>=5:
	a-=5
	counter+=1
while a>=4:
	a-=4
	counter+=1
while a>=3:
	a-=3
	counter+=1
while a>=2:
	a-=2
	counter+=1
while a>=1:
	a-=1
	counter+=1
print(1 if counter<b else 0)


### FIXED CODE ###

x=int(input())
if x<100:
	print(0)
elif x>=100:
	a=int(str(x)[-2:])
	b=int(str(x)[:-2])
	counter=0
	while a>=5:
		a-=5
		counter+=1
	while a>=4:
		a-=4
		counter+=1
	while a>=3:
		a-=3
		counter+=1
	while a>=2:
		a-=2
		counter+=1
	while a>=1:
		a-=1
		counter+=1
	print(1 if counter<=b else 0)
a = int(input())
b = int(input())
x = int(input())

if a <= x <= a + b:
    print("YES")
else:
    print("NO")


### FIXED CODE ###

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

if a <= x <= a + b:
    print("YES")
else:
    print("NO")
N=int(input())
cnt=0
ans=0
max=0
while cnt<N:
  cnt++
  p=int(input())
  ans += p
  if p>max:
    max=p
ans-=(max/2)
print(ans)

### FIXED CODE ###

N=int(input())
cnt=0
ans=0
max=0
while cnt<N:
  cnt+=1
  p=int(input())
  ans += p
  if p>max:
    max=p
ans-=int(max/2)
print(ans)
def find_7(num):
	num_list = list(map(int, str(num)))
	count = 0
	for x in num_list:
		count += 1
		if x == 7:
			return "Yes"
		elif count == len(num_list):
			return "No"

if __name__ == '__main__':
	print (find_7())

### FIXED CODE ###

num = input()

for x in num:
	if x == '7':
		print ("Yes")
		exit()

print ("No")
""" AtCoder """

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

print((a + b) * h / 2)


### FIXED CODE ###

""" AtCoder """

a = int(input())
b = int(input())
h = int(input())

print(int((a + b) * h / 2))
N=int(input())
graph=[[] for _ in range(N)]
for i in range(N-1):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    graph[a].append([b,c])
    graph[b].append([a,c])

def dfs(start):
    for x,cost in graph[start]:
        if d[x]==-1:
            d[x]=d[start]+cost
            dfs(x)

Q,K=map(int,input().split())
K-=1
d=[-1]*N
d[K]=0
dfs(K)
for i in range(Q):
    x,y=map(int,input().split())
    x-=1
    y-=1
    print(d[x]+d[y])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

N=int(input())
graph=[[] for _ in range(N)]
for i in range(N-1):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    graph[a].append([b,c])
    graph[b].append([a,c])

def dfs(start):
    for x,cost in graph[start]:
        if d[x]==-1:
            d[x]=d[start]+cost
            dfs(x)

Q,K=map(int,input().split())
K-=1
d=[-1]*N
d[K]=0
dfs(K)
for i in range(Q):
    x,y=map(int,input().split())
    x-=1
    y-=1
    print(d[x]+d[y])
N = int(input())
H = [int(s) for s in input().split()]
for i in range(N - 1):
    if H[i + 1] - H[i] >= 0:
        H[i + 1] -= H[i + 1] != H[i]
    else:
        print('No')
        exit()

print('Yes')


### FIXED CODE ###

N = int(input())
count = 0
for i in range(1,N+1):
  s = str(i)
  if len(s) % 2 == 1:
    count+=1
    
print(count)
import pandas as pd

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

t = []
for i in H:
    t.append(abs(A - (T - i*0.006)))

print(pd.Series(t).idxmin()+1)

### FIXED CODE ###

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

t = [abs(A - (T - i*0.006)) for i in H]
print(t.index(min(t))+1)
a,b,c,d=map(int,input().split())
ans=0
for x in range(n//r):
    for y in range(n//g):
        if (d-x*a+y*b)//c==0:
            ans+=1
print(ans)

### FIXED CODE ###

a,b=map(int,input().split())
print(a-(b-1))
_ = int(input())
nums = list(map(int, input().split())
max_n = 0
min_n = 0
for i in nums:
	if max_n < i:
        max_n = i
    if min_n > i:
        min_n =i
print(max_n - min_n)
    

### FIXED CODE ###

_ = int(input())
nums = list(map(int, input().split()))
max_n = 0
min_n = 100000000000000000000000
for i in nums:
	if max_n < i:
		max_n = i
	if min_n > i:
		min_n =i
print(max_n - min_n)
n = int(input())
cnt = 0
ans = 0

for i in range(105, n + 1, 2):
    for j in range(1, n + 1):
        if i%j == 0:
            cnt += 1
    if cnt == 8:
        ans += 1
    cnt = 0
print(ans

### FIXED CODE ###

n = int(input())
cnt = 0
ans = 0

for i in range(105, n + 1, 2):
    for j in range(1, n + 1):
        if i%j == 0:
            cnt += 1
    if cnt == 8:
        ans += 1
    cnt = 0
print(ans)
n,k,q=map(int,input().split())
a=list(map(int,input().split()))
ans=10**10
for y in a:
	t=[[]]
	for i in a:
		if i<y:
			if len(t[-1]):t.append([])
		else:
			t[-1].append(i)
	if len(t[-1])==0:del t[-1]
	co=0
	m=[]
	for i in range(len(t)):
		co+=max(len(t[i])-k+1,0)
		t[i].sort()
		m+=t[i][:-k+1]
	if co<q:continue
	m.sort()
	ans=min(ans,m[q-1]-y)
print(ans)

### FIXED CODE ###

n,k,q=map(int,input().split())
a=list(map(int,input().split()))
ans=10**10
for x in a:
  b=[[]]
  can=0
  for i in a:
    if i<x:
      if len(b[-1]):b.append([])
    else:b[-1].append(i)
  if len(b[-1])==0:del b[-1]
  for i in range(len(b)):b[i].sort()
  c=[]
  for i in b:
    i.sort()
    if len(i)>=k:c+=i[:len(i)-k+1]
  if len(c)<q:continue
  c.sort()
  ans=min(ans,c[q-1]-c[0])
print(ans)
import sys

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

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():
    N = in_n()
    X = in_s()
    nx = int(X, 2)

    ans = [0] * N

    oc = X.count('1')
    mx = nx % (oc - 1)
    px = nx % (oc + 1)

    tn = 1 << N - 1
    for i in range(N):

        if X[i] == '0':
            a = (px + pow(2, N - i - 1, oc + 1)) % (oc + 1)
        else:
            if oc - 1 == 0:
                ans[i] = 0
                continue
            else:
                a = (mx - pow(2, N - i - 1, oc - 1)) % (oc - 1)

        count = 1
        while a:
            a = a % bin(a).count('1')
            count += 1

        ans[i] = count
        tn = tn >> 1

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

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


def main():
    N = int(readline())
    X = readline().rstrip().decode('utf-8')
    nx = int(X, 2)

    ans = [0] * N

    oc = X.count('1')

    if oc - 1 != 0:
        mx = nx % (oc - 1)
        f = True
    else:
        f = False

    px = nx % (oc + 1)

    for i in range(N):

        if X[i] == '0':
            a = (px + pow(2, N - i - 1, oc + 1)) % (oc + 1)
        elif f:
            a = (mx - pow(2, N - i - 1, oc - 1)) % (oc - 1)
        else:
            ans[i] = 0
            continue

        count = 1
        while a:
            a = a % bin(a).count('1')
            count += 1

        ans[i] = count

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()
#!/usr/bin/env python3
import sys
import math

MOD = 1000000007  # type: int

def solve(X: int, Y: int):
    a = (2*Y - X)/3
    b = (2*X - Y)/3
    if ((2*Y - X)%3 != 0) and ((2*X - Y)%3 != 0):
        ans = 0
    else:
        if (a<0) or (b<0):
            ans = 0
        else:
            factorial_ab = math.factorial(int(min(a, b)))
            ans = math.factorial(int(a+b)) / factorial_ab
    print(int(ans%MOD))

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    solve(X, Y)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys
import math

MOD = 10**9+7  # type: int

def combi_count(n, r):
    x = 1
    y = 1
    for i in range(1, r+1):
        x = x * (n-i) % MOD
        y = y * i % MOD

    # nCr = n!/((n-r)!*r!) = (n!/(n-r)!) / r! 
    #     :=                 (    x    ) / y

    # x / y            % MOD
    # x * y^(-1)       % MOD
    # x * y**(MOD - 2) % MOD (from フェルマー定理)

    return x * pow(y, MOD-2, MOD) % MOD

def solve(X: int, Y: int):
    a = int((2*Y - X)/3)
    b = int((2*X - Y)/3)
    if ( ((2*Y - X)%3 != 0) and ((2*X - Y)%3 != 0) )  or ((a<0) or (b<0)):
        ans = 0
    else:
        ans = combi_count(a+b+1, min(a, b))
    print(ans)

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    X, Y = map(int, input().split())
    solve(X, Y)

if __name__ == '__main__':
    main()
n = int(input())
s = input()
i = 0
while i < n - 1:
  
  while s[i + 1] and s[i] == s[i + 1]:
    s.pop(i + 1)
    n -= 1
  i += 1
print(n)


### FIXED CODE ###

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

ans = 1
current = s[0]
for i in range(n):
  if current != s[i]:
    ans += 1 
    current = s[i]
print(str(ans))
n, m = map(int, input().split())
aa = map(int, input().split())
thre = sum(aa) / (4*m)
cnt = 0
for a in aa:
  if a >= thre
  cnt  +=1
if cnt >= m:
  print('Yes')
else:
  print('No')


### FIXED CODE ###

n, m = map(int, input().split())
aa = list(map(int, input().split()))
thre = sum(aa) / (4*m)
cnt = 0
for a in aa:
  if a >= thre:
    cnt +=1
if cnt >= m:
  print('Yes')
else:
  print('No')
from math import gcd
from functools import reduce
from itertools import combinations

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

b = list(combinations(a, n-1))

gcd_a = [reduce(gcd, list(x)) for x in b]
print(max(gcd_a))


### FIXED CODE ###

from fractions import gcd
from functools import reduce

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

left = [0] * (n + 1)
right = [0] * (n + 1)
for i in range(n):
   left[i+1] = gcd(left[i], a[i])
   right[n-i-1] = gcd(right[n-i], a[n-1-i])

ans = 0
for i in range(n):
   ans = max(ans, gcd(left[i], right[i+1]))
print(ans)
n, k = map(int, input().split())
h_li = [int(input()) for i in range(n)]
a = max(h_li)-min(h_li)
dp = [[-1]*(a+5)]*100010



def dfs(i, choosed):
    if i == n:
        if len(choosed) != k:
            dif = 10000000010
        else:
            dif = max(choosed) - min(choosed)

    elif len(choosed) >= 2 and dp[len(choosed)][max(choosed)-min(choosed)] != -1:
        dif = dp[len(choosed)][max(choosed)-min(choosed)]
            
    elif len(choosed) == k:
        dif = max(choosed) - min(choosed)
    else:
        dif = min(
            dfs(i+1, choosed + [h_li[i]]),
            dfs(i+1, choosed)
        )

    return dif

print(dfs(0, []))

### FIXED CODE ###

n, k = map(int, input().split())
h = [int(input()) for i in range(n)]
h = sorted(h)
dif = 10**9

for i in range(n-k+1):
    if dif > h[i+k-1] - h[i]:
        dif = h[i+k-1] - h[i]

print(dif)