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

import sys
def input():
	return sys.stdin.readline()[:-1]

BASE, MOD = 80408696819889532, (1<<61)-1

class RollingHash():
	def __init__(self, s, base, mod):
		self.mod = mod
		self.pw = pw = [1]*(len(s)+1)

		l = len(s)
		self.h = h = [0]*(l+1)

		v = 0
		for i in range(l):
			# case of letters
			h[i+1] = v = (v * base + ord(s[i])) % mod
		v = 1
		for i in range(l):
			pw[i+1] = v = v * base % mod

	# [l. r)
	def get(self, l, r):
		return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

	def concatenate(self, l1, r1, l2, r2):
		return (self.get(l1, r1) * self.pw[r2-l2] + self.get(l2, r2)) % self.mod

d = dict()
ans = 0
ss = [input() for _ in range(int(input()))]
zero = [0 for _ in range(26)]
ss.sort(key=lambda x: -len(x))
for s in ss:
	#print(s)
	n = len(s)
	rh = RollingHash(s, BASE, MOD)
	if n == 1:
		ans += zero[ord(s[0])-97]
	else:
		suff = rh.get(1, n)
		if suff in d:
			ans += d[suff][ord(s[0])-97]
		alph = [0 for _ in range(26)]
		alph[ord(s[0])-97] = 1
		for i in range(1, n-1):
			alph[ord(s[i])-97] = 1
			tmp = rh.get(i+1, n)
			if tmp in d:
				for i, a in enumerate(alph):
					d[tmp][i] += a
			else:
				d[tmp] = [0 for _ in range(26)]
				for i, a in enumerate(alph):
					d[tmp][i] += a
		alph[ord(s[n-1])-97] = 1
		for i, a in enumerate(alph):
			zero[i] += a
	#print(ans)
	#print(d, sep="\n")
print(ans)


### FIXED CODE ###

import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

BASE, MOD = 1999849216943526259, (1<<61)-1

d = dict()
ans = 0
ss = [str(input())[2:-1][::-1] for _ in range(int(input()))]
zero = [0 for _ in range(26)]
ss.sort(key=lambda x: -len(x))
for s in ss:
	n = len(s)
	if n == 1:
		ans += zero[ord(s[n-1])-97]
	else:
		hashes = [0 for _ in range(n-1)]
		hashes[0] = ord(s[0])
		for i in range(1, n-1):
			hashes[i] = (hashes[i-1] * BASE + ord(s[i])) % MOD
		if hashes[n-2] in d:
			ans += d[hashes[n-2]][ord(s[n-1])-97]
		alph = [0 for _ in range(26)]
		alph[ord(s[n-1])-97] = 1
		for i in range(n-2, 0, -1):
			alph[ord(s[i])-97] = 1
			if hashes[i-1] not in d:
				d[hashes[i-1]] = [0 for _ in range(26)]
			for j, a in enumerate(alph):
				d[hashes[i-1]][j] += a
		alph[ord(s[0])-97] = 1
		for j, a in enumerate(alph):
			zero[j] += a
print(ans)
### BUGGY CODE ###

import numpy as np

N,M,V,P = map(int,input().split())
A = [int(i) for i in input().split()]

#A = [[int(i),x]for x,i in enumerate(input().split())]


target = P

con = 0

for i in range(N):
  x = A[i]
  x = x + M
  Y = [k for k in A if k < x]
  c = A.count(x)
  y = len(Y)
  #振り分け範囲より、xの上限を下回る数が多い場合
  ##…xがAのなかでP番目に入れればカウントする
  if y > V - 1:
    bigger = N - y - c
    if target > bigger:
      con += 1
  #そうでなければ
  ##xの上限数を下回るYの数y個分振り分けた後
  ##xの上限数を同等または上回る値の個数zが、
  ##入っているべき順位より小さければカウントする
  else:
    z = N - y
    if V - y - 1 < z and target - 1 > z:
      con += 1


print(con)

### FIXED CODE ###

N,M,V,P = map(int,input().split())
A = sorted([int(i) for i in input().split()],reverse = True)

pps = 0
con = P

