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

#!python3

import heapq


INF = 10 ** 10

# input
N = int(input())
A = list(map(int, input().split()))
uv = [list(map(int, input().split())) for _ in range(N - 1)]


def solve(link, w):
    l = [None] * N
    visit = [False] * N
    # cost, len, node
    hq = [(0, -1, 0)]
    while hq:
        c, n, v = hq.pop()
        if visit[v] :
            continue
        visit[v] = True
        l[v] = abs(n)
        for x in link[v]:
            if not visit[x]:
                heapq.heappush(hq, (c + 1, n + w[v][x], x))

    return l


def main():
    link = [[] for _ in range(N)]
    w = [[0] * N for _ in range(N)]
    for u, v in uv:
        u -= 1
        v -= 1
        link[u].append(v)
        link[v].append(u)
        if A[u] < A[v]:
            w[u][v] = -1
        if A[v] < A[u]:
            w[v][u] = -1
    
    l = solve(link, w)
    for ans in l:
        print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!python3

import sys
sys.setrecursionlimit(10 ** 6)

import numpy as np


INF = 10 ** 10

# input
N = int(input())
A = list(map(int, input().split()))
uv = [list(map(int, input().split())) for _ in range(N - 1)]

# link
link = [[] for _ in range(N + 1)]
for u, v in uv:
    link[u].append(v)
    link[v].append(u)


def dfs(l, dp, pre, v):
    # LIS
    idx = np.searchsorted(dp, A[v - 1])
    l[v] = max(idx, l[pre])
    bef = dp[idx]
    dp[idx] = A[v - 1]
    
    for x in link[v]:
        if x != pre:
            dfs(l, dp, v, x)

    dp[idx] = bef


def main():
    l = [0] * (N + 1)
    dp = np.full(N + 1, INF)
    dp[0] = 0
    dfs(l, dp, 0, 1)
    for ans in l[1:]:
        print(ans)


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

n=int(input())
A=list(map(int,input().split()))
x=1
flag=1
for i in range(n):
  if A[i]==0:
    print(0)
    exit()
  else:
    x*=A[i]

if x>10**18:
  flag=0
  

if flag==1:
  print(x)
else:
  print("-1")

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
x=1
A.sort()
if 0 in A:
  print(0)
  exit()

for i in range(n):
  x*=A[n-i-1]
  if x>10**18:
    print(-1)
    exit()
  else:
    continue

print(x)
### BUGGY CODE ###

from itertools import product

K,S=map(int,input().split())
li_=list(product(range(K+1),repeat=3))
ans=0
for x in li_:
  if sum(x)==S:
    ans+=1
print(ans)


### FIXED CODE ###

K,S=map(int,input().split())
ans=0
for X in range(0,K+1):
  for Y in range(0,K+1):
    Z=S-X-Y
    if 0<=Z and Z<=K:
      ans+=1
print(ans)
### BUGGY CODE ###

x,k,d=map(int,input().split())
x=abs(x)
sa=x//d
ans=x
pbk,mbk=0,0
bk1,bk2,bk3=1,1,1
if sa>=k:
  ans=x-d*k
else:
  ans=x-d*sa
  for i in range(k-sa):
    if abs(ans-d)!=abs(ans+d):
      ans=min(abs(ans-d),abs(ans+d))
      if ans==1:
        bk3=max(abs(ans-d),abs(ans+d))
      if bk3!=1:
        bk1=min(abs(ans-d),abs(ans+d))
        bk2=max(abs(ans-d),abs(ans+d))
        ans=1 if (k-sa-i)%2==1 else bk1
        break
    else:
      ans=mbk if (k-sa-i)%2==0 else d
      break
    pbk=max(abs(ans-d),abs(ans+d))
    mbk=min(abs(ans-d),abs(ans+d))
print(ans)

### FIXED CODE ###

x,k,d=map(int,input().split())
x=abs(x)
sa=x//d
ans=x
pbk,mbk=0,0
bk1,bk2,bk3=1,1,1
mansbk,pansbk=0,0
if sa>=k:
  ans=x-d*k
else:
  ans=x-d*sa
  k=k-sa
  for i in range(k):
    mansbk=abs(ans-d)
    pansbk=abs(ans+d)
    if mansbk!=pansbk:
      ans=min(mansbk,pansbk)
      if bk3!=1:
        bk1=min(mansbk,pansbk)
        bk2=max(mansbk,pansbk)
        ans=mbk if (k-i)%2==0 else bk1
        break
      else:
        bk3=max(mansbk,pansbk) 
    else:
      ans=0 if (k-i)%2==0 else d
      break
    pbk=max(mansbk,pansbk)
    mbk=min(mansbk,pansbk)
