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

import sys
from itertools import accumulate
input=sys.stdin.buffer.readline

def main():
    n, k = map(int, input().strip().split())
    A = [*map(int, input().strip().split())]
    
    # for _ in range(min(k,int(math.log(n,2)))):
    
    for _ in "_"*k:
        b=[0]*(n)
        
        for i,v in enumerate(A):
            b[max(0,i-v)]+=1
            if i+v+1<n:
                b[i+v+1]-=1
        
        # update ans
        # cnt=0
        # for i in range(1,n):
        #     b[i]+=b[i-1]
        A=[*accumulate(b)]
        
        if min(A)==n:
            break
    print(" ".join(map(str,A)))

if '__main__' == __name__:
    main()

### FIXED CODE ###

import sys
from itertools import accumulate
input=sys.stdin.buffer.readline

def main():
    n, k = map(int, input().split())
    A = [*map(int, input().split())]
    
    # for _ in range(min(k,int(math.log(n,2)))):
    
    for _ in "_"*k:
        b=[0]*(n)
        
        for i,v in enumerate(A):
            if i>v:
            # b[max(0,i-v)]+=1
                b[i-v]+=1
            else:
                b[0]+=1
            j=i-~v
            # if i+v+1<n:
            #     b[i+v+1]-=1
            if j<n:
                b[j]-=1
        
        # update ans
        # cnt=0
        # for i in range(1,n):
        #     b[i]+=b[i-1]
        A=[*accumulate(b)]
        
        if min(A)==n:
            break
    print(" ".join(map(str,A)))

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

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

dp=[float('inf') for i in range(n)]
dp[0]=0

for i in range(1,n):
 for j in range(1,k+1):
  if i-j>=0:
   dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
  else:
   break

print(dp[-1])

### FIXED CODE ###

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

dp=[float('inf')]*n
dp[0]=0
dp[1]=abs(h[1]-h[0])
for i in range(2,n):
    for j in range(max(i-k,0),i):
        dp[i]=min(dp[i],dp[j]+abs(h[i]-h[j]))
print(dp[-1])
### BUGGY CODE ###

# AtCoder Grand Contest 029
# December 15, 2018
#

S = input()
count = 0

while True:
  if S.find('BW') >= 0:
    S = S.replace('BW', 'WB', 1)
    count += 1
  else:
    break

print(count)

### FIXED CODE ###

S = input()
N = len(S)

count = 0
num = 0
idx = -1
while True:
  idx = S.find('W', idx + 1)
  if idx < 0:
    break
  count += idx - num
  num += 1

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

def solve():
    from itertools import combinations
    
    N = int(input())
    S = input()
    
    passcode = set((''.join(t) for t in combinations(S, 3)))
    print(len(passcode))

solve()

### FIXED CODE ###

N = int(input())
S = input()

cnt = 0
for i in range(1000):
    n = '{:03d}'.format(i)
    i = 0
    for d in n:
        try:
            i = S.index(d, i) + 1
        except ValueError:
            break
    else:
        cnt += 1

print(cnt)
### BUGGY CODE ###

N = int(input())
numbers = range(1,N+1)
import re
ans = 0
for number in numbers: 
    digits = list(str(number))
    if re.match("^(3|5|7)+$",str(number)) and all(x in digits for x in ['3','5','7']):
        ans += 1
print(ans)

### FIXED CODE ###

nums = ['7','5','3']
N = input()
Max_digit = len(N)

def generator(n, nums):
    """
    return n-digit number in strings that are made out of numbers in nums and each one use precisely once
    """
    ans = [x for x in nums]
    
    for idx in range(1,n):
        new_ans = []
        for n1 in ans:
            for n2 in nums:
                new_ans.append(n1 + n2)
        ans = new_ans.copy()
    
    return [x for x in ans if all(num in x for num in nums)]

if Max_digit < 3:
    print(0)
if Max_digit == 3:
    ans = generator(3,nums)
    print(len([x for x in ans if int(x) <= int(N)]))
if Max_digit > 3:
    # count the number of eligible numbers which has less digits than N
    counter = 0
    for d in range(3, Max_digit):
        counter += len(generator(d,nums))
    # count the number of eligible numbers of the same digits as N and equal or less than N
    ans = generator(Max_digit, nums)
    counter += len([x for x in ans if int(x) <= int(N)])
    print(counter)
