Harryxun/stf_run huggingface dataset:
#https://atcoder.jp/contests/abc061/tasks/abc061_d



# coding: utf-8
# Your code here!

#input_template
inpPh = 3
debug = True
debug = False
if not debug:
    inpPh = 0

input1 ='''
3 3
1 2 4
2 3 3
1 3 5 
'''[1:]

input2 ='''
2 2
1 2 1
2 1 1
'''[1:]

input3 ='''
6 5
1 2 -1000000000
2 3 -1000000000
3 4 -1000000000
4 5 -1000000000
5 6 -1000000000
'''[1:]



inputXs = [input1, input2, input3, None]


if debug:
    try:
        inputXs.append(inputA0)
    except:
        pass
    else:
        pass



    
inploc = inpPh - 1 #0,1,2

if inpPh > 0:
    print(f'selected_input({inpPh}):\n'+inputXs[inploc])


inpX_lst = []
if debug and inpPh > 0:
    inpX_lst = inputXs[inploc].splitlines()


if inpPh == 0:
    N,M = tuple(map(lambda x: int(x), input().split() ) )
else:
    N,M = tuple( map(lambda x: int(x),  inpX_lst.pop(0).split() ) )

elist = []    

for i in range(M):
    if inpPh == 0:
        ai,bi,ci = list(map(lambda x: int(x), input().split() ))
    else:
        ai,bi,ci = list(map(lambda x: int(x), inpX_lst.pop(0).split() ))
    
    ai_loc, bi_loc = ai-1, bi - 1
    elist.append(( ai_loc, bi_loc,-ci))

vlist =[ None for _ in range(N)]    

        
s_loc,g_loc = 0, N-1

vlist[s_loc] = 0
#print(vlist)




is_inf = False
for i in range(len(vlist)):
    for e in elist:
        a,b,c = e
        if vlist[a] == None:
            continue
        elif vlist[b] == None or vlist[b] > vlist[a] + c:
            vlist[b] = vlist[a] + c
            if i == N-1 and b == N-1:
                pass
                is_inf = True
                 
res = -vlist[g_loc]            


if is_inf:
    print('inf')
else:
    print(res)



### FIXED CODE ###

import sys

INF = float('inf')

def Bellmanford(n, edges, r): #r: 始点
    d = [INF] * n
    d[r] = 0
    
    for i in range(n):
        for (u, v, c) in edges:
            if d[u] != INF and d[u] + c < d[v]:
                d[v] = d[u] + c
                if i == n-1 and v == n-1:
                    return 'inf'
    
    return -d[n-1]
    

N, M = map(int, sys.stdin.readline().split())
Edges = [None] * M

for i in range(M):
    ai, bi, ci = map(int, sys.stdin.readline().split())
    Edges[i] = (ai-1, bi-1, -ci)
    
ans = Bellmanford(N, Edges, 0)

print(ans)
while True:
    H, W = map(int, raw_input().split())
    if H == W == 0: break
    print '#'*W
    for i in range(H-2):
        print '#'+'.'*(W-2)+'#'
    print '#'*W+'\n'

### FIXED CODE ###

while 1:
    H, W = map(int,raw_input().split())
    if H + W == 0: break
    print ('#' * W)
    for h in range(H-2):
        print ('#' + '.' * (W - 2) + '#')
    print ('#' * W + '\n')
n=int(input())
for i in range(n):
  A=int(input())
  x=[]
  y=[]
  for j in range(A[i]):
    x,y=[int(s) for s in input().split()]
  X.append(x)
  Y.append(y)
  
c=0
for i in range(n):
  l=[1]*n
  for j in range(i, n-i):
    if l[j]==0:continue
    for k in range(A[j]):
    　　l[X[j][k]] *= Y[j][k]
if c<l.count(1):
  c=l.count(1) 
  
        
  
print(c)  
   

### FIXED CODE ###

n=int(input())
X=[]
Y=[]
A=[0]*n
for i in range(n):
  A[i]=int(input())
  a=A[i]
  x=[0]*a
  y=[0]*a
  for j in range(a):
    x[j],y[j]=[int(s) for s in input().split()]
  X.append(x)
  Y.append(y)
  