print(ans)
### BUGGY CODE ###

a = int(input())
l = list(map(int, input().split()))
l_2 = list(set(l))
l_2.sort()
if l_2[0] == 1:
    for i in range(len(l_2) - 1):
        print(l.count(l_2[i]))
        word = '0\n' * (l_2[i + 1] - l_2[i])
        if l_2[i + 1] - l_2[i] - 1 > 0:
            print(word[:-3])
    print(l.count(l_2[-1]))
    word = '0\n' * (a - max(l_2))
    print(word[:3 * (a - max(l_2) - 1) + 1])

### FIXED CODE ###

import collections
a = int(input())
l = list(map(int, input().split()))
l_2 = collections.Counter(l)
for i in range(a):
    print(l_2[i + 1])
### BUGGY CODE ###

import math

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

Z = []
for i in range(N):
    ver = [A[i], 0]
    Z.append(ver)

for k in range(K):
    h = Z.index(max(Z))
    Z[h][1] += 1
    Z[h][0] /= 2 

for j in range(N):
    A[j] = A[j]/(Z[j][1]+1)

print(math.ceil(max(A)))

### FIXED CODE ###

import math

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

def ink(L):
    cnt = 0
    for i in range(N):
        cnt += A[i]//L
        if A[i]%L != 0:
            cnt += 1
        cnt -= 1
    return cnt <= K

bottom, top = 0, max(A)

while(top - bottom > 1):
    middle = (top + bottom) // 2
    if ink(middle): top = middle
    else: bottom = middle

print(top)
### BUGGY CODE ###

import sys
def gcd(a,b):
    if(b == 0):
        return a
    else:
        c = b
        b = a%b
        a = c
        return(gcd(a,b))

x = int(input())
count = 0
for y in range(1,x+1):
    if gcd(x,y) == 1:
        count+=1

print(count)

### FIXED CODE ###

import sys
def euler(a):
    i = 2
    res = a
    #standard = a
    while i * i <= a:
        if a % i == 0:
            res = res - res//i
            while a % i == 0:
                a //= i

        i += 1
    if a != 1:
        res = res - res//a

    return res


x = int(input())


print(euler(x))
### BUGGY CODE ###

from sys import stdin

N, M = map(int, stdin.readline().split())
A = list(map(int, stdin.readline().split()))
for _ in range(M):
    B, C = map(int, stdin.readline().split())
    A.extend([C]*B)
A.sort(reverse=True)
ans = 0
for i in range(N):
    ans += A[i]

print(ans)


### FIXED CODE ###

from sys import stdin, exit

N, M = map(int, stdin.readline().split())
A = list(map(int, stdin.readline().split()))
p = [(A[i], 1) for i in range(N)]
for _ in range(M):
    B, C = map(int, stdin.readline().split())
    p.append((C, B))

p.sort(reverse=True)

ans, cnt = 0, N
for (v, c) in p:
    use = min(c, cnt)
    ans += use * v
    cnt -= use

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

import numpy as np
from scipy.sparse.csgraph import dijkstra
from itertools import count

with open(0) as f:
    N = int(f.readline())
    A = [list(map(int, line.split())) for line in f.readlines()]

A = np.array(A, dtype='int64')
shortcut = dijkstra(A, directed=False)
if not np.array_equal(A, shortcut):
    print(-1)
    exit()

ans = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(N):
            if k in (i, j):
                continue
            if A[i, j] < A[i, k] + A[k, j]:
                continue
            if A[i, j] == A[i, k] + A[k, j]:
                break
        else:
            ans += A[i, j]

print(ans)

### FIXED CODE ###

def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(200000)
from collections import deque
from bisect import bisect_left

N = int(input())
A = list(map(int, input().split()))
adj = [[] for i in range(N)]
for i in range(N - 1):
	u, v = map(int, input().split())
	adj[u - 1].append(v - 1)
	adj[v - 1].append(u - 1)


INF = 10 ** 10
done = [False] * N
done[0] = True
lisdp = [INF] * N
lisdp[0] = A[0]
change = [[-1, INF] for i in range(N)] #index, original
change[0] = [0, INF]
lisl = [0] * N
lisl[0] = 1

