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

from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

h,w = inpl()
s = [[0] * w for i in range(h)]
ss = [[0] * w for i in range(h)]
st = [[0] * w for i in range(h)]
for i in range(h):
    s[i] = input()

for i in range(h):
    cnt = 0
    start = w
    end = w
    for j in range(w)[::-1]:
        if s[i][j] == '.':
            cnt += 1
            start = j
        else:
            for k in range(start,end):
                ss[i][k] = cnt
            cnt = 0
            end = j
        if cnt > 0:
            for k in range(start,end):
                ss[i][k] = cnt
for i in range(w):
    cnt = 0
    start = h
    end = h
    for j in range(h)[::-1]:
        if s[j][i] == '.':
            cnt += 1
            start = j
        else:
            for k in range(start,end):
                st[k][i] = cnt
            cnt = 0
            end = j
        if cnt > 0:
            for k in range(start,end):
                st[k][i] = cnt
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, ss[i][j] + st[i][j])
print(ans-1)


### FIXED CODE ###

from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

h,w = inpl()
s = [[0] * w for i in range(h)]
r = [[0] * w for i in range(h)]
l = [[0] * w for i in range(h)]
u = [[0] * w for i in range(h)]
d = [[0] * w for i in range(h)]

for i in range(h):
    s[i] = input()

# cal l
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            l[i][j] = 0
        elif j == 0:
            l[i][j] = 1
        else:
            l[i][j] = l[i][j-1] + 1
# cal r
for i in range(h):
    for j in range(w)[::-1]:
        if s[i][j] == '#':
            r[i][j] = 0
        elif j == w-1:
            r[i][j] = 1
        else:
            r[i][j] = r[i][j+1] + 1
# cal u
for i in range(w):
    for j in range(h):
        if s[j][i] == '#':
            u[j][i] = 0
        elif j == 0:
            u[j][i] = 1
        else:
            u[j][i] = u[j-1][i] + 1
# cal d
for i in range(w):
    for j in range(h)[::-1]:
        if s[j][i] == '#':
            d[j][i] = 0
        elif j == h-1:
            d[j][i] = 1
        else:
            d[j][i] = d[j+1][i] + 1
ans = 0
# print(l,r,u,d)
for i in range(h):
    for j in range(w):
        ans = max(ans, r[i][j] + l[i][j] + u[i][j] + d[i][j])
print(ans-3)
### BUGGY CODE ###

from copy import deepcopy

n = int(input())
a = [list(map(lambda x:int(x) - 1, input().split())) for _ in range(n)]

d = [0] * n

ans = 0
temp = set([x for x in range(n)])
while 1:
    next_temp = set()
    for t in temp:
        if d[t] >= n - 1:
            continue
        u = a[t][d[t]]
        if a[u][d[u]] == t:
            next_temp.add(t)
            next_temp.add(u)
    #print(next_temp, d)
    for t in next_temp:
        d[t] += 1
    if len(next_temp) == 0:
        break
    temp = deepcopy(next_temp)
    ans += 1

if d.count(n-1) == n:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

from copy import deepcopy
from heapq import heappop, heappush

n = int(input())
a = [list(map(lambda x:int(x) - 1, input().split())) for _ in range(n)]

d = [0] * n

ans = 0
temp = []
for x in range(n):
    heappush(temp, x)
while 1:
    next_temp = []
    while len(temp) > 0:
        x = heappop(temp)
        if d[x] >= n-1:
            continue
        y = a[x][d[x]]
        #print(x, y)
        if y not in next_temp:
            if a[y][d[y]] == x:
                heappush(next_temp, x)
                heappush(next_temp, y)
    #print(next_temp)
    for t in next_temp:
        d[t] += 1
    if len(next_temp) == 0:
        break
    temp = [] + next_temp
    ans += 1

#print(d)

if d.count(n-1) == n:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

import sys
import numpy as np
def input(): return sys.stdin.readline().strip()
inf = sys.maxsize

if __name__ == '__main__':
    h, w, k = map(int,input().split())
    s = np.array([[int(i) for i in input()] for _ in range(h)])
    ans = inf
    for i in range(2 ** (h - 1)): #縦方向の割り方を全探索 O(512)
        hdiv = [1 if i & 2 ** j else 0 for j in range(h - 1)]
        hdiv.append(1)
        sh = sum(hdiv)
        tmpans = sh - 1
        partsum = [0 for _ in range(sh)]
        j = 0
        while j < w: #O(2 * 10 ** 3)
            tmp = 0
            idx = 0
            flag = True
            for kk in range(h): #O(10)
                tmp += s[kk][j]
                if hdiv[kk]:
                    partsum[idx] += tmp
                    if partsum[idx] > k:
                        tmpans += 1
                        partsum = [0 for _ in range(sh)]
                        flag = False
                        break
                    tmp = 0
                    idx += 1
            if flag:
                j += 1
        ans = min(ans, tmpans)
    print(ans)


