Harryxun/stf_run huggingface dataset:
def main(n,w,itemWeights,itemValues):
    m = 0
    for i in range(n):
        if itemValues[i] > itemValues[m]:
            m = i
    if w - itemWeights[m] < 0:
        return 0
    else if w - itemWeights[m] == 0:
        return itemValues[i]
    else:
        v = itemValues[m]
        itemWeights.pop(m)
        itemValues.pop(m)
        return v+main(n,w,itemWeights,itemValues)
    

inp1 = input().split()
n = inp1[0]
w = inp[1]
itemWeights = []
itemValues = []

for i in range(n)
    inp = input()
    itemWeights.append(int(inp[0]))
    itemValues.append(int(inp[1]))

print(main(n,w,itemWeights,itemValues))

### FIXED CODE ###

from collections import defaultdict

n, w = [int(x) for x in input().split()]
d = []
for _ in range(n):
    ww, nu = [int(x) for x in input().split()]
    d.append((ww, nu))

# dd[idx][ww] represents the maximum value that  we can get if total weight <= ww
# and allowed to use the first idx items.
dd = defaultdict(lambda: defaultdict(int))
for ww in range(w+1):
    dd[0][ww] = 0

for nn in range(n+1):
    dd[nn][0] = 0

for nn in range(1, n+1):
    www, nu = d[nn-1]
    for ww in range(1, w+1):
        # don't use item nn-1
        cur = dd[nn-1][ww]

        # use item nn-1
        if www <= ww:
            rem_ww = ww - www
            cand = dd[nn-1][rem_ww] + nu
            if cand > cur:
                cur = cand

        dd[nn][ww] = cur

print(dd[n][w])
import math
a,b,x=map(int,input().split())
cap=a**2*b
y=((cap-x)*2)/a**2

if y<=b:
      y=((cap-x)*2)/a**2
      theta=math.degrees(math.atan(y/a))
      print(ans)
else:
      y=(2*x)/(a*b)
      theta=math.degrees(math.atan(y/b))
      print(90-theta)

### FIXED CODE ###

import math
a,b,x=map(int,input().split())
cap=a**2*b
y=((cap-x)*2)/a**2

if y<=b:
      y=((cap-x)*2)/a**2
      theta=math.degrees(math.atan(y/a))
      print(theta)
else:
      y=(2*x)/(a*b)
      theta=math.degrees(math.atan(y/b))
      print(90-theta)
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

def binary_search(A, key):
left = 0
right = n
while left < right:
    mid = int((left + right)/2)
    if A[mid] == key:
        return True
    elif key < A[mid]:
        right = mid
    else:
        left = mid + 1 return False
cnt = 0
for i in T:
    if binary_search(S, i):
        cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
S = [int(s) for s in input().split()]
q = int(input())
T = [int(t) for t in input().split()]

def binary_search(A, key, n):
    left = 0
    right = n
    while left < right:
        mid = (left + right)//2
        if A[mid] == key:
            return True
        elif key < A[mid]:
            right = mid
        else:
            left = mid + 1
    return False

count = 0
for i in T:
    if binary_search(S, i, n):
        count += 1
print(count)
"""
問題文

N個の整数 A1,A2,...,ANが黒板に書かれています。
あなたはこの中から整数を 1つ選んで、1 以上 109以下の好きな整数に書き換えます。
元の整数と同じ整数に書き換えても構いません。書き換えた後のN個の整数の最大公約数の最大値を求めてください。

制約
入力は全て整数である。
2≤N≤105
1≤Ai≤109
"""