def dfs(v):
	for nv in adj[v]:
		if done[nv]:
			continue
		done[nv] = True
		ind = bisect_left(lisdp, A[nv])
		ori = lisdp[ind]
		change[nv] = [ind, ori]
		if ori == INF:
			lisl[nv] = lisl[v] + 1
		else:
			lisl[nv] = lisl[v]
		lisdp[ind] = A[nv]
		dfs(nv)
	lisdp[change[v][0]] = change[v][1]

dfs(0)
for i in range(N):
	print(lisl[i])	

### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)
from collections import deque
from bisect import bisect_left

N = int(input())
A = list(map(int, input().split()))
adj = [[] for i in range(N)]
for i in range(N - 1):
	u, v = map(int, input().split())
	adj[u - 1].append(v - 1)
	adj[v - 1].append(u - 1)


INF = 10 ** 10
done = [False] * N
done[0] = True
lisdp = [INF] * N
lisdp[0] = A[0]
change = [[-1, INF] for i in range(N)] #index, original
change[0] = [0, INF]
lisl = [0] * N
lisl[0] = 1

def dfs(v):
	for nv in adj[v]:
		if done[nv]:
			continue
		done[nv] = True
		ind = bisect_left(lisdp, A[nv])
		ori = lisdp[ind]
		change[nv] = [ind, ori]
		if ori == INF:
			lisl[nv] = lisl[v] + 1
		else:
			lisl[nv] = lisl[v]
		lisdp[ind] = A[nv]
		dfs(nv)
	lisdp[change[v][0]] = change[v][1]

dfs(0)
for i in range(N):
	print(lisl[i])
### BUGGY CODE ###

from collections import*
n=input();G=[[]for d in[deque([1,-1])]*-~n]
for C in[[0,1]+[0]*(n-2)+[2]]*~-n:a,b=map(int,raw_input().split());G[a]+=b,;G[b]+=a,
while d:
 v=d.popleft()
 for t in G[v]:exec"C[t]=C[v];d+=t,"*(C[t]<1)
print["Fennec","Snuke"][2*C.count(1)<=n]

### FIXED CODE ###