### FIXED CODE ###

import sys
inf = sys.maxsize

if __name__ == '__main__':
    h, w, k = map(int, sys.stdin.readline().strip().split())
    s = [[int(i) for i in sys.stdin.readline().strip()] for _ in range(h)]
    
    ans = inf
    for i in range(2 ** (h - 1)): #縦方向の割り方を全探索 O(512)
        hdiv = [1 if i & 2 ** j else 0 for j in range(h - 1)]
        hdiv.append(1)
        sh = sum(hdiv)
        tmpans = sh - 1
        partsum = [0 for _ in range(sh)]
        partsum_p = [0 for _ in range(sh)]
        j = 0
        for j in range(w): #O(10 ** 3)
            tmp = 0
            idx = 0
            flag = False
            for kk in range(h): #O(10)
                tmp += s[kk][j]
                if hdiv[kk]:
                    partsum_p[idx] = partsum[idx]
                    partsum[idx] += tmp
                    if partsum[idx] > k and not flag:
                        tmpans += 1
                        flag = True
                    tmp = 0
                    idx += 1
            if flag:
                partsum = [partsum[l] - partsum_p[l] for l in range(sh)]
                partsum_p = [0 for _ in range(sh)]
                for kk in range(sh):
                    if partsum[kk] > k:
                        tmpans = inf
                        break
        ans = min(ans, tmpans)
    print(ans)
### BUGGY CODE ###

from collections import Counter as co
n,m=map(int,input().split())
a=[]
for i in range(m):
    l,r=map(int,input().split())
    
    a.extend(list(range(l,r+1)))
d=co(a)
x,y=zip(*d.items())
print(y.count(m))


### FIXED CODE ###

from collections import Counter as co
n,m=map(int,input().split())
a=[]
x=0
y=10**6
for i in range(m):
    l,r=map(int,input().split())
    if(l>x):
        x=l
    if(r<y):
        y=r
if(y>=x):
    print(y-x+1)
else:
    print(0)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
ans1=[]
ans2=[]
ans1+=a
ans2+=a
for i in range(min(k,32)):
  now=0
  ans2=[]
  ans2+=ans1
  kans=[0]*n
  for j in range(n):
    if j+ans2[j]+1<=n-1:
      kans[j+ans2[j]+1]-=1
    now+=1+kans[j]
    #基本kans[j]は0だが終点は-1
    ans1[j]=now
  now=0
  kans=[0]*n
  for j in range(1,n+1):
    if n-j-ans2[n-j]>=0:
      kans[n-j-ans2[n-j]-1]-=1
    now+=1+kans[n-j]
    #基本kans[j]は0だが終点は-1
    ans1[n-j]+=now-1
print(*ans1)
  
    
      
    

### FIXED CODE ###

import itertools
n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(min(k,50)):
  imos=[0]*(n+1)
  for j in range(n):
    imos[max(j-a[j],0)]+=1
    imos[min(j+a[j]+1,n)]-=1
  a=list(itertools.accumulate(imos))
  if a[:n]==[n]*n:
    break
    
print(*a[:n])
### BUGGY CODE ###

from itertools import permutations
n,m,r=map(int,input().split())
visit=list(map(int,input().split()))
dist=[[10**9]*n for i in range(n)]
for i in range(m):
  a,b,c=map(int,input().split())
  dist[a-1][b-1],dist[b-1][a-1]=c,c
for i in range(n):
  dist[i-1][i-1]=0
for i in range(n):
  for j in range(n):
    for k in range(n):
      dist[j][k]=min(dist[j][k],dist[j][i]+dist[i][k])
ans=10**9
check=permutations(visit)
for i in check:
  c=0
  for j in range(1,r):
    c+=dist[i[j-1]-1][i[j]-1]
  if c<ans:ans=c
print(ans)


### FIXED CODE ###