### BUGGY CODE ###

N = int(input())

def Lucas(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    else:
        return Lucas(n - 2) + Lucas(n - 1)

print(Lucas(N))

### FIXED CODE ###

N = int(input())

Lucas = []
Lucas.append(2)
Lucas.append(1)

for i in range(2, 90):
    Lucas.append(Lucas[i - 2] + Lucas[i - 1])

print(Lucas[N])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
i = 0
ans = 0
while(i < n - 1):
    j = 1
    while(i + j < n):
        ans += a[i] * a[i+j]
        j+=1
    i+=1
ans = ans % (10**9 + 7)
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
i = 0
tmp = 0
tmpura = 0
while(i < n):
    tmp += a[i]
    i+=1
tmp=tmp **2
i = 0
while (i < n):
    tmpura += a[i]**2
    i+=1
tmpura=tmpura
ans = ((tmp - tmpura)//2)%(10**9+7)
print(ans)
### BUGGY CODE ###

N, W = map(int, raw_input().split())
dp = [0]*(W+1)

for i in range(N):
    w, v = map(int, raw_input().split())
    for j in range(W, w-1, -1):
        dp[j] = max(dp[j], dp[j-w]+v)

print dp[-1]

### FIXED CODE ###

def main():

    N, W = map(int, raw_input().split())
    dp = [0]*(W+1)
 
    for i in xrange(N):
        w, v = map(int, raw_input().split())
        for j in xrange(W, w-1, -1):
            x = dp[j-w] + v
            if x > dp[j]:
                dp[j] = x
 
    print dp[-1]

main()
### BUGGY CODE ###

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

p_list=[]
latest=""
cnt=[0]*(n+1)
ans=0
plt=0
for i in range(m):
    p,s=map(str,input().split())
    if s == "WA":
        cnt[int(p)] += 1;
    if s == "AC":
        if p != latest:
            if p not in p_list:
                ans+=1
                plt+=cnt[int(p)]
                p_list.insert(0,p)
                latest=p
        
print(str(ans) + " " + str(plt))



### FIXED CODE ###

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

p_list=[0]*(n+1)
cnt=[0]*(n+1)
ans=0
plt=0
for i in range(m):
    p,s=map(str,input().split())
    if s == "WA":
        cnt[int(p)] += 1;
    if s == "AC":
        if p_list[int(p)] == 0:
                ans+=1
                plt+=cnt[int(p)]
                p_list[int(p)] += 1
        
print(str(ans) + " " + str(plt))
### BUGGY CODE ###

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


def change(arr):
  newAs = [0] * n
  for i, a in enumerate(arr):
    for t in range(max(i - a, 0), min(i + a + 1, n)):
      newAs[t] += 1
  return newAs


for temp in range(min(k, 10**4)):
  As = change(As)
print(' '.join(map(str, As)))

### FIXED CODE ###

import math
from itertools import accumulate
n, k = map(int, input().split())
As = list(map(int, input().split()))
for i in range(min(41, k)):
  _As = [0]*(n+1)
  for j in range(n):
    l = max(0, j - As[j])
    r = min(n - 1, j + As[j])
    _As[l] += 1
    _As[r+1] -= 1
  As = list(accumulate(_As))[:-1]
print(' '.join([str(A) for A in As]))
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
c=[n for i in range(n)]
for j in range(k):
    d=[0 for i in range(n+1)]
    for i in range(n):
        d[max(i-a[i],0)]+=1
        d[min(i+a[i]+1,n)]-=1
    e=[d[0]]
    for i in range(n-1):#ちょっと特殊な累積和 普通のものの[1:-1]
        e.append(e[i]+d[i+1])
    #print(d,e,sep='\n')
    #print(e)
    a=e
    if e==c:
        break
print(*a)


### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
c=[n for i in range(n)]
for j in range(k):
    d=[0 for i in range(n+1)]
    for i in range(n):
        d[max(i-a[i],0)]+=1
        d[min(i+a[i]+1,n)]-=1
    e=[d[0]]
    for i in range(n-1):#ちょっと特殊な累積和 普通のものの[1:-1]
        e.append(e[i]+d[i+1])
    #print(d,e,sep='\n')
    #print(e)
    a=e
    if e==c:
        break
print(*a)
### BUGGY CODE ###

n = int(input())
a = tuple(map(int, input().split()))

b = []
for i in range(len(a)):
    b.append(a[i])
    b = b[::-1]

print(*b)


### FIXED CODE ###

n = int(input())
a = tuple(map(int, input().split()))
reverse_a = a[::-1]


if n % 2 == 0:
    first = first = reverse_a[::2]
    second = a[::2]
else:
    first = reverse_a[::2]
    second = a[1:n:2]

print(*first+second)
### BUGGY CODE ###

n = int(input())
li = []
for i in range(n):
  li.append(input())
li_a = sorted(list(set(li)))
li_ans = [0 for i in range(len(li_a))]
for x in li:
  b = li_a.index(x)
  li_ans[b] += 1
for i in range(len(li_ans)):
  if li_ans[i] == max(li_ans):
    print(li_a[i])


### FIXED CODE ###

n = int(input())
li = []
for i in range(n):
  li.append(input())
from collections import Counter
s = Counter(li)
a = list(s.values())
b = list(s.keys())
ans = []
m = 0
for x in a:
  m = max(m, x)
for i in range(len(a)):
  if a[i] == m:
    ans.append(b[i])
ans_a = sorted(ans)
ans_b = "\n".join(ans_a)
print(ans_b)
### BUGGY CODE ###

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

L.sort(reverse=True)

import itertools
from math import factorial

nCr = N*(N-1)*(N-2)/6
A = []*(int(nCr))

A = list(itertools.combinations(L,3))

count = 0
 
for i in range(len(A)):
    a = A[i][0]
    b = A[i][1]
    c = A[i][2]
    
    if b+c > a:
        count += 1
print(count)  

### FIXED CODE ###

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

L.sort()

import bisect
ans = 0

for i in range(N-2):
    for j in range(i+1,N-1):
        a = L[i] 
        b = L[j] 
        
        insert_index = bisect.bisect_left(L,a+b)
        #print(insert_index,a,b,a+b)
        
        if i < insert_index:
            ans += insert_index - j - 1
            #print(i,j,insert_index)
        
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
AB = [list(map(int,input().split())) for i in range(m)]
#入力
AB.reverse()
ans = [0]*(m+1)
ans[m] = n*(n-1)//2
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    # 属している集合の要素数
    def search(self,x):
        count = 0
        for y in range(1,n+1):
            if UnionFind.same_check(self,x,y):
                count += 1
        return count
uf = UnionFind(n)

for i in range(m):
    a = AB[i][0]
    b = AB[i][1]
    #print(a,b)
    if uf.same_check(a,b):
        ans[m-i-1] = ans[m-i]
        continue
    else:
        s = uf.search(a)
        t = uf.search(b)
        #print(s,t)
        uf.union(a,b)
        ans[m-i-1] = ans[m-i] + s*(s-1)//2 + t*(t-1)//2 - (s+t)*(s+t-1)//2
for i in range(1,m+1):
    print(ans[i])

### FIXED CODE ###

n,m = map(int,input().split())
AB = [list(map(int,input().split())) for i in range(m)]
#入力
AB.reverse()
ans = [0]*(m+1)
ans[m] = n*(n-1)//2
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.count = [1]* (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.count[y] += self.count[x]
            self.count[x] = 0
        else:
            self.par[y] = x
            self.count[x] += self.count[y]
            self.count[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    # 属している集合の要素数
    def search(self,x):
        q = UnionFind.find(self,x)
        return self.count[q]

uf = UnionFind(n)

for i in range(m):
    a = AB[i][0]
    b = AB[i][1]
    #print(a,b)
    if uf.same_check(a,b):
        ans[m-i-1] = ans[m-i]
        continue
    else:
        s = uf.search(a)
        t = uf.search(b)
        #print(s,t)
        uf.union(a,b)
        ans[m-i-1] = ans[m-i] + s*(s-1)//2 + t*(t-1)//2 - (s+t)*(s+t-1)//2
for i in range(1,m+1):
    print(ans[i])
### BUGGY CODE ###

n, k = map(int,input().split())
n_min = 10**18
n_min_sb = 10**19
if k == 1:
    n_min = 0
else:
    while n_min != n_min_sb:
        n = abs(n-k)
        if n_min > n:
            n_min_sb = n_min
            n_min = n
        if n_min < n:
            n_min_sb = n_min
print(n_min)

### FIXED CODE ###

n, k = map(int, input().split())
print(min(n%k, k-n%k))
### BUGGY CODE ###

n,C = map(int,input().split())
d = [[int(i) for i in input().split()] for _ in range(C)]
c = [[int(i)-1 for i in input().split()] for _ in range(n)]

cnt0 = [0]*C
cnt1 = [0]*C
cnt2 = [0]*C
for i in range(n):
    for j in range(n):
        for k in range(C):
            if (i+j)%3 == 0: cnt0[k] += d[c[i][j]][k]
            elif (i+j)%3 == 1: cnt1[k] += d[c[i][j]][k]
            else: cnt2[k] += d[c[i][j]][k]

ans = float("inf")
for i in range(C):
    for j in range(C):
        if i == j: continue
        for k in range(C):
            if i == k or j == k: continue
            ans = min(ans, cnt0[i] + cnt1[j] + cnt2[k])
print(ans)

### FIXED CODE ###

n,C = map(int,input().split())
d = [[int(i) for i in input().split()] for _ in range(C)]
c = [[int(i)-1 for i in input().split()] for _ in range(n)]

cnt0 = [0]*C
cnt1 = [0]*C
cnt2 = [0]*C
for i in range(n):
    for j in range(n):
        for k in range(C):
            if (i+j)%3 == 0: cnt0[k] += d[c[i][j]][k]
            elif (i+j)%3 == 1: cnt1[k] += d[c[i][j]][k]
            else: cnt2[k] += d[c[i][j]][k]

ans = float("inf")
for i in range(C):
    for j in range(C):
        if i == j: continue
        for k in range(C):
            if i == k or j == k: continue
            ans = min(ans, cnt0[i] + cnt1[j] + cnt2[k])
print(ans)
### BUGGY CODE ###

A, B, C, D = map(int, input().split())

c = C - A
d = D - B
mod = 998244353
dp = [[0]*(d+1) for i in range(c+1)]
dp[0][0] = 1

for i in range(c+1):
    for j in range(d+1):
        if i > 0 and j > 0:
            if i == j == 1:
                dp[i][j] -= (A+i-1) * (B+j-1)
            else:
                tmp = dp[i-1][j-1]
                #print(tmp, i, j)
                tmp *= (A+i-1)*(B+j-1)

                # print(dp[i][j], tmp)
                dp[i][j] -= tmp

        if i < c:
            dp[i+1][j] += dp[i][j]*(B+j)
        if j < d:
            dp[i][j+1] += dp[i][j]*(A+i)
        # print(dp)
        dp[i][j] %= mod

print(dp[c][d])

### FIXED CODE ###

def main():
    A, B, C, D = map(int, input().split())

    c = C - A
    d = D - B
    mod = 998244353
    dp = [[0]*(d+1) for i in range(c+1)]
    dp[0][0] = 1

    for i in range(c+1):

        for j in range(d+1):
            ret = 0
            if i == 0 and j == 0:
                continue
            if i > 0 and j > 0:
                if i == j == 1:
                    ret -= (A+i-1) * (B+j-1)
                else:
                    ret -= dp[i-1][j-1]
                    ret *= (A+i-1)*(B+j-1)
            ret += dp[i-1][j]*(B+j) + dp[i][j-1]*(A+i)

            ret %= mod
            dp[i][j] = ret
    print(dp[c][d])


main()
### BUGGY CODE ###

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

maxNum = -1

for indx in range(N - (K - 1)):
  maxNum = max(sum(inList[indx: indx + K]), maxNum)

print((maxNum + K) / 2)

### FIXED CODE ###

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

lastSum = sum(inList[0: K])
maxNum = lastSum

for indx in range(1, N - (K - 1)):
  maxNum = max(lastSum - inList[indx-1] + inList[indx+K-1], maxNum)
  lastSum = lastSum - inList[indx-1] + inList[indx+K-1]

print((maxNum + K) / 2)
### BUGGY CODE ###

s = list(input())

minLength = 4
maxLength = len(s)
cnt = 0

for position in range(maxLength):
    modCnt = 0
    for i in range(position, maxLength):
        modCnt = (modCnt + int(s[i])) % 3
        if modCnt == 0:
            num = int(''.join(s[position:i+1]))
            if num % 673 == 0:
                cnt += 1

print(cnt)


### FIXED CODE ###

s = list(input())
mods = [0]*(len(s))
countRemainder = [0] * 2019
cnt = 0


m = 1
mod = 0
for i in range(len(s)):
    mod += int(s[len(s) - i - 1]) * m

    mod %= 2019
    m *= 10
    m %= 2019

    countRemainder[mod] += 1

countRemainder[0] += 1

for i in range(2019):
    cnt += int(countRemainder[i] * (countRemainder[i] - 1) / 2)

print(cnt)
### BUGGY CODE ###

def solve():
    s = input()
    t = input()

    dp = [[0] * (len(t)+1) for _ in range(len(s)+1)]

    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])
    
    res = ""
    i = len(s)
    j = len(t)
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            res = s[i-1] + res
            i -= 1
            j -= 1
    
    print(res)
if __name__ == '__main__':
    solve()

### FIXED CODE ###

def solve():
    s = input()
    t = input()

    dp = [[0] * (len(t)+1) for _ in range(len(s)+1)]

    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])
    
    res = ""
    i = len(s)
    j = len(t)
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            res = s[i-1] + res
            i -= 1
            j -= 1
    
    print(res)