n = input()
G = [[] for i in xrange(n)]
for i in xrange(n-1):
    a, b = map(int, raw_input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

from collections import deque
deq = deque()
deq.append((0, 0))
deq.append((n-1, 1))
C = [None]*n
C[0] = 0; C[n-1] = 1
while deq:
    v, col = deq.popleft()
    for t in G[v]:
        if C[t] is None:
            C[t] = col
            deq.append((t, col))
B = C.count(0)
W = C.count(1)
if B == W:
    print "Snuke"
elif B < W:
    print "Snuke"
elif B > W:
    print "Fennec"
### BUGGY CODE ###

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

bt = [0]*60

ans = 0

for i in range(n):
    s = a[i]
    for j in range(60):
        if((s>>j) & 1):
            ans += (i-bt[j])*(2**j)
            ans %= mod
            bt[j] += 1
        else:
            ans += bt[j]*(2**j)
            ans %= mod


print(ans)


### FIXED CODE ###

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

bt = [0]*60

ans = 0

for j in range(60):
    for i in range(n):
        s = a[i]
        if((s>>j) & 1):
            ans += (i-bt[j])*(2**j)
            ans %= mod
            bt[j] += 1
        else:
            ans += bt[j]*(2**j)
            ans %= mod

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

import bisect,collections,copy,heapq,itertools,math,numpy,string,random
import sys
from decimal import Decimal
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

D = I()
C = LI()
s = [LI() for _ in range(D)]

T = [1 for _ in range(D)]
#print(D,C)
#print(s)
#print(T)
def last(d,i):
    T_d = T[:d]
    n = [j for j, x in enumerate(T_d,1) if x == i]
    if n:
        #print(T_d,i,"n=",n)
        return max(n)
    else:
        return 0
        
def Score(T):
    score = 0
    for d in range(1,D+1):
        sum_c = 0
        for i in range(1,26+1):
            sum_c += C[i-1] * (d -last(d,i))
        score += s[d-1][T[d-1]-1] - sum_c
        #print(score)
    score_d = max(10**6 + score,0)
    #print(score_d)
    return score_d

score_0 = Score(T)
for j in range(50):
    T_new = [random.randint(1,26) if i%36 == 0 else T[i] for i in range(D)]
    if Score(T_new) > score_0:
        T = T_new
        score_0 = Score(T_new)
        
for t in T:
    print(t)

### FIXED CODE ###

import bisect,collections,copy,heapq,itertools,math,numpy,string,random
import sys
from decimal import Decimal
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

D = I()
C = LI()
s = [LI() for _ in range(D)]

T = [random.randint(1,26) for _ in range(D)]
#print(D,C)
#print(s)
#print(T)
def last(d,i):
    T_d = T[:d]
    n = [j for j, x in enumerate(T_d,1) if x == i]
    if n:
        #print(T_d,i,"n=",n)
        return max(n)
    else:
        return 0
        
        
score = 0
for d in range(1,D+1):
    sum_c = 0
    for i in range(1,26+1):
        sum_c += C[i-1] * (d -last(d,i))
    score += s[d-1][T[d-1]-1] - sum_c
    #print(score)
    #print(max(10**6 + score,0))
for t in T:
    print(t)
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

import sys

def main():
    S = input()
    T = input()
    N, M = len(S), len(T)
    # Sのi文字目までTのj文字目までのLCSの長さ
    dp = [[0]*(M+1) for _ in range(N+1)]
    for i in range(1,N+1):
        for j in range(1,M+1):
            if S[i-1] == T[j-1]:
                dp[i][j] = dp[i-1][j-1]+1
            dp[i][j] = max(dp[i][j], dp[i-1][j], dp[i][j-1])
    i, j = N, M
    ret = ''
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:    # i-1から更新された
            i -= 1
        elif dp[i][j] == dp[i][j-1]:  # j-1から更新された
            j -= 1
        else:                         # i-1, j-1から更新された
            i -= 1
            j -= 1
            ret += S[i]
#    print(dp)
    print(ret[::-1])

if __name__=='__main__':
    main()


### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

####################################################
# LCS(longest common sequence)
# 部分列で最長の共通のもの
####################################################

# dp[i+1][j+1]:= s の i 文字目までと t の j 文字目まででの LCS の長さ

import numpy as np

def main():
    S = np.array(list(input()), dtype='unicode')
    T = np.array(list(input()), dtype='unicode')
    ls = len(S)
    lt = len(T)

    equal = S[:, None] == T[None,:]
#    print(eq)

    dp = np.zeros((ls + 1, lt + 1), dtype=int)

    for i in range(ls):
        dp[i + 1][1:] = np.maximum(dp[i][1:], dp[i][:-1] + equal[i])
        dp[i + 1] = np.maximum.accumulate(dp[i + 1])

#    for i in range(ls):
#        for j in range(lt):
#            dp[i+1][j+1] = max(dp[i][j+1], dp[i][j]+ eq[i][j])
#            dp[i+1][j+1] = max(dp[i+1][j+1] , dp[i+1][j])

#    print(dp)

    # 復元
    res = ''
    i, j = ls, lt
    while (i > 0 and j > 0):
        # (i-1, j) -> (i, j) と更新されていた場合
        if dp[i][j] == dp[i-1][j]:
            i-=1   # DP の遷移を遡る
        # (i, j-1) -> (i, j) と更新されていた場合
        elif dp[i][j] == dp[i][j-1]:
            j-=1   # DP の遷移を遡る
        # (i-1, j-1) -> (i, j) と更新されていた場合
        else:
            res = S[i-1] + res
            # このとき s[i-1] == t[j-1] なので、t[j-1] + res でも OK
            i-=1
            j-=1   # DP の遷移を遡る
    print(res)

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

def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)

n=int(input())
arr=[int(i) for i in input().split()]
sum=0
for i in range(n):
    sum+=arr[i]
sum//=2
for x in range(n):
    ex=0
    i=x
    while(True):
        ex+=arr[i]
        i+=2
        i%=n
        if (i+1)%n==x:
            ex+=arr[i]
            break

    print(((ex-sum)*2),end=" ")


### FIXED CODE ###

def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)

n=int(input())
arr=[int(i) for i in input().split()]
sum=0
for i in range(n):
    sum+=arr[i]
sum//=2
ans=0
for x in range(0,1):
    ex=0
    i=x
    while(True):
        ex+=arr[i]
        i+=2
        i%=n
        if (i+1)%n==x:
            ex+=arr[i]
            break

    ans=((ex-sum))
io=0
while(io!=n):
    print(ans*2,end=" ")
    ans=arr[(io)%n]-ans
    io+=1
### BUGGY CODE ###

