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

#dp[i+1][j+1]:=Sのi文字目までとTのj文字目までのLCSの長さ
S=input()
T=input()
ls=len(S)
lt=len(T)

dp=[["" for j in range(lt+1)] for i in range(ls+1)]

for i in range(ls):
    for j in range(lt):
        if S[i]==T[j]: 
            dp[i+1][j+1]=max(dp[i][j]+S[i],dp[i+1][j],dp[i][j+1],key=len)
        else:
            dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1],key=len)
print(dp[ls][lt])

### FIXED CODE ###

s = input()
t = input()
ls = len(s)
lt = len(t)


dp = [[0 for i in range(lt+1)] for j in range(ls+1)]
answer = ''

for i in range(ls):
    for j in range(lt):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])


i = ls-1
j = lt-1
while (0 <= i) & (0 <= j):
    if s[i] == t[j]:
        answer += s[i]
        i -= 1
        j -= 1
    elif dp[i+1][j+1] == dp[i+1][j]:
        j -= 1
    else:
        i -= 1
if len(answer) == 0:
  print('')
else:
  print(answer[::-1])
### BUGGY CODE ###

class Binary_Indexed_Tree:
    def __init__(self, n):
        self.size = n
        self.tree = [0 for _ in range(n+1)]

    # a[i]にxを加算(1 <= i <= n) 1-indexed
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & (-i)

    # a[1] から a[t] までの合計を得る (1 <= t <= n)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)

        return s




class RangeUpdate:
    def __init__(self, n):
        self.p = Binary_Indexed_Tree(n + 1)
        self.q = Binary_Indexed_Tree(n + 1)

    # a[s] から a[t] まで一律xを加算 (1 <= s <= t <= n)
    def add(self, s, t, x):
        t += 1
        self.p.add(s, -x * s)
        self.p.add(t, x * t)
        self.q.add(s, x)
        self.q.add(t, -x)

    # a[s] から a[t] までの合計を得る (1 <= s <= t <= n)
    def sum(self, s, t):
        t += 1
        return self.p.sum(t) + self.q.sum(t) * t - self.p.sum(s) - self.q.sum(s) * s

alpha_small_dict = {chr(i):i-97 for i in range(97, 97+26)} #辞書ver
n = int(input())
S = input()
data = [[0 for i in range(n)] for j in range(26)]

bit = [RangeUpdate(n) for i in range(26)]
for i,x in enumerate(S):
    bit[alpha_small_dict[x]].add(i+1,i+1,1)
    data[alpha_small_dict[x]][i] = 1
q = int(input())
for i in range(q):
    x,y,z = input().split()
    x,y = int(x),int(y)
    #print(x,y,z)
    if x == 1:
        num = alpha_small_dict[z]
        for j in range(26):
            if data[j][y-1] == 1:
                data[j][y-1] = 0
                bit[j].add(y,y,-1)
                break
        data[num][y-1] = 1
        bit[num].add(y,y,1)
    else:
        z = int(z)
        ans = 0
        for j in range(26):
            if bit[j].sum(y,z) >= 1:
                ans += 1
        print(ans)

### FIXED CODE ###

class Binary_Indexed_Tree:
    def __init__(self, n):
        self.size = n
        self.tree = [0 for _ in range(n+1)]

    # a[i]にxを加算(1 <= i <= n) 1-indexed
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & (-i)

    # a[1] から a[t] までの合計を得る (1 <= t <= n)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)

        return s

alpha_small_dict = {chr(i):i-97 for i in range(97, 97+26)} #辞書ver
n = int(input())
S = input()
data = [[0 for i in range(n)] for j in range(26)]

bit = [Binary_Indexed_Tree(n) for i in range(26)]
for i,x in enumerate(S):
    bit[alpha_small_dict[x]].add(i+1,1)
    data[alpha_small_dict[x]][i] = 1
q = int(input())
for i in range(q):
    x,y,z = input().split()
    x,y = int(x),int(y)
    #print(x,y,z)
    if x == 1:
        num = alpha_small_dict[z]
        for j in range(26):
            if data[j][y-1] == 1:
                data[j][y-1] = 0
                bit[j].add(y,-1)
                break
        data[num][y-1] = 1
        bit[num].add(y,1)
    else:
        z = int(z)
        ans = 0
        for j in range(26):
            if bit[j].sum(z)-bit[j].sum(y-1) >= 1:
                ans += 1
        print(ans)
### BUGGY CODE ###

from collections import deque