for i in range(P,N):
  #P以降でi番目に大きい数を加算
  pps += A[i - 1]

  #xの上限が順位に入らない
  if A[i] + M < A[P - 1]:
    break
  #点数をいくら振り分けてもいいスコアの数
  fv = min(P - 1 + N - i, V)
  #左辺第二項は、P以降とi以前の、点数の振り分け可能数に上限がある数
  #左辺は振り分けた後にA[i]がP入りを果たせる区間の総和の上限を示す
  #右辺第一項は、振り分け可能数に上限がある数の総和
  #右辺第二項は、振り分けないといけない数の残り
  #右辺は、点数を振り分けた後の値の区間の総和を示すため、
  #右辺が左辺を上回った場合、ループは終了となる
  if (A[i] + M) * (i - P + 1) < pps + M * (V - fv):
    break
  con += 1
  
print(con)
### BUGGY CODE ###

def MI():
    return map(int, input().split())

def LI():
    return list(map(int, input().split()))

# N = int(input())
# group = 0
# tmp = 0

# while tmp < N: 
#     tmp += 26**group
#     group += 1
    
# print(group)

from collections import Counter

N = int(input())
A = LI()
Q = int(input())
A_c = Counter(A)

for _ in range(Q):
    B, C = MI()
    tmp = A_c[B]
    A_c[B] = 0
    
    if B in A_c.keys():
        A_c[C] += tmp
    else:
        A_c[C] = tmp
    
    ans = 0
    
    
    for k, v in A_c.items():
        ans += k * v

    print(ans)

### FIXED CODE ###

def MI():
    return map(int, input().split())

def LI():
    return list(map(int, input().split()))

# N = int(input())
# group = 0
# tmp = 0

# while tmp < N: 
#     tmp += 26**group
#     group += 1
    
# print(group)

from collections import Counter

N = int(input())
A = LI()
ans = sum(A)
Q = int(input())
A_c = Counter(A)

for _ in range(Q):
    B, C = MI()
    tmp_B = A_c[B]
    tmp_C = A_c[C]
    A_c[B] = 0
    
    if B in A_c.keys():
        A_c[C] += tmp_B
    else:
        A_c[C] = tmp_B
    
    ans = ans - B * tmp_B + C * (A_c[C] - tmp_C)
    print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A, W = [], []
num, j = 0, 0

for i in range(M):
    P, S = map(str, input().split())
    if P not in A:
        if S == "AC":
            A.append(P)
            num += W.count(A[j])
            j += 1
        else:
            W.append(P)

print(len(A), num)


### FIXED CODE ###

N, M = map(int, input().split())
ac = [0]*N
wa = 0

for i in range(M):
    P, S = map(str, input().split())
    P = int(P)-1
    if ac[P] != 1 and S == "AC":
        wa += abs(ac[P])
        ac[P] = 1
    elif ac[P] != 1 and S == "WA":
        ac[P] -= 1

print(ac.count(1), wa)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
import sys
sys.setrecursionlimit(10 ** 5+1)
# import numpy as np
# import IPython

s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


N, M = ds_in()

to_par = {i: [] for i in range(1, N+1)}
to_chi = {i: [] for i in range(1, N+1)}
con_list = []
for _ in range(N - 1 + M):
    a, b = ds_in()
    to_par[b].append(a)


def find_all_parents(child):
    """
    child : int
    """
    all_parents = []
    for p in to_par[child]:
        all_parents.append(p)
        all_parents.extend(find_all_parents(p))
    all_parents = list(set(all_parents))
    return all_parents


parents_dict = {i: find_all_parents(i) for i in range(1, N+1)}

ans = {i: 0 for i in range(1, N+1)}
for child in range(1, N+1):
    par_cand = to_par[child]
    all_par = []
    for p in par_cand:
        all_par.extend(parents_dict[p])
    all_par = list(set(all_par))
    for p in par_cand:
        if p not in all_par:
            ans[child] = p
            break

for i in range(1, N+1):
    print(ans[i])


# IPython.embed()


### FIXED CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
# import sys
# sys.setrecursionlimit(10 ** 5+1)
import numpy as np
# import IPython

s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


N, M = ds_in()

child = {i+1: [] for i in range(N)}
parent = {i+1: [] for i in range(N)}
inflow = {i+1: 0 for i in range(N)}
for _ in range(N+M-1):
    a, b = ds_in()
    child[a].append(b)
    parent[b].append(a)
    inflow[b] += 1

candidates = []
for i, j in inflow.items():
    if j == 0:
        candidates.append(i)

sorted_edges = []
while len(sorted_edges) < N:
    par = candidates.pop()
    sorted_edges.append(par)
    for chi in child[par]:
        inflow[chi] -= 1
        if inflow[chi] == 0:
            candidates.append(chi)


sorted_index = np.zeros(N+1, dtype=int)
sorted_index[sorted_edges] = np.arange(N)

