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

def main():
    import heapq
    hpop=heapq.heappop
    hpush=heapq.heappush
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    h = []
    h2 = []
    h2a=h2.append
    heapq.heapify(h)
    for i in range(n):
        hpush(h, (-b[i], i))
    cnt = 0
    while h:
        i, j = hpop(h)
        i=-i
        temp = i-a[j]
        temp2=b[j-1]+b[(j+1)%n]
        sho=temp//temp2
        if  sho==0:
            h2a((i, j))
            continue
        cnt += sho
        b[j] -= temp2*sho
        hpush(h, (-b[j], j))
    h2.sort(key=lambda x: x[1])
    for i in range(n):
        if a[i] != h2[i][0]:
            print(-1)
            return 0
    print(cnt)


main()

### FIXED CODE ###

def main():
    from heapq import heappop as hpop
    from heapq import heappush as hpush
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    h = []
    for i in range(n):
        hpush(h, (-b[i], i))
    cnt = 0
    while h:
        i, j = hpop(h)
        i = -i
        jj = (j+1) % n
        temp = i-a[j]
        temp2 = b[j-1]+b[jj]
        sho = temp//temp2
        if sho == 0:
            if temp:
                print(-1)
                return 0
            continue
        cnt += sho
        b[j] -= temp2*sho
        hpush(h, (-b[j], j))
    print(cnt)
main()
### BUGGY CODE ###

import sys
from collections import deque
import numpy as np
input = sys.stdin.readline
h, w = [int(x) for x in input().strip().split()]
g = np.array([[int(x == '#') for x in input().strip()] for _ in range(h)])

ans = -1
q = deque([])
for i in range(h):
    for j in range(w):
        if g[i, j]:
            q.append((i, j))
vec = [(0, 1), (1, 0), (0, -1), (-1, 0)]

while q:
    q_ = q
    q = deque([])
    ans += 1
    while q_:
        i, j = q_.pop()
        for x, y in vec:
            ti, tj = i+x, j+y
            if 0 <= ti < h and 0 <= tj < w:
                if g[ti, tj] == 0:
                    g[ti, tj] = 1
                    q.append((ti, tj))
print(ans)


### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
h, w = [int(x) for x in input().strip().split()]
g = [[x for x in list(input().strip())] for _ in range(h)]

ans = -1
q = []
for i in range(h):
    for j in range(w):
        if g[i][j] == '#':
            q.append((i, j))
vec = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while q:
    q_ = deque(q)
    q = deque([])
    ans += 1
    while q_:
        i, j = q_.pop()
        for x, y in vec:
            ti, tj = i+x, j+y
            if 0 <= ti < h and 0 <= tj < w:
                if g[ti][tj] == '.':
                    g[ti][tj] = '#'
                    q.append((ti, tj))
print(ans)
### BUGGY CODE ###

n, k, q = input().split()
N = int(n)
K = int(k)
Q = int(q)
Q_list = []
for i in range(Q):
    Q_list.append(int(input()))

for i in range(N):
    p = K - len([a for a in Q_list if not a == i + 1])
    if p <= 0:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

n, k, q = input().split()
N = int(n)
K = int(k)
Q = int(q)
Q_list = [0] * N
for i in range(Q):
    num = int(input())
    Q_list[num - 1] += 1

for i in range(N):
    p = K - (Q - Q_list[i])
    if p <= 0:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

import math
number, jump =input().rstrip().split()
number = int(number)
jump = int(jump)
scaffolding = input().rstrip().split()
scaffolding = list(map(int, scaffolding))
res = [math.inf for i in range(number)]
res[0] =0 
for i in range(number):
    for j in range(1,jump+1):
        if i-j < 0:break
        cost = abs(scaffolding[i]-scaffolding[i-j])
        res[i]=min(res[i],res[i-j]+cost)

print(res[number-1])


### FIXED CODE ###

import math
import sys
input = sys.stdin.readline
number, jump =input().rstrip().split()
number = int(number)
jump = int(jump)
scaffolding = input().rstrip().split()
scaffolding = list(map(int, scaffolding))
res = [0 for i in range(number)]
res[1] = abs(scaffolding[1]-scaffolding[0])
#test = [math.inf for k in range(jump)]
#test[0] = 0