"""
3 5 7
最大公約数: 1
最大の最大公約数: 1

8 4 6
最大公約数: 2
最大の最大公約数: 4
『aとbとcの最大公約数』　＝　『aとbの最大公約数』と『c』　の最大公約数

A1 , A2 , A3 ... An

gcd(A1 , A2 , A3 ... An-1) * N
= gcd * N * N
= gcd * N^2

gcd(A1 , A2 , A3 ... An-1)
gcd(A1 , A2 , A3 ... An-2 , An) = gcd(A1 , A2 , A3 ... An-2) , An
"""
import math
from fractions import gcd  # for Ver.3.4 or lower.
from functools import reduce
gcd_map = {}
def GCD(numbers , startIndex , endIndex):
    if len(numbers) == 0 : return 0
    if len(numbers) == 1 : return numbers[0]
    if len(numbers) == 2 : return gcd_sub(numbers[0] , numbers[1])
    else : 
        set_index = (startIndex , endIndex)
        if set_index in gcd_map : 
            return gcd_map[set_index]
        value = GCD(numbers[1:] , startIndex + 1 , endIndex)
        gcd_map[set_index] = value
        return value

def gcd_sub(a , b) : 
    rst = gcd(a , b)
    return rst

def main() : 
    N = int(input())
    a_list = input().split(" ")
    a_list = [int(i) for i in a_list]
    maxValue = 0
    for i in reversed(range(N)) : 
        if i == 0 : 
            prev_list = a_list[1:]
            after_list = []
        elif i == N - 1 : 
            prev_list = []
            after_list = a_list[:N-1]
        else : 
            prev_list = a_list[0 : i ]
            after_list = a_list[i + 1 :] 
        rst = gcd(GCD(prev_list , 0 , i - 1) , GCD(after_list , i + 1 , N - 1))
        if maxValue < rst : maxValue = rst
    print(maxValue)
main()


### FIXED CODE ###

"""
問題文

N個の整数 A1,A2,...,ANが黒板に書かれています。
あなたはこの中から整数を 1つ選んで、1 以上 109以下の好きな整数に書き換えます。
元の整数と同じ整数に書き換えても構いません。書き換えた後のN個の整数の最大公約数の最大値を求めてください。

制約
入力は全て整数である。
2≤N≤105
1≤Ai≤109
"""

"""
3 5 7
最大公約数: 1
最大の最大公約数: 1

8 4 6
最大公約数: 2
最大の最大公約数: 4
『aとbとcの最大公約数』　＝　『aとbの最大公約数』と『c』　の最大公約数

A1 , A2 , A3 ... An

gcd(A1 , A2 , A3 ... An-1) * N
= gcd * N * N
= gcd * N^2

gcd(A1 , A2 , A3 ... An-1)
gcd(A1 , A2 , A3 ... An-2 , An) = gcd(A1 , A2 , A3 ... An-2) , An
"""
def gcd(a, b):  # a>b
    a, b = max(a, b), min(a, b)
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

from functools import reduce
def GCD(numbers):
    if len(numbers) == 0 : return 0
    if len(numbers) == 1 : return numbers[0]
    if len(numbers) == 2 : 
        return gcd(numbers[0] , numbers[1])
    else : 
        value = GCD(numbers[:len(numbers)-1])
        result = gcd(value , numbers[len(numbers) - 1])
        return result

def main() : 
    N = int(input())
    a_list = input().split(" ")
    a_list = [int(i) for i in a_list]
    R = [0 for i in range(N - 1)]
    L = [0 for i in range(N - 1)]
    R[0] = a_list[0]
    L[0] = a_list[-1]

    for i in range(1 , N-1) : 
        R[i] = gcd(R[i - 1] , a_list[i])
    
    for j in range(1 , N-1) : 
        L[j] = gcd(L[j - 1] , a_list[- j - 1])
    
    maxValue = 0
    for i in range(N - 2) : 
        value = gcd(R[i] , L[N - i - 3])
        if value > maxValue : maxValue = value
    print(max(maxValue , R[-1] , L[-1]))
main()
import sys                        
n = raw_input()
num = n.count('o')
print(700+(num*100))

### FIXED CODE ###

import sys                        
n = input()
num = n.count('o')
print(700+(num*100))
S = input()
T = input()

N = len(S)
M = len(T)

if N < M:
    print('UNRESTORABLE')
    exit()