if __name__ == '__main__':
    solve()
### BUGGY CODE ###

import heapq
from collections import defaultdict

def main():
    N, M = map(int, input().split())
    ans = 0
    d = defaultdict(list)
    for _ in range(N):
        A, B = map(int, input().split())
        d[A].append(-B)
    cand = []
    heapq.heapify(cand)
    for day in range(M-1,-1,-1):
        diff = M - day
        if d[diff]:
            cand += d[diff]
            heapq.heapify(cand)
        if cand:
            ans -= heapq.heappop(cand)

    print(ans)



if __name__ == "__main__":
    main()

### FIXED CODE ###

from heapq import heappush, heappop

def main():
    N, M = map(int, input().split())

    # 日数別に仕事を管理
    works = [[] for _ in range(M)]

    for i in range(N):
        A, B = map(int, input().split())
        
        if A > M:
            continue
        
        deadline = M - A
        # heapqは最小値を返す仕組みしかないので、最大値を返すため-する
        works[deadline].append(-B)
    
    ans = 0
    heapque = []

    # i日目に始めることができる仕事で報酬の高いものを選ぶ
    for i in range(M - 1, -1, -1):
        for work in works[i]:
            # heapqに候補を追加
            heappush(heapque, work)
        
        if heapque:
            ans += heappop(heapque)
    
    print(-ans)