for i in range(2, number):
    h=max(0,i-jump)
    res[i]=min(res[k]+abs(scaffolding[i]-scaffolding[k]) for k in range(h,i))   
    #res[i] = min(test)
    

print(res[number-1])
### BUGGY CODE ###


def main():
    N = int(input())
    S = input()

    dp = [[0 for _ in range(N+10)] for _ in range(N+10)]
    ans = 0
    for i in reversed(range(N)):
        for j in reversed(range(i+1,N)):
            if S[i] != S[j]:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i+1][j+1] + 1
            if i >= j: continue
            tmp = min(dp[i][j], j-i)
            ans = max(ans, tmp)


    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###


def main():
    N = int(input())
    S = input()
    ans = 0

    """
    他言語ならこれで行けるはずだが、pythonだとTLE
    dp = [[0 for _ in range(N+10)] for _ in range(N+10)]
    for i in reversed(range(N)):
        for j in reversed(range(i+1,N)):
            if S[i] != S[j]:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i+1][j+1] + 1
            if i >= j: continue
            tmp = min(dp[i][j], j-i)
            ans = max(ans, tmp)
    """
    i = j = 0

    while  j <= N-1:
        # 頭から見ていき、部分文字列が、その後ろのどこかにあれば範囲を広げる。かぶってはいけないのでj-iが最大
        if S[i:j] in S[j:]:
            ans = max(ans, j-i)
            j += 1
        else:
            i += 1
        

    print(ans)

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

def main():
    n = [int(i) for i in input().split()]
    bridge = []
    counter = 0
    reqs = [[int(j) for j in input().split()] for i in range(n[1])]
    reqs.sort(key=lambda x:(x[0],x[1]))
    prefix = 0
    
    for i in range(1, n[0]+1):
        if i in bridge:
            bridge = []
            counter += 1
        for j in range(prefix, len(reqs)):
            if reqs[j][0] == i:
                bridge.append(reqs[j][1])
            else:
                prefix = j
                break
    
    print(counter)
 
main()

### FIXED CODE ###

def main():
    n = [int(i) for i in input().split()]
    bridge = set()
    counter = 0
    reqs = [[int(j) for j in input().split()] for i in range(n[1])]
    reqs.sort(key=lambda x:(x[0],x[1]))
    prefix = 0
    
    for i in range(1, n[0]+1):
        if i in bridge:
            bridge.clear()
            counter += 1
        for j in range(prefix, len(reqs)):
            if reqs[j][0] == i:
                bridge.add(reqs[j][1])
            else:
                prefix = j
                break
    
    print(counter)
 
main()
### BUGGY CODE ###

from scipy.misc import comb
from sys import stdin
N = int(stdin.readline().rstrip())
A = [int(_) for _ in stdin.readline().rstrip().split()]
A.sort()
max_a = A[-1]
A.pop(N-1)
ans = 0
ans_a = 0
for a in A:
    tmp = comb(max_a, a, exact=True)
    if tmp > ans:
        ans = tmp
        ans_a = a
print(max_a, ans_a)

### FIXED CODE ###

from sys import stdin
N = int(stdin.readline().rstrip())
A = [int(_) for _ in stdin.readline().rstrip().split()]
A.sort()
max_a = A[-1]
print(max_a, min(A, key=lambda a:abs(max_a-a*2)))
### BUGGY CODE ###

K = int(input())
S = input()
X = len(S)
mod = 10**9+7

temp = pow(26,K,mod)
ans = pow(26,K,mod)

Y = 25*pow(26, mod-2, mod)

for i in range(X+1,K+X+1):
   
    temp *= Y
    temp %= mod
    
    temp *= i-1
    temp %= mod
    
    temp *= pow(i-X, mod-2, mod)
    temp %= mod    

    ans += temp
    ans %= mod

print(ans)

### FIXED CODE ###

K = int(input())
S = input()
X = len(S)
mod = 10**9+7

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

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

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

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod


A = 0
B = K
temp = cmb(A+X-1,X-1,mod)*power(25,A,mod)
temp %= mod
temp *= power(26,B,mod)
temp %= mod

ans = temp

for i in range(X+1,K+X+1):

    temp *= 25
    temp %= mod
    
    temp *= pow(26, mod-2, mod)
    temp %= mod
    
    temp *= i-1
    temp %= mod
    
    temp *= pow(i-X, mod-2, mod)
    temp %= mod    

    ans += temp
    ans %= mod

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

