Harryxun/stf_run huggingface dataset:
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)

for _ in range(M):
    A[0] = int(A[0]/2)
    if A[0]<A[1]:
        A = sorted(A, reverse=True)

print(sum(A))

### FIXED CODE ###

from heapq import (
    heapify,  # 優先度付きキューの生成
    heappop,
    heappush,
    heappushpop,
    heapreplace
    )

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

#heapqは最小値しか取り出さないので-1倍する
A = [-i for i in map(int,input().split())]
heapify(A)

for _ in range(M):
    s = -heappop(A)
    s //= 2
    heappush(A, -s)

print(-sum(A))
a = input()
b = input()
s = ""
for i in range(len(a)+len(b)):
    if i%2==0:a
        s+=a[i//2]
    else:
        s+=b[i//2]
print(s)

### FIXED CODE ###

a = input()
b = input()
s = ""
for i in range(len(a)+len(b)):
    if i%2==0:
        s+=a[i//2]
    else:
        s+=b[i//2]
print(s)
n=input().split(" ")
a=int(n[0])
b=int(n[1])
c=int(n[2])
count=0
for i in range(a+b+1):
     if c%i==0:
       count=i+1
print(count)


### FIXED CODE ###

x=input().split(" ")
a=int(x[0])
b=int(x[1])
c=int(x[2])
count=0
for i in range(a,b+1):
  if c%i==0:
   count+=1
print(count)
from operator import itemgetter
tik = [[1,2],[7,3],[4,4],[5,5],[3,5],[2,5],[9,6],[8,7],[6,6]]
dic = {"1":2,"7":3,"4":4,"5":5,"3":5,"2":5,"9":6,"8":7,"6":6}

n,k = map(int, input().split())
x = list(map(int, input().split()))
inf = float("INF")
dp = [0]+[-1]*(n+10)
q = []
for i in range(k):
    q.append([x[i],dic[str(x[i])]])

q = sorted(q, key=itemgetter(1), reverse=False)

s = []
p=0
t = 0
for i in range(n):
    for j in range(k):
        if i+q[j][1] <=n:
            if dp[i]!=-1:
            
                if  dp[i]==0:
                    dp[i+q[j][1]] = q[j][0]
                else:dp[i+q[j][1]] = str(dp[i])+str(q[j][0])
        #if i+q[j][1] ==n:
            #print(dp[20])
s = list(dp[n])
s.sort()
s = s[::-1]
print(''.join(s))

### FIXED CODE ###

from operator import itemgetter
tik = [[1,2],[7,3],[4,4],[5,5],[3,5],[2,5],[9,6],[8,7],[6,6]]
dic = {"1":2,"7":3,"4":4,"5":5,"3":5,"2":5,"9":6,"8":7,"6":6}

n,k = map(int, input().split())
x = list(map(int, input().split()))
dp = [0]+[-1]*(n+10)
q = []
for i in range(k):
    q.append([x[i],dic[str(x[i])]])

q = sorted(q, key=itemgetter(1), reverse=False)

s = []
p=0
t = 0
for i in range(n):
    for j in range(k):
        if i+q[j][1] <=n:
            if dp[i]!=-1:
            
                if  dp[i]==0:
                    ko = q[j][0]
                    dp[i+q[j][1]] = max(q[j][0],dp[i+q[j][1]])

                else:
                    ko = dp[i]+q[j][0]
                    dp[i+q[j][1]] = max(dp[i]*10+q[j][0], dp[i+q[j][1]])
        #if i+q[j][1] ==n:
            #print(dp[20])
s = list(str(dp[n]))
s.sort()
s = s[::-1]
print(''.join(s))
def solve(d,c,s,k):
    last=[0]*27
    srate=[]
    ans=[]
    for i in range(1,d+1):
        a=0
        for j in range(1,27):
            a-=c[j-1]*(i-last[j])
        pa=0
        mlast=[0]*2
        for t in range(1,27):
            if s[i-1][t-1]+c[t-1]*(min(k*(k-1)/2,(366-d)*((366-d)-1)/2))>pa:
                mlast=[t,i]
                pa=s[i-1][t-1]+c[t-1]*(i-last[t])
        a+=pa
        last[mlast[0]]=mlast[1]           
        ans.append(mlast[0])
        srate.append(a)
    return ans,srate

def main():
    d=int(input())
    c=list(map(int,input().split()))
    s=[list(map(int,input().split())) for _ in range(d)]
    mrate=0
    for i in range(26):
        a,srate=solve(d,c,s,i)
        if mrate<srate[-1]:
            ans=[]
            ans.append(a)
            mrate=srate[-1]
    for i in ans[0]:
        print(i)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    d=int(input())
    c=list(map(int,input().split()))
    s=[list(map(int,input().split())) for _ in range(d)]
    last=[0]*27
    ans=[]
    for i in range(1,d+1):
        a=0
        for j in range(1,27):
            a-=c[j-1]*(i-last[j])
        pa=0
        mlast=[0]*2
        for t in range(1,27):
            if s[i-1][t-1]+c[t-1]*(i-last[j])>pa:
                mlast=[t,i]
                pa=s[i-1][t-1]+c[t-1]*(i-last[j])
        a+=pa
        last[mlast[0]]=mlast[1]           
        ans.append(mlast[0])
    for i in ans:
        print(i)

if __name__ == '__main__':
    main()
N,m=map(int,input().split())
s = set()
for i in range(m):
    s.add(int(input()))
memo={0:1}
mod=1000000007
def climb_stairs(n):
    if memo.__contains__(n):
        return memo[n]
    else:
        if s.__contains__(n):
            return 0
        elif n==1:
            return 1
        else:
            memo[n]=((climb_stairs(n-1)%mod + (climb_stairs(n-2) %mod)%mod
            return memo[n]
print(climb_stairs(N))

### FIXED CODE ###

I=lambda : list(map(int,input().split()))

n,m = I();md=10**9+7;p=0;a=1
dp=[0,1];l=[0]*(10**5+2)
for _ in range(m):
    x=int(input())
    l[x]=1
for i in range(1,n+1):
    if l[i]:
        dp.append(0)
    else:
        dp.append((dp[-1]+dp[-2])%md)
print(dp[-1])
n,a,b=int(x) for x in input().split()
c=0
def sual(N,A,B):
  l=list('{}'.format(N))
  s=sum(l)
  if A<=s<=B:
    return True
  else:
    return False
for x in range(n):
  if sual(x+1,a,b):
    c=c+x+1
print(c)

### FIXED CODE ###

n,a,b=(int(x) for x in input().split())
c=0
d=[]
def sual(N,A,B):
  l=list('{}'.format(N))
  for y in range(len(l)):
      d.append(int(l[y]))
  e=sum(d)
  d.clear()
  if A<=e<=B:
    return True
  else:
    return False

for x in range(n):
  if sual(x+1,a,b):
    c=c+x+1
print(c)
s = input()
n = len(s)
a = 0
if n % 2 == 0:
  for i in range(0,n+1,2):
    if s[i] == "R":
      a = 1
      break
  for i in range(1,n,2):
    if s[i] == "L":
      a = 1
      break
if n % 2 == 1:
  for i in range(0,n,2):
    if s[i] == "R":
      a = 1
      break
  for i in range(1,n+1,2):
    if s[i] == "L":
      a = 1
      break
if a == 0:
  print("Yes")
if a == 1:
  print("No")

### FIXED CODE ###

s = input()
n = len(s)
a = 0
if n % 2 == 0:
  for i in range(0,n,2):
    if s[i] == "L":
      a = 1
      break
  for i in range(1,n,2):
    if s[i] == "R":
      a = 1
      break
else:
  for i in range(0,n,2):
    if s[i] == "L":
      a = 1
      break
  for i in range(1,n,2):
    if s[i] == "R":
      a = 1
      break
if a == 0:
  print("Yes")
if a == 1:
  print("No")
N=input()
lista=list(map(int,input().split()))
  for _ in range(1,N+1):
  print(lista.count(_))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=[0]*n
for aa in a:
  ans[aa-1]+=1
for an in ans:
  print(an)
import math
a,b,X = map(int, input().split())
x = X/(a**2)

if x<=b/2:
        t = 2*a*x/(b**2)
        print(90-math.degrees(math.atan(t)))

else:
        t = a/(2*b-2*x)
        print(90-math.degrees(math.atan(t)))


### FIXED CODE ###

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

if x<=b/2:
        t = 2*a*x/(b**2)
        print(90-math.degrees(math.atan(t)))

else:
        if a**2*b==X:
                print(0)
        else:
                t = a/(2*b-2*x)
                print(90-math.degrees(math.atan(t)))
o=list(input())
e=list(input())

for i in range(len(o)+1):
  print(o[i],end="")
  print(e[i],end="")

### FIXED CODE ###

o=list(input())
e=list(input())+[""]
for x,y in zip(o,e):print(x+y,end="")
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
#define INF 100000000000

signed main(){
  ll n,m,r;cin >> n >> m >> r;
  vector<ll> rx(r);for(int i=0;i<r;i++)cin >> rx[i];
  vector<vector<ll>> wf(n,vector<ll>(n,INF));
  for(int i=0;i<n;i++) wf[i][i]=0;
  for(int i=0;i<m;i++){
    ll a,b,c;cin >> a >> b >> c;
    wf[a-1][b-1]=c;
    wf[b-1][a-1]=c;
  }
  for(int k=0;k<n;k++){
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
        wf[i][j]=min(wf[i][j],wf[i][k]+wf[k][j]);
      }
    }
  }
  ll cnt=INF;
  vector<ll> v(r);for(int i=0;i<r;i++) v[i]=i;
  do{
    ll cnt_sub=0;
    for(int i=0;i<r-1;i++){
      cnt_sub+=wf[rx[v[i]]-1][rx[v[i+1]]-1];
    }
    cnt=min(cnt,cnt_sub);
  }while(next_permutation(v.begin(),v.end()));
  cout << cnt << endl;
}


### FIXED CODE ###

import itertools
n,m,r=map(int,input().split())
rx=[int(i) for i in input().split()]
inf=100000000
wf=[[inf]*n for i in range(n)]
for i in range(n):
    wf[i][i]=0

for i in range(m):
    a,b,c=map(int,input().split())
    wf[a-1][b-1]=c
    wf[b-1][a-1]=c

for k in range(n):
    for i in range(n):
        for j in range(n):
            if wf[i][j]>wf[i][k]+wf[k][j]:
                wf[i][j]=wf[i][k]+wf[k][j]
cnt=0
l=list(itertools.permutations([i for i in range(r)]))
cnt=inf
for i in l:
    cnt_sub=0
    for j in range(r-1):
        cnt_sub+=wf[rx[i[j]]-1][rx[i[j+1]]-1]
    cnt=min(cnt,cnt_sub)
print(cnt)
import collections
from scipy.special import comb

N = int(input())
b =[]
for i in range(N):
    a = input()
    b.append([j for j in a])
    b[i].sort()
a = [''.join(j) for j in b]
b = [k for k in collections.Counter(a).values()]
c = 0
for x in range(len(b)):
    if b[x] > 1:
        c += comb(b[x], 2, exact=True)
    else:
        None
print(c)

### FIXED CODE ###

import collections
import math

N = int(input())
b =[]
for i in range(N):
    a = input()
    b.append([j for j in a])
    b[i].sort()
a = [''.join(j) for j in b]
b = [k for k in collections.Counter(a).values()]
c = 0
for x in range(len(b)):
    if b[x] > 1:
        c += math.factorial(b[x]) // (math.factorial(b[x] - 2) * math.factorial(2))
    else:
        None
print(c)
import sys
import numpy as np
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
X, Y, A, B, C = [int(x) for x in input().strip().split()]
p = np.array(sorted([int(x) for x in input().strip().split()], reverse=True))[:X]
q = np.array(sorted([int(x) for x in input().strip().split()], reverse=True))[:Y]
r = np.array(sorted([int(x) for x in input().strip().split()], reverse=True))[:min(C, X+Y)]

pq = np.hstack((p, q))
pq.sort()
pq = pq[::-1]
ri = 0
for i, t in enumerate(pq):
    if t < r[ri]:
        pq[i] = r[ri]
        ri += 1
print(sum(pq))

### FIXED CODE ###

import sys
import numpy as np
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
X, Y, A, B, C = [int(x) for x in input().strip().split()]
p = np.array(sorted([int(x) for x in input().strip().split()], reverse=True))[:X]
q = np.array(sorted([int(x) for x in input().strip().split()], reverse=True))[:Y]
r = np.array(sorted([int(x) for x in input().strip().split()], reverse=True))[:min(C, X+Y)]

pq = np.hstack((p, q))
pq.sort()
ri = 0
for i, t in enumerate(pq):
    if t < r[ri]:
        pq[i] = r[ri]
        ri += 1
    if ri == len(r):
        break
print(sum(pq))
n = int(input())
a = list(map(int, input().split()))
dic = {}; ans = []
for i in range(n+1)[1:]:
    dic.setdefault(a[i-1],[]).append(i)
heapq.heapify(a)
for i in range(n):
    res = heapq.heappop(a)
    ans.append(dic[res][0])
print(*ans)

### FIXED CODE ###

import heapq
n = int(input())
a = list(map(int, input().split()))
dic = {}; ans = []
for i in range(n+1)[1:]:
    dic.setdefault(a[i-1],[]).append(i)
heapq.heapify(a)
for i in range(n):
    res = heapq.heappop(a)
    ans.append(dic[res][0])
print(*ans)
import math

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

def solve(N, K, As):
    if N == 1:
        if K == As[0]:
            print("POSSIBLE")
        else:
            print("IMPOSSIBLE")
        return
    g = As[-1]
    for a in As[:-1]:
        g = math.gcd(g, a)
    maxA = max(As)
    if (maxA >= K) and ((maxA - K)%g) == 0:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

solve(N, K, As)


### FIXED CODE ###

import fractions

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

def solve(N, K, As):
    if N == 1:
        if K == As[0]:
            print("POSSIBLE")
        else:
            print("IMPOSSIBLE")
        return
    g = As[-1]
    for a in As[:-1]:
        g = fractions.gcd(g, a)
    maxA = max(As)
    if (maxA >= K) and ((maxA - K)%g) == 0:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

solve(N, K, As)
#!/usr/bin/env python3

import sys
import math
import itertools

def main():
    N, T = map(int, sys.stdin.readline().split())
    shops = list(tuple(map(int, sys.stdin.readline().split())) for _ in range(N))

    shops.sort(key=lambda x: x[0] / (x[0] + x[1] + 1), reverse=True)
    memo = {}

    def dp(i, t):
        assert i >= 0
        assert t >= 0

        if i == 0:
            return 0

        if (i, t) in memo:
            return memo[i, t]

        h = i - 1
        s = int((t - shops[h][1]) / (shops[h][0] + 1)) - 1
        x = max(dp(h, s) + 1, dp(h, t)) if s >= 0 else dp(h, t)
        memo[i, t] = x
        return x

    print(dp(N, T))
    #print(sorted(memo.items()))

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env pypy3

import sys
import math
import itertools
import bisect

INF = int(1e18)
T_MAX = int(1e9)

def main():
    N, T = map(int, sys.stdin.readline().split())
    shops = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]

    nzshops = [(a, b) for a, b in shops if a > 0]
    zshops  = [(a, b) for a, b in shops if a == 0]

    nzshops.sort(key=lambda x: x[0] / (x[0] + x[1] + 1), reverse=True)
    zshops.sort()

    dp = [[0] + [INF] * int(math.log(T_MAX, 2)) for _ in range(len(nzshops) + 1)]
    for i in range(1, len(dp)):
        for c in range(1, len(dp[i])):
            a, b = nzshops[i - 1]
            t = dp[i - 1][c - 1] + 1
            dp[i][c] = min(dp[i - 1][c], t + t * a + b)

    rs = list(itertools.accumulate(1 + b for _, b in zshops))
    ans = max(c + bisect.bisect(rs, T - dp[-1][c])
            for c in range(len(dp[-1])) if dp[-1][c] <= T)

    print(ans)

if __name__ == '__main__':
    main()
n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
b=[]
for i in range(m):
    p=list(map(int,input().split()))
    b.append(p)
b.sort(key=lambda x:-x[1])
a.sort()
wes=-1
i=0
s=0
while True:
    wes+=b[i][0]
    if a[wes]>=b[i][1]:
        wes-=b[i][0]
        wes+=1
        break
    else:
        
        s+=b[i][0]*b[i][1]
        i+=1
for j in range(b[i][0]):
    if a[wes+j]<b[i][1]:
        a[wes+j]=b[i][1]
f=a[wes:]
s+=sum(f)
print(s)

### FIXED CODE ###

n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
b=[]
s=0
for i in range(m):
    p=list(map(int,input().split()))
    b.append(p)
    s+=p[0]
b.sort(key=lambda x:-x[1])
a.sort()
if s>n:
    s=n
c=[]
i=0
sun=0
while sun<s:
    for j in range(b[i][0]):
        c.append(b[i][1])
    sun+=b[i][0]
    i+=1
for u in range(s):
    if a[u]<c[u]:
        a[u]=c[u]
    
print(sum(a))
a=[]

for i in range(6):
    a.append(int(input())

a=a.sort()
if(a[4]-a[0]>a[5]):
    print(':(')
else:
    print('Yay!')

### FIXED CODE ###

a=[]

for i in range(5):
    a.append(int(input()))

k=int(input())
for i in range(5):
    for j in range(5):
        if(i==j):
            continue
        else:
            if(abs(a[i]-a[j])>k):
                print(':(')
                exit()

print('Yay!')
S = input()
 
ans = 0
c = []
 
for i in range(len(S)):
  if S[i] =="R":
    ans += 1
  else:
    c.append(ans)
    ans = 0
 
 
print(max(c))

### FIXED CODE ###

S = input()
 
ans = 0
c = []
 
for i in range(len(S)):
    if S[i] =="R":
        ans += 1
    else:
        c.append(ans)
        ans = 0

c.append(ans)
 
print(max(c))
a, b, c, d = map(int,input().split())

# aとcの距離の絶対値ACを定義
if (a - c) <= 0:
    AC = (a-c)
else:
    AC = (c-a)

# BがAとCの間に入る場合のみ、AB間、BC間を定義
if a < b < c:
    AB = (b - a)
    BC = (c - b)
if c < b < a:
    AB = (a-b)
    BC = (b-c)

# AとCの距離がd以下ならYes！
if AC <= d:
    print('Yes')
if (AC - AB - BC) <= d:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

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

# aとcの距離の絶対値ACを定義
if (a - c) >= 0:
    AC = (a-c)
else:
    AC = (c-a)

# BがAとCの間に入る場合のみ、AB間、BC間を定義
if a < b < c:
    AB = (b - a)
    BC = (c - b)
if c < b < a:
    AB = (a-b)
    BC = (b-c)

# AとCの距離がd以下ならYes！
if AC <= d:
    print('Yes')
# AB間、BC間ともにd以下ならYes！
elif AB <= d and BC <= d:
    print('Yes')
else:
    print('No')
a,b,c,d,e,k = int(input()) for i in range(6)
print("Yay!" if e - a <= k else ":(")

### FIXED CODE ###

a,b,c,d,e,k = [int(input()) for i in range(6)]
print("Yay!" if abs(a - e) <= k else ":(")
# -*- coding: utf-8 -*-
# problem C2

N = int(input())
ls = [1]
ans = 0

if N == 1:
        print(1)
else:
    for i in range(1, N+1):
        for j in ls:
            x = j * i
            if x not in ls:
                ans += 1
                n.append(x)
    print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
# problem C2

## N! = 1 * 2 * ... * N
## N! = 2~e2 + 3~e3 + 5~e5 + ... + prime~eprime
## e2 = ord2(1) + ord2(2) + ... + ord2(N)
## ans = (e2 + 1)(e3 + 1)(e5 + 1)...
## e2 = [N/2] + [N/4] + [N/8] + [N/16] +...

from math import floor as gs
N = int(input())

## creating prime numbers until N
def fun_prime(k):
    counter = 0
    primes = [2, 3]

    for n in range(5, k+1, 2):
        isprime = True
        for i in range(1, len(primes)):
            if primes[i] ** 2 > n:
                break
            if n % primes[i] == 0:
                isprime = False
                break
        if isprime == True:
            primes.append(n)
    return(primes)
primes_N = fun_prime(N)

ans = 1
if N == 1:
    print(int(ans))
else:
    for prime in primes_N:
        e = 0
        power = prime
        while power <= N:
            e += gs(N/power)
            power = power * prime
        ans = ans * (e + 1)
    ans = ans % (10 ** 9 + 7)
    print(int(ans))
num_list = [int(input()) for i in range(3)]
result_yen = int(intput())

count = 0

for yen_500 in range(coin_list[0]):
    for yen_100 in range(coin_list[1]):
        for yen_50 in range(coin_list[2]):
            if result_yen == yen_500*500 + yen_100*100 + yen_50 *50:
                count += 1
                
print(count)

### FIXED CODE ###

input_num = [int(input()) for i in range(4)]

coin_list = input_num[0:3]
result_yen = input_num[3]

count = 0

for yen_500 in range(coin_list[0]+1):
    for yen_100 in range(coin_list[1]+1):
        for yen_50 in range(coin_list[2]+1):
            if result_yen == yen_500*500 + yen_100*100 + yen_50 *50:
                count += 1
                
print(count)
n = int(input())
d,x = map(int,input().split())

a = []
for i in range(n):
  a.append(int(input()))

count = 0
for i in range(1,d+1):
  for j in a:
    if (i-1)%a == 0:
      count += 1

print(count + n)



### FIXED CODE ###

n = int(input())
m, k = [int(_) for _ in input().split()]
    
for i in range(n):
    for j in range(1, m+1, int(input())):
        k += 1
print(k)
import math

MOD = math.pow(10, 9) + 7


def check(h, w, a, b):
    c, d = h - a, w - b
    start2p = math.factorial(a + b) // (math.factorial(a) * math.factorial(b))
    p2end = math.factorial(c + b) // (math.factorial(c) * math.factorial(d))
    return (start2p * p2end) % MOD


def main():
    h, w, a, b = map(int, input().split())
    print(check(h, w, a, b))


if __name__ == '__main__':
    main()


### FIXED CODE ###

MOD = 1000000007


def mod_pow(a, n, mod):
    """
    二分累乗法による a^n (mod m)の実装

    :param a: 累乗の底
    :param n: 累乗の指数
    :param mod: 法
    :return: a^n (mod m)
    """

    result = 1
    a_n = a
    while n > 0:
        if n & 1:
            result = result * a_n % mod
        a_n = a_n * a_n % mod
        n >>= 1
    return result


def mod_inverse(a, mod):
    """
    フェルマーの小定理による a^-1 ≡ 1 (mod m)の実装
    aの逆元を計算する

    a^-1 ≡ 1 (mod m)
    a * a^-2 ≡ 1 (mod m)
    a^-2 ≡ a^-1 (mod m)

    :param a: 逆元を計算したい数
    :param mod: 法
    :return: a^-1 ≡ 1 (mod m)
    """

    return mod_pow(a=a, n=mod - 2, mod=mod)


class ModCombination:
    """
    nCk (mod m)を扱うクラス
    """

    def __init__(self, mod, n_max):
        """
        イニシャライザ
        予め 1~nの階乗と階乗の逆元を計算しておく

        :param mod: 法
        :param n_max: nの最大値(100,000で約1秒)
        """
        self.mod = mod
        self.n_max = n_max
        self.facts = [1, 1]
        self.inverses = [None, 1]
        self.fact_inverses = [1, 1]

        for i in range(2, self.n_max + 1):
            self.facts.append(self.facts[i - 1] * i % self.mod)
            # self.inverses.append(mod_inverse(i, self.mod))
            self.inverses.append(self.mod - self.inverses[self.mod % i] * (
                        self.mod // i) % self.mod)
            self.fact_inverses.append(
                self.fact_inverses[i - 1] * self.inverses[i] % self.mod
            )

    def mod_combination(self, n, k):
        """
        nCk (mod m)を計算する

        :param n: n
        :param k: k
        :return: nCk (mod m)
        """
        if not 0 < k < n:
            raise ValueError

        denominator = \
            self.fact_inverses[k] * self.fact_inverses[n - k] % self.mod
        return self.facts[n] * denominator % self.mod


def calc_routes(combination, dx, dy):
    if dx == 0 or dy == 0:
        return 1
    else:
        return combination.mod_combination(dx + dy, dx)


def check(h, w, a, b):
    combination = ModCombination(mod=MOD, n_max=h + w)
    p = (b + 1, h - a)
    all_routes = 0
    while p[0] <= w and p[1] > 0:
        d1 = (p[0] - 1, p[1] - 1)
        d2 = (w - p[0], h - p[1])
        r1 = calc_routes(combination, *d1)
        r2 = calc_routes(combination, *d2)
        routes = r1 * r2 % MOD
        all_routes += routes
        all_routes %= MOD
        p = (p[0] + 1, p[1] - 1)
    return all_routes


def main():
    h, w, a, b = map(int, input().split())
    print(check(h, w, a, b))


if __name__ == '__main__':
    main()
n ,k =map(int, input().split())
S=[]

def merge(array):                                   # line1
    mid = len(array)                                # line2
    if mid > 1:                                     # line3
        left = merge(array[:(mid//2)])               # line4
        right = merge(array[(mid//2):])              # line5
        array = []                                  # line6
        while len(left) != 0 and len(right) != 0:   # line7
            if left[0] < right[0]:                  # line8
                array.append(left.pop(0))           # line9
            else:                                   # line10
                array.append(right.pop(0))          # line11
        if len(left) != 0:                          # line12
            array.extend(left)                      # line13
        elif len(right) != 0:                       # line14
            array.extend(right)                     # line15
    return array



for i in range(n):
	a=int(input())
	S.append(a)
L=merge(S)
#print(L)
ans=-L[0]+L[n-1]
for i in range(k):
	if -L[i]+L[i+k-1]<ans:
		ans=-L[i]+L[i+k-1]
print(ans)
	

### FIXED CODE ###

n ,k =map(int, input().split())
S=[]

def merge(array):                                   # line1
    mid = len(array)                                # line2
    if mid > 1:                                     # line3
        left = merge(array[:(mid//2)])               # line4
        right = merge(array[(mid//2):])              # line5
        array = []                                  # line6
        while len(left) != 0 and len(right) != 0:   # line7
            if left[0] < right[0]:                  # line8
                array.append(left.pop(0))           # line9
            else:                                   # line10
                array.append(right.pop(0))          # line11
        if len(left) != 0:                          # line12
            array.extend(left)                      # line13
        elif len(right) != 0:                       # line14
            array.extend(right)                     # line15
    return array



for i in range(n):
	a=int(input())
	S.append(a)
L=merge(S)

ans=-L[0]+L[n-1]
for i in range(n-k+1):
	if -L[i]+L[i+k-1]<ans:
		ans=-L[i]+L[i+k-1]
print(ans)
n = int(input())
	if n%2 == 0;
  		y = n/2
	if round(n/2)<(n/2):
    	y=round((n+1)/2)
	print(str(y/n))

### FIXED CODE ###

n = int(input())
if n%2==0:
    print(str((n/2)/n))
else:
    print(str(((n+1)/2)/n))