main()
### BUGGY CODE ###

import sys
INF = 10**18
sys.setrecursionlimit(10**6)
from collections import defaultdict
def li():
    return [int(x) for x in input().split()]
from collections import deque

H, W = li()
Ch, Cw = li()
Dh, Dw = li()
S = [list(input()) for x in range(H)]

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

def bfs():
    costmap = [[-1] * W for i in range(H)]
    costmap[Ch-1][Cw-1] = 0
    que = deque([])
    que.append((Cw, Ch))

    while que:
        # print(que)
        # 左から取り出す
        x, y = que.popleft()
        # 通常移動パターン
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # バリデーション
            if nx <= 0 or nx > W or ny <= 0 or ny > H:
                continue
            if S[ny-1][nx-1] != '.':
                continue
            # 初探索 or コストが下がる場合
            if costmap[ny-1][nx-1] == -1 or costmap[y-1][x-1] < costmap[ny-1][nx-1]:
                # コストゼロは左から
                que.appendleft((nx, ny))
                costmap[ny-1][nx-1] = costmap[y-1][x-1]
        # 特殊移動パターン
        for i in range(x-2, x+3):
            for j in range(y-2, y+3):
                nx, ny = i, j
                # バリデーション
                if nx <= 0 or nx > W or ny <= 0 or ny > H:
                    continue
                if S[ny-1][nx-1] != '.':
                    continue
                # 初探索 or コストが下がる場合
                if costmap[ny-1][nx-1] == -1 or costmap[y-1][x-1] < costmap[ny-1][nx-1]:
                    # コスト1は右から
                    que.append((nx, ny))
                    costmap[ny-1][nx-1] = costmap[y-1][x-1] + 1
    return costmap