from sys import stdin
import math
import itertools
import re
import sys
sys.setrecursionlimit(10**8)
 
 
def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]
 
dp = {}
T = {}
 
def solve(input_string):
    S = input_string[1]
    intMatrix = makeIntMatrix(input_string[2:])
    #print(input_string[2:])
    for line in intMatrix:
        L, R = line
        #print(l, r)
        #print(S[l:r+1])
        #cnt = len(re.findall(r'AC', S[l-1:r]))
        totalCnt = cntAC(L, R, S)
        print(totalCnt)
    return
 

"""
wrong answer
def cntAC(l, r, D, S, cnt):
    global dp
    global T
    if r-l == D+1:
        return cnt
    if str(l)+str(r) not in T:
        T[str(l)+str(r)] = S[l-1:r]
        t = T[str(l)+str(r)]
    if str(l)+str(r) not in dp:
        #print(t)
        dp[str(l)+str(r)] = len(t.split('AC'))-1
        cnt = dp[str(l)+str(r)]
        return cntAC(l-1, r, D, S, cnt)
    else:
        cnt = dp[str(l)+str(r)]
        return cntAC(l-1, r, D, S, cnt)
"""
 

def cntAC(L, r, S):
    global dp
    global T
    for l in range(L, r)[::-1]:
        if str(l)+str(r) not in T:
            T[str(l)+str(r)] = S[l-1:r]
            t = T[str(l)+str(r)]
        else:
            t = T[str(l)+str(r)]
        if str(l)+str(r) not in dp:
            dp[str(l)+str(r)] = len(t.split('AC'))-1
            cnt = dp[str(l)+str(r)]
        else:
            cnt = dp[str(l)+str(r)]
    return cnt
 

def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    #print(answer)
 
 
if __name__ == '__main__':
    main()


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t=[0]*(N+1)
for i in range(N):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
  l, r = map(int, input().split())
  print(t[r-1] - t[l-1])
### BUGGY CODE ###

