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

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 998244353
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, s = LI()
a = LI()

dp = [[0]*(s+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(1, n+1):
    x = a[i-1]
    for j in range(s+1):
        if j == 0:
            dp[i][j] += dp[i-1][j] + 1
            dp[i][j] %= mod
        elif dp[i-1][j]:
            dp[i][j] += dp[i-1][j] * 2
            dp[i][j] %= mod
        if j - x < 0:
            continue
        if j - x == 0:
            dp[i][j] += pow(2, dp[i-1][j-x])
            dp[i][j] %= mod
        elif dp[i-1][j-x]:
            dp[i][j] += dp[i-1][j-x]
            dp[i][j] %= mod
print(dp[-1][-1])


### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 998244353
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, s = LI()
a = LI()

dp = [[0]*(s+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(1, n+1):
    x = a[i-1]
    for j in range(s+1):
        if j == 0:
            dp[i][j] += dp[i-1][j] + 1
            dp[i][j] %= mod
        elif dp[i-1][j]:
            dp[i][j] += dp[i-1][j] * 2
            dp[i][j] %= mod
        if j - x < 0:
            continue
        if j - x == 0:
            dp[i][j] += pow(2, dp[i-1][j-x], mod)
            dp[i][j] %= mod
        elif dp[i-1][j-x]:
            dp[i][j] += dp[i-1][j-x]
            dp[i][j] %= mod
print(dp[-1][-1])
### BUGGY CODE ###

import collections
n,m=map(int,input().split())
A=[]
for i in range(n):
  A.append([int(_) for _ in input().split()])
D=dict()
for i in range(m):
  D[i+1]=1
ans=n
for _ in range(m):
  p=[]
  for i in range(n):
    for j in range(m):
      if D[A[i][j]]==1:
        p.append(A[i][j])
        break
  a,b=collections.Counter(p).most_common()[0]
  if b<ans:
    ans=b
  D[a]=0
print(ans)

### FIXED CODE ###

import collections
n,m=map(int,input().split())
A=[]
for i in range(n):
  A.append([int(_) for _ in input().split()])
D=dict()
for i in range(m):
  D[i+1]=1
ans=n
for _ in range(m):
  p=[]
  for i in range(n):
    for j in range(m):
      if D[A[i][j]]==1:
        p.append(A[i][j])
        break
  pp=collections.Counter(p).most_common()
  a,b=pp[0]
  ans=min(ans,b)
  D[a]=0
print(ans)
### BUGGY CODE ###

S = input()
MOD = 10 ** 9 + 7
N = len(S)

dp = [[0 for _ in range(13)] for _ in range(N + 1)]
dp[0][0] = 1

for i in range(N):
    for j in range(0, 10):
        if (S[i] != '?' and S[i] != str(j)):
            continue
        for k in range(0, 13):
            dp[i + 1][(k * 10 + j) % 13] += dp[i][k]

    for j in range(0, 13):
        dp[i + 1][j] %= MOD

print(dp[N][5])


### FIXED CODE ###

S = input()
MOD = 10 ** 9 + 7
N = len(S)

dp = [[0 for _ in range(13)] for _ in range(N + 1)]
dp[0][0] = 1

for i in range(N):
    for j in range(0, 10):
        if (S[i] != '?' and S[i] != str(j)):
            continue
        for k in range(0, 13):
            dp[i + 1][(k * 10 + j) % 13] += dp[i][k]

    for j in range(0, 13):
        dp[i + 1][j] %= MOD

print(dp[N][5])
### BUGGY CODE ###

N, M = map(int, input().split())
 
hashset = None
 
for _ in range(M):
  L, R = map(int, input().split())
  if hashset is None:
    hashset = set(range(L, R+1))
  else:
    hashset = hashset & set(range(L, R+1))

print(len(hashset))

### FIXED CODE ###

N, M = map(int, input().split())
 
left, right = 1, N
 
for _ in range(M):
  L, R = map(int, input().split())
  
  left = max(L, left)
  right = min(R, right)

ans = right - left + 1 if left <= right else 0 
print(ans)
### BUGGY CODE ###

#

import sys
from math import ceil
input=sys.stdin.readline

def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    aveA=sum(A)/N
    K_i=[int(A[i]/aveA*K/N) for i in range(N)]
    dA=[A[i]/(K_i[i]+1) for i in range(N)]
    res=K-sum(K_i)
    for i in range(res):
        maxi=dA.index(max(dA))
        K_i[maxi]+=1
        dA[maxi]=A[maxi]/(K_i[maxi]+1)
    
    maxi=dA.index(max(dA))
    print(ceil(A[maxi]/(K_i[maxi]+1)))
    
    
    
if __name__=="__main__":
    main()


### FIXED CODE ###

#

import sys
from math import ceil
input=sys.stdin.readline

def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    aveA=sum(A)/N
    d=K/N
    K_i=[int(A[i]/aveA*d) for i in range(N)]
    dA=[A[i]/(K_i[i]+1) for i in range(N)]
    res=K-sum(K_i)
    b=[]
    for i in range(N):
        b.append([dA[i],i])
    b.sort(reverse=True)
    now=0
    for i in range(res):
        K_i[b[now][1]]+=1
        dA[b[now][1]]=A[b[now][1]]/(K_i[b[now][1]]+1)
        if dA[b[now][1]]<b[now+1][0]:
            now+=1
    
    maxi=dA.index(max(dA))
    print(ceil(A[maxi]/(K_i[maxi]+1)))
    
    
    
if __name__=="__main__":
    main()
### BUGGY CODE ###

N = int(input())
a = list(input().split())
for i in range(N):
    s = str(i + 1)
    print(a.count(s))


### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
li = [0] * N

for i in range(N-1):
    li[a[i]-1] = li[a[i]-1] + 1

for i in range(N):
    print(li[i])
### BUGGY CODE ###

txt = input()
txt_list = list(txt)

count = 0

while True:
    pre_count = count
    for i in range(len(txt)-1):
        if txt_list[i] == 'B' and txt_list[i+1] == 'W':
            tmp = txt_list[i]
            txt_list[i] = txt_list[i+1]
            txt_list[i+1] = tmp
            count += 1
    if pre_count == count:
        break

print(count)

### FIXED CODE ###

txt = input()
txt_list = list(txt)

num = 0
count = 0
for i in range(len(txt)):
    if txt_list[i] == 'W':
        count += i-num 
        num += 1

print(count)
### BUGGY CODE ###

import math
def P(n, r):
    return math.factorial(n)//math.factorial(n-r)
def C(n, r):
    return P(n, r)//math.factorial(r)
S = input()[::-1]
N = len(S)
cnt = [0]*(N+1)
ans = 0
keta = 1
for i in range(N):
    cnt[i] = (cnt[i-1] + int(S[i])*keta)%2019
    keta *= 10
cnt2 = [0]*2020
for i in cnt:
    cnt2[i] += 1
for i in cnt2:
    if i >= 2:
        ans += C(i,2)
print(ans)

### FIXED CODE ###

import math
def P(n, r):
    return math.factorial(n)//math.factorial(n-r)
def C(n, r):
    return P(n, r)//math.factorial(r)
S = input()[::-1]
N = len(S)
cnt = [0]*(N+1)
ans = 0
keta = 1
for i in range(N):
    cnt[i] = (cnt[i-1] + int(S[i])*keta)%2019
    keta *= 10
    keta %= 2019
cnt2 = [0]*2020
for i in cnt:
    cnt2[i] += 1
for i in cnt2:
    if i >= 2:
        ans += C(i,2)
print(ans)
### BUGGY CODE ###

a=0
S=input()
N=len(S)
for i in range(N-3):
  for j in range(i+3,N):
    A=int(S[i:j+1])
    if A%2019==0:
      a=a+1
print(a)

### FIXED CODE ###

ans=0
S=input()
a=len(S)
k=0
c=dict()
mod=2019
s=1
c[0]=1
for i in range(a):
  k+=(s*int(S[a-i-1]))
  k%=mod
  s*=10
  s%=mod
  if k in c:
    c[k]+=1
  else:
    c[k]=1
for i in c:
  ans+=c[i]*(c[i]-1)//2
print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
b, c = sorted(a)[-2:]
for i in range(n):
    print(b if a.index(c) == i else c)


### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
b, c = sorted(a)[-2:]
j = a.index(c)
for i in range(n):
    print((c, b)[i == j])
### BUGGY CODE ###

import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


N, Q = list(map(int, input().split()))
STX=[]
D=[]
for i in range(N):
    S, T, X = list(map(int, input().split()))
    STX.append((X, S, T))
STX = sorted(STX, key=lambda x: x[0])

for i in range(Q):
    D.append(int(input()))

skip = [-1]*Q

dist = [10000000000000]*Q

for (X, S, T) in STX:
    s = S - X
    t = T - X - 1
    a = bisect.bisect_left(D, s)
    b = bisect.bisect_right(D, t)
    #print(D)
    j = a
    while j < b:
        if skip[j] == -1:
            skip[j] = b
            dist[j] = X
            j+=1
        else:
            j=skip[j]



for i in range(Q):
    if dist[i] > 100000000000:
        print(-1)
    else:
        print(dist[i])


### FIXED CODE ###

import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


N, Q = list(map(int, input().split()))
STX=[]
D=[]
for i in range(N):
    S, T, X = list(map(int, input().split()))
    STX.append((X, S, T))
STX = sorted(STX, key=lambda x: x[0])

for i in range(Q):
    D.append(int(input()))

skip = [-1]*Q

dist = [-1]*Q

for X, S, T in STX:
    s = S - X
    t = T - X - 1
    a = bisect.bisect_left(D, s)
    b = bisect.bisect_right(D, t)
    #print(D)
    j = a
    while j < b:
        if skip[j] == -1:
            skip[j] = b
            dist[j] = X
            j+=1
        else:
            j=skip[j]


for i in range(Q):
    print(dist[i])
### BUGGY CODE ###

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

while True:
    t = max(arr) % min(arr)
    if t == 0:
        arr.pop(arr.index(max(arr)))
    else:
        arr[arr.index(max(arr))] = t
    
    if len(arr) == 1 or max(arr) == min(arr):
        print(min(arr))
        break

### FIXED CODE ###

n = int(input())
b = list(map(int,input().split()))
b.sort()
     
d = b[0] + 0
 
while len(b) > 1 :
    for i in range(1,len(b)) :
        b[i] = b[i] % b[0]
    if b.count(0) == len(b)-1 :
        d = b[0]
        break
    else :
        b.sort()
        for j in range(b.count(0)) :
            b.remove(0)
print(d)
### BUGGY CODE ###

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

mul = 1
for i in range(k):
    mul *= a[i]
pre = mul

ans = []
for i in range(k, n):
    mul *= a[i]
    mul //= a[i-k]
    if pre < mul:
        ans.append("Yes")
    else:
        ans.append("No")
    pre = mul
print("\n".join(ans))

### FIXED CODE ###

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

ans = []
for i in range(k, n):
    if a[i-k] < a[i]:
        ans.append("Yes")
    else:
        ans.append("No")
print("\n".join(ans))
### BUGGY CODE ###

import itertools

def read():
    N = int(input().strip())
    L = list(map(int, input().strip().split()))
    return N, L

def solve(N, L):
    L.sort()
    count = 0
    for a, b, c in itertools.combinations(L, 3):
        if c < a + b:
            count += 1
    return count

if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))


### FIXED CODE ###

import itertools
import bisect

def read():
    N = int(input().strip())
    L = list(map(int, input().strip().split()))
    return N, L

def solve(N, L):
    L.sort()
    x = 0
    t = [0 for _ in range(N+1)]
    for i in range(N):
        for j in range(i+1, N):
            k = bisect.bisect_left(L, L[i] + L[j])
            if j < k:
                x += (k - j - 1)
    return x

if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))
### BUGGY CODE ###