costmap = bfs()
# print(costmap)
print(costmap[Dh-1][Dw-1])


### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
s=[list(input()) for i in range(h)]
 
#幅優先で解く。
dx=[1,0,-1,0]
dy=[0,1,0,-1]
def bfs():
  maze=[[-1]*w for i in range(h)]
  maze[ch-1][cw-1]=0
  qu=deque([])
  qu.append((cw-1,ch-1))
  magic=0
  
  while qu:
    x,y=qu.popleft()
    for i in range(4):
      nx=dx[i]+x
      ny=dy[i]+y
      if 0<=nx<=w-1 and 0<=ny<=h-1 and s[ny][nx]=="." and (maze[ny][nx]==-1 or maze[ny][nx]>maze[y][x]):
        qu.appendleft((nx,ny))
        maze[ny][nx]=maze[y][x]
    for i in range(x-2,x+3):
      for j in range(y-2,y+3):
        nx=i
        ny=j
        if 0<=nx<=w-1 and 0<=ny<=h-1 and s[ny][nx]=="." and (maze[ny][nx]==-1 or maze[ny][nx]>maze[y][x]+1):
          qu.append((nx,ny))
          maze[ny][nx]=maze[y][x]+1
  return maze
    
maze = bfs()
print(maze[dh-1][dw-1])
### BUGGY CODE ###