INF = float("inf")

H, W, K = map(int, input().split())
A = [list(input()) for _ in range(H)]

Si, Sj = (0, 0)
for i, a in enumerate(A):
    if "S" in a:
        Si, Sj = (i, a.index("S"))
        break

dist = [[INF] * W for _ in range(H)]
dist[Si][Sj] = 0

ans = INF

Q = deque([(0, Si, Sj)])
while Q:
    dist, i, j = Q.popleft()
    if dist > K:
        break

    ans = min(
        ans,
        1 + (i + K - 1) // K,
        1 + (j + K - 1) // K,
        1 + (H - 1 - i + K - 1) // K,
        1 + (W - 1 - j + K - 1) // K
    )

    if dist > K or ans == 0:
        break

    distance = dist + 1

    for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and A[ni][nj] == ".":
            A[ni][nj] = "#"
            Q.append((distance, ni, nj))

print(ans)


### FIXED CODE ###

from collections import deque

INF = float("inf")

H, W, K = map(int, input().split())
A = [list(input()) for _ in range(H)]

Si, Sj = (0, 0)
for i, a in enumerate(A):
    if "S" in a:
        Si, Sj = (i, a.index("S"))
        break

dist = [[INF] * W for _ in range(H)]
dist[Si][Sj] = 0


ans = INF

Q = deque([(Si, Sj)])
while Q:
    i, j = Q.popleft()

    ans = min(
        ans,
        1 + (i + K - 1) // K,
        1 + (j + K - 1) // K,
        1 + (H - 1 - i + K - 1) // K,
        1 + (W - 1 - j + K - 1) // K
    )

    if dist[i][j] == K:
        continue

    distance = dist[i][j] + 1

    for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ni, nj = i + di, j + dj

        if not (0 <= ni < H and 0 <= nj < W and A[ni][nj] == "."):
            continue

        A[ni][nj] = "#"

        if dist[ni][nj] > distance:
            dist[ni][nj] = distance
            Q.append((ni, nj))

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

import math
import sys
import bisect

N, M = [int(x) for x in input().split()]
MOD = 10**9 + 7

divisor = []
dict = {}

m = M
d = 2
while m != 1:
    while m % d == 0:
        divisor.append(d)
        m //= d
        dict[d] = dict.get(d,0) + 1
    d += 1
C = dict.values()
ret = 1

for c in C:
    ret = ret * math.factorial(c + N - 1)
    ret = ret // math.factorial(c)
    ret = ret // math.factorial(N - 1)
    ret = ret % MOD

print(ret)




### FIXED CODE ###

import math

N, M = [int(x) for x in input().split()]
MOD = 10 ** 9 + 7

divisor = []
dict = {}

m = M
d = 2
while m != 1:
    while m % d == 0:
        # divisor.append(d)
        m //= d
        dict[d] = dict.get(d, 0) + 1
    d += 1
C = dict.values()
ret = 1


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

def combinations_count(n, r):
    a = max(r, n-r)
    b = min(r, n-r)
    r = 1
    for i in range(a+1, n+1):
        r *= i
    return r // math.factorial(b)


for c in C:
    ret *= combinations_count(c + N - 1, c)
    ret %= MOD

print(ret)
### BUGGY CODE ###

import sys

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

li1 = []
li2 = []

for i in range(m):
    s = list(input().split())
    if "1" in s:
        li1.append(s)
    elif str(n) in s:
        li2.append(s)
        
for i in range(len(li1)):
    for j in range(len(li2)):
        x = set(li1[i]) | set(li2[j])
        if len(x) == 3:
            print("POSSIBLE")
            sys.exit()
    

print("IMPOSSIBLE")



### FIXED CODE ###

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

sa = set()
sb = set()

for i in range(M):
    a,b = map(int,input().split())
    if a==1 : sb.add(b)
    if b == N : sa.add(a)
    
print("IMPOSSIBLE" if len(sa&sb) == 0 else "POSSIBLE")
### BUGGY CODE ###

# 配るDP

mod = 998244353

def main(N, S):
    dp = [0 if n != 0 else 1 for n in range(N)] # 初期値
    lst_S = sorted(list(S))

    for i in range(N):
        if dp[i] == 0:  # 計算時間削減のため， 時間さえ間に合えば不要かも．
            continue
        for j in lst_S:
            if i + j > N - 1:
                break
            else:
                dp[i+j] = (dp[i+j] + dp[i]) % mod
    print(dp[-1])