for i in range(1, N+1):
    if i == sorted_edges[0]:
        print(0)
    else:
        print(parent[i][np.argmax(sorted_index[parent[i]])])
### BUGGY CODE ###

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True
S=[]
for i in range(1,10**5):
  if is_prime(i) and is_prime((i+1)//2):
    S+=[i]

N=int(input())
for i in range(N):
  l,r = map(int,input().split())
  count=0
  for j in range(l,r+1):
    if j in S:
      count +=1
  print(count)

### FIXED CODE ###

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True
S=[]
for i in range(1,10**5):
  if is_prime(i) and is_prime((i+1)//2):
    S+=[i]
Count=[0]
count=0
for i in range(1,10**5):
  if i in S:
    count+=1
  Count +=[count]

N=int(input())
for i in range(N):
  l,r=map(int,input().split())
  print(Count[r]-Count[l-1])
### BUGGY CODE ###

from collections import defaultdict
import heapq as hq
from itertools import permutations
def dijkstra(E, D, start):
    q = []
    V = [-1]*N
    V[start] = 0
    for e in E[start]:
        hq.heappush(q, (D[start, e],e))
    while q:
        d, v = hq.heappop(q)
        if V[v] >= 0:
            continue
        V[v] = d
        for e in E[v]:
            if V[e] == -1:
                hq.heappush(q, (D[v,e]+d, e))
    return V
N, M, r = map( int, input().split())
R = list( map( int, input().split()))
d = defaultdict( int)
E = [ [] for _ in range(N)]
for _ in range(M):
    a, b, c = map( int, input().split())
    a, b = a-1, b-1
    d[(a,b)] = d[(b,a)] = c
    E[a].append(b)
    E[b].append(a)
W = [ dijkstra(E,d,i) for i in range(N)]
ans = 10**9
for P in permutations( range(r)):
    now = R[P[0]]-1
    cans = 0
    for i in range(1,r):
        cans += W[now][R[P[i]]-1]
        now = R[P[i]]-1
    if cans < ans:
        ans = cans
print( ans)

### FIXED CODE ###

from collections import defaultdict
import heapq as hq
from itertools import permutations
def dijkstra(E, D, start,W):
    q = []
    V = [-1]*N
    V[start] = 0
    # for i in range(start):
    #     V[i] = W[i][start]
    #     for e in E[i]:
    #         if e > start:
    #             hq.heappush(q, (V[i] + D[(i,e)], e))
    for e in E[start]:
        if V[e] == -1:
            hq.heappush(q, (D[start, e],e))
    # print(V, q)
    while q:
        d, v = hq.heappop(q)
        if V[v] >= 0:
            continue
        V[v] = d
        for e in E[v]:
            if V[e] == -1:
                hq.heappush(q, (D[v,e]+d, e))
    return V
N, M, r = map( int, input().split())
R = list( map( int, input().split()))
d = defaultdict( int)
E = [ [] for _ in range(N)]
for _ in range(M):
    a, b, c = map( int, input().split())
    a, b = a-1, b-1
    d[(a,b)] = d[(b,a)] = c
    E[a].append(b)
    E[b].append(a)
W = [ [-1]*N for i in range(N)]
# for i in range(N):
#     W[i] = dijkstra(E,d,i,W)
    # print(W)
for i in range(r):
    W[R[i]-1] = dijkstra(E,d,R[i]-1,W)

ans = 10**9
for P in permutations( range(r)):
    now = R[P[0]]-1
    cans = 0
    for i in range(1,r):
        cans += W[now][R[P[i]]-1]
        now = R[P[i]]-1
    if cans < ans:
        ans = cans
print( ans)
### BUGGY CODE ###

from collections import *
import sys
input = sys.stdin.readline

#n以下の素数列挙(O(n log(n))
def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass


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

pr = primes(10**6+1)

d = defaultdict(lambda : 0)

for elt in a:
    for p in pr:
        if elt < p:
            break
        c = 0
        while not elt%p:
            c += 1
            elt //= p
        if c > d[p]:
            d[p] = c
    if elt > 1 and d[elt] == 0:
        d[elt] = 1



lcm  = 1
for elt in d:
    lcm = lcm*pow(elt,d[elt],mod)%mod

res = 0
for e in a:
    res = (res + pow(e,mod-2,mod))%mod
print(res*lcm%mod)



### FIXED CODE ###

#a,bの最大公約数
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

#a,bの最小公倍数
def lcm(a, b):
	return a * b // gcd (a, b)


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

l = a[0]
for e in a:
    l = lcm(l,e)

a_sum = 0
for e in a:
    a_sum = (a_sum + pow(e,mod-2,mod))%mod

print((l%mod)*a_sum%mod)
### BUGGY CODE ###

import collections
N=int(input())
L=list(map(int,input().split()))
l=[]
L.sort()
lis=[0]*(max(L)+1)
cnt=0
ans=0
c=collections.Counter(L)
values=list(c.values())	#aのCollectionのvalue値のリスト(n_1こ、n_2こ…)
key=list(c.keys())	#先のvalue値に相当する要素のリスト(要素1,要素2,…)
l1=0
l2=0
mi=0
ma=0
le=0
for i in range(len(key)):
    l.append([key[i],values[i]])#lは[要素i,n_i]の情報を詰めたmatrix
l.sort(key=lambda x:x[0])
#print(lis,L)
for i in range(max(L)+1):
    #print(cnt)
    cnt=cnt+c[i]
    lis[i]=cnt
for i in range(len(L)-1):
    for j in range(i+1,len(L)):
        l1=L[i]
        l2=L[j]#l1<=l2
        ma=min(l1+l2-1,max(L))
        mi=max(l2-l1+1,min(L))
        le=lis[ma]-lis[mi-1]
        if mi<=l1<=ma:
            le=le-1
        if mi<=l2<=ma:
            le=le-1
        #print(l1, l2,c[l1],c[l2],ma,mi,le)
        ans=ans+c[l1]*c[l2]*max(le,0)
print(ans//3)



### FIXED CODE ###

import collections
N=int(input())
L=list(map(int,input().split()))
l=[]
L.sort()
lis=[0]*(max(L)+1)
cnt=0
ans=0
c=collections.Counter(L)
values=list(c.values())	#aのCollectionのvalue値のリスト(n_1こ、n_2こ…)
key=list(c.keys())	#先のvalue値に相当する要素のリスト(要素1,要素2,…)
l1=0
l2=0
mi=0
ma=0
le=0
for i in range(len(key)):
    l.append([key[i],values[i]])#lは[要素i,n_i]の情報を詰めたmatrix
l.sort(key=lambda x:x[0])
#print(lis,L)
for i in range(max(L)+1):
    #print(cnt)
    cnt=cnt+c[i]
    lis[i]=cnt
for i in range(len(L)-1):
    for j in range(i+1,len(L)):
        l1=L[i]
        l2=L[j]#l1<=l2
        ma=min(l1+l2-1,L[len(L)-1])
        mi=max(l2-l1+1,L[0])
        le=lis[ma]-lis[mi-1]
        if mi<=l1<=ma:
            le=le-1
        if mi<=l2<=ma:
            le=le-1
        #print(l1, l2,c[l1],c[l2],ma,mi,le)
        ans=ans+max(le,0)
print(ans//3)
### BUGGY CODE ###

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

dp = [[[[0 for _ in range(K + 1)] for _ in range(2)] for _ in range(K + 1)] for _ in range(N - K + 1)]
for r in range(N - K + 1):
    for b in range(K + 1):
        for i in range(K + 1):
            if b == 0 and i == 0:
                dp[r][b][0][i] = 1
                dp[r][b][1][i] = 1
            if r > 0:
                dp[r][b][0][i] = (dp[r-1][b][0][i] + dp[r-1][b][1][i]) % mod
            if b > 0 and i > 0:
                dp[r][b][1][i] = (dp[r][b-1][0][i-1] + dp[r][b-1][1][i]) % mod

for i in range(1, K+1):
    print(dp[N-K][K][1][i])


### FIXED CODE ###

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

from math import factorial

# comb init
nmax = 2000 + 1  # change here
fac = [0] * (nmax + 1)
finv = [0] * (nmax + 1)
inv = [0] * (nmax + 1)
fac[0] = 1
fac[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
for i in range(2, nmax):
    fac[i] = fac[i - 1] * i % mod
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    finv[i] = finv[i - 1] * inv[i] % mod


def comb(n, r):
    if n < r:
        return 0
    else:
        return (fac[n] * ((finv[r] * finv[n - r]) % mod)) % mod


r = N - K
for b in range(1, K+1):
    print((comb(r+1, b) * comb(K - 1, b - 1)) % mod)
### BUGGY CODE ###

# -*- coding:utf-8 -*-


def solve():
    """ TLE """
    X, Y, Z, K = list(map(int, input().split(" ")))
    A = list(map(int, input().split(" ")))
    B = list(map(int, input().split(" ")))
    C = list(map(int, input().split(" ")))

    ans = []

    for x in range(X):
        for y in range(Y):
            for z in range(Z):
                abc = A[x]+B[y]+C[z]
                if len(ans) < K-1:
                    ans.append(abc)
                    continue
                elif len(ans) == K-1:
                    ans.append(abc)
                    ans.sort(reverse=True)
                    continue
                
                if abc > ans[-1]:
                    ans[-1] = abc
                    ans.sort(reverse=True)
                    continue

    
    for i in range(0, K):
        print(ans[i])


if __name__ == "__main__":
    solve()


### FIXED CODE ###

# -*- coding:utf-8 -*-

def solve():
    """ TLE """
    X, Y, Z, K = list(map(int, input().split(" ")))
    A = list(map(int, input().split(" ")))
    B = list(map(int, input().split(" ")))
    C = list(map(int, input().split(" ")))
    A.sort(reverse=True)
    B.sort(reverse=True)
    C.sort(reverse=True)

    ans = []

    for x in range(X):
        for y in range(Y):
            ab = A[x] + B[y]
            for z in range(Z):
                if (x+1)*(y+1)*(z+1) > K:
                    break

                ans.append(ab + C[z])

    ans.sort(reverse=True)              
    
    for i in range(0, K):
        print(ans[i])


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

N = int(input())
tree = [list() for _ in range(N)]
for _ in range(N-1):
    u, v, w = map(int, input().split())
    tree[u-1].append((v-1, w))
    tree[v-1].append((u-1, w))
stack = [0]
ans = [0] * N
searched = [False] * N
while stack:
    node = stack.pop()
    for v, w in tree[node]:
        if not searched[v]:
            searched[v] = True
            if w % 2 != 0:
                ans[v] = ans[node] ^ 1
            else:
                ans[v] = ans[node]
        stack.append(v)
print(*ans, sep='\n')


### FIXED CODE ###

n = int(input())
tree = [list() for _ in range(n)]
ans = [1] * n
for _ in range(n-1):
    u, v, w = map(int, input().split())
    tree[u-1].append((v-1, w))
    tree[v-1].append((u-1, w))

stack = [0]
judge = [False] * n
while stack:
    node = stack.pop()
    judge[node] = True
    for snode, distance in tree[node]:
        if judge[snode]:
            continue
        if distance % 2 != 0:
            ans[snode] = ans[node] ^ 1
        else:
            ans[snode] = ans[node]
        stack.append(snode)
print(*ans, sep='\n')
### BUGGY CODE ###

from collections import deque
def main():
    H,W = map(int,input().split())
    masu = [list(input()) for _ in range(H)]
    def bfs():
        que = deque()
        seen = [[0]*(W+2)] + [[0] + [1]*(W)+[0]  for _ in range(H)] +[[0]*(W+2)] 
        for w in range(W):
            for h in range(H):
                if masu[h][w] == '#':
                    que.append((w,h,0))
                    seen[h+1][w+1] =0
        while que:
            a,b,k = que.popleft()
            for x,y in [[0,1],[1,0],[0,-1],[-1,0]]:
                nx = a+x
                ny = b+y
                if seen[ny+1][nx+1]:
                    seen[ny+1][nx+1] = 0
                    que.append((nx,ny,k+1))
        return k
    print(bfs())
if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import deque
 
def solve(h, w, a):
    used = [[True] * (w+2) for _ in range(h+2)]
    que = deque()
    for r in range(h):
        used[r+1][1:-1] = map(lambda _:_=="#", a[r])
        for c in range(w):
            if a[r][c] == "#":
                que.append((r+1, c+1, 0))
    neighbors = [(1,0), (0,1), (-1,0), (0,-1)]
    while que:
        r, c, k = que.popleft()
        for dr, dc in neighbors:
            nr, nc = r+dr, c+dc
            if not used[nr][nc]:
                que.append((nr, nc, k+1))
                used[nr][nc] = True
    return k
 
h, w = map(int, input().split())
a = [input() for _ in range(h)]
print(solve(h, w, a))
### BUGGY CODE ###

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

count_min = x * a + y * b
for p_a in range(x + 1):
    for p_b in range(y + 1):
        for p_ab in range(max(x, y) * 2 + 1):
            if p_a + 0.5 * p_ab == x and p_b + 0.5 * p_ab == y:
                count = p_a * a + p_b * b + p_ab * c
                if count < count_min:
                    count_min = count

print(count_min)

### FIXED CODE ###

a, b, c, x, y = map(int, input().split())
 
ans_min = x * a + y * b
for i in range(100001):
    ans = i * 2 * c + max(0, x - i) * a + max(0, y - i) * b
    if ans < ans_min:
        ans_min = ans
 
print(ans_min)
### BUGGY CODE ###

def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    C = [int(input()) for _ in range(N)]

    dp = [1] * (N + 1)
    dp[0] = 1
    D = {c: set() for c in set(C)}
    pre = -1
    for n in range(N):
        c = C[n]
        S = D[c]
        dp[n + 1] = dp[n]
        if pre == c:
            dp[n] = 0
            continue

        if len(S) != 0:
            dp[n + 1] = (dp[n + 1] + sum(dp[s] for s in S)) % mod
        D[c].add(n)
        pre = c
    print(dp[-1])


if __name__ == "__main__":
    main()


### FIXED CODE ###

def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def main():
    mod = 10 ** 9 + 7
    N = int(input())

    dp = [1] * (N + 1)
    dp[0] = 1
    D = {}
    pre = -1
    for n in range(N):
        c = int(input())
        dp[n + 1] = dp[n]
        if pre == c:
            dp[n] = 0
            continue
        r = D.setdefault(c, 0)
        dp[n + 1] = (dp[n + 1] + r) % mod
        D[c] = r + dp[n]
        pre = c
    print(dp[-1])


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

# 累積和

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

dp = [1] * (M+1)
dpleft = [0] * (M)
MOD = 10 ** 9 + 7

for n in range(N):
    ndp = [1]
    for m in range(M):
        if S[n] == T[m]:
            ndp.append(ndp[-1] + dp[m+1])
            dpleft[m] = dp[m+1]
        else:
            ndp.append(ndp[-1] + dpleft[m])
    dp = ndp
print(dp[-1] % MOD)


### FIXED CODE ###

N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
dp = [1] * (M+1)
dpleft = [0] * (M)
MOD = 10 ** 9 + 7
ndp = [1] * (M+1)
for n in range(N):
    for m in range(M):
        if S[n] == T[m]:
            ndp[m+1] = ndp[m] + dp[m+1]
            dpleft[m] = dp[m+1]
        else:
            ndp[m+1] = ndp[m] + dpleft[m]
    dp = ndp[:]
print(dp[-1] % MOD)
### BUGGY CODE ###

from collections import deque
S=deque(input())
Q=int(input())
h=0
for i in range(Q):
    q=input().split()
    if q[0]=="1":
        h=1-h
    else:
        t=int(q[1])
        if t==h+1:
            S.appendleft(q[2])
        else:
            S.append(q[2])
if h==0:
    for i in S:
        print(i,end="")
else:
    for i in range(len(S)):
        print(S[-i-1],end="")

### FIXED CODE ###

from collections import deque
S=deque(input())
Q=int(input())
h=0
for i in range(Q):
    q=input().split()
    if q[0]=="1":
        h=1-h
    else:
        t=int(q[1])
        if t==h+1:
            S.appendleft(q[2])
        else:
            S.append(q[2])
if h==0:
    for i in S:
        print(i,end="")
else:
    for i in range(len(S)):
        print(S[-i-1],end="")
### BUGGY CODE ###

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

### FIXED CODE ###

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

from copy import deepcopy
from math import ceil
N, A, B = map(int, input().split())
H = [int(input()) for i in range(N)]

A -= B  # 爆発は追加ダメージ扱いとする

# にぶたん
ok, ng = 10 ** 9, 0
while abs(ok - ng) > 1:
    X = (ok + ng) // 2

    h = deepcopy(H)
    h = [max(hi - B * X, 0) for hi in h]
    h = [ceil(hi / A) for hi in h]

    if sum(h) <= X:
        ok = X
    else:
        ng = X

print(ok)


### FIXED CODE ###

import math

N, A, B = map(int, input().split())
H = [int(input()) for i in range(N)]

add_damage = A-B
left = 1
right = 10**9
ans = float('inf')

for i in range(int(math.log(10**9, 2)+1)):
    T = (left+right) // 2
    h = H.copy()
    h = list(map(lambda x: max(0, x-T*B), h))
    h = list(map(lambda x: math.ceil(x / add_damage), h))
    need = sum(h)
    
    if need <= T:
        right = T
        ans = min(ans, T)
    else:
        left = T

print(int(ans))