from collections import defaultdict

H, W, M = list(map(int, input().split()))
hw = [list(map(int, input().split())) for _ in range(M)]

d1 = defaultdict(int)
d2 = defaultdict(int)

b = [[False] * (W+1) for _ in range(H+1)]

for h, w in hw:
    d1[h] += 1
    d2[w] += 1
    b[h][w] = True

m1 = max(d1.values())
m2 = max(d2.values())

e1 = [k for k in d1.keys() if d1[k] == m1]
e2 = [k for k in d2.keys() if d2[k] == m2]

flag = True

for x in e1:
    for y in e2:
        if not b[x][y]:
            flag = False
            break
    if not flag:
        break

if flag:
    print(m1+m2-1)
else:
    print(m1+m2)

### FIXED CODE ###

from collections import defaultdict

H, W, M = list(map(int, input().split()))
hw = [list(map(int, input().split())) for _ in range(M)]

d1 = defaultdict(int)
d2 = defaultdict(int)

b = defaultdict(int)

for h, w in hw:
    d1[h] += 1
    d2[w] += 1
    b[(h, w)] = 1

m1 = max(d1.values())
m2 = max(d2.values())

e1 = [k for k in d1.keys() if d1[k] == m1]
e2 = [k for k in d2.keys() if d2[k] == m2]

flag = True

for x in e1:
    for y in e2:
        if b[(x, y)] == 1:
            pass
        else:
            flag = False
            break
    if not flag:
        break

if flag:
    print(m1+m2-1)
else:
    print(m1+m2)
### BUGGY CODE ###

import collections
n = int(input())
s_n = [] * n
for i in range(n):
    s = input()
    s_n.append(collections.Counter(s))

cnt = 0
for i in range(n):
    if s_n[i] == -1:
        continue
    for j in range(i+1,n):
        if s_n[i] == s_n[j]:
            cnt += 1

print(cnt)


### FIXED CODE ###

n = int(input())
ans = 0
used_s = {}
for _ in range(n):
    s = "".join(sorted(input()))
    if not s in used_s.keys():
        used_s[s] = 0
    else:
        used_s[s] += 1
        ans += 1 * used_s[s]

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

N = int(input())
A = list(map(int, input().split()))
n = 0
for i in range(N-1):
  for j in range(i+1, N):
    if j - i == A[i] + A[j]:
      n = n + 1
      
print(n)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
AM = []
AP = []
AMlist = [0] * N
APlist = [0] * N

for i in range(N):
  plus = i+1 + A[i]
  AP.append(plus)  
  if AP[i] <= N:
    APlist[AP[i]-1] += 1
  minus = i+1 - A[i]
  AM.append(minus)
  if AM[i] > 0 and AM[i] <= N:
    AMlist[AM[i]-1] += 1
    
ans = 0

for j in range(N):
  ans += APlist[j] * AMlist[j]

print(ans)