ans = 'UNRESTORABLE'
for i in range(N-M,-1,-1):
    make = True
    for j in range(M):
        if S[i+j] == '?':
            continue
        if S[i+j] != T[j]:
            make = False
    if make:
        ans = list(S[:i] + T + S[i+M:])
        break

for i in range(N):
    if ans[i] == '?':
        ans[i] = 'a'
print(''.join(ans))


### FIXED CODE ###

S = list(input())
T = list(input())
lenS = len(S)
lenT = len(T)
change = 0
for i in range(lenS-lenT,-1,-1):
    a = 1
    for j in range(lenT):
        if S[i+j] != T[j] and S[i+j] != '?':
            a = 0
    if a == 1:
        for j in range(lenT):
            S[i+j] = T[j]
        change = 1
        break

for i in range(lenS):
    if S[i] == '?':
        S[i] = 'a'

if change == 1:
    print(''.join(S))
else:
    print('UNRESTORABLE')
import sys
 
c = 0
for line in sys.stdin:
	if int(line) == 0:
		break
    c+=1
    print 'Case %s: %s' %(c,line),

### FIXED CODE ###

import sys
 
c = 0
for line in sys.stdin:
	if line[0] == '0':
		break
	c+=1
	print 'Case %s: %s' %(c,line),
S = input()
N = len(S)
for i in range(N):
    if S[i] == 'A':
        a_index = i
        break
for i in range(N,-1,-1):
    if S[i] == 'Z':
        z_index = i
        break

print(N - z_index - a_index)


### FIXED CODE ###

S = input()
N = len(S)
for i in range(N):
    if S[i] == 'A':
        a_index = i
        break
S=S[::-1]
for i in range(N):
    if S[i] == 'Z':
        z_index = i
        break

print(N - z_index - a_index)
import math
A, B, C, D = map(int, input().split())

E = (C * D) // math.gcd(C, D)

c = B // C - (A - 1) // C 
d = B // D - (A - 1) // D 
e = B // E - (A - 1) // E
ans = B - A - c - d + e + 1
print(ans)

### FIXED CODE ###

import fractions
A, B, C, D = map(int, input().split())

E = (C * D) // fractions.gcd(C, D)

c = B // C - (A - 1) // C 
d = B // D - (A - 1) // D 
e = B // E - (A - 1) // E
ans = B - A - c - d + e + 1
print(ans)
A=int,input()
op=input()
B=int,input()
if op == '+':
    print(A+B)
else:
    print(A-B)

### FIXED CODE ###

A,op,B=map(str,input().split())
if op == '+':
    print(int(A)+int(B))
else:
    print(int(A)-int(B))
l = input()
mod = 10**9+7

def dfs(ni,t1,na):
    if ni == len(l):
        return (na+pow(2,t1,mod))%mod
    if l[ni] == "0":
        return dfs(ni+1,t1,na)
    else:
        na = (na+pow(2,t1,mod)*pow(3,len(l)-1-ni,mod)%mod)%mod
        return dfs(ni+1,t1+1,na)

ans=dfs(0,0,0)

print(ans)


### FIXED CODE ###

l = str(input())
ll = len(l)
mod = 10**9+7

ans = 0
t1 = 0
for i in range(ll):
    if l[i] == "0":
        continue
    ans = (ans+pow(2,t1,mod)*pow(3,ll-i-1,mod)%mod)%mod
    t1 += 1

ans = (ans+pow(2,t1,mod))%mod

print(ans)
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, A: "List[int]"):
    c = dict((0, 1))
    total = 0
    res = 0
    for a in A:
        total = (total + a) % M
        c[total] = c.get(total, 0) + 1
        res += c[total] - 1
    print(res)
    return


# Generated by 1.1.4 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()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, M, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, M: int, A: "List[int]"):
    c = dict()
    c[0] = 1
    total = 0
    res = 0
    for a in A:
        total = (total + a) % M
        if total in c:
            c[total] += 1
        else:
            c[total] = 1
        res += c[total] - 1
    print(res)
    return


# Generated by 1.1.4 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()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, M, A)

if __name__ == '__main__':
    main()