n,m=map(int,input().split())
a=[int(input()) for i in range(m)]

b=[0]*(n+1)
b[0]=1
MOD=(10**9)+7
  
if 1 not in a:
  b[1]=1
  
for j in range(2,n+1):
  if j not in a:
    b[j]=(b[j-1]+b[j-2])%MOD
    
print(b[n])    
    
  
  
  



### FIXED CODE ###

n,m=map(int,input().split())
mod=10**9+7
a=[0]*(n+1)
dp=[0]*(n+1)
dp[0]=1
for i in range(m):
    a[int(input())]=1
    
if a[1]==1:
    dp[1]=0
else:
    dp[1]=1
    
for j in range(2,n+1):
    if a[j]==0:
        dp[j]=dp[j-1]+dp[j-2] 
                  
print(dp[n]%mod)
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0
for i in range(10):
    for x in range(n):
        if (i==int(s[x])):
            for j in range(10):
                for y in range(x+1,n):
                    if (j==int(s[y])):
                        for k in range(10):
                            for z in range(y+1,n):
                                if (k==int(s[z])):
                                    ans += 1
                                    break
                        break
            break
        

print(ans)

### FIXED CODE ###

n = int(input())
s = input()
ans = 0
for i in range(10):
    for x in range(n):
        if (i==int(s[x])):
            for j in range(10):
                for y in range(x+1,n):
                    if (j==int(s[y])):
                        for k in range(10):
                            for z in range(y+1,n):
                                if (k==int(s[z])):
                                    ans += 1
                                    break
                        break
            break
        

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