if __name__ == '__main__':
    N, K = list(map(int, input().split()))
    S = set()
    for k in range(K):
        L, R = list(map(int, input().split()))
        S = S | {i for i in range(L, R+1)}
    main(N, S)

### FIXED CODE ###

mod = 998244353

# 貰うDP
def main(N, S):
    dp = [0 if n != 0 else 1 for n in range(N)]     # dp[i]はマスiに行く通り数． (答えはdp[-1]), dp[0] = 1 (最初にいる場所だから1通り)
    A = [0 if n != 0 else 1 for n in range(N)]      # dp[i] = A[i] - A[i-1] (i >= 1), A[0] = dp[0] = 1 (i = 0) が成り立つような配列を考える．

    for i in range(1, N):   # 今いる点 (注目点)
        for l, r in S:  # 選択行動範囲 (l: 始点, r: 終点)
            if i - l < 0:   # 注目点が選択行動範囲の始点より手前の場合 → 注目点に来るために使用することはできない．
                break
            else:           # 注目点に来るために使用することができる場合
                dp[i] += A[i-l] - A[max(i-r, 0)-1]  # lからrの間で，注目点に行くために使用できる点を逆算． そこに行くことができる = 選択行動範囲の値を選択することで注目点に達することができる通り数．
        dp[i] %= mod
        A[i] = (A[i-1] + dp[i]) % mod
    print(dp[-1])

if __name__ == '__main__':
    N, K = list(map(int, input().split()))
    S = {tuple(map(int, input().split())) for k in range(K)}
    S = sorted(list(S), key = lambda x:x[0])    # 始点でsort (範囲の重複がないため)
    main(N, S)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
import fractions
from functools import reduce