n = int(input())
a = int(input())
b = int(input())
ans = 0

for i in range(1, n+1):
    s = 0
    num = i
    while num > 0:
        s = s + num % 10
        num = num // 10
    if a <= s <= b:
        ans = ans + i
print(ans)


### FIXED CODE ###

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

for i in range(1, n+1):
    s = 0
    num = i
    while num > 0:
        s = s + num % 10
        num = num // 10
    if a <= s <= b:
        ans = ans + i
print(ans)
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
	int k;
	cin >> k;
    ans = 0
	
	for (int i = 1; i <= k; ++i) {
		for (int j = i; j <= k; j += i) {
			ans += i;
		}
	}
	cout << ans << '\n';
	
	return 0;
}


### FIXED CODE ###

N = int(input())
ans = 0
l = [0] * (10 ** 7 + 1)
for i in range(1, N + 1):
    for j in range(i, N + 1, i):
        l[j] += 1

for i in range(1, N + 1):
    ans += i * l[i]
print(ans)
A,B,K = int(input()).split()

if(A>K):
  A = A-K
else:
  if(B>K):
    A = 0
    B = B - K
  else:
    A = 0
    B = 0
    
print(A,B)

### FIXED CODE ###

A,B,K = map(int, input().split())
 
if A >= K:
  A = A-K
else:
  if B >= (K-A):
    B = B - (K-A)
    A = 0
  else:
    A = 0
    B = 0
    
print(A,B)
ABC = S
ARC = S

### FIXED CODE ###

S = input()

if S == "ABC":
  print("ARC")
else:
  print("ABC")
n=int(input())
A=sorted(map(int,input().split()))
ans=A[0]
for i in range(1,n):
  ans=(ans+A[i])/2
print(ans^(-1))


### FIXED CODE ###

n=int(input())
ans=0
A=list(map(int,input().split()))
for i in range(n):
  ans+=A[i]**(-1)
  
print(ans**(-1))
N = int(input())

ans = [0]*4
for n in range(n):
  C = input()
  if C = "AC":
    ans[0] += 1
  elif C = "WA":
    ans[1] += 1
  elif C = "TLE":
    ans[2] += 1
  elif C = "RE":
    ans[3] += 1

print("AC x ".format(ans[0]))
print("WA x ".format(ans[1]))
print("TLE x ".format(ans[2]))
print("RE x ".format(ans[3]))


### FIXED CODE ###

N = int(input())

ans = [0]*4
for n in range(N):
  C = input()
  if C == "AC":
    ans[0] += 1
  elif C == "WA":
    ans[1] += 1
  elif C == "TLE":
    ans[2] += 1
  elif C == "RE":
    ans[3] += 1

print("AC x {}".format(ans[0]))
print("WA x {}".format(ans[1]))
print("TLE x {}".format(ans[2]))
print("RE x {}".format(ans[3]))
n=int(input())
h=list(map(int,input().split()))
f=[0]*n
cnt=0
while 1:
    flag=0
    for i in range(n):
        if h[i]!=f[i]:
            f[i]+=1
            flag=1
        elif h[i]==f[i] and flag==1:
            cnt+=1
            flag=0
    if flag:==1
        cnt+=1

    if h == f:
        break

print(cnt)


### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
f=[0]*n
cnt=0
while 1:
    flag=0
    for i in range(n):
        if h[i]!=f[i]:
            f[i]+=1
            flag=1
        elif h[i]==f[i] and flag==1:
            cnt+=1
            flag=0
    if flag==1:
        cnt+=1

    if h==f:
        break

print(cnt)
import sys
a = map(int, input().split())

print(3*a*a)


### FIXED CODE ###

import sys
a = int(input())
print(3*a**2)
h,w=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(h)]
e=[]
flag=0
for i in range(h):
  if i%2:
    for j in range(w-1,-1,-1):
      if a[i][j]%2:
        flag=1
        break
  else:
    for j in range(w):
      if a[i][j]%2:
        flag=1
        break
  if flag:break
else:
  print(0)
  exit()