#!/usr/bin/env python3
def main():
    import sys

    input = sys.stdin.readline

    A, B, N = map(int, input().split())

    ans = 0
    for x in range(N + 1):
        res = int((A * x) // B) - A * int(x // B)
        ans = max(ans, res)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
def main():
    import sys

    input = sys.stdin.readline

    A, B, N = map(int, input().split())

    x = min(B - 1, N)
    print((A * x) // B - A * (x // B))


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

N,Q = map(int,input().split())
S = input()
qa = []
for i in range(Q):
    lr = [int(i) for i in input().split()]
    qa.append(lr)

for j in range(Q):
    count = 0
    start = qa[j][0]-1
    end = qa[j][1]
    string = S[start:end]
    for i in range(len(string)-1):
        if string[i:i+2] == "AC":
            count += 1
    print(count)

### FIXED CODE ###

import time
N,Q = map(int, input().split())
S = input()
AC = [0]*(N+1)

for i in range(N):
    if S[i:i+2] == "AC":
        AC[i+1] = AC[i] + 1
    else:
        AC[i+1] = AC[i]

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

n, m = map(int, input().split())
a = list(map(int, input().split()))
for i in range(m):
  a[a.index(max(a))] //= 2
print(sum(a))


### FIXED CODE ###

import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
a = [i*-1 for i in a]
heapq.heapify(a)
for i in range(m):
    x = ((-1) * heapq.heappop(a)) //2
    heapq.heappush(a, -x)
print(-sum(a))
### BUGGY CODE ###

from copy import deepcopy
from collections import deque
h,w,n = (int(i) for i in input().split())
c1,ans = [deque([]) for i in range(w)],0
for i in range(h):
	s = input()
	for j in range(w): c1[j].append(int(s[j]))
if n<4:
	for i in range(1,h):
		for j in range(w):
			c,m,a = deepcopy(c1),0,0
			del c[j][i]
			c[j].appendleft(0)
			while 1:
				d = []
				for k in range(i-h,-h,-1):
					k2 = 0
					while k2<w-n+1:
						if c[k2][k] and all(c[k2][k]==c[k2+k3][k] for k3 in range(1,n)):
							b = n
							for k3 in range(k2+n,w):
								if c[k2][k]==c[k3][k]: b+=1
								else: break
							d.append((h+k,k2,b))
							k2+=b
						else: k2+=1
				if d:
					for k,k2,k3 in d:
						a+=(2**m)*c[k2][k]*k3
						for k4 in range(k2,k2+k3): del c[k4][k]
					for k,k2,k3 in d:
						for k4 in range(k2,k2+k3): c[k4].appendleft(0)
				else: break
				m+=1
			ans = max(ans,a)
print(ans)

### FIXED CODE ###

from copy import deepcopy
h,w,n = (int(i) for i in input().split())
c1,ans = [[] for i in range(w)],0
for i in range(h):
	s = input()
	for j in range(w): c1[j].append(int(s[j]))
if n<4:
	if h==30: z = 25
	else: z = h//2
	for i in range(z,h):
		for j in range(w):
			c,m,a = deepcopy(c1),0,0
			del c[j][i]
			c[j].insert(0,0)
			while 1:
				d = []
				for k in range(i-h,-h,-1):
					k2 = 0
					while k2<w-n+1:
						if c[k2][k] and all(c[k2][k]==c[k2+k3][k] for k3 in range(1,n)):
							b = n
							for k3 in range(k2+n,w):
								if c[k2][k]==c[k3][k]: b+=1
								else: break
							d.append((h+k,k2,b))
							k2+=b
						else: k2+=1
				if d:
					for k,k2,k3 in d:
						a+=(2**m)*c[k2][k]*k3
						for k4 in range(k2,k2+k3): del c[k4][k]
					for k,k2,k3 in d:
						for k4 in range(k2,k2+k3): c[k4].insert(0,0)
				else: break
				m+=1
			ans = max(ans,a)
print(ans)
### BUGGY CODE ###

# 解説を見た
# よく理解していない

def main():
    n = int(input())
    s = input()
    q = int(input())
    *ks, = map(int, input().split())

    for k in ks:
        cnt = 0
        d, m, dm = 0, 0, 0
        for char in s[:k]:
            if char == 'D':
                d += 1
            elif char == 'M':
                m += 1
                dm += d
            elif char == 'C':
                cnt += dm

        for p_char, char in zip(s, s[k:]):
            if p_char == 'D':
                dm -= m
                d -= 1
            elif p_char == 'M':
                m -= 1

            if char == 'D':
                d += 1
            elif char == 'M':
                m += 1
                dm += d
            elif char == 'C':
                cnt += dm

        print(cnt)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def solve():
    n = int(input())
    s = input()
    q = int(input())
    ks = list(map(int, input().split()))

    for k in ks:
        ans = 0
        cnt = 0
        d = 0
        m = 0
        for i in range(n):
            if s[i] == 'D':
                d += 1
            elif s[i] == 'M':
                m += 1
                cnt += d
            elif s[i] == 'C':
                ans += cnt

            if i >= k - 1:
                if s[i - k + 1] == 'D':
                    cnt -= m
                    d -= 1
                elif s[i - k + 1] == 'M':
                    m -= 1

        print(ans)


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

import collections
mod = 10**9+7
fac = [1]
caf = [1]
n=int(input())

def pow(n,p):
    res=1
    while p >0:
        if p%2==0:
            n = n**2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod

for i in range(1,n+2):
    fac.append((fac[i-1]*i)%mod)
    caf.append(pow(fac[i],mod-2)%mod)

def ncr(n,r):
    if n < r: return 0
    return fac[n]*caf[r]*caf[n-r]

def main():
    global n
    a=list(map(int,input().split()))

    ca= collections.Counter(a)
    tyo= ca.most_common()[0][0]
    kaburi=[i for i, x in enumerate(a) if x == tyo]

    for i in range(1,n+2):
        print((ncr(n+1,i)-ncr(n+1-(kaburi[1]-kaburi[0]+1),i-1))%mod)

main()


### FIXED CODE ###

import collections
mod = 10**9+7
fac = [1]
caf = [1]
n=int(input())

def pow(n,p):
    res=1
    while p >0:
        if p%2==0:
            n = n**2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod

for i in range(1,n+2):
    fac.append((fac[i-1]*i)%mod)
    caf.append(pow(fac[i],mod-2)%mod)

def ncr(n,r):
    if n < r: return 0
    return fac[n]*caf[r]*caf[n-r]

def main():
    global n
    a=list(map(int,input().split()))

    ca= collections.Counter(a)
    tyo= ca.most_common()[0][0]
    kaburi=[i for i, x in enumerate(a) if x == tyo]

    for i in range(1,n+2):
        print((ncr(n+1,i)-ncr(n+1-(kaburi[1]-kaburi[0]+1),i-1))%mod)

main()