s=0
for i in range(2**n):
  c=0
  d=0
  B=[0]*n
  for j in range(n):
    if((i >> j) & 1):
      c=c+1
      B[j]=1
  for k in range(n):
    if B[k]==1:
      for j in range(A[k]):
        if Y[k][j]!=B[X[k][j]-1]:
          d=-1
          break
    if d<0:
      break
  if s<c and d==0:
    s=c
      
      
print(s)
import sys,heapq
input = sys.stdin.buffer.readline


n,m = map(int,input().split())
edge = [[] for _ in range(n)]

for _ in range(m):
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

#True:訪問済み False:未訪問
flag = [False]*n

def dfs(now):
    if flag[now]:
        return 0
    
    flag[now] = True

    size = 0
    for nxt in edge[now]:
        if not flag[nxt]:
            size += dfs(nxt)

    return size + 1

res = 0

for i in range(n):
    if flag[i]:
        continue
    res = max(res,dfs(i))

print(res)


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

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

#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]



#初期化
#根なら-size,子なら親の頂点
par = [-1]*n


for _ in range(m):
    a,b = map(int,input().split())
    unite(a-1,b-1)

res = 0
for e in par:
    if e < 0:
        res = max(res,-e)
print(res)
h,w,a,b=map(int,input().split())

tmp=[0]*w
lista=[]
for i in range(h):
    lista.append([0]*w)
    
if a>w/2 or b>h/2:
    print("No")

elif h==1:
    for i in range(w-a):
        lista[0][a+i]=1
elif w==1:
    for i in range(h-b):
                lista[b+i][0]=1
else:  
    for i in range(w-a):
        lista[0][a+i]=1
        
    print(lista)
    if a==0:    
        for i in range(w):
            for j in range(b):
                lista[j][i]=1 

    if b!=0:    
        for i in range(a):
            for j in range(h-b):
                lista[b+j][i]=1 
        for i in range(b):
            for i in range(w-a):
                lista[i][a+j]=1




for i in range(h):
    row = ""
    for j in range(w):
        row += str(lista[i][j])
    print(row)

### FIXED CODE ###

h,w,a,b=map(int,input().split())

lista=[]

for i in range(h):
    lista.append([0]*w)

if (a>w/2)|(b>h/2):
    print("No")

else:
    if h==1:
        for i in range(w-a):
            lista[0][a+i]=1
    elif w==1:
        for i in range(h-b):
            lista[b+i][0]=1

    elif (a==0)&(b==0):
        lista=lista

    else:  
        for i in range(w-a):
            lista[0][a+i]=1
        
           
        if a==0:    
            for i in range(w):
                for j in range(b):
                    lista[j][i]=1 
        elif b==0:    
            for i in range(h):
                for j in range(w-a):
                    lista[i][j+a]=1                         
        else:    
            for i in range(a):
                for j in range(h-b):
                    lista[b+j][i]=1 
            for i in range(b):
                for j in range(w-a):
                    lista[i][a+j]=1


 

    for i in range(h):
        row = ""
        for j in range(w):
            row += str(lista[i][j])
        print(row)
import math
from scipy.special import comb
p=[]
d=[i+1for i in range(1,10**5)]
while 1:
    t=d[0]
    if math.sqrt(10**5)<=t:
        p+=d
        break
    p.append(t)
    d=[e for e in d if e%t]
n,m=map(int,input().split())
a=1
while m>1:
    t=p.pop(0)
    if m%t:
        continue
    c=0
    while not m%t:
        m//=t
        c+=1
    a=a*math.factorial(n+c-1)//(math.factorial(n-1)*math.factorial(c))%(10**9+7)
print(a)

### FIXED CODE ###