def xor(a, b):
    ab = "{0:020b}".format(a)
    bb = "{0:020b}".format(b)
    r = ""
    for i in range(20):
        if ab[i] == bb[i]:
            r += "0"
        else:
            r += "1"
    return int(r, 2)


def D(n, a):
    n = len(a)
    count = 0
    
    l = 0
    r = 0
    
    x = 0
    sum = 0
    for l in range(n):
        while r < n:
            if xor(x, a[r]) == sum + a[r]:
                sum += a[r]
                x = sum
                r += 1
            else:
                break
        
        #print(l, r - 1, x, sum)
        count += r - l
        x = xor(x, a[l])
        sum -= a[l]
        
    return count

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

### FIXED CODE ###

def D(n, a):
    n = len(a)
    count = 0
    
    l = 0
    r = 0
    
    sum = 0
    for l in range(n):
        while r < n:
            if sum & a[r] == 0:
                sum += a[r]
                x = sum
                r += 1
            else:
                break
        count += r - l
        sum -= a[l]
        
    return count

n = int(input())
a = list(map(int, input().split()))
print(D(n, a))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
a_sum=[0]
s=0
for ai in a:
    s+=ai
    a_sum.append(s)
# print(a_sum)
k=[[0]*20 for i in range(n)]
for i in range(n):
    for j in range(20):
        k[i][j] = 1 if (a[i] % 2**(j+1)) >= 2**j else 0
a_xor=[[0]*20]
s=[0]*20
for ki in k:
    xori=[]
    for j in range(20):
        xori.append((s[j]+ki[j]) % 2)
    a_xor.append(xori)
    s=xori
# print(a_xor)
# 2 5 4 6 -> 2 7 3 5
ans=0
for l in range(1,n+1):
    for r in range(l,n+1):
        xor = sum([((a_xor[l-1][i]+a_xor[r][i]) % 2) * 2**i for i in range(20)])
        if a_sum[r]-a_sum[l-1]==xor:
            ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
l=0
r=0
now=0
ans=[0]*n
while l < n:
    if r < n and now^a[r] == now + a[r]:
        now += a[r]
        ans[l]=r
        r+=1
    else:
        now -= a[l]
        l+=1
        ans[l-1]=r-1
print(sum([ans[i]-i+1 for i in range(n)]))
### BUGGY CODE ###

mod = 1000000007
n = int(input())
a = list(map(int,input().split()))
import itertools
b = list(itertools.combinations(a, 2))
#print(b)
for i in range(len(b)):
    b[i] = (b[i][0]*b[i][1])%mod
print(sum(b)%mod)

### FIXED CODE ###

mod = 1000000007
n = int(input())
a = list(map(int,input().split()))
ans = 0
b = sum(a)
for i in range(n-1):
    b = b-a[i]
    ans += (a[i]*(b))%mod
print(ans%mod)
### BUGGY CODE ###

K, S = map(int, input().split())

a = []
ans = 0
for i in range(K + 1):
    for j in range(i + 1):
        for k in range(j + 1):
            # print(i, j, k)
            if i + j + k == S:
                tmp = [i, j, k]
                a.append(tmp)

                length = len(set(tmp))
                if length == 3:
                    ans += 6
                elif length == 2:
                    ans += 3
                else:
                    ans += 1

print(ans)


### FIXED CODE ###

K, S = map(int, input().split())

# a = []
ans = 0
for i in range(K + 1):
    for j in range(i + 1):
        k = S - i - j
        if k >= 0 and k <= j:
            # print(i, j, k)
            if i == j and j == k:
                ans += 1
            elif i == j or j == k:
                ans += 3
            else:
                ans += 6

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

import sys

sys.setrecursionlimit(10**5)

words = lambda t : list(map(t, input().split()))
n,q = words(int)
edges = [[] for _ in range(n)]
for i in range(n-1):
    a,b = words(int)
    edges[a-1].append(b-1)

points = [0] * n
for i in range(q):
    p,x = words(int)
    points[p-1] += x

ans = [0] * n
def digTree(edges, points, cur, sum_p):
    #print("debug: ", cur, sum_p)
    sum_pp = sum_p +  points[cur]
    ans[cur] = sum_pp
    for child in edges[cur]:
        digTree(edges, points, child, sum_pp)

