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

from bisect import*
def main():
    root=[[],[]]
    def search_higher(key):
        ptr0,ptr1=root
        ret=None
        while ptr1:
            i=bisect(ptr0,key)
            if i!=len(ptr0):ret=ptr0[i]
            ptr0,ptr1=ptr1[i]
        i=bisect(ptr0,key)
        if i!=len(ptr0):ret=ptr0[i]
        return ret
    def search_lower(key):
        ptr0,ptr1=root
        ret=None
        while ptr1:
            i=bisect_left(ptr0,key)
            if i!=0:ret=ptr0[i-1]
            ptr0,ptr1=ptr1[i]
        i=bisect_left(ptr0,key)
        if i!=0:ret=ptr0[i-1]
        return ret
    def insert_rec(ptr,key):
        ptr0,ptr1=ptr
        b_size=256
        if not ptr[1]:
            insort(ptr0,key)
            if len(ptr0)==b_size*2-1:
                ret=[[],[]]
                ret[0]=ptr0[:b_size]
                ptr[0]=ptr0[b_size:]
                return ret
        else:
            i=bisect(ptr0,key)
            tmp=insert_rec(ptr1[i],key)
            if tmp:
                ptr0.insert(i,tmp[0].pop())
                ptr1.insert(i,tmp)
                if len(ptr1)==b_size*2:
                    ret=[[],[]]
                    ret[1]=ptr1[:b_size]
                    ptr[1]=ptr1[b_size:]
                    ret[0]=ptr0[:b_size]
                    ptr[0]=ptr0[b_size:]
                    return ret
    def insert(key):
        tmp=insert_rec(root,key)
        if tmp:root[0],root[1]=[tmp[0].pop()],[tmp,root]
    n,*a=map(int,open(0).read().split())
    l=[0]*n
    for i,v in enumerate(a,1):l[v-1]=i
    insert(0)
    insert(n+1)
    c=0
    for i,v in enumerate(l,1):
        c+=(search_higher(v)-v)*(v-search_lower(v))*i
        insert(v)
    print(c)
main()

### FIXED CODE ###

root=lambda x:x if par[x]==x else root(par[x])
same=lambda x,y:root(x)==root(y)
def unite(*z):
  x,y=map(root,z)
  if x!=y:
    if rank[x]<rank[y]:
      par[x]=y
      size[y]+=size[x]
    else:
      par[y]=x
      size[x]+=size[y]
      if rank[x]==rank[y]:rank[x]+=1
n,*a=map(int,open(0).read().split())
*par,=range(n)
rank=[1]*n
size=[1]*n
b=[0]*n
for i,t in enumerate(a):b[t-1]=i
c=0
for k in b[::-1]:
  l=r=1
  if k>0 and a[k-1]>a[k]:
    l+=size[root(k-1)]
    unite(k-1,k)
  if k+1<n and a[k+1]>a[k]:
    r+=size[root(k+1)]
    unite(k+1,k)
  c+=l*r*a[k]
print(c)
### BUGGY CODE ###

s = int(input())
ss = len(str(s))

count = 0
for i in range(ss):
    for j in range(i,ss):
        sa = s // (10**i)
        sb = sa % (10**(j+1-i))
        if (sb % 2019 == 0):
            count += 1

print(count)

### FIXED CODE ###

s = input()[::-1]

dataset = [0]*2019
dataset[0] = 1

n = 0
d = 1

for i in s:
    n += int(i) * d
    a = n % 2019
    dataset[a] += 1
    d *= 10
    d %= 2019

count = 0
for i in dataset:
    count += i * (i-1) // 2

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

n,q=map(int,input().split())
s=input()
ans=[]
for i in range(len(s)-1):
    if s[i:i+2]=='AC':ans.append(i)
for _ in range(q):
    l,r=map(int,input().split())
    cnt=0
    print(len([n for n in ans if l-1<=n<r-1]))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
ans=[0]*n
cnt=0
for i in range(len(s)-1):
    if s[i:i+2]=='AC': cnt+=1
    ans[i]=cnt