import math
import random
from scipy.misc import comb
class Prime:
    seed_primes=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
    def is_prime(self,n):
        is_prime_common=self.is_prime_common(n)
        if is_prime_common is not None:return is_prime_common
        if n<2000000:return self.is_prime_brute_force(n)
        return self.is_prime_miller_rabin(n)
    def is_prime_common(self,n):
        if n==1:return False
        if n in Prime.seed_primes:return True
        if any(map(lambda x:n%x==0,self.seed_primes)):return False
    def is_prime_brute_force(self,n):
        for k in range(2,int(math.sqrt(n))+1):
            if n%k==0:return False
        return True
    def is_prime_miller_rabin(self,n):
        d=n-1
        while d&1==0:d>>=1
        witnesses=self.get_witnesses(n)
        for w in witnesses:
            y=pow(w,d,n)
            while d!=n-1and y!=1and y!=n-1:
                y=y*y%n
                d<<=1
            if y!=n-1and d&1==0:return False
        return True
    def get_witnesses(self,num):
        def _get_range(num):
            if num<2047:return 1
            if num<1373653:return 2
            if num<25326001:return 3
            if num<3215031751:return 4
            if num<2152302898747:return 5
            if num<3474749660383:return 6
            if num<341550071728321:return 7
            if num<3825123056546413051:return 9
            return 12
        return self.seed_primes[:_get_range(num)]
    def gcd(self,a,b):
        if a<b:return self.gcd(b,a)
        if b==0:return a
        while b:a,b=b,a%b
        return a
    @staticmethod
    def f(x,n,seed):
        p=Prime.seed_primes[seed%len(Prime.seed_primes)]
        return(p*x+seed)%n
    def find_factor(self,n,seed=1):
        if self.is_prime(n):return n
        x,y,d=2,2,1
        count=0
        while d==1:
            count+=1
            x=self.f(x,n,seed)
            y=self.f(self.f(y,n,seed),n,seed)
            d=self.gcd(abs(x-y),n)
        if d==n:
            return self.find_factor(n,seed+1)
        return self.find_factor(d)
    def find_factors(self,n):
        primes={}
        if self.is_prime(n):
            primes[n]=1
            return primes
        while n>1:
            factor=self.find_factor(n)
            primes.setdefault(factor,0)
            primes[factor]+=1
            n//=factor
        return primes
n,m=map(int,input().split())
a=1
for c in Prime().find_factors(m).values():
    a=a*comb(n+c-1,c,exact=1)%(10**9+7)
print(a)
def resolve():
    N = int(input())
    conds = [list(map(int, input().split(" "))) for i in range(N)]
    
    # [[cx, cy, H]]
    candidates = []

    first = sorted(conds, reverse=True, key=lambda x:x[2])[0]
    for cx in range(101):
        for cy in range(101):
            H = abs(first[0]-cx)+abs(first[1]-cy)+first[2]
            for n in range(1, N):
                cond = conds[n]
                if cond[2] == 0:
                    if abs(cond[0]-cx)+abs(cond[1]-cy) < cond[2]: 
                        ansflg = False
                        break
                else:
                    if abs(cond[0]-cand[0])+abs(cond[1]-cand[1])+cond[2] != H:
                        ansflg = False
                        break
            else:
                print("{} {} {}".format(cx, cy, H))
                exit()


if '__main__' == __name__:
    resolve()

### FIXED CODE ###

def resolve():
    N = int(input())
    if N==1:
        print("Hello World")
        return
    A = int(input())
    B = int(input())
    print(A+B)


if '__main__' == __name__:
    resolve()
o=list(input())
e=list(input())
l=[]
if len(o)==len(e):
    for i in range(len(o)):
        l.append(o[i])
        l.append(e[i])
    print("".join(l))
else:
    for i in range(len(e)):
        l.append(o[i])
        l.append(e[i])
    l.append(o[len(o)])
    print("".join(l))


### FIXED CODE ###

o=list(input())
e=list(input())
l=[]
if len(o)==len(e):
    for i in range(len(o)):
        l.append(o[i])
        l.append(e[i])
    print("".join(l))
else:
    for i in range(len(e)):
        l.append(o[i])
        l.append(e[i])
    l.append(o[len(o)-1])
    print("".join(l))
"""
python3 main.py < input.txt
"""
import math
import itertools as it
import heapq

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

L=[A[0]]
for i in range(1, N):
        L.append(math.gcd(1,2))