digTree(edges, points, 0, 0)
print(" ".join(map(str,ans)))


### FIXED CODE ###

import sys

sys.setrecursionlimit(10**6 + 1000)


words = lambda t : list(map(t, input().split()))
n,q = words(int)
par = [0] * n
for i in range(n-1):
    a,b = words(int)
    par[b-1] = a-1

points = [0] * n
for i in range(q):
    p,x = words(int)
    points[p-1] += x

ans = [0] * n
ans[0] = points[0]
for i in range(1,n):
    ans[i] = ans[par[i]] + points[i]


print(" ".join(map(str,ans)))
### BUGGY CODE ###

s=list(input())


l=0
r=len(s)-1

count=0
while True:
    #print(s,l,r)
    if s[l]!=s[r]:
        if s[l]=="x":
            s.insert(r+1,"x")
            l+=1
        elif s[r]=="x":
            s.insert(l,"x")
            #r-=1
            l+=1
        else:
            res=-1
            break

        #print(s,l,r)


        count+=1
    else:
        r-=1
        l+=1

    if l>=r:
        res=count
        break


print(res)

### FIXED CODE ###


s=list(input())


l=0
r=len(s)-1

count=0
while True:
    #print(s,l,r)
    if s[l]!=s[r]:
        if s[l]=="x":
            #s.insert(r+1,"x")
            l+=1
        elif s[r]=="x":
            #s.insert(l,"x")
            r-=1
            #l+=1
        else:
            res=-1
            break

        #print(s,l,r)


        count+=1
    else:
        r-=1
        l+=1

    if l>=r:
        res=count
        break


print(res)
### BUGGY CODE ###

from collections import deque
H,W = map(int,input().split())
maze = []
for i in range(H):
    maze.append(input())
q = deque()
saitan = [1000000]*H*W
for i in range(H):
    for k in range(W):
        if maze[i][k] == '#':
            q.append(i*W+k)
            saitan[i*W+k] = 0
len_q = len(q)

#print(start)
def bfs(h,w,q,Saitan,len_Q):
    
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while len(q)>0 and len_Q < h * w:
        j = q.popleft()
        y = int(j/w)
        x = j%w
        #print(saitan)
        for k in range(4):
            my = y + dy[k]
            mx = x + dx[k]
            #print(sx,sy,j,x,y,mx,my)
            if not((0 <=my <= h-1) and (0 <= mx <= w-1)):
                #print('q')
                continue
            if saitan[(my*w + mx)] <= saitan[y*w + x] + 1:
                #print('c')
                continue
                
            saitan[(my*w + mx)] = saitan[y*w + x] + 1
            q.append(my*w + mx)
            len_Q += 1
            #Sumi.append(my*w + mx)
    return max(saitan)

print(bfs(H,W,q,saitan,len_q))
#print(saitan)

### FIXED CODE ###

from collections import deque
H,W = map(int,input().split())
maze = []
for i in range(H):
    maze.append(input())
q = deque()
saitan = [1000000]*H*W
for i in range(H):
    for k in range(W):
        if maze[i][k] == '#':
            q.append(i*W+k)
            saitan[i*W+k] = 0
len_q = len(q)

#print(start)
def bfs(h,w,q,Saitan,len_Q):
    
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while len(q)>0 and len_Q < h * w:
        j = q.popleft()
        y = int(j/w)
        x = j%w
        #print(saitan)
        for k in range(4):
            my = y + dy[k]
            mx = x + dx[k]
            #print(sx,sy,j,x,y,mx,my)
            if not((0 <=my <= h-1) and (0 <= mx <= w-1)):
                #print('q')
                continue
            if saitan[(my*w + mx)] <= saitan[y*w + x] + 1:
                #print('c')
                continue
                
            saitan[(my*w + mx)] = saitan[y*w + x] + 1
            q.append(my*w + mx)
            len_Q += 1
            #Sumi.append(my*w + mx)
    return max(saitan)

print(bfs(H,W,q,saitan,len_q))
#print(saitan)
### BUGGY CODE ###

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

def ligh(li):
  for x in range(k):
    if li==[n]*n:
      return li
    ne=[0]*n
    ar=[]
    for (i,a) in zip(range(n),li):
      for j in range(max(0,i-a),min(i+a+1,n)):
        ne[j]+=1
    li=ne
    #print(li)
  return li