for _ in range(q):
    l,r=map(int,input().split())
    print(ans[r-2]-ans[l-2])
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    ans = 0
    for a in range(1, N + 1):
        i = (a // K) - 1
        while True:
            i += 1
            b = K * i - a
            if b < a:
                continue
            elif b > N:
                break
            else:
                j = (b // K) - 1
                while True:
                    j += 1
                    c = K * j - b
                    if c < b:
                        continue
                    elif c > N:
                        break
                    elif (a + c) % K == 0:
                        if len(set([a, b, c])) == 1:
                            ans += 1
                        elif len(set([a, b, c])) == 3:
                            ans += 6
                        else:
                            ans += 3
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    ans = 0
    if K % 2 == 1:
        ans = (N // K) ** 3
    else:
        ans = (N // K) ** 3
        r = K // 2
        ans += len([1 for v in range(1, N+1) if v % K == r]) ** 3
    print(ans)


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

import sys
import bisect
#input = sys.stdin.readline
N,M=map(int,input().split())
A=[int(i) for i in input().split()]
B=[0]*M
C=[0]*M
for i in range(M):
    B[i],C[i]=[int(x) for x in input().split()]
A.sort()
#print(A)
for b,c in zip(B,C):
    index = bisect.bisect_left(A,c)
    #print(index)
    if index != 0:
        A[index:0] =[c]*b
        del A[:b]
    #print(A)
print(sum(A))

### FIXED CODE ###

import sys
import bisect
import numpy as np
#input = sys.stdin.readline
N,M=map(int,input().split())
A=[int(i) for i in input().split()]
B=[0]*M
C=[0]*M
for i in range(M):
    B[i],C[i]=[int(x) for x in input().split()]
matrix = np.vstack((np.array(B),np.array(C)))
matrix = matrix[:, np.argsort(-matrix[1])]
list2=np.zeros(N)
i=0
for b,c in zip(matrix[0],matrix[1]):
    i += b
    #print(i-b,b)
    if i < N:
        list2[i-b:i] = c
        #print(list2)
    else: 
        list2[i-b:]=c
        #print(list2)
A.extend(list(list2))
A.sort()
print(int(sum(A[N:])))
### BUGGY CODE ###

s=input()
k=int(input())

x=[]
for i in range(len(s)):
    for j in range(i+1,len(s)+1):
        x.append(s[i:j] )
y=list(set(x))
z=sorted(y)

print(z[k-1])

### FIXED CODE ###

s=input()
k=int(input())
l=len(s)
def find_substring_from_a(a):
    a_s=[]
    for i in range(l):
        if s[i]==a:
            for j in range(1,min(6,l-i+1 )):
                a_s.append(s[i:i+j])
    return sorted(set(a_s) )
moji_list = sorted(set(s))
length = 0
for a in moji_list:
    a_s=find_substring_from_a(a)
    lenas = len(a_s)
    if length+lenas >=k:
        break
    else:
        length+=lenas
print(a_s[k-length-1])
### BUGGY CODE ###

from fractions import Fraction
N = int(input())
for h in range(1, 3501):
    for n in range(1, 3501):
        w1 = 4 / N - (1 / h + 1 / n)
        w = Fraction(w1)
        de = w.denominator
        nu = w.numerator
        if w1 > 0 and de % nu == 0:
            print(h, n, de // nu)
            exit()

### FIXED CODE ###

N = int(input())
for h in range(3501):
    for n in range(h):
        if 4 * h * n - N * (h + n) > 0 and (N * h * n) % (4 * h * n - (N * (h + n))) == 0:
            w = (N * h * n) // (4 * h * n - N * (h + n))
            print(h, n, w)
            exit()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N_ken,M_si = map(int,input().split())
ken_year_map = {}
for i in range(1,N_ken+1):ken_year_map[i]=[]

ken_list = []
year_list = []

for si in range(1,M_si+1):
    ken,year = map(int,input().split())
    ken_list.append(ken)
    year_list.append(year)
    ken_year_map[ken] += [year]
        
for i in ken_year_map:
    ken_year_map[i].sort()

for ken,year in zip(ken_list,year_list):
    print((str(ken*1000000 + ken_year_map[ken].index(year)+1)).zfill(12))


### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect

N_ken,M_si = map(int,input().split())
ken_year_map = {}
for i in range(1,N_ken+1):ken_year_map[i]=[]

ken_list = [0]*M_si
year_list = [0]*M_si

for si in range(M_si):
    ken_list[si],year_list[si] = map(int,input().split())
    ken_year_map[ken_list[si]] += [year_list[si]]
        
for i in ken_year_map:
    ken_year_map[i].sort()

for ken,year in zip(ken_list,year_list):
    print('{:06}{:06}'.format(ken,bisect.bisect_right(ken_year_map[ken], year)))
### BUGGY CODE ###

#https://atcoder.jp/contests/dp/tasks/dp_i
import math
N = int(input())
P_List = list(map(float,input().split()))
dp = [[0 for j in range(N + 1)] for i in range(N+1)]
std = math.ceil(N/2)
for i in range(N+1):
    if i == 0:
        dp[i][0] = 1
    else:
        Current_P = P_List[i - 1]
        for j in range(i + 1):
            if (N - i + j) < std:
                dp[i][j] = 0
            elif j == 0:
                dp[i][j] = dp[i - 1][j]*(1 - Current_P)
            elif j != i:
                dp[i][j] = (dp[i - 1][j]*(1 - Current_P)) + (dp[i - 1][j - 1]*Current_P)
            else:
                dp[i][j] = dp[i - 1][j - 1]*Current_P
    
print(sum(dp[N][math.ceil(std):]))

### FIXED CODE ###

#https://atcoder.jp/contests/dp/tasks/dp_i
import math
N = int(input())
P_List = list(map(float,input().split()))
dp = [[0 for j in range(N + 1)] for i in range(N+1)]
std = math.ceil(N/2)
for i in range(N+1):
    if i == 0:
        dp[i][0] = 1
    else:
        Current_P = P_List[i - 1]
        for j in range(i + 1):
            if (N - i + j) < std:
                dp[i][j] = 0
            elif j == 0:
                dp[i][j] = dp[i - 1][j]*(1 - Current_P)
            elif j != i:
                dp[i][j] = (dp[i - 1][j]*(1 - Current_P)) + (dp[i - 1][j - 1]*Current_P)
            else:
                dp[i][j] = dp[i - 1][j - 1]*Current_P
    
print(sum(dp[N][math.ceil(std):]))
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()

l = []
r = []

for i in range(q):
    l_tmp,r_tmp = map(int,input().split())
    l.append(l_tmp)
    r.append(r_tmp)


for i in range(q):
    tmp_s = s[l[i]-1:r[i]]
    print(tmp_s.count("AC"))


### FIXED CODE ###

n,q = map(int,input().split())
s = input()


t = [0] * n
for i in range(n-1):
    if s[i] == "A" and s[i+1] == "C":
        t[i+1] = t[i] + 1
    else:
        t[i+1] = t[i]


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

import sys
import numpy as np
input = sys.stdin.readline

MOD=10**9+7
N, K = map(int, input().split())
grid = np.empty((0,N), int)
for i in range(N):
  array = list(map(int, input().strip().split()))
  array2 = np.array(array)
  grid = np.append(grid,[array2],axis=0)
#print(grid)
dp=[[grid]]
gridsave=grid
i=1
while 2**i<=K:
  #print(i)
  #dp.insert(1,grid*grid)
  #gridsave=np.dot(dp[i-1][0],dp[i-1][0])
  gridsave=[[0]*N]*N
  gridsave =np.array(gridsave)
  for j in range(N):
    for k in range(N):
      for l in range(N):
        #print(l,'1 ',dp[i-1][0][j][l])
        #print(l,'2 ',dp[i-1][0][l][k])
        gridsave[j][k]=(gridsave[j][k]+(dp[i-1][0][j][l]*dp[i-1][0][l][k])%MOD)%MOD

  gridsave=np.mod(gridsave,MOD)
  #print(gridsave)
  dp.append([gridsave])
  i+=1
i-=1
K-=2**i
i-=1
#print('dp',dp)
grid1=dp[len(dp)-1][0]
#print(grid1)
#print(i)
while K>0:
  if K>=2**i:
    #print('i',i)
    grid1=np.dot(grid1,dp[i][0])
    grid1=np.mod(grid1,MOD)
    K-=2**i
    #print('grid1',grid1)
  i-=1
  #print('K',K)
ans=0
#print(grid1)
for i in range(N):
  for j in range(N):
    ans=(ans+grid1[i][j])%MOD
print(ans)

### FIXED CODE ###

import sys
import numpy as np
input = sys.stdin.readline

MOD=10**9+7
N, K = map(int, input().split())
grid = np.empty((0,N), dtype='O')
for i in range(N):
  array = list(map(int, input().strip().split()))
  array2 = np.array(array)
  grid = np.append(grid,[array2],axis=0)
#print(grid)
dp=[[grid]]
gridsave=np.eye(N,dtype="O")
#print(gridsave)
i=1
while K:
  if K & 1:
    gridsave=np.dot(grid,gridsave) % MOD
  grid=np.dot(grid,grid) % MOD
  K>>=1
ans=np.sum(gridsave)%MOD
#print(gridsave)
print(ans)
### BUGGY CODE ###

x, k, d = map(int, input().split())

if abs(x)-d*k>=0:
    print(abs(x)-d*k)
    exit()


num = 0

while k>0:
    s = abs(x)
    s = s-d
    if abs(s)>=abs(x):
        break
    x = abs(s)
    k -= 1


if k == 0:
    print(abs(s))
    exit()

if k%2 == 0:
    print(abs(x))
else:
    print(abs(s))

### FIXED CODE ###

x, k, d = map(int, input().split())
n = abs(x)//d

if n>=k:
    print(abs(x)-d*k)
else:
    if (k-n)%2 == 0:
        print(abs(abs(x)-d*n))
    else:
        print(abs(abs(x)-d*(n+1)))
### BUGGY CODE ###

# coding: utf-8
# Your code here!
h,w=map(int,input().split())

maze=[]
m=[]
wn=0
INF = 10**5

for i in range(h):
    row=list(input())
    maze.append(row)
    m.append([INF for i in range(w)])
    for j in range(w):
        if row[j]==".":
            wn+=1


m[0][0]=0
dx=[1,0,-1,0]
dy=[0,1,0,-1]

queue=[]
queue.append([0,0])

while len(queue)>0:

    y,x=queue.pop(0)
    maze[y][x]="#"
    for i in range(4):
        ny=y+dy[i]
        nx=x+dx[i]
        if 0<=ny<h and 0<=nx<w:
            if maze[ny][nx]==".":
                queue.append([ny,nx])
                m[ny][nx]=min(m[ny][nx],m[y][x]+1)


if m[-1][-1]==INF:
    print(-1)
else:
    print(wn-2-(m[-1][-1]-1))

    


### FIXED CODE ###

# coding: utf-8
# Your code here!
h,w=map(int,input().split())

maze=[]
m=[]
wn=0
INF = 10**5

for i in range(h):
    row=list(input())
    maze.append(row)
    m.append([INF for i in range(w)])
    for j in range(w):
        if row[j]==".":
            wn+=1


m[0][0]=0
dx=[1,0,-1,0]
dy=[0,1,0,-1]

queue=[]
queue.append([0,0])
maze[0][0]="#"

while len(queue)>0:

    y,x=queue.pop(0)
    for i in range(4):
        ny=y+dy[i]
        nx=x+dx[i]
        if 0<=ny<h and 0<=nx<w:
            if maze[ny][nx]==".":
                queue.append([ny,nx])
                maze[ny][nx]="#"
                m[ny][nx]=min(m[ny][nx],m[y][x]+1)


if m[-1][-1]==INF:
    print(-1)
else:
    print(wn-2-(m[-1][-1]-1))
### BUGGY CODE ###

I=lambda:map(int,input().split())
n,m=I()
d=[0]+[9**9]*2**n
while m:
 m-=1;a,_=I();s=sum(1<<c-1for c in I())
 for j in range(2**n):d[s|j]=min(d[s|j],d[j]+a)
print(d[-2]%9**9or-1)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
e=[(int(input().split()[0]),list(map(int,input().split())))for _ in range(m)]
INF=10**18
dp=[INF]*2**n
dp[0]=0
for i in range(2**n):
    if dp[i]>=INF:continue
    for a,c in e:
        bit=i
        for j in c:
            bit|=2**(n-j)
        dp[bit]=min(dp[bit],dp[i]+a)
a=dp[-1]
if a>=INF:
    print(-1)
else:
    print(dp[-1])
### BUGGY CODE ###

N = int(input())
list = []
for i in range(N):
    if(N%(i+1) == 0):
        list.append([i+1, N//(i+1)])
min = 1000000000000
for i in list:
    if(min > i[0]+i[1]):
        min = i[0]+i[1]
print(min-2)

### FIXED CODE ###

import math
N = int(input())
list = []
for i in range(int(math.sqrt(N))):
    if(N%(i+1) == 0):
        list.append([i+1, N//(i+1)])
min = 1000000000000
for i in list:
    if(min > i[0]+i[1]):
        min = i[0]+i[1]
print(min-2)
### BUGGY CODE ###

from sys import stdin


n = int(stdin.readline().strip())
a_lst = [int(x) for x in stdin.readline().strip().split()]

min_diff = 2020202021

for i in range(len(a_lst)):
  left = sum(a_lst[:i])
  right = sum(a_lst[i:])
  if abs(left - right) < min_diff:
    min_diff = abs(left - right)
    
print(min_diff)

### FIXED CODE ###

from sys import stdin


n = int(stdin.readline().strip())
a_lst = [int(x) for x in stdin.readline().strip().split()]

pos = len(a_lst) // 2
min_diff = 10000000000000000000

while(True):
  left = sum(a_lst[:pos])
  right = sum(a_lst[pos:])
  diff = right - left
  
  if min_diff > abs(diff): min_diff = abs(diff)
  else: break
  
  if diff > 0: pos += 1
  elif diff < 0: pos -= 1
    
print(min_diff)
### BUGGY CODE ###

from math import gcd
N = int(input())
A = list(map(int,input().split()))
A.sort()
c = 0
flg = 0
for i in range(N-1,0,-1):
  for j in range(i-1,-1,-1):
    c = gcd(A[i],A[j])
    if c != 1:
      flg = 1
a = gcd(A[0],A[1])
for i in range(2,N):
  a = gcd(a,A[i])
if a == 1 and flg == 0:
  print("pairwise coprime")
elif a == 1 and flg == 1:
  print("setwise coprime")
else:
  print("not coprime")

### FIXED CODE ###

from math import gcd

N = int(input())
A = list(map(int,input().split()))
 
flg = 0
l = [0]*(max(A)+1)
for i in A:
  l[i] += 1
a = gcd(A[0],A[1])
for i in range(2,N):
  a = gcd(a,A[i])
for i in range(2,max(A)+1):
  if sum(l[i::i]) > 1:
    flg = 1
    break



if a == 1 and flg == 0:
  print("pairwise coprime ")
elif a == 1 and flg == 1:
  print("setwise coprime")
else:
  print("not coprime")
### BUGGY CODE ###

n = int(input())

data = {}
names = []
max_poll = 1

for i in range(n):
    s = input()
    if s in names:
        data[s] += 1
    else:
        data[s] = 1
        names.append(s)
    if max_poll < data[s]:
        max_poll = data[s]

winner = []
for key, value in data.items():
    if max_poll == value:
        winner.append(key)

winner.sort()
for i in winner:
    print(i)


### FIXED CODE ###

n = int(input())

data = {}
names = []
max_poll = 1

for i in range(n):
    s = input()
    try:
        data[s] += 1
    except:
        data[s] = 1
        names.append(s)
    if max_poll < data[s]:
        max_poll = data[s]

winner = []
for key, value in data.items():
    if max_poll == value:
        winner.append(key)

winner.sort()
for i in winner:
    print(i)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    x,y,z,k=map(int,input().split())
    A=list(map(int,input().split()))
    B=list(map(int,input().split()))
    C=list(map(int,input().split()))
    S=[]
    from itertools import product
    for a,b,c in product(A,B,C):
        S.append(a+b+c)
    S.sort(reverse=1)
    for i in range(k):
        print(S[i])
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    x,y,z,k=map(int,input().split())
    A=list(map(int,input().split()))
    B=list(map(int,input().split()))
    C=list(map(int,input().split()))
    S=[]
    T=[]
    from itertools import product
    for a,b in product(A,B):
        S.append(a+b)
    S.sort(reverse=1)
    S=S[:k]
    for s,c in product(S,C):
        T.append(s+c)
    T.sort(reverse=1)
    for i in range(k):
        print(T[i])
resolve()
### BUGGY CODE ###

s=input()
a_count=[0]
c_count=[0]
q_lcount=[0]
q_rcount=[0]
n=len(s)
for i in range(n):
    if s[i]=='A':
        a_count.append(a_count[i]+1)
        q_lcount.append(q_lcount[i])
    elif s[i]=='?':
        a_count.append(a_count[i])
        q_lcount.append(q_lcount[i]+1)
    else:
        a_count.append(a_count[i])
        q_lcount.append(q_lcount[i])
for i in range(n):
    if s[n-1-i]=='C':
        c_count.append(c_count[i]+1)
        q_rcount.append(q_rcount[i])
    elif s[n-1-i]=='?':
        c_count.append(c_count[i])
        q_rcount.append(q_rcount[i]+1)
    else:
        c_count.append(c_count[i])
        q_rcount.append(q_rcount[i])
q=q_lcount[n]
ans=0
INF=10**9+7
a=3**q
b=a//3
c=b//3
d=c//3
for i in range(n):
    if s[i]=='B':
        x=a_count[i]*c_count[n-1-i]*a
        y=a_count[i]*q_rcount[n-1-i]*b
        z=q_lcount[i]*c_count[n-1-i]*b
        w=q_lcount[i]*q_rcount[n-1-i]*c
        ans=(ans+x+y+z+w)%INF
    elif s[i]=='?':
        x=a_count[i]*c_count[n-1-i]*b
        y=a_count[i]*q_rcount[n-1-i]*c
        z=q_lcount[i]*c_count[n-1-i]*c
        w=q_lcount[i]*q_rcount[n-1-i]*d
        ans=(ans+x+y+z+w)%INF
print(int(ans))


### FIXED CODE ###

s=input()
a_count=[0]
c_count=[0]
q_lcount=[0]
q_rcount=[0]
n=len(s)
for i in range(n):
    if s[i]=='A':
        a_count.append(a_count[i]+1)
        q_lcount.append(q_lcount[i])
    elif s[i]=='?':
        a_count.append(a_count[i])
        q_lcount.append(q_lcount[i]+1)
    else:
        a_count.append(a_count[i])
        q_lcount.append(q_lcount[i])
    if s[n-1-i]=='C':
        c_count.append(c_count[i]+1)
        q_rcount.append(q_rcount[i])
    elif s[n-1-i]=='?':
        c_count.append(c_count[i])
        q_rcount.append(q_rcount[i]+1)
    else:
        c_count.append(c_count[i])
        q_rcount.append(q_rcount[i])
q=q_lcount[n]
ans=0
INF=10**9+7
a=3**q
b=a//3
c=b//3
d=c//3
a=a%INF
b=b%INF
c=c%INF
d=d%INF
for i in range(n):
    if s[i]=='B':
        x=a_count[i]*c_count[n-1-i]*a
        y=a_count[i]*q_rcount[n-1-i]*b
        z=q_lcount[i]*c_count[n-1-i]*b
        w=q_lcount[i]*q_rcount[n-1-i]*c
        ans=(ans+x+y+z+w)%INF
    elif s[i]=='?':
        x=a_count[i]*c_count[n-1-i]*b
        y=a_count[i]*q_rcount[n-1-i]*c
        z=q_lcount[i]*c_count[n-1-i]*c
        w=q_lcount[i]*q_rcount[n-1-i]*d
        ans=(ans+x+y+z+w)%INF
print(int(ans))
### BUGGY CODE ###

a, b = map(int, input().split())
c = []
while True:
    for i in range(a):
        x = i + 2
        if a%x == 0:
            if b%x == 0:
                c.append(x)
                a = int(a/x)
                b = int(b/x)
                break
    if i == a-1:
        break
s = 1
for j in c:
    s = s * j
print(s)



### FIXED CODE ###

a, b = map(int, input().split())
c = []
if a > b:
    a, b = b, a
if b%a == 0:
    print(a)
else:
    while True:
        for i in range(a):
            x = i + 2
            if a%x == 0:
                if b%x == 0:
                    c.append(x)
                    a = a//x
                    b = b//x
                    break
                elif b%(a//x) == 0:
                    c.append(a//x)
                    a = x
                    b = b//(a//x)
                    break
            if x > a**0.5:
                break
        if x > a**0.5:
            break
    s = 1
    for j in c:
        s = s * j
    print(s)
### BUGGY CODE ###

n = int(raw_input())
a = map(int,raw_input().split(' '))
b = []
for i in range(n):
    if i%2 == 0:
        b.append(a[i])
    else:
        b.insert(0,a[i])
if n%2 != 0:
    b.reverse()
s = str(b[0])
for i in range(n-1):
    s += ' ' + str(b[i+1])
print s

### FIXED CODE ###

n = int(raw_input())
a = map(int,raw_input().split(' '))
b = [0 for i in range(int(round(n/2.)))]
b_r = [0 for i in range(n//2)]
for i in range(n):
    if i%2 == 0:
        b[i/2] = a[i]
    else:
        b_r[i/2] = a[i]

n2 = int(round(n/2.))
if n%2 == 0:
    s = str(b_r[n2-1])
    for i in range(1,n):
        if i < n2:
            s += ' ' + str(b_r[n2-1-i])
        else:
            s += ' ' + str(b[i-n2])
    print s
else:
    s = str(b[n2-1])
    for i in range(1,n):
        if i < n2:
            s += ' ' + str(b[n2-1-i])
        else:
            s += ' ' + str(b_r[i-n2])
    print s
### BUGGY CODE ###

N = int(input())
p = 1

for i in range(N):
    p = p * (i + 1)

print(p % (10 ** 9 + 7))  # べき乗の書き方

### FIXED CODE ###

N = int(input())
p = 1

for i in range(N):
    p = p * (i + 1)
    p = p % (10 ** 9 + 7)

print(p)  # べき乗の書き方
### BUGGY CODE ###

import numpy as np


def main():
    n, k = map(int, input().split())
    A = np.array(list(map(int, input().split())))
    for _ in [0] * k:
        new_A = np.array([0] * n)
        for i in range(n):
            left = i - A[i]
            right = i + A[i] + 1
            if left < 0:
                if right >= n:
                    new_A += 1
                else:
                    new_A[:right] += 1

            else:
                if right >= n:
                    new_A[left:] += 1
                else:
                    new_A[left:right] += 1


        A = new_A
        if min(A) == n:
            break

    for a in A:
        print(a, end=" ")


if __name__ == "__main__":
    main()


### FIXED CODE ###

# 累積和
import numpy as np
from numba import njit

@njit(cache=True)
def loop(n, k, A):
    for _ in [0] * k:
        B = np.zeros(n + 1, dtype=np.int64)
        for i in range(n):
            left = max(0, i - A[i])
            right = min(n, i + A[i] + 1)
            B[left] += 1
            B[right] -= 1
        A = np.cumsum(B)[:-1]
        #print(A)
        if np.all(A == n):
            return A
            break

    return A


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    A = np.array(a, dtype=np.int64)
    A = loop(n, k, A)
    print(*A)


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

import numpy as np
N, Y = list(map(int, input().split()))
flag=0
s = np.array([10000, 5000, 1000])
try:
  for x in range(N+1):
    for y in range(N+1-x):
      z = N - x- y
      #if x*10000 + y*5000 + z*1000 == Y:
      if s.dot(np.array([x,y,z])) == Y:
        print(x, y, z)
        flag = 1
        raise Exception
except Exception:
  pass
if flag == 0:
  print('-1 -1 -1')


### FIXED CODE ###

N, Y = list(map(int, input().split()))
flag=0
try:
  for x in range(N+1):
    for y in range(N+1-x):
      z = N - x- y
      if x*10000 + y*5000 + z*1000 == Y:
        print(x, y, z)
        flag = 1
        raise Exception
except Exception:
  pass
if flag == 0:
  print('-1 -1 -1')