from itertools import permutations
n,m,r=map(int,input().split())
visit=list(map(int,input().split()))
dist=[[10**9]*n for i in range(n)]
for i in range(m):
  a,b,c=map(int,input().split())
  dist[a-1][b-1],dist[b-1][a-1]=c,c
for i in range(n):
  dist[i-1][i-1]=0
for i in range(n):
  for j in range(n):
    for k in range(n):
      dist[j][k]=min(dist[j][k],dist[j][i]+dist[i][k])
ans=10**9
check=permutations(visit)
for i in check:
  c=0
  for j in range(1,r):
    c+=dist[i[j-1]-1][i[j]-1]
  if c<ans:ans=c
print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(_) for _ in input().split()]

res = 0

for i in set(a):
    tmp = a.count(i)
    if tmp < i:
        res += tmp
    else:
        res += tmp - i

print(res)

### FIXED CODE ###

import bisect
n = int(input())
a = [int(_) for _ in input().split()]
a.sort()

res = 0

for i in set(a):
    tmp = bisect.bisect_right(a,i)-bisect.bisect_left(a,i)
    if tmp < i:
        res += tmp
    else:
        res += tmp - i

print(res)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(int(1e6))
import math

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

if N > M:
    A.sort(reverse=True)
    A1 = A[0:M]
    A2 = A[M:]
    for _ in range(M):
        i = A1.index(max(A1))
        A1[i] = A1[i] // 2
    print(sum(A1 + A2))
else:
    for _ in range(M):
        i = A.index(max(A))
        A[i] = A[i] // 2
    print(sum(A))


### FIXED CODE ###

import sys
sys.setrecursionlimit(int(1e6))

import heapq

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
h_A = []
for a in A:
    heapq.heappush(h_A, -a)