for i in ligh(a):
  print(i,end=" ")


### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
def ligh(li):
  for x in range(k):
    if li==[n]*n:
      return li
    ne=[0]*(n+1)
    zr=[]
    lis=[]
    for (i,a) in zip(range(n),li):
      if a==0:
        zr.append(i)
      else:
        ne[max(0,i-a)]+=1
        ne[min(i+a+1,n)]-=1

    for i in range(1,n):
      ne[i]+=ne[i-1]
    for i in zr:
      ne[i]+=1
    li=ne[:-1]
    #print(li)
  return li

for i in ligh(a):
  print(i,end=" ")
### BUGGY CODE ###

import heapq

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

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

b = [0] * m
c = [0] * m
for i in range(m):
    b[i], c[i] = map(int,input().split())

#print(a)

heapq.heapify(a)
#print(a)

for j in range(m):
    for k in range(b[j]):
        #if a[0] > c[j]:
        #    break
        #else:
        heapq.heappushpop(a,c[j])

print(sum(a))

### FIXED CODE ###

import heapq

from operator import itemgetter

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

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

info = [0] * m
for i in range(m):
    info[i] = list(map(int,input().split()))

info = sorted(info,key = itemgetter(1),reverse = True)
#print(a)

heapq.heapify(a)
#print(a)

d = 0
count = 0

for j in range(len(info)):
    for k in range(info[j][0]):
        if a[0] > info[j][1]:
            d = 1
            break
        else:
            heapq.heappushpop(a,info[j][1])
            count += 1
        if count >= n:
            d = 1
            break
    if d == 1:
        break

print(sum(a))
### BUGGY CODE ###

x, y = map(int,input().split())
li = list(map(int, input().split()))
p = [0]*x
a = 0
ans = 0
for i in range(x):
    p[i] =  li[i]*(li[i]+1)//2/li[i]
for i in range(x-y+1):
    a = sum(p[i:i+y])
    ans = max(ans,a)
    a = 0
    
print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
L = list(map(int,input().split()))
LL = []
for i in range(n):
    kitai = L[i]*(L[i]+1)//2/L[i]
    LL.append(kitai)
#print(LL)
k_sum = sum(LL[:k])
num = []
num.append(k_sum)
for i in range(1,n-k+1):
    k_sum += (LL[k+i-1] - LL[i-1])
    #print(LL[k+i-1],LL[i-1])
    num.append(k_sum)
print(max(num))
### BUGGY CODE ###

def main():
    s = input()
    charlim = len(s)
    total = 0
    unit = 2019
    for charnum in range(5, charlim+1):
        for i in range(charlim-charnum+1):
            cand = int(s[i:i+charnum])
            if cand % 2019 == 0:
                total += 1
    print(total)

if __name__ == '__main__':
    main()

### FIXED CODE ###

s = input()
p = 2019
mods = [0] * p
mods[0] = 1
current = 0
base = 1
cnt = 0

for c in map(int, s[::-1]):
    current = (current + base * int(c)) % p
    base = base * 10 % p
    mods[current] += 1

