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

# -*- coding: utf-8 -*-


# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    h, w = input_to_int_map()
    zone = [[s for s in input()] for i in range(h)]

    from collections import deque
    black_cell = deque()
    black_cell_pos = set()

    black_distance = [[0] * w for i in range(h)]
    for i, row in enumerate(zone):
        for j, cell in enumerate(row):
            if cell == "#":
                black_cell.append((i, j))
                black_cell_pos.add((i, j))

    while black_cell:
        black_h, black_w = black_cell.popleft()
        pre_black_distance = black_distance[black_h][black_w]
        for i, j in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            move_h = black_h + i
            move_w = black_w + j
            if move_h < 0 or move_w < 0 or move_h >= h or move_w >= w:
                continue
            if not (move_h, move_w) in black_cell_pos:
                black_distance[move_h][move_w] = pre_black_distance + 1
                black_cell.append((move_h, move_w))
                black_cell_pos.add((move_h, move_w))

    return max(list(map(max, black_distance)))


if __name__ == "__main__":
    print(main())


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]

# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    """
    BFSを用いて、全マス目を黒くする回数を求める

    Args:
        black_cells: 「開始時の黒マス」の座標が入ったキュー（複数座標あり）
        dist: 「開始時の黒マス」からの距離の入ったリスト  [[-1, -1, 0], ...]
        　　　（白マスの初期値は0）

    Returns:
        g: 操作を繰り返した数
    """
    d = 0
    while black_cells:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)
### BUGGY CODE ###

h,w=map(int,input().split())
h+=2
w+=2
s=[]
l=[[0 for i in range(w)]for j in range(h)]
yl=[[]for j in range(h)]
tl=[[]for j in range(w)]
s.append(["#"]*w)
for i in range(h-2):
    a=input()
    s.append("#"+a+"#")
s.append(["#"]*w)

for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            yl[i].append(j)
            tl[j].append(i)
ans=0
import bisect
for i in range(1,h-1):
    for j in range(1,w-1):
        if s[i][j]!="#":
            n=bisect.bisect(yl[i],j)
            m=bisect.bisect(tl[j],i)
            p=0
            p+=yl[i][n]-yl[i][n-1]+tl[j][m]-tl[j][m-1]-3
            
            ans=max(ans,p)
                
        
print(ans)
    








### FIXED CODE ###

h,w=map(int,input().split())
s=[]
l=[[0 for i in range(w)]for j in range(h)]
 
for i in range(h):
    a=input()
    s.append(a)

yoko=[[0 for j in range(w)] for j in range(h)]
tate=[[0 for j in range(w)] for j in range(h)]

for i in range(h):
    p=0
    for j in range(w):
        if s[i][j]=="#" or j==w-1:
            if s[i][j]==".":
                for k in range(p):
                    yoko[i][j-k-1]+=p+1
                yoko[i][j]+=p+1
            else:
                for k in range(p):
                    yoko[i][j-k-1]+=p
            p=0
        elif s[i][j]==".":
            p+=1
for i in range(w):
    p=0
    for j in range(h):
        if s[j][i]=="#" or j==h-1:
            if s[j][i]==".":
                for k in range(p):
                    tate[j-k-1][i]+=p+1
                yoko[j][i]+=p+1
            else:
                for k in range(p):
                    tate[j-k-1][i]+=p
            p=0
        elif s[j][i]==".":
            p+=1
ans=0
for i in range(h):
    for j in range(w):
        ans=max(ans,yoko[i][j]+tate[i][j]-1)

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

n=int(input())
s=set()
for i in range(n):
  s^={input()}
print(len(s))

### FIXED CODE ###

from collections import Counter
N=int(input())
A=Counter([int(input()) for i in range(N)])
print(sum(1 if count%2 else 0 for count in A.values()))
### BUGGY CODE ###

def main():
	n=int(input())
	a=list(map(int, input().split()))
	count = 0
	for i in range(n):
		for j in range(n):
			if i == j:
				count =count
			elif a[i]==a[j] :
				count+=1
			else:
				count=count
	if count==0:
		print('YES')
	else:
		print('NO')
main()

### FIXED CODE ###

def main():
	n=int(input())
	a=list(map(int, input().split()))
	a.sort()
	c=0
	for i in range(n-1):
		if a[i] == a[i+1]:
			print('NO')
			c+=1
			break
	if c==0:
		print('YES')
main()
### BUGGY CODE ###

LIMIT = 1000000000000000000

def main():
    N = int(input())  # 文字列または整数(一変数)
    a = list(map(int, input().split()))  # 整数のリスト
    answer = 1

    for i in range(N):
        answer *= a[i]

    if answer > LIMIT:
        print(-1)
    else:
        print(answer)


if __name__ == '__main__':
    main()


### FIXED CODE ###

LIMIT = 1000000000000000000

def main():
    N = int(input())  # 文字列または整数(一変数)
    a = list(map(int, input().split()))  # 整数のリスト
    answer = 1

    for i in range(N):
        answer *= a[i]
        if answer > LIMIT:
            if 0 in a[i:]:
                print(0)
                return
            else:
                print(-1)
            return

    print(answer)

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

s=input()
l=len(s);mod=10**9+7
dp=[[0]*13 for i in range(l)]
rem=[1,10,9,12,3,4]
for i in range(l)[::-1]:
  dig=(l-i-1)%6
  if s[i]=="?":
    if i==l-1:
      for j in range(10):
        dp[-1][(j*rem[dig])%13]=1
    else:
      for j in range(10):
        for h in range(13):
          dp[i][(h+j*rem[dig])%13]+=dp[i+1][h]
          dp[i][(h+j*rem[dig])%13]%=mod
  else:
    a=int(s[i])
    if i==l-1:
      dp[i][(a*rem[dig])%13]=1
    else:
      for j in range(13):
        dp[i][(j+a*rem[dig])%13]+=dp[i+1][j]
        dp[i][(j+a*rem[dig])%13]%=mod
print(dp[0][5])


### FIXED CODE ###

s=input()
l=len(s);mod=10**9+7
dp=[[0]*13 for i in range(l)]
rem=[1,10,9,12,3,4]
for i in range(l)[::-1]:
  dig=(l-i-1)%6
  if s[i]=="?":
    if i==l-1:
      for j in range(10):
        dp[-1][(j*rem[dig])%13]=1
    else:
      for j in range(10):
        for h in range(13):
          dp[i][(h+j*rem[dig])%13]+=dp[i+1][h]
          dp[i][(h+j*rem[dig])%13]%=mod
  else:
    a=int(s[i])
    if i==l-1:
      dp[i][(a*rem[dig])%13]=1
    else:
      for j in range(13):
        dp[i][(j+a*rem[dig])%13]+=dp[i+1][j]
        dp[i][(j+a*rem[dig])%13]%=mod
print(dp[0][5])
### BUGGY CODE ###

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

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
res = 0
dict = {}
dict[a[0]+1] = 1
for i in range(1,n):
  res += dict.get(i+1-a[i],0)
  dict[a[i]+i+1] = dict.get(a[i]+i+1,0) + 1
print(res)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n, = map(int, readline().split())
xyp = tuple(tuple(map(int, readline().split())) for _ in range(n))

N = 1<<n
INF = 1<<60
resx = []
resy = []
for i in range(n):
    x,y,p = xyp[i]
    rx = [abs(x)]*N
    ry = [abs(y)]*N
    for j in range(n):
        for k in range(1<<j):
            rx[k+(1<<j)] = min(rx[k],abs(x-xyp[j][0]))
            ry[k+(1<<j)] = min(ry[k],abs(y-xyp[j][1]))
    
    for j in range(N):
        rx[j] *= p
        ry[j] *= p
    resx.append(rx)
    resy.append(ry)


ans = [INF]*(n+1)
for m0 in range(N):
    v = n
    for i in range(n):
        if m0>>i&1: v-=1
    mx = (N-1)&~m0
    while mx>=0:
        my = (N-1)^m0^mx
        r = 0    
        for i in range(n):
            r += min(resx[i][mx],resy[i][my])
        if r < ans[v]:
            ans[v] = r
        mx = (mx-1)&~m0
        

for i in ans:
    print(i)



### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n, = map(int, readline().split())
xyp = tuple(tuple(map(int, readline().split())) for _ in range(n))

N = 1<<n
INF = 1<<60
resx = []
resy = []
for i in range(n):
    x,y,p = xyp[i]
    rx = [min(abs(x),abs(y))]*N
    ry = [min(abs(x),abs(y))]*N
    for j in range(n):
        for k in range(1<<j):
            rx[k+(1<<j)] = min(rx[k],abs(x-xyp[j][0]))
            ry[k+(1<<j)] = min(ry[k],abs(y-xyp[j][1]))
    
    for j in range(N):
        rx[j] *= p
        ry[j] *= p
    resx.append(rx)
    resy.append(ry)

ans = [INF]*(n+1)
N = 3**n

p = tuple(3**i for i in range(n+1))
rv = [0]*N
rx = [0]*N
ry = [0]*N
for j in range(n):
    for k in range(p[j]):
        rv[k+  p[j]] = rv[k+2*p[j]] = rv[k]
        rv[k] += 1

        rx[k+  p[j]] = rx[k]|(1<<j)
        ry[k+  p[j]] = ry[k]

        rx[k+2*p[j]] = rx[k]
        ry[k+2*p[j]] = ry[k]|(1<<j)

for mask in range(N):
    v = rv[mask]
    x = rx[mask]
    y = ry[mask]
    
    r = 0    
    for i in range(n):
        r += min(resx[i][x],resy[i][y])
    if r < ans[v]:
        ans[v] = r

for i in ans[::-1]:
    print(i)
### BUGGY CODE ###

number = int(input())
heights = list(map(int, input().split()))
timeslist = []
for i in range(number):
    times = number-i-1
    q = 0
    for j in range(times):
        if heights[i+j] >= heights[i+j+1]:
            q+=1
        else:
            break
    timeslist.append(q)
print(max(timeslist))

### FIXED CODE ###

number = int(input())
heights = list(map(int, input().split()))
plusminus=[]
answerlist = [0]
q = 0
for i in range(number-1):
    if i != number-2 and heights[i]>=heights[i+1]:
        q += 1
    elif i == number-2 and heights[i]>=heights[i+1]:
        q += 1
        answerlist.append(q)
    else:
        answerlist.append(q)
        q = 0
print(max(answerlist))
### BUGGY CODE ###

a = int(input())

N = [1,2,3,4,5,6,7,8,9]

for x in range(a-1):
  tmp = N.pop(0)
  if tmp%10 != 0:
    N.append(tmp*10+tmp%10-1)
  N.append(tmp*10+tmp%10)
  if tmp%10 != 9:
    N.append(tmp*10+tmp%10+1)
print(N.pop(0))

### FIXED CODE ###

a = int(input())

N = [1,2,3,4,5,6,7,8,9]

for x in range(a):
  tmp = N[x]
  if tmp%10 != 0:
    N.append(tmp*10+tmp%10-1)
  N.append(tmp*10+tmp%10)
  if tmp%10 != 9:
    N.append(tmp*10+tmp%10+1)
print(N[a-1])
### BUGGY CODE ###

H,N = map(int,input().split())
spells = [list(map(int,input().split())) for i in range(N)]
INF = 10**10
dp = [INF]*(H+1)
dp[0] = 0
for use in spells:
    damage = use[0]
    mp = use[1]
    for i in range(1,H+1):
        dp[i] = min(dp[max(0,i-damage)] + mp, dp[i])
print(dp[-1])

### FIXED CODE ###

h,n=map(int,input().split())
mahou=[list(map(int,input().split())) for i in range(n)]
INF=10**10
dp=[INF]*(h+1)#そのHPを与えるのに必要な最小MP
dp[0]=0
for hp in range(h+1):
  for use in mahou:
    dp[hp]=min(dp[max(0,hp-use[0])]+use[1],dp[hp])
print(dp[h])
### BUGGY CODE ###

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

class BIT(object):
    def __init__(self, size):
        self.size = size+1
        self.bitree = [0]*self.size
        
    def addval(self, idx:int, val:int):
        if idx < self.size:
            self.bitree[idx] += val
            self.addval(idx + (idx&(-idx)), val)
            
    def getsum(self, idx:int):
        if idx <= 0:
            return 0
        else:
            return self.bitree[idx] + self.getsum(idx - (idx&(-idx)))
    
    def reset(self):
        self.bitree = [0]*self.size


def val2ord(a: list, rev=False):
    dic = {ai: i for i, ai in enumerate(sorted(a, reverse=rev))}
    return [dic[ai] for ai in a]


n,k = li()
a = [ni() for _ in range(n)]

acc = [0] + list(accumulate(a))

b = [acci - i*k for i,acci in enumerate(acc)]

c = val2ord(b)

bitree = BIT(n+1)

ans = 0

for ci in c:
    bitree.addval(ci+1, 1)
    ans += bitree.getsum(ci+1)-1

print(ans)

### FIXED CODE ###

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

class BIT(object):
    def __init__(self, size):
        self.size = size+1
        self.bitree = [0]*self.size
        
    def addval(self, idx:int, val:int):
        while idx < self.size:
            self.bitree[idx] += val
            idx += idx&(-idx)
            
    def getsum(self, idx:int):
        ret = 0
        while idx > 0:
            ret += self.bitree[idx]
            idx -= idx&(-idx)
            
        return ret
    
    def reset(self):
        self.bitree = [0]*self.size


def val2ord(a: list, rev=False):
    dic = {ai: i for i, ai in enumerate(sorted(a, reverse=rev))}
    return [dic[ai] for ai in a]


n,k = li()
a = [ni() for _ in range(n)]

acc = [0] + list(accumulate(a))

b = [acci - i*k for i,acci in enumerate(acc)]
c = val2ord(b)

bitree = BIT(n+1)

ans = 0
for ci in c:
    bitree.addval(ci+1, 1)
    ans += bitree.getsum(ci+1)-1

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

import collections
from itertools import combinations
N = int(input())
ab = [tuple(map(int, input().split())) for i in range(N-1)]
M = int(input())
uv = [tuple(map(int, input().split())) for i in range(M)]

G = [[-1]*N for i in range(N)]
for i in range(N-1):
    a, b = ab[i]
    a -= 1
    b -= 1
    G[a][b] = i
    G[b][a] = i

q = collections.deque()

G2 = [[set() for j in range(N)] for i in range(N)]

for i in range(N):
    q.append((i, set()))
    reached = [False]*N
    reached[i] = True
    while(q):
        x, s = q.popleft()
        for y in range(N):
            if G[x][y] == -1 or reached[y]:
                continue
            else:
                G2[i][y] = s | set([G[x][y]])
                q.append((y, s | set([G[x][y]])))
                reached[y] = True


ans = 2**(N-1)
a = set(range(N-1))
ans2 = 0
for i in range(1, M+1):
    for x in combinations(range(M), i):
        tmp = set(range(N-1))
        for y in x:
            u, v = uv[y]
            u -= 1
            v -= 1
            tmp &= (a - G2[u][v])
        #print(((-1)**(i-1)), len(tmp), tmp, x)
        ans2 += ((-1)**(i-1)) * 2 ** (len(tmp))
    #print(ans2, i)

print(ans-ans2)


### FIXED CODE ###

import collections
from itertools import combinations
N = int(input())
ab = [tuple(map(int, input().split())) for i in range(N-1)]
M = int(input())
uv = [tuple(map(int, input().split())) for i in range(M)]


def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


G = [[-1]*N for i in range(N)]
for i in range(N-1):
    a, b = ab[i]
    a -= 1
    b -= 1
    G[a][b] = i
    G[b][a] = i

q = collections.deque()

G2 = [[0 for j in range(N)] for i in range(N)]

for i in range(N):
    q.append((i, 0))
    reached = [False]*N
    reached[i] = True
    while(q):
        x, s = q.popleft()
        for y in range(N):
            if G[x][y] == -1 or reached[y]:
                continue
            else:
                G2[i][y] = s | (1 << G[x][y])
                q.append((y, s | 1 << G[x][y]))
                reached[y] = True


ans = 2**(N-1)
ans2 = 0
for i in range(1, 2**M):
    tmp = 2**(N-1) - 1
    for j in range(M):
        if (i >> j) % 2 == 1:
            u, v = uv[j]
            u -= 1
            v -= 1
            tmp &= ~G2[u][v]
    ans2 += ((-1)**(popcount(i)-1)) * (1 << popcount(tmp))
    # print(ans2, i)
print(ans-ans2)
### BUGGY CODE ###

from heapq import heappop, heappush

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())

l = []
for _ in range(H):
    s = input()
    l.append([1 if i=="#" else 0 for i in s])

Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

q = [(0, Ch, Cw)]
INF = 10**12
used = [[False]*W for _ in range(H)]
costs = [[INF]*W for _ in range(H)]
used[Ch][Cw] = True
costs[Ch][Cw] = 0

while q:
    cost, h, w = heappop(q)
    if h==Dh and w==Dw:
        break

    for hh, ww in [(h+1, w), (h-1, w), (h, w+1), (h, w-1)]:
        if not (0<=hh<H and 0<=ww<W):
            continue
        if l[hh][ww]:
            continue
        # used[hh][ww] = True
        if costs[hh][ww] > costs[h][w]:
            costs[hh][ww] = costs[h][w]
            heappush(q, (cost, hh, ww))

    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if dh==0 and dw==0:
                continue
            hh = h+dh
            ww = w+dw
            if not (0<=hh<H and 0<=ww<W):
                continue
            if l[hh][ww]:
                continue
            if costs[hh][ww] > costs[h][w]+1:
                costs[hh][ww] = costs[h][w]+1
                heappush(q, (cost+1, hh, ww))
            # heappush(q, (cost+1, hh, ww))


print(costs[Dh][Dw] if costs[Dh][Dw]!=INF else -1)


### FIXED CODE ###

from heapq import heappop, heappush
import sys
input=sys.stdin.readline


def solve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())

    l = []
    for _ in range(H):
        s = input()
        l.append([1 if i=="#" else 0 for i in s])

    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1

    q = [(0, (Ch, Cw))]
    INF = 10**12
    costs = [[INF]*W for _ in range(H)]
    costs[Ch][Cw] = 0

    while q:
        cost, pos = heappop(q)
        h, w = pos
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                hh = h+dh
                ww = w+dw
                if not (0<=hh<H and 0<=ww<W):
                    continue
                if l[hh][ww]:
                    continue
                
                if (abs(dh)==1 and abs(dw)==0) or (abs(dh)==0 and abs(dw)==1):
                    if costs[hh][ww] > costs[h][w]:
                        costs[hh][ww] = costs[h][w]
                        heappush(q, (cost, (hh, ww)))
                elif costs[hh][ww] > costs[h][w]+1:
                    costs[hh][ww] = costs[h][w]+1
                    heappush(q, (cost+1, (hh, ww)))

    print(costs[Dh][Dw] if costs[Dh][Dw]!=INF else -1)


solve()
### BUGGY CODE ###

n = int(input())
a=list(map(int,input().split()))
a.sort()
dp = [True for _ in range(a[n-1])]
for val in set(a):
    for i in range(2*val,a[n-1]+1,val):
        dp[i-1]=False
ans = 0
for val in a:
    if dp[val-1] and a.count(val)==1:
        ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
dp=[True]*a[-1]
def hantei(i):
    ans = True
    if i!=n-1:
        if a[i]==a[i+1]: ans = False
    if i!=0:
        if a[i]==a[i-1]: ans=False
    return ans
for val in set(a):
    for i in range(2*val,a[-1]+1,val): dp[i-1]=False
ans=0
for i in range(n):
    if dp[a[i]-1] and hantei(i)==1: ans+=1
print(ans)
### BUGGY CODE ###

import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

s = s()

mod = 2019
num_int = 0
mod_dict = defaultdict(int)
mod_dict[num_int % mod] += 1
for i in range(len(s)):
    num_int = 10 ** i * int(s[-i-1]) + num_int
    mod_dict[num_int % mod] += 1

for i in mod_dict:
    ans += ((mod_dict[i] - 1) * mod_dict[i]) // 2

print(ans)

### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

s = s()

mod = 2019
num_int = 0
mod_dict = defaultdict(int)
mod_dict[num_int % mod] += 1
s = s[::-1]
t = 1
for i in range(len(s)):
    num_int += t * int(s[i])
    num_int %= mod
    t *= 10
    t %= mod
    mod_dict[num_int] += 1

for i in mod_dict:
    ans += ((mod_dict[i] - 1) * mod_dict[i]) // 2

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

n,k=map(int, input().split())
p=list(map(int, input().split()))
ans = 0.0
for i in range(len(p)-k+1):
    karians = sum(p[i:i+k])/2 + k*0.5
    if ans < karians:
        ans = karians
print(ans)


### FIXED CODE ###

n,k=map(int, input().split())
p=list(map(int, input().split()))
ksum = sum(p[0:k])
ans = kans = ksum/2 + k*0.5
for i in range(n-k):
    ksum = ksum -p[i] +p[i+k]
    kans = ksum/2 + k*0.5
    if ans < kans:
        ans = kans
print(ans)