for _ in range(M):
    x = heapq.heappop(h_A)
    heapq.heappush(h_A, -(-x // 2))

prices = [- heapq.heappop(h_A) for _ in range(N)]
print(sum(prices))
### BUGGY CODE ###

N = int(input())
X = [int(_) for _ in input().split()]

X2 = sorted(X)
r = X2[N // 2 ]
l = X2[N // 2 -1]

for i in range(N):
    if X2.index(X[i]) < N // 2:
        print(r)
    else:
        print(l)

### FIXED CODE ###

import bisect

N = int(input())
X = [int(_) for _ in input().split()]

X2 = sorted(X)
r = X2[N // 2 ]
l = X2[N // 2 -1]

for i in range(N):
    if bisect.bisect_left(X2, X[i]) < N // 2:
        print(r)
    else:
        print(l)
### BUGGY CODE ###

n = int(input())
temparr = input()
temparr = temparr.split()
arr = []
for i in temparr:
    arr.append(int(i)  % 1000000007)
    
ans = 0 
for i in range(n - 1):
    curnum = arr[i]
    for j in range(i + 1, n):
        ans += curnum * arr[j]
        if ans >= 1000000007:
            ans = ans % 1000000007

if ans >= 1000000007:
    print(ans % 1000000007)
else:
    print(ans)

### FIXED CODE ###

n = int(input())
temparr = input()
temparr = temparr.split()
arr = []
for i in temparr:
    arr.append(int(i)  % 1000000007)
    
ans = 0 
total = []
curtotal = sum(arr)
total.append(curtotal)
for i in range(n):
    curtotal -= arr[i]
    total.append(curtotal)
for i in range(n):
    total[i] = total[i] % 1000000007

for i in range(n - 1):
    curnum = arr[i]
    tempans = curnum * total[i + 1]
    if tempans >= 1000000007:
        tempans = tempans % 1000000007
    ans += tempans

if ans >= 1000000007:
    print(ans % 1000000007)
else:
    print(ans)
### BUGGY CODE ###

n=int(input())
p=list(map(float,input().split()))
dp=[[0]*(n//2+2) for i in range(n)] #dp[i][j]=i番目までに裏がj枚出る確率
dp[0][0]=p[0]
dp[0][1]=1-p[0]
for i in range(1,n):
    dp[i][0]=dp[i-1][0]*p[i]
    for j in range(1,n//2+1):
        dp[i][j]=dp[i-1][j]*p[i]+dp[i-1][j-1]*(1-p[i])
ans=0
for i in range(n//2+1):
    ans+=dp[-1][i]
print(ans)

### FIXED CODE ###

n=int(input())
p=list(map(float,input().split()))
dp=[[0]*(n//2+2) for i in range(n)] #dp[i][j]=i番目までに裏がj枚出る確率
dp[0][0]=p[0]
dp[0][1]=1-p[0]
for i in range(1,n):
    dp[i][0]=dp[i-1][0]*p[i]
    for j in range(1,n//2+1):
        dp[i][j]=dp[i-1][j]*p[i]+dp[i-1][j-1]*(1-p[i])
ans=0
for i in range(n//2+1):
    ans+=dp[-1][i]
print(ans)
### BUGGY CODE ###

ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
INF = 10**18

N,K=rl()

W = [[0 for _ in range(2*K+3)] for _ in range(2*K+3)]
for i in range(N):
    x,y,c=input().split()
    x = int(x)%(2*K)
    y = (int(y) if c=='W' else int(y)+K)%(2*K)
    if (x<K)^(y<K):
        x %= K
        y %= K
        W[0][y+1] += 1
        W[0][y+K+1] -= 1
        W[x+1][0] += 1
        W[x+1][y+1] -= 2
        W[x+1][y+K+1] += 2
        W[x+1][2*K] -= 1
        W[x+K+1][0] -= 1
        W[x+K+1][y+1] += 2
        W[x+K+1][y+K+1] -= 2
        W[x+K+1][2*K] += 1
        W[2*K][y+1] -= 1
        W[2*K][y+K+1] += 1
    else:
        x %= K
        y %= K
        W[0][0] += 1
        W[x+1][0] -= 1
        W[0][y+1] -= 1
        W[x+1][y+1] += 2
        W[x+K+1][y+1] -= 2
        W[x+1][y+K+1] -= 2
        W[x+K+1][y+K+1] += 1
        W[x+K+1][0] += 1
        W[2*K][0] -= 1
        W[2*K][y+1] += 1
        W[0][y+K+1] += 1
        W[0][2*K] -= 1
        W[x+1][2*K] += 1

ans = 0
for x in range(0,2*K+1):
    for y in range(0,2*K+1):
        W[x][y] += W[x][y-1]
for y in range(0,2*K+1):
    for x in range(0,2*K+1):
        W[x][y] += W[x-1][y]
        ans = max(ans,W[x][y])

print(ans)

### FIXED CODE ###

ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
INF = 10**18

N,K=rl()

W = [[0 for _ in range(2*K+3)] for _ in range(2*K+3)]
for i in range(N):
    x,y,c=input().split()
    x = int(x)%(2*K)
    y = (int(y) if c=='W' else int(y)+K)%(2*K)
    if (x<K)^(y<K):
        x %= K
        y %= K
        W[0][y+1] += 1
        W[0][y+K+1] -= 1
        W[x+1][0] += 1
        W[x+1][y+1] -= 2
        W[x+1][y+K+1] += 2
        W[x+1][2*K] -= 1
        W[x+K+1][0] -= 1
        W[x+K+1][y+1] += 2
        W[x+K+1][y+K+1] -= 2
        W[x+K+1][2*K] += 1
        W[2*K][y+1] -= 1
        W[2*K][y+K+1] += 1
    else:
        x %= K
        y %= K
        W[0][0] += 1
        W[x+1][0] -= 1
        W[0][y+1] -= 1
        W[x+1][y+1] += 2
        W[x+K+1][y+1] -= 2
        W[x+1][y+K+1] -= 2
        W[x+K+1][y+K+1] += 1
        W[x+K+1][0] += 1
        W[2*K][0] -= 1
        W[2*K][y+1] += 1
        W[0][y+K+1] += 1
        W[0][2*K] -= 1
        W[x+1][2*K] += 1

ans = 0
for x in range(0,2*K+1):
    for y in range(0,2*K+1):
        W[x][y] += W[x][y-1]
for y in range(0,2*K+1):
    for x in range(0,2*K+1):
        W[x][y] += W[x-1][y]
        ans = max(ans,W[x][y])

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

n = int(input())
s = input()
l = [0]*n
for i in range(n):
    l[i] = s[0:i].count('W') + s[i+1:].count('E')
print(min(l))    

### FIXED CODE ###

n = int(input())
s = input()
es = s.count('E')
e_cnt = 0
l = [0]*n
for i in range(n):
    left = i-e_cnt
    if s[i] == 'E':
        e_cnt +=1
    right = es - e_cnt
    l[i] = right+left

print(min(l))
### BUGGY CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

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())

s = ns()
n = len(s)
MOD = 10**9 + 7

dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1

for i, si in enumerate(s):
    if si == '?':
        for k in range(10):
            for j in range(13):
                dp[i+1][(10*j + k) % 13] += dp[i][j]
                dp[i + 1][(10 * j + k) % 13] %= MOD

    else:
        k = int(si)
        for j in range(13):
            dp[i + 1][(10 * j + k) % 13] += dp[i][j]
            dp[i + 1][(10 * j + k) % 13] %= MOD

print(dp[n][5])

### FIXED CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

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())

s = ns()
n = len(s)
MOD = 10**9 + 7

dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1

for i, si in enumerate(s):
    if si == '?':
        for k in range(10):
            for j in range(13):
                dp[i+1][(10*j + k) % 13] += dp[i][j]
                dp[i + 1][(10 * j + k) % 13] %= MOD

    else:
        k = int(si)
        for j in range(13):
            dp[i + 1][(10 * j + k) % 13] += dp[i][j]
            dp[i + 1][(10 * j + k) % 13] %= MOD

print(dp[n][5])
### BUGGY CODE ###

N,Q = map(int, input().split())
import copy
es = {}
for i in range(N-1):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    if a in es:
        es[a].append(b)
    else:
        es[a] = [b]


point_root = [0] * N
query = [None]
for i in range(Q):
    p,x = map(int, input().split())
    point_root[p-1] += x 

ans = [0] * N
for i in range(N):
    ans[i] += point_root[i]
    if es.get(i, None) != None:
        next_nodes = es[i] # これからポイントを足し行くやつら
    else:
        continue
    
    visited = [False] * N
    visited[i] = True
    idx_n = 0
    while idx_n <= len(next_nodes)-1:
        #idx_n = 0
        if idx_n <= len(next_nodes)-1:
            if visited[next_nodes[idx_n]] == False:
                ans[next_nodes[idx_n]] += point_root[i]
                visited[next_nodes[idx_n]] = True
            #print("--",es,next_nodes)
                #print(es[next_nodes[0]])
                #print("ne",next_nodes)
                idx = next_nodes[idx_n]
                #print("aaa",idx, es)
                tmp = es.get(idx, None)
                if tmp != None:
                    next_nodes.extend(tmp)
                    idx_n += 1
                #next_nodes = next_nodes[1:]
            else:
                idx_n += 1
        else:
            break

print(*ans)



### FIXED CODE ###

N,Q = map(int, input().split())
import copy
import sys

sys.setrecursionlimit(10**6)
es = [[] for i in range(N)]

for i in range(N-1):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    es[a].append(b)
    es[b].append(a)


point = [0] * N

for i in range(Q):
    p,x = map(int, input().split())
    point[p-1] += x 

ans = [0] * N
ans[0] = point[0] # 一番上の根なのでこれだけ
visited = [False] * N
visit_cnt = 1
from collections import deque
nexts = deque([0])
while len(nexts) >= 1:
    now = nexts.popleft()
    visited[now] = True

    for next in es[now]:
        if visited[next] == True:
            continue
        nexts.append(next)
        ans[next] = ans[now] + point[next]


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

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

n, q = map(int, input().split())
clst = list(map(int, input().split()))
lr_1 = [list(map(int, input().split())) + [i] for i in range(q)]
lr = lr_1.copy()
lr.sort(key=lambda x:x[1])
bit = Bit(n)
pos = 0
last = [-1 for _ in range(n)]
ans = []
for i, c in enumerate(clst):
    bit.add(i + 1, 1)
    if last[c - 1] != -1:
        bit.add(last[c - 1] + 1, -1)
    last[c - 1] = i
    while lr[pos][1] == i + 1:
        l = lr[pos][0]
        r = lr[pos][1]
        ans.append([bit.sum(r) - bit.sum(l - 1), lr[pos][2]])
        pos += 1
        if pos == q:
            break
    if pos == q:
        break
ans.sort(key=lambda x:x[1])
for num, _ in ans:
    print(num)



### FIXED CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

import sys
input = sys.stdin.buffer.readline

n, q = map(int, input().split())
clst = list(map(int, input().split()))
lr = []
for i in range(q):
    l, r = map(int, input().split())
    lr.append([l, r, i])
lr.sort(key=lambda x:x[1])
bit = Bit(n)
pos = 0
last = [-1 for _ in range(n)]
ans = [-1 for _ in range(q)]
for i, c in enumerate(clst):
    bit.add(i + 1, 1)
    if last[c - 1] != -1:
        bit.add(last[c - 1] + 1, -1)
    last[c - 1] = i
    while lr[pos][1] == i + 1:
        l = lr[pos][0]
        r = lr[pos][1]
        ans[lr[pos][2]] = bit.sum(r) - bit.sum(l - 1)
        pos += 1
        if pos == q:
            break
    if pos == q:
        break
    
print(*ans, sep="\n")
### BUGGY CODE ###

import string

ALPHABETS = string.ascii_lowercase

s = input()
N = len(s)
MAX = 2 * 10 ** 5
a = [0] * (N + 1)
for i, c in enumerate(s):
    idx = ALPHABETS.index(c)
    a[i+1] = a[i] ^ (2 ** idx)

opt = [0] * (N + 1)
dp = {}
dp[0] = 0
for i in range(1, N + 1):
    dp[a[i]] = min(dp.get(a[i], MAX), min([dp.get(a[i] ^ 2 ** j, MAX) if not j == -1 else dp.get(a[i] ^ 0, MAX) for j in range(-1, 26)]) + 1)

print(dp[a[N]] if dp[a[N]] != 0 else 1)


### FIXED CODE ###

s = input()
N = len(s)
a = 0
dp = {}
dp[0] = 0
bits = [2 ** i for i in range(26)]

for c in s:
    a = a ^ bits[ord(c)-ord('a')]
    dp[a] = min(dp.get(a, N), min([dp.get(a ^ bit, N) for bit in bits]) + 1)

print(dp[a] if dp[a] != 0 else 1)
### BUGGY CODE ###

import numpy as np
a = map(int,raw_input().split())
N = a[0]
x = a[1]
A = map(int,raw_input().split())

B = [A]
m = sum(B[0])
for idx in xrange(1,N):
  B.append( [min(B[idx-1][i], A[i-idx]) for i in range(N)] )
  m = min(m, sum(B[idx])+idx*x)
 
print int(m)

### FIXED CODE ###

import time
import numpy as np
import copy

tflag = False
if tflag:
  N = 2000
  m = 1000000000
  x = np.random.randint(m)
  A = list(np.random.randint(m,size=(N)))
  st = time.time()
else:
  N, x = map(int,raw_input().split())
  A = map(int,raw_input().split())

#B = copy.deepcopy(A)
B = A
A = A + A
m = sum(B)
for idx in xrange(1,N):
  for jdx in xrange(N):
    if B[jdx] > A[jdx+N-idx]:
      B[jdx] = A[jdx+N-idx]
#  A = np.append(A, A[0])
#  A = np.delete(A, 0)
#  B = np.fmin(B,A)
  m = min(sum(B)+idx*x, m)

print int(m)
### BUGGY CODE ###

n = int(input())
data = [int(input()) for k in range(n)]
for i in range(n):
	s = [data[t] for t in range(n)]
	s[i] = 0
	s.sort()
	print(s[-1])

### FIXED CODE ###

n = int(input())
data = [int(input()) for k in range(n)]
m1,m2 = sorted(data, reverse=1)[:2]
b = [m2 if x==m1 else m1 for x in data]
print('\n'.join(map(str,b)))
### BUGGY CODE ###

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

ans=[]
[ans.append(a[i]) if i%2 ==0 else ans.insert(0,a[i]) for i in range(n)]
print(str(ans).replace("[","").replace("]","").replace(",","") if n%2 ==0 else str(ans[::-1]).replace("[","").replace("]","").replace(",","") )

### FIXED CODE ###

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

ans=[0]*n
for i in range(n):
  if i%2 ==0:
    ans[n//2+i//2]=a[i]
  else:
    ans[n//2-i//2-1]=a[i]

print(str(ans).replace("[","").replace("]","").replace(",","") if n%2 ==0 else str(ans[::-1]).replace("[","").replace("]","").replace(",","") )
### BUGGY CODE ###

s=input()
ans=0
for i in range(0,len(s)-4):
    for j in range(i+5, len(s)+1):
        if int(s[i:j])%2019==0:
            ans+=1

print(ans)

### FIXED CODE ###

s=input()
s= s[::-1]

S=[0,]
cnt=[0]*2019
cnt[0]=1
d=1
num=0
for i in range(len(s)):
    num += int(s[i])*d
    num %= 2019
    d *= 10
    d%= 2019
    # S.append((int(S[i]) + int(s[i]) * 10**i) % 2019)
    cnt[num]+=1

ans=0
for i in cnt:
    ans += i*(i-1) //2

print(ans)