flag=0
y,x=i,j
while True:
  nx,ny=x,y
  if y%2:
    if x:nx=x-1
    else:ny=y+1
  else:
    if x<w-1:nx=x+1
    else:ny=y+1
  if a[y][x]%2:flag=1-flag
  if flag:e.append((y+1,x+1,ny+1,nx+1))
  if h%2:
    if (ny,nx)==(h-1,w-1):break
  else:
    if (ny,nx)==(h-1,0):break
  x,y=nx,ny
print(len(e))
for i in e:
  print(*i)

### FIXED CODE ###

h,w=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(h)]
ans=[]
for i in range(h):
  for j in range(w-1):
    if a[i][j]%2:
      a[i][j]-=1
      a[i][j+1]+=1
      ans+=[(i+1,j+1,i+1,j+2)]
for i in range(h-1):
  if a[i][w-1]%2:
    a[i][w-1]-=1
    a[i+1][w-1]+=1
    ans+=[(i+1,w,i+2,w)]
print(len(ans))
for i in ans:
  print(*i)
import sys

args = [int(input()) for i in range(6)]

 if (args[0] - arg[4]) > args[5]:
            print(":(")
            sys.exit()
print("Yay!")

### FIXED CODE ###

import sys

loops1 = 4
loops2 = 5
arg1 = 0
arg2 = 1

i=0
j=0

args = [int(input()) for i in range(6)]

for i in range(arg1,loops1):
	for j in range(arg2,loops2):
		if (args[j] - args[i]) > args[5]:
			print(":(")
			sys.exit()
print("Yay!")
r = input()
ptrint(r**2/1)

### FIXED CODE ###