### FIXED CODE ###

"""
python3 main.py < input.txt
"""
import math
import itertools as it
import heapq

def gcd(a, b):
        return a if b == 0 else gcd(b, a%b)
N=int(input())
A=list(map(int, input().split()))

L=[A[0]]
for i in range(1, N):
        L.append(gcd(L[-1], A[i]))
R=[A[-1]]
for i in reversed(range(N-1)):
        R.append(gcd(R[-1], A[i]))
R.reverse()

m=max(R[1], L[-2])
for i in range(1, N-1):
        m=max(m, gcd(L[i-1], R[i+1]))
print(m)
N=int(input())
S=input()
T=input()
U=[]
for i in range(N):
  U.append(S[i])
  U.append(T[i])
print(U)

### FIXED CODE ###

N=int(input())
S,T=input().split()
U=[]
for i in range(N):
  U.append(S[i])
  U.append(T[i])
print("".join(U))
a,b=map(int,input().split())
if a*b %2=0:
	print("Even")
else:
	print("Odd")

### FIXED CODE ###

a,b=map(int,input().split())
if a*b %2==0:
	print("Even")
else:
	print("Odd")
def c():
    n = int(input())
    a = list(map(int, input().split()))
    l = list(map(lambda i: min(8, i//400), a))
    over_rate = l.count(8)
    res = set(l)
    try: res.remove(8)

    mi = max(1, len(res))
    ma = len(res) + over_rate
    print(mi, ma)


### FIXED CODE ###

def c():
    n = int(input())
    a = list(map(int, input().split()))
    x = []
    def set_col(rate):
        if rate <= 399:
            return '灰色'
        elif rate <= 799:
            return '茶色'
        elif rate <= 1199:
            return '緑色'
        elif rate <= 1599:
            return '水色'
        elif rate <= 1999:
            return '青色'
        elif rate <= 2399:
            return '黄色'
        elif rate <= 2799:
            return '橙色'
        elif rate <= 3199:
            return '赤色'
        else:
            x.append(1)
            return

    res = set(map(set_col, a))
    if None in res: res.remove(None)
    mi = max(1, len(res))
    ma = len(res) + len(x)
    print(mi, ma)

c()
import queue
r,c=map(int,input().split())
#sy,sx=map(int,input().split())
#gy,gx=map(int,input().split())
a=[list(input()) for i in range(r)]
sy,sx = (1,1)
#gy,gx = (2,2)
def minload(sy,sx,a):
    sy-=1
    sx-=1
    #gy-=1
    #gx-=1
    q = queue.Queue()
    d=[(-1,0),(1,0),(0,-1),(0,1)]
    a[sy][sx]=0
    for i in d:
        if 0<=sy+i[0]<r and 0<=sx+i[1]<c and a[sy+i[0]][sx+i[1]]==".":
            a[sy+i[0]][sx+i[1]]=1
            q.put((sy+i[0],sx+i[1]))
    while True:
        if queue.Queue.empty(q):
            break
        y,x=q.get()
        #if y==r and x==c:
            #break
        for i in d:
            if 0<=y+i[0]<r and 0<=x+i[1]<c and a[y+i[0]][x+i[1]]==".":
                a[y+i[0]][x+i[1]]=a[y][x]+1
                q.put((y+i[0],x+i[1]))
    #print(a[gy][gx])
    max = 0
    for i in a:
        for j in i:
            if j != '#' and j !='.':
                if j > max:
                    max = j
    return(max)
max = 0
for sy in range(1,r+1): 
    for sx in range(1,c+1):
        b = []
        for i in a:
            b.append(list(i))
        if a[sy-1][sx-1]==".":
            local_max = minload(sy,sx,b)
            #print(local_max)
            #print(b)
        if local_max > max:
            max = local_max
print(max)

### FIXED CODE ###

import queue
r,c=map(int,input().split())
#sy,sx=map(int,input().split())
#gy,gx=map(int,input().split())
a=[list(input()) for i in range(r)]
sy,sx = (1,1)
#gy,gx = (2,2)
def minload(sy,sx,a):
    sy-=1
    sx-=1
    #gy-=1
    #gx-=1
    q = queue.Queue()
    d=[(-1,0),(1,0),(0,-1),(0,1)]
    a[sy][sx]=0
    for i in d:
        if 0<=sy+i[0]<r and 0<=sx+i[1]<c and a[sy+i[0]][sx+i[1]]==".":
            a[sy+i[0]][sx+i[1]]=1
            q.put((sy+i[0],sx+i[1]))
    while True:
        if queue.Queue.empty(q):
            break
        y,x=q.get()
        #if y==r and x==c:
            #break
        for i in d:
            if 0<=y+i[0]<r and 0<=x+i[1]<c and a[y+i[0]][x+i[1]]==".":
                a[y+i[0]][x+i[1]]=a[y][x]+1
                q.put((y+i[0],x+i[1]))
    #print(a[gy][gx])
    max = 0
    for i in a:
        for j in i:
            if j != '#' and j !='.':
                if j > max:
                    max = j
    return(max)
ans = 0
for sy in range(1,r+1): 
    for sx in range(1,c+1):
        b = []
        for i in a:
            b.append(list(i))
        if a[sy-1][sx-1]==".":
            local_max = minload(sy,sx,b)
            #print(local_max)
            #print(b)
        else:
            local_max = 0
        if local_max > ans:
            ans = local_max
print(ans)
N,A,B=map(int,input().split())
v=list(map(int,input().split()))
v.sort(reverse=True)
a=v[:A]
b=v[:B]
avg=sum(a)/A
print(avg)
c=[[0]*51 for _ in range(51)]
c[0][0]=1
for i in range(50):
  c[i+1][0]=1
  c[i+1][i+1]=1
  for j in range(i):
    c[i+1][j+1]=c[i][j]+c[i][j+1]
if a[0]==a[-1]:
  ans=0
  x=v.count(a[0])
  for i in range(A,B+1):
    if i<=x:
      ans+=C[x][i]
else:
  x=v.count(a[-1])
  y=a.count(a[-1])
  ans=c[x][y]
print(ans)

### FIXED CODE ###

N,A,B=map(int,input().split())
v=list(map(int,input().split()))
v.sort(reverse=True)
a=v[:A]
b=v[:B]
avg=sum(a)/A
print(avg)
c=[[0]*51 for _ in range(51)]
c[0][0]=1
for i in range(50):
  c[i+1][0]=1
  c[i+1][i+1]=1
  for j in range(i):
    c[i+1][j+1]=c[i][j]+c[i][j+1]
if a[0]==a[-1]:
  ans=0
  x=v.count(a[0])
  for i in range(A,B+1):
    if i<=x:
      ans+=c[x][i]
else:
  x=v.count(a[-1])
  y=a.count(a[-1])
  ans=c[x][y]
print(ans)
import fractions
N,M=list(map(int, input().split()))
a = list(map(int, input().split()))
ans = a[0]
for i in range(1, N):
    ans = ans * a[i] // fractions.gcd(ans, a[i])
if ans%2==1 or ans/2>M:
 print(0)
else:
 c=int(M/ans*2)
 d=int((1+c)/2)
 print(d)


### FIXED CODE ###

import fractions
N,M = map(int,input().split())
A = list(map(int,input().split()))
t=1
while A:
 b=0
 for i in range(N):
  A[i]=int(A[i]/2)
  if A[i]%2==1:
   b+=1
 if b==N:
  break
 elif 0<b<N:
  t=0
  break
 else:
  t+=1
if t==0:
 print(0)
else:
 ans = A[0]
 for i in range(1, N):
  ans = ans * A[i] // fractions.gcd(ans, A[i])
 ans=min(ans,(M+1))
 c=int(M/(2**(t-1))/ans)
 d=int(M/(2**(t))/ans)
 print(c-d)
if inputs[0] <= inputs[2] and inputs[2] <= inputs[1]:
    print("Yes")
elif inputs[0] >= inputs[2] and inputs[2] >= inputs[1]:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

inputs = list(map(int,input().split()))
if inputs[0] < inputs[2] < inputs[1] or inputs[0] > inputs[2] > inputs[1]:
    print("Yes")
else:
    print("No")
import collections, itertools
H, W, ch, cw, dh, dw, *S = open(0).read().split()
H, W, ch, cw, dh, dw = [int(_) + 1 for _ in [H, W, ch, cw, dh, dw]]
H += 3
W += 3
S = ['#' * W] + ['#' * W] + ['##' + s + '##'
                             for s in S] + ['#' * W] + ['#' * W]
Dist = [[None] * W for _ in range(H)]
Q = collections.deque([(0, ch, cw)])
while Q:
    d, ox, oy = Q.popleft()
    if Dist[ox][oy] is not None:
        continue
    stack = [[ox, oy]]
    warp = set()
    while stack:
        x, y = stack.pop()
        if (x, y) == (dh, dw):
            print(d)
            exit()
        Dist[x][y] = d
        for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
            nx, ny = x + dx, y + dy
            if Dist[nx][ny] is None:
                if S[nx][ny] == '.':
                    stack += [[nx, ny]]
                else:
                    warp.add((x, y))
    for x, y in warp:
        for dx, dy in itertools.product(range(-2, 3), repeat=2):
            nx, ny = x + dx, y + dy
            if Dist[nx][ny] is None and S[ox][oy] == '.':
                Q += [(d + 1, nx, ny)]
print(-1)


### FIXED CODE ###

import collections, itertools
H, W, ch, cw, dh, dw, *S = open(0).read().split()
H, W, ch, cw, dh, dw = [int(_) + 1 for _ in [H, W, ch, cw, dh, dw]]
H += 3
W += 3
S = ['#' * W] + ['#' * W] + ['##' + s + '##'
                             for s in S] + ['#' * W] + ['#' * W]
Dist = [[None] * W for _ in range(H)]
Q = collections.deque([(0, ch, cw)])
while Q:
    d, ox, oy = Q.popleft()
    if Dist[ox][oy] is not None:
        continue
    stack = [[ox, oy]]
    warp = set()
    while stack:
        x, y = stack.pop()
        if (x, y) == (dh, dw):
            print(d)
            exit()
        Dist[x][y] = d
        for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
            nx, ny = x + dx, y + dy
            if Dist[nx][ny] is None:
                if S[nx][ny] == '.':
                    stack += [[nx, ny]]
                else:
                    warp.add((x, y))
    for x, y in warp:
        for dx, dy in itertools.product(range(-2, 3), repeat=2):
            nx, ny = x + dx, y + dy
            if Dist[nx][ny] is None and S[nx][ny] == '.':
                Q += [(d + 1, nx, ny)]
print(-1)
n = int(input())
d = int(input())
a = n/d + 1
print(a)

### FIXED CODE ###

import math
n, d = map(int, input().split())
se = d * 2 + 1
print(math.ceil(n/se))
n = int(input())
a_list = list(map(int, input().split()))

status = True
execute = 0
while status:
    for i in range(len(a_list)):
        if a_list[i] % 2 == 1:
            status = False
            break
        else:
            a_list[i] = a_list[i] / 2
    if status:
        execute += 1
print(execute)


### FIXED CODE ###

s = input()
counter = 0

for i in range(len(s)):
    if s[i] == '1':
        counter += 1
print(counter)
s = input()
K = int(input())

sub = set()

for i in range(len(s)):
	for j in range(i + 1,i + K + 1):
		sub.add(s[i:j])

ans = list(sorted(sub))

print(sub[K - 1])

### FIXED CODE ###

s = input()
K = int(input())

sub = set()

for i in range(len(s)):
	for j in range(i + 1,i + K + 1):
		sub.add(s[i:j])

ans = list(sorted(sub))

print(ans[K - 1])
n=int(input())
A=list(map(int, input().split()))

L=[0]*2*n
c=0

for i,a in enumerate(A):
  L[i+a]+=1
  if 2*n>i-a>0:
    c+=L[i-a]

print(c)


### FIXED CODE ###

n=int(input())
A=list(map(int, input().split()))
d={}
c=0

for i,a in enumerate(A):
  if i+a not in d:
    d[i+a]=1
  else:
    d[i+a]+=1
  if i-a in d:
    c+=d[i-a]

print(c)
import bisect

alp = {s:i for i, s in enumerate('abcdefghijklmnopqrstuvwxyz')}
N = len(alp)
S = input()
K = int(input())
ans = ''
for s in S:
  i = alp[s]
  if K>=N-i:
    ans += 'a'
    K -= N-i
  else:
    ans += s
if K == 0:
  print(ans)
else:
  K = K%N
  last_s = alp[(S.find(ans[-1])+K)%N]
  print(ans[:-1] + last_s)


### FIXED CODE ###

S = input()
K = int(input())
alp = '0bcdefghijklmnopqrstuvwxyza'
alp_dict = {s:i for i,s in enumerate(alp)}


cnt = 0
ans = ''
for i,s in enumerate(S):
  if cnt + (26-alp_dict[s]) <= K:
    cnt += (26-alp_dict[s])
    ans += 'a'
  else:
    ans += s

if (K-cnt)%26==0:
  print(ans)
else:
  rest = (K-cnt)%26
  print(ans[:-1]+alp[(alp_dict[ans[-1]]+rest)%26])
x = int(input())
# 5 or 6
if x % 11 == 0:
    ans = x // 11 * 2
elif x % 11 <= 6:
    ans = x // 11 * 2 + 1
else:
    ans = x // 11 * 2 + 2

print(ans

### FIXED CODE ###

x = int(input())
# 5 or 6
if x % 11 == 0:
    ans = x // 11 * 2
elif x % 11 <= 6:
    ans = x // 11 * 2 + 1
else:
    ans = x // 11 * 2 + 2

print(ans)
f=lambda:[*map(int,input().split())]
n,k=f()
a=f()
# Binary Search
def ok(x):
    c=0
    for i in a:
      c+=0--i//x
    return c<=n+k
l,r=0,10**9+1
while r-l>10**-2:
  m=(l+r)/2
  if ok(m): r=m
  else: l=m
from math import *
t=ceil(r)
print(t-ok(t-1))

### FIXED CODE ###

f=lambda:[*map(int,input().split())]
n,k=f()
a=f()
a=[i*100 for i in a]
# Binary Search
def ok(x):
    c=0
    for i in a:
      c+=0--i//x
    return c<=n+k
l,r=0,10**11+1
while r-l>1:
  m=l+r>>1
  if ok(m): r=m
  else: l=m
t=0--r//100
print(t-ok(t-1) if t>1 else t)
from sys import stdin
from collections import deque
sa = deque(list((stdin.readline().rstrip())))
sb = deque(list((stdin.readline().rstrip())))
sc = deque(list((stdin.readline().rstrip())))

next = "a"
for i in range(300):
    if next == "a":
        next = sa.popleft()
    if next == "b":
        next = sb.popleft()
    if next == "c":
        next = sc.popleft()
    if len(sa) == 0 and next == "a":
        print("A")
        break
    if len(sb) == 0 and next == "b":
        print("B")
        break
    if len(sc) == 0 and next == "c":
        print("C")
        break

### FIXED CODE ###

from sys import stdin
from collections import deque
sa = deque(list((stdin.readline().rstrip())))
sb = deque(list((stdin.readline().rstrip())))
sc = deque(list((stdin.readline().rstrip())))

next = "a"
for i in range(300):
    if len(sa) == 0 and next == "a":
        print("A")
        break
    if len(sb) == 0 and next == "b":
        print("B")
        break
    if len(sc) == 0 and next == "c":
        print("C")
        break
        
    
    if next == "a":
        next = sa.popleft()
    elif next == "b":
        next = sb.popleft()
    elif next == "c":
        next = sc.popleft()
a,b=map(int,input().split())
if a>=13:
  print(b)
if 6<=a<=12:
  pritn(b/2)
if a<=5:
  print(0)

### FIXED CODE ###

a,b=map(int,input().split())
if a>=13:
  print(b)
if a>=6 and a<=12:
  print(b//2)
if a<=5:
  print(0)