def main():
    N = int(input())
    a = list(map(int,input().split()))
    MOD = 10**9+7
            
    def lcm(x,y):
        return((x*y)//fractions.gcd(x,y))
        
    l = reduce(lcm,a)
    ans = 0
    for num in a:
        ans += l//num
        ans %= MOD
    
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
import fractions
from functools import reduce

def main():
    N = int(input())
    a = list(map(int,input().split()))
    MOD = 10**9+7
            
    def lcm(x,y):
        return((x*y)//fractions.gcd(x,y))
        
    l = reduce(lcm,a)
    ans = 0
    for num in a:
        ans += l//num
    
    print(ans%MOD)

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

s = raw_input()
n = 0

while (len(s) > 2):
    for i in xrange(1, len(s)-1):
        if s[i-1] != s[i+1]:
            s = s[0:i] + s[i+1:len(s)]
            n += 1
            break
    if len(s) == 3 and s[0] == s[2]:
        break

if n % 2 == 1:
    print "First"
else:
    print "Second"

### FIXED CODE ###

s = raw_input()
n = len(s)-2

if s[0] == s[len(s)-1]:
    n -= 1

if n % 2 == 1:
    print "First"
else:
    print "Second"
### BUGGY CODE ###

from functools import lru_cache
from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)
import numpy as np

n, m, k = map(int, input().split())
ab = [tuple(map(int,input().split())) for i in range(m)]
cd = [tuple(map(int,input().split())) for i in range(k)]
es1 = [[] for i in range(n)]
for i, (a,b) in enumerate(ab):
    a,b = a-1,b-1
    es1[a].append(b)
    es1[b].append(a)

es2 = [[] for i in range(n)]
for i, (c,d) in enumerate(cd):
    c,d = c-1,d-1
    es2[c].append(d)
    es2[d].append(c)

ans = [0]*n

@lru_cache(maxsize=None)
def calc(i):
    ans = 0
    visited = [False] * n
    i_good = np.array(es1[i])
    i_bad = np.array(es2[i])
    visited
    queue = deque()
    queue.extend(i_good)

    while len(queue):
        next_ = queue.pop()
        if visited[next_] == False:
            if (not next_ in i_good) and (not next_ in i_bad):
                ans += 1
            visited[next_] = True
            queue.extend(es1[next_])

    ans -= 1
    if ans < 0:
        ans = 0

    return ans



for i in range(n):
    ans[i] = calc(i)

print(*ans, sep=' ')


### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def root(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.root(x)]

    def is_same(self, x, y):
        return self.root(x) == self.root(y)

    def members(self, x):
        root = self.root(x)
        return [i for i in range(self.n) if self.root(i) == root]

    def all_roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n, m, k = map(int, input().split())
uf = UnionFind(n)
ab = [tuple(map(int,input().split())) for i in range(m)]
cd = [tuple(map(int,input().split())) for i in range(k)]
es1 = [[] for i in range(n)]
for i, (a,b) in enumerate(ab):
    a,b = a-1,b-1
    es1[a].append(b)
    es1[b].append(a)
    uf.union(a,b)

es_block_in_union = [[] for i in range(n)]
for i, (c,d) in enumerate(cd):
    c,d = c-1,d-1
    if uf.is_same(c,d):
        es_block_in_union[c].append(d)
        es_block_in_union[d].append(c)


ans = [0]*n
for i in range(n):
    ans[i] =  uf.size(i) - len(es_block_in_union[i])  - len(es1[i]) -1

print(*ans, sep=' ')
### BUGGY CODE ###

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

A, B, N = MAP()

left, right = 0, N

def f(x):
    return int(A*x/B) - A*int(x/B)


while right-left > 1:
    mid1 = (left + right)*1// 3
    mid2 = (left + right)*2// 3

    if f(mid1) < f(mid2):
        if left == mid1:
            break
        left = mid1
    else:
        if right == mid1:
            break
        right = mid2

ans = f(left)
for i in range(left, right+1):
    ans = max(ans, f(i))
print(ans)
# ans = 0
# # whilefor i in range(1, N+1):
# #     ans = max(ans, f(i))
# # print(ans)

# x = N//2
# if f(x) <= f(x)
# direc = "R"



### FIXED CODE ###

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

A, B, N = MAP()

left, right = 0, N

def f(x):
    return int(A*x/B) - A*int(x/B)


# while right-left > 1:
#     mid1 = (left + right)*1// 3
#     mid2 = (left + right)*2// 3

#     if f(mid1) < f(mid2):
#         if left == mid1:
#             break
#         left = mid1
#     else:
#         if right == mid1:
#             break
#         right = mid2

# ans = f(left)
# for i in range(left, right+1):
#     ans = max(ans, f(i))
# print(ans)
# ans = 0
# # whilefor i in range(1, N+1):
# #     ans = max(ans, f(i))
# # print(ans)

# x = N//2
# if f(x) <= f(x)
# direc = "R"

ans = 0
if B > N:
    ans = f(N)
else:
    ans = f(B-1)

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

# D - Line++
import numpy as np 

N, X, Y = map(int, input().split())
cnt = np.zeros(N, dtype=np.int64)
T = np.zeros((N,N), dtype=np.int64)
for i in range(N):
    for j in range(i+1,N):
         tmp = min(j-i, abs(i-X+1)+abs(j-Y+1)+1)
         T[i,j] = tmp
         cnt[tmp] += 1

for k in range(1, N):
    print(cnt[k])

### FIXED CODE ###

# D - Line++

N, X, Y = map(int, input().split())
X -= 1
Y -= 1
cnt = [0] * N

for i in range(N):
    for j in range(i+1,N):
         tmp = min(j-i, abs(i-X)+abs(j-Y)+1)
         cnt[tmp] += 1

for k in range(1, N):
    print(cnt[k])
### BUGGY CODE ###

# coding: utf-8
import sys
input = sys.stdin.readline

def f(n, p):
    dp = [[ 0.0 ] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 1.0
    for i in range(n):
        for j in range(n + 1):
            dp[i + 1][j] = dp[i][j - 1] * p[i] + \
                dp[i][j] * (1 - p[i])
    return(sum(dp[n][n // 2 + 1:]))

n = int(input()) # n: odd, 1 <= n <= 2999
p = list(map(float, input().split())) # 0 < pi[i] < 1
print(f(n, p))


### FIXED CODE ###

# coding: utf-8
import sys
input = sys.stdin.readline

def f2(n, p):
    dp = [ 0.0 ] * (n + 1)
    dp[0] = 1.0
    # pprint.pprint(dp, width = 50)
    for i in range(n):
        dp_ = list(dp)
        pi_ = 1 - p[i]
        for j in range(n + 1):
            dp[j] = dp_[j - 1] * p[i] + dp_[j] * pi_
        # pprint.pprint(dp, width = 50)
    return(sum(dp[n // 2 + 1:]))

n = int(input()) # n: odd, 1 <= n <= 2999
p = list(map(float, input().split())) # 0 < pi[i] < 1
print(f2(n, p))
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [float("inf")] * n
dp[0] = 0
for i in range(1, n):
  if i < k:
    dp[i] = min( { dp[j]+abs(h[j]-h[i]) for j in range(i) } )
  else:
    dp[i] = min( { dp[i-j-1]+abs(h[i-j-1]-h[i]) for j in range(k) } )
print(dp[n-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [float("inf")] * n
dp[0] = 0
for i in range(1, n):
  if i < k:
    dp[i] = min([ dp[j]+abs(h[j]-h[i]) for j in range(i) ])
  else:
    dp[i] = min( [ dp[i-j-1]+abs(h[i-j-1]-h[i]) for j in range(k) ] )
print(dp[n-1])
### BUGGY CODE ###

import sys
import itertools
import numpy as np

def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i:
        divisors.append(n//i)
  return divisors
def abc(n):
  b = 2
  fct = [0]
  while b * b <= n:
    while n % b == 0:
      n //= b
      fct.append(b)
    b = b + 1
  if n > 1:
    fct.append(n)
  return fct
def getNearestValue(list, num):
  idx = np.abs(np.asarray(list) - num).argmin()
  return list[idx]
for n in range(2,10**12):
  list_ = abc(n)

  list_.sort()
  tmp = np.sqrt(n)
  N = len(list_)

  dp = [[1 for i in range(N+1)] for j in range(N+1)]

  for i in range(N):
    for j in range(1,N):
      if i == j:
          continue
      else:
        if dp[i][j-1] * list_[j] <= tmp:
          dp[i][j] = dp[i][j-1] * list_[j]
        else:
          continue
  tmplist = list(itertools.chain.from_iterable(dp))

  tmp1 = max(tmplist)
  if tmp1 == 0:
    print(n-1)
    sys.exit()
    
    
  tmp2 = make_divisors(n)
  tmp2.sort()
  sq = np.sqrt(n)
  tmpnum = n
  for i in tmp2:
    if i > sq:
      break
    else:
      tmpnum = min(tmpnum-1, n//i + i - 2)
    
  if (tmp1 - 1)+(n//tmp1-1) != tmpnum:
    print(n)

### FIXED CODE ###

a,b = map(int,input().split())
if a >= 10 or b >= 10:
  print(-1)
else:
  print(a*b)
### BUGGY CODE ###

s = input()
t = input()
dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]

hassame = False
for i, s_ in enumerate(s):
    if hassame or s_ == t[0]: dp[i+1][1]=1; hassame=True
hassame = False
for i, t_ in enumerate(t):
    if hassame or t_ == s[0]: dp[1][i+1]=1; hassame=True

lcs = 0
for i, s_ in enumerate(s):
    if i==0: continue
    for j, t_ in enumerate(t):
        if j==0: continue
        if s_!=t_:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
        else:
            dp[i+1][j+1] = dp[i][j]+1
        lcs = max(lcs, dp[i+1][j+1])

ans = ''
i, j = len(s), len(t)
while 0<i and 0<j:
        if s[i-1] == t[j-1]: ans+=s[i-1]; i-=1; j-=1
        else:
            if dp[i-1][j] > dp[i][j-1]: i-=1
            else: j-=1
print(ans[::-1])


for i in range(len(s)):
    dp+=s[i]

### FIXED CODE ###

s = input()
t = input()
dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]

hassame = False
for i, s_ in enumerate(s):
    if hassame or s_ == t[0]: dp[i+1][1]=1; hassame=True
hassame = False
for i, t_ in enumerate(t):
    if hassame or t_ == s[0]: dp[1][i+1]=1; hassame=True

lcs = 0
for i, s_ in enumerate(s):
    if i==0: continue
    for j, t_ in enumerate(t):
        if j==0: continue
        if s_!=t_:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
        else:
            dp[i+1][j+1] = dp[i][j]+1
        lcs = max(lcs, dp[i+1][j+1])

ans = ''
i, j = len(s), len(t)
while 0<i and 0<j:
        if s[i-1] == t[j-1]: ans+=s[i-1]; i-=1; j-=1
        else:
            if dp[i-1][j] > dp[i][j-1]: i-=1
            else: j-=1
print(ans[::-1])


for i in range(len(s)):
    dp+=s[i]
### BUGGY CODE ###

N=int(input())
suu=(N/2)-1
d=list(map(int,input().split()))
for n in range(round(suu)):
    s=d.index(max(d))
    d.pop(s)
dai=max(d)
s=d.index(max(d))
d.pop(s)
syo=max(d)
print(dai-syo)


### FIXED CODE ###

N=int(input())
d=list(map(int,input().split()))
d.sort()
dai=d[round((N/2)-1)]
syo=d[round(N/2)]
print(syo-dai)
### BUGGY CODE ###

N, K = map(int, input().split())
MOD = 10 ** 9 + 7


def comb(n, k, p):
    """power_funcを用いて(nCk) mod p を求める"""
    from math import factorial
    if n < 0 or k < 0 or n < k:
        return 0
    if n == 0 or k == 0:
        return 1
    a = factorial(n) % p
    b = factorial(k) % p
    c = factorial(n-k) % p
    return (a*power_func(b, p-2, p)*power_func(c, p-2, p)) % p


def power_func(a, b, p):
    """a^b mod p を求める"""
    if b == 0:
        return 1
    if b % 2 == 0:
        d = power_func(a, b//2, p)
        return d*d % p
    if b % 2 == 1:
        return (a*power_func(a, b-1, p)) % p


memo = [[-1 for _ in range(K + 1)] for _ in range(K + 1)]


def dp(n, k):
    # n個のボールをk個のグループに分ける(空のグループを許容)
    if n <= 0 or k <= 1:
        return 1
    if memo[n][k] >= 0:
        return memo[n][k]
    memo[n][k] = 0
    for i in range(n, -1, -1):
        memo[n][k] += dp(n - i, k - 1) % MOD
    return memo[n][k]


for i in range(1, K + 1):
    print(comb(N - K + 1, i, MOD) * dp(K - i, i) % MOD)


### FIXED CODE ###

N, K = map(int, input().split())
MOD = 10 ** 9 + 7


def comb(n, k, p):
    """power_funcを用いて(nCk) mod p を求める"""
    from math import factorial
    if n < 0 or k < 0 or n < k:
        return 0
    if n == 0 or k == 0:
        return 1
    a = factorial(n) % p
    b = factorial(k) % p
    c = factorial(n-k) % p
    return (a*power_func(b, p-2, p)*power_func(c, p-2, p)) % p


def power_func(a, b, p):
    """a^b mod p を求める"""
    if b == 0:
        return 1
    if b % 2 == 0:
        d = power_func(a, b//2, p)
        return d*d % p
    if b % 2 == 1:
        return (a*power_func(a, b-1, p)) % p


memo = [[-1 for _ in range(K + 1)] for _ in range(K + 1)]


def dp(n, k):
    # n個のボールをk個のグループに分ける(空のグループを許容)
    if n <= 0 or k <= 1:
        return 1
    if memo[n][k] >= 0:
        return memo[n][k]
    memo[n][k] = 0
    for i in range(n, -1, -1):
        memo[n][k] += dp(n - i, k - 1) % MOD
    return memo[n][k]


for i in range(1, K + 1):
    print(comb(N - K + 1, i, MOD) * comb(K - 1, i - 1, MOD) % MOD)
### BUGGY CODE ###

n = int(input())
a_list = list(map(int, input().split()))
count = 0
while True:
  for i in a_list:
    if i % 2 ==  1:
      break
    else:
      a_list = list(map(lambda x:x/2 , a_list))
      count += 1
print(count)
    
  

### FIXED CODE ###

n = int(input())
a_list = list(map(int, input().split()))
ans = 0
while True:
  if [i for i in a_list if i % 2 == 1]:
      break
  a_list = list(map(lambda x:x/2 , a_list))
  ans += 1
print(ans)
### BUGGY CODE ###

def main():
    import sys 
    input= sys.stdin.readline
    n,m,v,p=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort(reverse=True)
    cnt=p
    #from bisect import bisect_left
    #print(a[5]+m)
    for i in range(p,n):
        if (a[i]+m )<a[p-1]:
            break
        # 3 2 2 1 1 0
        cnt+= ((a[i]+m)*(i-p+1)-sum(a[p-1:i])+(n-(i-p+1))*m)>=v*m
              
    print(cnt)

if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    import sys 
    input= sys.stdin.readline
    n,m,v,p=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort(reverse=True)
    cnt=p
    #from bisect import bisect_left
    #print(a[5]+m)
    s=sum(a[p-1:p])
    for i in range(p,n):
        if (a[i]+m )<a[p-1]:
            break
        # 3 2 2 1 1 0
        
        cnt+= ((a[i]+m)*(i-p+1)-s+(n-(i-p+1))*m)>=v*m
        try: s+=a[i]
        except: continue      
    print(cnt)

if __name__=='__main__':
    main()