#template
from collections import Counter
def inputlist(): return [int(j) for j in input().split()]
#template
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0

    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True

        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

N,X,Y = inputlist()
X-=1
Y-=1
ans = [0]*N
cost = [[float('inf') for _ in range(N)] for _ in range(N)]
for i in range(N):
    if i != N-1:
        cost[i][i+1] = 1
    if i != 0:
        cost[i][i-1] = 1
    if i == X:
        cost[X][Y] = 1
    if i == Y:
        cost[i][X] = 1
for i in range(N):
    ans[i] = dijkstra(i,N,N,cost)
li = [0]*(N)
for i in range(N):
    for j in range(N):
        li[ans[i][j]] +=1
for i in range(1,N):
    print(li[i]//2)

### FIXED CODE ###

#template
def inputlist(): return [int(j) for j in input().split()]
#template
#issueから始める
N,X,Y = inputlist()
graph = [[] for _ in range(N+1)]
for i in range(1,N):
    graph[i].append(i+1)
    graph[i+1].append(i)
graph[X].append(Y)
graph[Y].append(X)
seen = [False]*(N+1)
ans = [0]*(N+1)
def bfs(i):
    from collections import deque
    que = deque()
    que.append([i,0])
    seen[i] = True
    while len(que)!=0:
        li = que.popleft()
        x = li[0]
        count = li[1]
        for j in graph[x]:
            if seen[j]:
                continue
            seen[j] = True
            counta= count + 1
            que.append([j,counta])
            ans[counta]+=1
for i in range(1,N+1):
    seen = [False]*(N+1)
    bfs(i)
for i in range(1,N):
    print(ans[i]//2)
### BUGGY CODE ###

N=int(input())
print(0)
s=input()
if s=='Vacant':
  exit()
a=s
print(N-1)
s=input()
if s=='Vacant':
  exit()
left=0
right=N
while True:
  n=(left+right)//2
  print(n)
  s=input()
  if s=='Vacant':
    exit()
  if n%2!=0:
    if s==x:
      right=n
    else:
      left=n
  else:
    if s!=x:
      right=n
    else:
      left=n

### FIXED CODE ###

import sys
N=int(input())
print(0)
s=input()
a=s
if s=='Vacant':
  sys.exit()
left=0
right=N
while True:
  n=(left+right)//2
  print(n)
  s=input()
  if s=='Vacant':
    sys.exit()
  if n%2!=0:
    if s==a:
      right=n
    else:
      left=n
  else:
    if s!=a:
      right=n
    else:
      left=n
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=1
for i in range(n):
    ans*=a[i]
if ans>10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=1
if 0 in a:
    print(0)
    exit()
for i in range(n):
    ans*=a[i]
    if ans>10**18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

N,M,Q = map(int,input().split())
memo = [[0 for i in range(N)] for j in range(N)]
for i in range(M):
    l,r = map(int,input().split())
    memo[l-1][r-1] += 1
for i in range(N):
    for j in range(N):
        if i < j:
            memo[i][j] += memo[i][j-1] + sum(memo[j-k][j] for k in range(j-i))
for i in range(Q):
    p,q = map(int,input().split())
    print(memo[p-1][q-1])

### FIXED CODE ###

N,M,Q = map(int,input().split())
memo = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(M):
    l,r = map(int,input().split())
    memo[l][r] += 1
for i in range(N):
    for j in range(N):
        memo[i+1][j+1] += memo[i][j+1] + memo[i+1][j] - memo[i][j]
for i in range(Q):
    p,q = map(int,input().split())
    print(memo[q][q] - memo[p-1][q] - memo[q][p-1] + memo[p-1][p-1])
### BUGGY CODE ###

from math import factorial
from collections import Counter
mod = 10**9 + 7

n = int(input())
length = n+1
li = list(map(int,input().split()))

counter = Counter(li)
for k, v in counter.items():
    if v==2:
        dup = k
be, af = [i for i, x in enumerate(li) if x==dup]
soto = be + length - af - 1

for k in range(1, n+2):
    if k == 1:
        print(n)
    elif k == n+1:
        print(1)
    else:
        zyouhukuari = factorial(length) // (factorial(k)*factorial(length-k))
        if soto-k+1 >= 0:
            zyouhuku = factorial(soto) // (factorial(k-1)*factorial(soto-k+1))
        else:
            zyouhuku = 0
        val = zyouhukuari - zyouhuku
        print(val%mod)

### FIXED CODE ###

import collections

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

c = collections.Counter(a)
dup = c.most_common()[0][0]

id = [i for i, x in enumerate(a) if x == dup]
L = id[0]
R = id[1]

MOD = 10**9 +7
factorial = [1]
inverse = [1]

for i in range(1, N+2):
    factorial.append(factorial[i-1] * i % MOD)
    inverse.append(pow(factorial[i], MOD-2, MOD))
    

def C(n, r):
    if n < r:
        return 0
    return (factorial[n] * inverse[r] * inverse[n-r]) % MOD

print(N)
for i in range(2, N+2):
    ans = (C(N+1, i) - C(L+(N-R), i-1)) % MOD
    print(ans)
### BUGGY CODE ###

ab=[]
n,m = map(int,input().split())


for i in range(m):
    ab.append(tuple(map(int,input().split())))

abr=[]
enabled=set()
remain=set()
disabled=set()
for i in range(m):
    abr.append(range(ab[i][0],ab[i][1]))
    remain.add(i)
    disabled.add(i)


res=0
for i in range(1,n+1):
    for j in disabled:
        if i == abr[j][0]:
            enabled.add(j)
    for j in enabled:
        if i == abr[j][-1] and j in remain:
            res+=1
            remain-=enabled
            disabled=remain
            enabled-=enabled
            break


print(res)

### FIXED CODE ###

ab=[]

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

for i in range(m):
    ab.append(tuple(map(int,input().split())))

ab.sort(key=lambda x:x[1])

res=0
for z in range(len(ab)):
    x=ab[0][1]
    for j in range(len(ab)):
        if x > ab[0][0]:
            del ab[0]
        else:
            res+=1
            break
    if len(ab)==0:
        res+=1
        break
    
print(res)
### BUGGY CODE ###

import math
A,B,N = map(int, input().split())
c = 0
d = 0
for i in range(1,N+1):
	c = (math.floor(A * i / B))-(A * (math.floor(i / B)))
	if c>d:
		d=c
print(d)

### FIXED CODE ###

import math
A,B,N = map(int, input().split())
c = 0
if B > N:
	c = (math.floor(A * N / B))-(A * (math.floor(N / B)))
elif B <= N:
	c = (math.floor(A * (B-1) / B))-(A * (math.floor((B - 1) / B)))
print(c)
### BUGGY CODE ###

def dfs(num,count,ans):
    #print(num,count)
    ans=max(ans,count)
    for index,item in enumerate(l[num-1]):
        if item==1:
            dp[index+1]=max(dp[index+1],count)
            ans=dfs(index+1,count+1,ans)
    return ans
    
N,M=map(int,input().split())

l=[[0]*N for _ in range(N)]

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

for _ in range(M):
    x,y=map(int,input().split())
    l[x-1][y-1]=1
    try:
        start.remove(y)
    except:
        pass
#print(l)

dp=[0]*(N+1)
ans=0
for i in start:
    ans=max(dfs(i,0,0),ans)

#print(dp)
print(ans)
    

### FIXED CODE ###

# coding: utf-8
# Your code here!
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

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

linked=[[] for i in range(N)]

for _ in range(M):
    x,y=map(int,input().split())
    linked[x-1].append(y-1)



def saiki(num):
    if visited[num]==1:
        return dp[num]
    
    visited[num]=1
    value=0
    if linked[num]:
        for item in linked[num]:
            value=max(value,saiki(item)+1)
    dp[num]=value
    return value

dp=[0]*N
visited=[0]*N
ans=0
for i in range(N):
    ans=max(ans,saiki(i))

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

def solve():
    ans = 0
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for j in range(K):
        check = [0]*(N+1)
        for i in range(N):
            check[max(0,i-A[i])] += 1
            check[min(N,i+A[i]+1)] -= 1
        A = [check[0]]*N
        for i in range(1,N):
            A[i] = A[i-1]+check[i]
        if A==[N]*N:
            break
    return A
print(*solve())

### FIXED CODE ###

from copy import copy
def solve():
    ans = 0
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for j in range(K):
        check = [0]*(N+1)
        for i in range(N):
            check[max(0,i-A[i])] += 1
            check[min(N,i+A[i]+1)] -= 1
        B = [check[0]]*N
        for i in range(1,N):
            B[i] = B[i-1]+check[i]
        A = copy(B)
        if A==[N]*N:
            break
    return A
print(*solve())
### BUGGY CODE ###

import math
n, a, b = map(int, input().split())
d = []
for i in range(n):
    d.append(input())
# [d1, d2, d3, ..., dN]
h = [int(m) for m in d]#int型に直す
#print(x)

low = 0
high = math.ceil(max(h)/b)
def avg(a, b):
    return (a + b) // 2
# t は中央番目の数
t = avg(low, high)

# 探索の下限のlowが上限のhighになるまで探索
# lowがhighに達すると数は見つからなかっTrueたということ
X = 0
Y = 0
def cri(p):
    if p > 0:
        return p
    else:
        return 0
while True:
    for j in range(n):
        X += cri(math.ceil((h[j] - t * b) / (a - b)))
    if X <= t:
        for j in range(n):
            Y += cri(math.ceil((h[j] - (t - 1) * b) / (a - b)))
        if Y > t - 1:
            print(t)
            exit()
        else:
            high = t - 1
    elif X > t:
        low = t + 1
    t = avg(low, high)
    X = 0
    Y = 0

### FIXED CODE ###

import math
n, a, b = map(int, input().split())
d = []
for i in range(n):
    d.append(input())
# [d1, d2, d3, ..., dN]
h = [int(m) for m in d]#int型に直す
#print(x)

low = 0
high = math.ceil(max(h)/b)
# t は中央番目の数
t = (low + high) // 2

# 探索の下限のlowが上限のhighになるまで探索
# lowがhighに達すると数は見つからなかっTrueたということ
X = 0
Y = 0
s = 0
while high - low >= 0:
    for j in range(n):
        X += max(0, math.ceil((h[j] - t * b) / (a - b)))
        #Y += max(0, math.ceil((h[j] - (t - 1) * b) / (a - b)))
    if X == t:
        print(t)
        exit()
    elif X < t:
        high = t - 1
        """for j in range(n):
            Y += max(0, math.ceil((h[j] - (t - 1) * b) / (a - b)))"""
    elif X > t:
        low = t + 1
    s = t
    t = (low + high) // 2
    X = 0
    Y = 0
for j in range(n):
  if math.ceil((h[j] - s * b) / (a - b)) > 0:
            Y += math.ceil((h[j] - s * b) / (a - b))
if Y <= s:
  print(s)
else:
  print(s + 1)