r = int(input())
print(r**2)
if(int(input()) >= 30:
   print('Yes')
else:
   print('No')

### FIXED CODE ###

if(int(input())) >= 30:
   print('Yes')
else:
   print('No')
S = int(input())

W = int(input())

if W >= S/2:
  print("unsafe")
  
else:
  print("safe")

### FIXED CODE ###

s, w = map(int, input().split())

if w >= s:
  print("unsafe")
  
else:
  print("safe")
import sys

def S(n):
  return n / sum(map(int, str(n)))


def f(n):
  d = 0
  C = [n]
  while S(n) > (10**(d-1) / (9*d)):
    c = 10**(d+1) * (n // 10**(n+1) + 1) - 1
    C.append(c)
  
  Smin = float('inf')
  res = 0
  for c in C:
    if S(c) < Smin:
      res = c  
  return res
  
def main():
  input = sys.stdin.readline
  K = int(input())
  ans = 1
  while _ in range(K):
    print(ans)
    ans = f(ans+1)


if __name__ == '__main__':
  main()

### FIXED CODE ###

import sys

def S(n):
  return n / sum(map(int, str(n)))


def f(n):
  d = 0
  C = [n]
  while S(n) > (10**d / 9*(d+1)):
    c = 10**(d+1) * (n // 10**(d+1) + 1) - 1
    C.append(c)
    d += 1
  Smin = float('inf')
  res = 0
  for c in C:
    if S(c) < Smin:
      Smin = S(c)
      res = c  
  return res


def main():
  input = sys.stdin.readline
  K = int(input())
  ans = 1
  for _ in range(K):
    print(ans)
    ans = f(ans+1)


if __name__ == '__main__':
  main()
import sys
input = sys.stdin.readline
n = int(input())
a = [int(input()) for i in range(n)]
b = [0]*n
for i in range(n):
  if a[i]%2:
    b[i] = 1
  elif a[i]:
    b[i] = 2
DP = [[0 for i in range(5)] for j in range(n+1)]
for i in range(1,n+1):
  for j in range(5):
    for k in range(j,5):
      if k == 0 or k == 4:
        DP[i][k] = DP[i-1][j]+a[i-1]
      elif k == 1 or k == 3:
        DP[i][k] = DP[i-1][j]+abs(b[i-1]-2)
      else:
        DP[i][k] = DP[i-1][j]+abs(b[i-1]-1)
print(min(DP[n]))


### FIXED CODE ###

n,k=map(int,input().split())
if (n+1)//2>=k:
  print("YES")
else:
  print("NO")
N = int(input())
S = input()

ans = 0
for i in range(N):
    ans = max(ans,len(set(s[:i]) & set(s[i:])))
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
ans = 0
for i in range(N):
    ans = max(ans,len(set(S[:i]) & set(S[i:])))
print(ans)
N = int(input())
a = []
for _ in [0]*N:
    a.append(int(input()))

def solve(i, n):
    if n == 2:
        print(i)
    elif i == N:
        print(-1)
    else:
        return solve(i+1, a[n-1])

solve(0, 1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
N = int(input())
a = [0]*(N+1)
for i in range(1, N+1):
    a[i] = int(input())

def solve(i, n):
    if n == 2:
        print(i)
    elif i == N:
        print(-1)
    else:
        return solve(i+1, a[n])

solve(0, 1)
# 21:15
import math

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

def F(n,c,d):
    x = n
    x -= n//c
    x -= n//d
    lcm = c*d//math.gcd(c,d)
    x += n//lcm
    return x

print(F(b,c,d) - F(a-1,c,d))

### FIXED CODE ###

# 21:15
import fractions as math

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

def F(n,c,d):
    x = n
    x -= n//c
    x -= n//d
    lcm = c*d//math.gcd(c,d)
    x += n//lcm
    return x

print(F(b,c,d) - F(a-1,c,d))
import fractions
N=int(input())
A=list(map(int,input().split()))
c=1
a=0
w=10**9+7
for A_ in A:
    c_=c*A_//fractions.gcd(c,A_)
    a=((a+c/A_)*c_//c)%w
    #a=(a*c_//c+c_//A_)%w
    c=c_
print(int(a))

### FIXED CODE ###

import fractions
N=int(input())
A=list(map(int,input().split()))
c=1
a=0
w=10**9+7
for A_ in A:
    c=c*A_//fractions.gcd(c,A_)
for A_ in A:
    a+=c//A_
print(int(a%w))
S = input()
for i in range(1, len(S)):
  s = S[:-i]
  l = len(s) / 2
  if s[:l] == s[l:]:
    print(len(s))


### FIXED CODE ###

import sys
S = input()

for i in range(1, len(S)):
  s = S[:-i]
  l = len(s) // 2
  if s[:l] == s[l:]:
    print(len(s))
    sys.exit()
N, K = map(int, input().split())
paskal = [[0]*N for _ in range(N)] 


for i in range(N):
    for j in range(0, i+1):
        if j == 0 or j == i:
            paskal[i][j] = 1
        else:
            paskal[i][j] = (paskal[i-1][j-1] + paskal[i-1][j]) % 1000000007



for i in range(1, K+1):
    ans = paskal[N-K+1][i] * paskal[K-1][i-1]
    print(ans)

### FIXED CODE ###

#%%
"""
#(w+h-1) C w
a,b = 1, 1
for i in range(1, w+h-1):
    a *= i
    a %= mod
for i in range(1, w):
    b *= i
    b %= mod
for i in range(1, h):
    b *= i
    b %= mod

ans = a * pow(b, mod-2, mod) % mod
"""

n, k = map(int, input().split())
mod = 10**9 + 7

for i in range(1, k+1):
    if i <= n - k + 1: 
        a, b, c, d = 1, 1, 1, 1
        for j in range(1, n-k+1+1):
                a *= j
                a %= mod
        for j in range(1, i+1):
                b *= j
                b %= mod
        for j in range(1, n-k+1-i+1):
                b *= j
                b %= mod
        for j in range(1, k-1+1):
                c *= j
                c %= mod
        for j in range(1, i-1+1):
                d *= j
                d %= mod
        for j in range(1, k-i+1):
                d *= j
                d %= mod
        #print(a, b, c, d)
        ans = a * pow(b, mod-2, mod) * c * pow(d, mod-2, mod) 
        ans %= mod
    else:
        ans = 0
    print(ans)
W,H,x,y,z = map(int, input().split())
if (x-r >= 0 and x + r <= W) and (y-r >= 0 and y + r <= H):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

W,H,x,y,r = map(int, input().split())
if (x-r >= 0 and x + r <= W) and (y - r >= 0 and y + r <= H):
                                                            print("Yes")
else:
                                                            print("No")
x = map(int,raw_input().split())
z=x[0]*x[1]
a=(x[0]+x[1])*2
print(z,a)

### FIXED CODE ###

x = map(int,raw_input().split())
z=x[0]*x[1]
a=(x[0]+x[1])*2
print z,a
N, A, B = map(int, input().split())
S = list(input())
 
ok_count = 0
ok_fcount = 0
for s in S:
  if s == a:
    if ok_count < A+B-1
      print('Yes')
      ok_count +=1
      
    else:
      print('No')
      
  elif s == b:
    if ok_count <= A+B-1 and ok_fcount < B-1:
      print('Yes')
      ok_count+=1
      ok_fcount+=1
      
    else:
      print('No')
      
  else:
    print('No')

### FIXED CODE ###

N, A, B = map(int, input().split())
S = input()
 
ok_count = 0
ok_fcount = 0
for i in range(N):
  if S[i] == 'a':
    if ok_count < A+B:
      print('Yes')
      ok_count +=1
      
    else:
      print('No')
      
  elif S[i] == 'b':
    if ok_count < A+B and ok_fcount < B:
      print('Yes')
      ok_count+=1
      ok_fcount+=1
      
    else:
      print('No')
      
  else:
    print('No')
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

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

prev_com1 = 0
ans = 0
for i in range(h-a):
  com1 = cmb(i+b,b)
  com2 = cmb(h-b+h, h)
  ans += (com1 - prev_com1)*com2
  prev_com1 = com1
print(ans)

### FIXED CODE ###

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

mod = 10**9+7 #出力の制限
N = h+w
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

ans = 0
for j in range(b,w):
  ans += cmb(h-a-1+j, j, mod) * cmb(a-1+w-j-1, a-1, mod)
print(ans%mod)
import bisect

A, B, Q = map(int,input().split())
INF = 10**18
s = [-INF] +  [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]
x_list = [int(input()) for i in range(Q)]

for x in x_list:
    
    b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
    a = b - 1
    c = d - 1 
    ans = min(abs(s[a]-x) + min(abs(t[a]-s[a]), abs(t[b]-s[a])),
              abs(s[b]-x) + min(abs(t[a]-s[b]), abs(t[b]-s[b])),
              abs(t[a]-x) + min(abs(s[a]-t[a]), abs(s[b]-t[a])),
              abs(t[b]-x) + min(abs(s[a]-t[b]), abs(s[b]-t[b])))

    # for s in [s_list[a], s_list[b]]:
    #     for t in [t_list[c], t_list[d]]:
    #         dist1 = abs(s-x) + abs(t-s)
    #         dist2 = abs(t-x) + abs(t-s)
    #         ans = min(ans, dist1,dist2)
    print(ans)


### FIXED CODE ###

import bisect

A, B, Q = map(int,input().split())
INF = 10**18
s_list = [-INF] +  [int(input()) for i in range(A)] + [INF]
t_list = [-INF] + [int(input()) for i in range(B)] + [INF]
x_list = [int(input()) for i in range(Q)]

for x in x_list:
    
    b, d = bisect.bisect_right(s_list, x), bisect.bisect_right(t_list, x)
    a = b - 1
    c = d - 1 
    ans = INF
    for s in [s_list[a], s_list[b]]:
        for t in [t_list[c], t_list[d]]:
            dist1 = abs(s-x) + abs(t-s)
            dist2 = abs(t-x) + abs(t-s)
            ans = min(ans, dist1,dist2)
    print(ans)
n = int(input())
s = input()
slimes = s.split("")
i = 0
while i < n - 1:
  s = slimes[i]
  while s == slimes[i + 1]:
    slimes.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))