print(sum(el*(el-1)//2 for el in mods))
### BUGGY CODE ###

n, m, q = map(int, input().split())
abcd = []
for i in range(q):
    abcd.append(list(map(int, input().split())))

A = []


def dfs(num):
    if len(num) == n:
        A.append(num)
    else:
        now = num[-1]
        for i in range(now, m + 1):
            dfs(num + [i])


for i in range(1, 10):
    dfs([i])

ans = 0
for i in range(len(A)):
    now = A[i]
    point = 0
    for j in range(q):
        a, b, c, d = abcd[j]
        a -= 1
        b -= 1
        if int(now[b]) - int(now[a]) == c:
            point += d

    ans = max(ans, point)

print(ans)


### FIXED CODE ###

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

A = []


def dfs(num):
    if len(num) == n:
        A.append(num)
    else:
        now = num[-1]
        for i in range(now, m + 1):
            dfs(num + [i])


for i in range(1, 10):
    dfs([i])

ans = 0
for now in A:
    point = 0
    for a, b, c, d in abcd:
        if now[b-1] - now[a-1] == c:
            point += d

    ans = max(ans, point)

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

from itertools import accumulate


def solve(string):
    s = string.replace("?", "q").lower()
    n = len(s)
    i_a = []
    i_b = []
    i_c = []
    i_q = []
    for i, _s in enumerate(s):
        exec("i_{}.append({})".format(_s, i))
    s = s[::-1]

    c_b = [1 if _s == "b" else 0 for _s in s]
    c_c = [1 if _s == "c" else 0 for _s in s]
    c_q = [1 if _s == "q" else 0 for _s in s]
    c_b = list(accumulate(c_b))[::-1]
    c_c = list(accumulate(c_c))[::-1]
    c_q = list(accumulate(c_q))[::-1]
    ans = 0
    # ABC
    ans += sum(
        sum(c_c[_b + 1] * 3**len(i_q)
            for _b in i_b
            if _a < _b < n - 1)
        for _a in i_a
        if _a < n - 2)
    # AB?
    ans += sum(
        sum(c_q[_b + 1] * 3**(len(i_q) - 1)
            for _b in i_b
            if _a < _b < n - 1)
        for _a in i_a
        if _a < n - 2)
    # A?C
    ans += sum(
        sum(c_c[_b + 1] * 3**(len(i_q) - 1)
            for _b in i_q
            if _a < _b < n - 1)
        for _a in i_a
        if _a < n - 2)
    # ?BC
    ans += sum(
        sum(c_c[_b + 1] * 3**(len(i_q) - 1)
            for _b in i_b
            if _a < _b < n - 1)
        for _a in i_q
        if _a < n - 2)
    # A??
    ans += sum(
        sum(c_q[_b + 1] * 3**(len(i_q) - 2)
            for _b in i_q
            if _a < _b < n - 1)
        for _a in i_a
        if _a < n - 2)
    # ?B?
    ans += sum(
        sum(c_q[_b + 1] * 3**(len(i_q) - 2)
            for _b in i_b
            if _a < _b < n - 1)
        for _a in i_q
        if _a < n - 2)
    # ??C
    ans += sum(
        sum(c_c[_b + 1] * 3**(len(i_q) - 2)
            for _b in i_q
            if _a < _b < n - 1)
        for _a in i_q
        if _a < n - 2)
    # ???
    ans += sum(
        sum(c_q[_b + 1] * 3**(len(i_q) - 3)
            for _b in i_q
            if _a < _b < n - 1)
        for _a in i_q
        if _a < n - 2)
    return str(int(ans % (10**9 + 7)))


if __name__ == '__main__':
    print(solve(input()))


### FIXED CODE ###

def solve(string):
    s = string.replace("?", "d").lower()
    n = len(s)
    dp = [[0] * (n + 1) for _ in range(4)]
    dp[0][0] = 1
    mod = 10**9 + 7
    for i, _s in enumerate(s):
        dp[0][i + 1] = dp[0][i] % mod
        dp[1][i + 1] = dp[1][i] % mod
        dp[2][i + 1] = dp[2][i] % mod
        dp[3][i + 1] = dp[3][i] % mod
        if _s == "a":
            dp[1][i + 1] += dp[0][i]
        if _s == "b":
            dp[2][i + 1] += dp[1][i]
        if _s == "c":
            dp[3][i + 1] += dp[2][i]
        if _s == "d":
            dp[0][i + 1] *= 3
            dp[1][i + 1] *= 3
            dp[1][i + 1] += dp[0][i]
            dp[2][i + 1] *= 3
            dp[2][i + 1] += dp[1][i]
            dp[3][i + 1] *= 3
            dp[3][i + 1] += dp[2][i]
    return str(int(dp[3][-1] % (10**9 + 7)))


if __name__ == '__main__':
    print(solve(input()))
### BUGGY CODE ###

import copy
n = int(input())
string_list = [int(input()) for i in range(n)]

max_num = max(string_list)

for j in string_list:
    if j != max_num:
        print(max_num)
    else:
        templist = copy.deepcopy(string_list)
        templist.remove(j)
        print(max(templist))

### FIXED CODE ###

import copy
n = int(input())
string_list = [int(input()) for i in range(n)]

sorted_list = sorted(string_list)
max_num = max(string_list)

for j in string_list:
    if j != max_num:
        print(max_num)
    else:
        print(sorted_list[-2])