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

from collections import deque
N = int(input())
S = list(input())
R = []
G = []
B = []
for i in range(N):
    if S[i] == "R":
        R.append(i)
    elif S[i] == "G":
        G.append(i)
    elif S[i] == "B":
        B.append(i)
    #if i / 2 in R or i / 2 in G or i / 2 in B
count = len(R)*len(G)*len(B)


for a in R:
    for b in G:
        for c in B:
            num = [a, b, c]
            num.sort()
            if 2 * num[1] - num[0] == num[2]:
                count -= 1

print(count)

### FIXED CODE ###

N = int(input())
S = list(input())
R = []
G = []
B = []
Reval = {}
Geval = {}
Beval = {}
for i in range(N):
    if S[i] == "R":
        R.append(i)
        Reval[2*i] = 2*i
    elif S[i] == "G":
        G.append(i)
        Geval[2*i] = 2*i
    elif S[i] == "B":
        B.append(i)
        Beval[2*i] = 2*i
count = len(R)*len(G)*len(B)

for a in R:
    for b in G:
        if (a + b) in Beval:
            count -= 1
for a in G:
    for b in B:
        if (a + b) in Reval:
            count -= 1
for a in B:
    for b in R:
        if (a + b) in Geval:
            count -= 1
print(count)
### BUGGY CODE ###

s, t = input(), input()
for i in range(len(s)):
  if s[i] != t[i]:
    a = s[i]
    b = t[i]
    s = s.translate(str.maketrans({a: b, b: a}))
if s == t:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

s, t = input(), input()
ls, lt = [ [s[0], {0}] ], [ [t[0], {0}] ]

for i in range(len(s)-1):
  if s[i] != s[i+1]:
    b = True
    for j in range(len(ls)):
      if s[i+1] in ls[j][0]:
        ls[j][1].add(i+1)
        b = False
    if b:
      ls.append( [s[i+1], {i+1}] )
      
for i in range(len(t)-1):
  if t[i] != t[i+1]:
    b = True
    for j in range(len(lt)):
      if t[i+1] in lt[j][0]:
        lt[j][1].add(i+1)
        b = False
    if b:
      lt.append( [t[i+1], {i+1}] )

if len(ls) != len(lt):
  print("No")
else:
  for i in range(len(ls)):
    if ls[i][1] != lt[i][1]:
      print("No")
      exit()
  print("Yes")
### BUGGY CODE ###

import sys
import math
from collections import deque
import copy

input = sys.stdin.readline

s = input()
t = input()

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

for i in range(1, len(s)):
    for l in range(1, len(t)):
        if s[i - 1] == t[l - 1]:
            dp[i][l] = max(max(dp[i - 1][l - 1] + 1, dp[i][l - 1]), dp[i - 1][l])
        else:
            dp[i][l] = max(dp[i][l - 1], dp[i - 1][l])
length = dp[len(s) - 1][len(t) - 1]
if length == 0:
    print("")
else:
    ans = ''
    i = len(s) - 1
    l = len(t) - 1
    while i > 0 and l > 0:
        if dp[i-1][l] == dp[i][l] and i >= 1:
            i -= 1
        elif dp[i][l-1] == dp[i][l] and l >= 1:
            l -= 1
        else:
            ans = s[i - 1] + ans
            i -= 1
            l -= 1
    print(ans)


### FIXED CODE ###

import sys
import math
from collections import deque
import copy

input = sys.stdin.readline

s = input()
t = input()

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

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

import bisect

n = int(input())
s = input()

RGB = [[], [], []]
for i in range(n):
    if s[i] == 'R':
        RGB[0].append(i)
    elif s[i] == 'G':
        RGB[1].append(i)
    else:
        RGB[2].append(i)
total = len(RGB[0]) * len(RGB[1]) * len(RGB[2])
RGB.sort(key=lambda x:len(x))

len_B=len(RGB[2])
max_B=max(RGB[2])
min_B=min(RGB[2])
for r in RGB[0]:
    for g in RGB[1]:
        dif = abs(r - g)
        up = max(r,g)+dif
        down = min(r,g)-dif
        if max_B >=up:
            if RGB[2][bisect.bisect_left(RGB[2],up)]==up:
                total-=1
        if min_B <= down and max_B >= down:
            if RGB[2][bisect.bisect_left(RGB[2],down)]==down:
                total-=1
        if dif % 2 == 0:
            center = (r+g)/2
            center_posi=bisect.bisect_left(RGB[2], center)
            if center_posi < len_B:
                if RGB[2][center_posi]==center:
                    total-=1
print(total)

### FIXED CODE ###

import bisect
import itertools

n = int(input())
s = input()

RGB = [[], [], []]
for i in range(n):
    if s[i] == 'R':
        RGB[0].append(i)
    elif s[i] == 'G':
        RGB[1].append(i)
    else:
        RGB[2].append(i)
total = len(RGB[0]) * len(RGB[1]) * len(RGB[2])
RGB.sort(key=lambda x:len(x))
len_B=len(RGB[2])
max_B=max(RGB[2])
min_B=min(RGB[2])
#for r in RGB[0]:
#    for g in RGB[1]:
bool_B=[False for i in range(n)]
for i in RGB[2]:
    bool_B[i]=True

for rg in itertools.product(RGB[0],RGB[1]):
    r=rg[0]
    g=rg[1]
    dif = abs(r - g)

    up = max(r,g)+dif
    down = min(r,g)-dif

    if max_B >=up:
        if bool_B[up]:
            total-=1
    if min_B <= down and max_B >= down:
        if bool_B[down]:
            total-=1
    if dif % 2 == 0:
        center = (r+g)//2
        if min_B<=center and max_B >= center:
            if bool_B[center]:
                total-=1
print(total)
### BUGGY CODE ###

k, s = map(int, input().split())

cnt = 0

for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x + y + z == s:
                cnt += 1
            else:
                cnt += 0

print(cnt)

### FIXED CODE ###

k, s = map(int, input().split())

cnt = 0

for x in range(k+1):
    for y in range(k+1):
        z = s - x - y
        if 0 <= z <= k:
            cnt += 1
        else:
            cnt += 0

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

import math
from functools import reduce

k = int(input()) + 1


def gcd(*numbers):
    return reduce(math.gcd, numbers)


def counter(num):
    count = 0
    for a in range(1, num):
        for b in range(1, num):
            t = gcd(a,b)
            for c in range(1, num):
                    count += gcd(t, c)
    print(count)

counter(k)


### FIXED CODE ###

from math import gcd 

num = int(input()) + 1

count = 0
for a in range(1, num):
    for b in range(1, num):
        t = gcd(a,b)
        for c in range(1, num):
                count += gcd(t, c)
print(count)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

N = int(input())
v = [[] for _ in range(N)]
for i in range(N - 1) :
    a = int(input())
    v[a-1].append(i + 1)

def rec(cur) :
    ret = []
    for nex in v[cur] :
        ret.append(rec(nex))
    ret.sort(reverse=True)
    if len(ret) == 0 :
        return 0
    return max([i + 1 + ret[i] for i in range(len(ret))])
    
print(rec(0))


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
v = [[] for _ in range(N)]
for i in range(N - 1) :
    a = int(input())
    v[a-1].append(i + 1)

l = [0]
i = 0
while i < len(l) :
    cur = l[i]
    for nex in v[cur] :
        l.append(nex)
    i += 1

dp = [0] * N
while len(l) > 0 :
    cur = l.pop()
    ret = []
    for nex in v[cur] :
        ret.append(dp[nex])
    
    if len(ret) == 0 :
        continue
        
    ret.sort(reverse=True)
    dp[cur] = max([i + 1 + ret[i] for i in range(len(ret))])
    
print(dp[0])
### BUGGY CODE ###

n,k=map(int,input().split())
if k>((n-2)*(n-1))//2:
  print(-1)
else:
  ans=[]
  for a in range(1):
    for b in range(a+1,n):
        ans.append([a+1,b+1])
  i,j,cnt=2,3,0
  while cnt<((n-2)*(n-1))//2-k:
    while j<=n:
      ans.append([i,j])
      j+=1
      cnt+=1
      if cnt==((n-2)*(n-1))//2-k:
        break
    i+=1
  print(len(ans))
  for i in range(len(ans)):
    print(*ans[i])

### FIXED CODE ###

n,k=map(int,input().split())
if k>((n-2)*(n-1))//2:
  print(-1)
else:
  ans=[]
  for b in range(1,n):
    ans.append((1,b+1))
  s=[]
  for i in range(1,n-1):
    for j in range(i+1,n):
      s.append((i+1,j+1))
  for i in range(((n-2)*(n-1))//2-k):
    ans.append((s[i][0],s[i][1]))
  print(len(ans))
  for i in range(len(ans)):
    print(*ans[i])
### BUGGY CODE ###

import sys
input = sys.stdin.readline


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1] * (n + 1)
        self.rnk = [0] * (n + 1)

    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def size(self, x):
        return -self.root[self.find_root(x)]


def main():
    N = int(input())
    x_list = []
    y_list = []
    for i in range(N):
        x, y = map(int, input().split())
        x_list.append([x, i])
        y_list.append([y, i])

    x_list.sort()
    y_list.sort()
    adj = []
    for i in range(N-1):
        adj.append([x_list[i + 1][0] - x_list[i][0], x_list[i + 1][1], x_list[i][1]])
        adj.append([y_list[i + 1][0] - y_list[i][0], y_list[i + 1][1], y_list[i][1]])

    adj.sort()
    uf = UnionFind(N)
    ans = 0
    for edge in adj:
        weight, u, v = edge
        if not uf.isSameGroup(u, v):
            ans += weight
            uf.unite(u, v)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# 6199094

import array
import sys
input = sys.stdin.readline

class UnionFind():
    def __init__(self,n):
        self.parent = [-1 for _ in range(n)]

    def size(self,x):
        return -self.parent[self.find(x)]

    def find(self,x):
        if(self.parent[x]<0):
            return x
        else:
            self.parent[x]=self.find(self.parent[x])
            return self.parent[x]

    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return False
        if(self.size(x)<self.size(y)):
            self.parent[y]+=self.parent[x]
            self.parent[x]=y
        else:
            self.parent[x]+=self.parent[y]
            self.parent[y]=x
        return True

    def same(self,x,y):
        return self.find(x)==self.find(y)

def main():
    N = int(input())
    xli = []
    yli = []
    x_app = xli.append
    y_app = yli.append


    for i in range(N):
        x,y = (int(x) for x in input().split())
        x_app([x-1,i])
        y_app([y-1,i])
    xli.sort()
    yli.sort()

    edges = []
    edges_app = edges.append
    for i in range(N-1):
        edges_app((xli[i][1],xli[i+1][1],xli[i+1][0]-xli[i][0]))
        edges_app((yli[i][1],yli[i+1][1],yli[i+1][0]-yli[i][0]))


    edges.sort(key=lambda edge: edge[2])
    uf = UnionFind(N)
    weight = 0

    for edge in edges:
        if not uf.same(edge[0], edge[1]):
            uf.unite(edge[0], edge[1])
            weight+=edge[2]
    print(weight)

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

int1 = lambda x: int(x) - 1

N, M = map(int, input().split())
edges = [tuple(map(int1, input().split())) for _ in range(M)]
G = [set() for _ in range(N)]
for s, t in edges:
    G[s].add(t)


def E(dp, i):
    return sum(dp[x] for x in G[i]) / len(G[i]) + 1


dp0 = [0] * N
for i in range(N - 2, -1, -1):
    dp0[i] = E(dp0, i)

ans = dp0[0]
for s, t in edges:
    if len(G[s]) == 1:
        continue

    G[s].remove(t)
    dp = dp0.copy()
    for i in range(s, -1, -1):
        dp[i] = E(dp, i)
    ans = min(ans, dp[0])
    G[s].add(t)
print(ans)

### FIXED CODE ###

int1 = lambda x: int(x) - 1

N, M = map(int, input().split())
edges = [tuple(map(int1, input().split())) for _ in range(M)]
G = [set() for _ in range(N)]
for s, t in edges:
    G[s].add(t)


def E(dp, i):
    return sum(dp[x] for x in G[i]) / len(G[i]) + 1


dp0 = [0] * N
for i in range(N - 2, -1, -1):
    dp0[i] = E(dp0, i)

ans = dp0[0]
for i in range(N - 1):
    if len(G[i]) == 1:
        continue

    maxE = 0
    maxE_ind = None
    for x in G[i]:
        if dp0[x] > maxE:
            maxE_ind = x
            maxE = dp0[x]

    dp = dp0.copy()
    G[i].remove(maxE_ind)
    for j in range(i, -1, -1):
        dp[j] = E(dp, j)
    ans = min(ans, dp[0])
    G[i].add(maxE_ind)

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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

def main():
  N = int(input())
  XY = [tuple(map(int,input().split())) for _ in range(N-1)]
  MOD =10**9+7
  
  E = [[] for _ in range(N)]
  for x,y in XY:
    x -= 1
    y -= 1
    E[x].append(y)
    E[y].append(x)
  
  def dfs(v,s):
    b = 1
    w = 1
    for u in E[v]:
      if u != s:
        b0,w0 = dfs(u,v)
        b *= w0
        w *= (b0+w0)
    #b %= MOD
    #w %= MOD
    return b,w

  b,w = dfs(0,-1)
  print((b+w) % MOD)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

def main():
  N = int(input())
  XY = [tuple(map(int,input().split())) for _ in range(N-1)]
  MOD =10**9+7
  
  E = [[] for _ in range(N)]
  for x,y in XY:
    x -= 1
    y -= 1
    E[x].append(y)
    E[y].append(x)
  
  def dfs(v,s):
    b = 1
    w = 1
    for u in E[v]:
      if u != s:
        b0,w0 = dfs(u,v)
        b *= w0
        w *= (b0+w0)
    #b %= MOD
    #w %= MOD
    return b,w

  b,w = dfs(0,-1)
  print((b+w) % MOD)

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

import heapq
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
c = [[] for _ in range(h)]
dp = [[-1]*w for _ in range(h)]
que = []
for i in range(h):
  c[i] = input()

dp[x1][y1] = 0
heapq.heappush(que, (dp[x1][y1], [x1,y1]))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
while que:
  p= heapq.heappop(que)
  p = p[1]
  if (p[0] == x2) & (p[1] == y2):exit(print(dp[x2][y2]))
  for i in range(4):
    for j in range(1,k+1):
      nx = p[0] + dx[i]*j
      ny = p[1] + dy[i]*j
      if not ((0 <= nx < h) & (0 <= ny < w)):break
      if c[nx][ny] == '@':break
      if 0 <= dp[nx][ny] <= dp[p[0]][p[1]]:break
      dp[nx][ny] = dp[p[0]][p[1]] + 1
      heapq.heappush(que, (dp[nx][ny], [nx,ny]))

if dp[x2][y2] != 0:
  print(dp[x2][y2])
else:
  print(-1)


### FIXED CODE ###

#import heapq
from collections import deque
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
dp = [[-1]*w for _ in range(h)]
#que = []
que = deque()
c = [input() for _ in range(h)]

dp[x1][y1] = 0
#heapq.heappush(que, (dp[x1][y1], [x1,y1]))
que.append((x1,y1))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
while que:
  x,y=que.popleft()
  if x==x2 and y==y2:
    exit(print(dp[x][y]))
  for dx,dy in [[1,0],[-1,0],[0,-1],[0,1]]:
    for i in range(1,k+1):
      xx=x+dx*i
      yy=y+dy*i
      if not(0<=xx<h and 0<=yy<w) or c[xx][yy]=="@":break
      if 0<=dp[xx][yy]<=dp[x][y]:break
      if dp[xx][yy]==-1:que.append((xx,yy))
      dp[xx][yy]=dp[x][y]+1
print(-1)
### BUGGY CODE ###




from scipy.sparse.csgraph import floyd_warshall as fw

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

S = [[float("inf") for i in range(N)] for i in range(N)]

for i in range(M):
    a, b, c = map(int, input().split())
    S[a-1][b-1] = c
    S[b-1][a-1] = c

Sdist = fw(S)

for i in range(N):
    for j in range(N):
        if Sdist[i][j]>L:
            Sdist[i][j] = float("inf")
        else:
            Sdist[i][j] = 1

Ssup = fw(Sdist)

Q = int(input())

for i in range(Q):
    s, t = map(int, input().split())
    if Ssup[s-1][t-1]==float("inf"):
        print(-1)
    else:
        print(int(Ssup[s-1][t-1]-1))

### FIXED CODE ###


from scipy.sparse.csgraph import floyd_warshall as fw
N, M, L = map(int, input().split())

# 町間の道の長さのマトリックスを初期値無限で作成
S = [[float("INF") for i in range(N)] for i in range(N)]

# 町間の道の長さ情報をマトリックスに入力
for i in range(M):
    a, b, c = map(int,input().split())
    S[a-1][b-1] = c
    S[b-1][a-1] = c


# ワーシャルフロイド法で最短距離のマップを生成
Sf = fw(S)

T = [[float("INF")for i in range(N)] for i in range(N)]

# 町間を補給なしで通行可能な場合は1、不可能な場合はINFとしてマトリックスを作成
# （町間距離がタンク容量より大きい場合は通行不可）
for i in range(N):
    for j in range(N):
        if Sf[i][j] <= L:
            T[i][j] = 1

# ワーシャルフロイド法で町間移動可否のマップを生成
# すぐ上のfor文で、補給なしで移動できない町間の移動コストはINFにしたが、
# この処理で複数回の補給を行えば移動できる距離を
Tf = fw(T)

for i in range(int(input())):
    a, b = map(int, input().split())
    if Tf[a-1][b-1] != float("INF"):
        print(int(Tf[a-1][b-1])-1)
    else:
        print(-1)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
from functools import lru_cache
import sys
sys.setrecursionlimit(10**5+10) 

@lru_cache(None)
def up(i,pre):
    if i == len(A) - 1:
        return abs(A[pre] - A[i])
    res1 = res2 = float("inf")
    res1 = up(i + 1,i)
    if i + 2 <=len(A) -1: 
        res2 = up(i + 2,i)
    return min(abs(A[pre] - A[i]) + res1,abs(A[pre] - A[i]) + res2)

if N > 2:
    print(min(up(1,0),up(2,0)))
else:
    print(up(1,0))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
dp = [0 for _ in range(len(A))]
dp[0] = 0 
for i in range(1,N):
    if i - 2>=0:
        dp[i] = min(dp[i-1] + abs(A[i] - A[i-1]),dp[i-2] + abs(A[i] - A[i-2]))
    else:
        dp[i] =dp[i-1] + abs(A[i] - A[i-1])

print(dp[len(A)-1])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
minus=[]
res=0
for i in range(0,n):
  minus.append(i-a[i])
for i in range(0,n):
  res+=minus.count(i+a[i])
print(res)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
minus={}
plus={}
res=0
for i in range(0,n):
  pp=a[i]
  if i-pp in minus:
    minus[i-pp]+=1
  else:
    minus[i-pp]=1
  if i+pp in plus:
    plus[i+pp]+=1
  else:
    plus[i+pp]=1
for j in range(len(minus)):
  t=minus.popitem()
  try:
    res+=t[1]*plus[t[0]]
  except KeyError:
    pass
print(res)
### BUGGY CODE ###

from collections import deque
N,Q = map(int,input().split())
ab = [[] for i in range(N)]
for i in range(N-1):
    a,b = list(map(int,input().split()))
    a -= 1
    b -= 1
    ab[a].append(b)
    ab[b].append(a)
px = [0 for i in range(N)]
for i in range(Q):
    p,x = list(map(int,input().split()))
    px[p-1] += x
que = deque()
alr = set()
alr.add(0)
que.append(0)
while que:
    q = que.popleft()
    sumq = px[q]
    for i in ab[q]:
        if i not in alr:
            que.append(i)
            alr.add(i)
            px[i] += sumq
print(*px)

### FIXED CODE ###

from collections import deque
N,Q = map(int,input().split())
ab = [[] for i in range(N)]
for i in range(N-1):
    a,b = list(map(int,input().split()))
    a -= 1
    b -= 1
    ab[a].append(b)
    ab[b].append(a)
px = [0 for i in range(N)]
for i in range(Q):
    p,x = list(map(int,input().split()))
    px[p-1] += x
que = deque()
alr = set()
alr.add(0)
que.append(0)
while que:
    q = que.popleft()
    sumq = px[q]
    for i in ab[q]:
        if i in alr:
            continue
        else:
            que.append(i)
            alr.add(i)
            px[i] += sumq
print(*px)
### BUGGY CODE ###

#!/usr/bin/env python3
# Generated by https://github.com/kyuridenamida/atcoder-tools
import sys
import itertools
import collections

INF = 1145141919


def solve(S: int):
    l = list(reversed(str(S)))
    a = [int(l[c]) * 10**c for c in range(len(l))]

    def list_cumsum(l):
        return list(itertools.accumulate(l))
    s = [n % 2019 for n in list_cumsum([0]+a)]

    return sum([int(v * (v-1) / 2) for v in collections.Counter(s).values()])


def main():

    sys.setrecursionlimit(10 ** 6)

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = int(next(tokens))  # type: int
    print(solve(S))


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
# Generated by https://github.com/kyuridenamida/atcoder-tools
import sys
import itertools
import collections

INF = 1145141919


def solve(S: int):
    l = list(reversed(str(S)))
    a = [int(l[c]) * pow(10, c, 2019) for c in range(len(l))]

    def list_cumsum(l):
        return list(itertools.accumulate(l))
    s = [n % 2019 for n in list_cumsum([0]+a)]

    return sum([int(v * (v-1) / 2) for v in collections.Counter(s).values()])


def main():

    sys.setrecursionlimit(10 ** 6)

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = int(next(tokens))  # type: int
    print(solve(S))


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

import sys
N = int(input())
for h in range(1, 3501):
    for n in range(1, 3501):
        numer = N * h * n
        denom = 4 * h * n - N * n - N * h
        if denom > 0 and numer % denom == 0:
            print(h, n, numer // denom)
            sys.exit()


### FIXED CODE ###

import sys
N = int(input())
for h in range(1, 3501):
    for n in range(1, 3501):
        numer = N * h * n
        denom = 4 * h * n - N * n - N * h
        if denom > 0 and numer % denom == 0:
            print(h, n, numer // denom)
            sys.exit()
### BUGGY CODE ###

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

min = 20000000
hantei1 = 0

for i in range(L,R):
    for j in range(i+1,R+1):
        tmp = (i * j) % 2019
        if min > tmp :
            min = tmp
        if tmp == 0:
            min = 0
            hantei = 1
            break
    if hantei1 == 1:
        break

print(min)

### FIXED CODE ###

L,R = list(map(int,input().split()))
 
min = 20000000
 
#探索範囲決め
for i in range(L,R+1):
    tmp = i
    if tmp % 2019 == 0:
        break

for i in range(L,tmp+2):
    for j in range(i + 1,tmp+2):
        if min > (i * j) % 2019 and i <= R and j <= R and L <= i:
            min = (i * j) % 2019
            if min == 0:
                break
    if min == 0:
        break
 
print(min)
### BUGGY CODE ###

h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
u=[[0]*w for i in range(h)]
d=[[0]*w for i in range(h)]
l=[[0]*w for i in range(h)]
r=[[0]*w for i in range(h)]
for i in range(w):
  if s[0][i]=='.':
    u[0][i]=1
  for j in range(1,h):
    if s[j][i]=='.':
      u[j][i]+=u[j-1][i]+1
for i in range(w):
  if s[h-1][i]=='.':
    d[h-1][i]=1
  for j in range(h-2,-1,-1):
    if s[j][i]=='.':
      d[j][i]+=d[j+1][i]+1
for i in range(h):
  if s[i][0]=='.':
    l[i][0]=1
  for j in range(1,w):
    if s[i][j]=='.':
      l[i][j]+=l[i][j-1]+1
for i in range(h):
  if s[i][w-1]=='.':
    r[i][w-1]=1
  for j in range(w-2,-1,-1):
    if s[i][j]=='.':
      r[i][j]+=r[i][j+1]+1
ans=0
for i in range(h):
  for j in range(w):
    if s[i][j]=='.':
      ans=max(ans,u[i][j]+d[i][j]+l[i][j]+r[i][j]-3)
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
u=[[0]*w for i in range(h)]
d=[[0]*w for i in range(h)]
l=[[0]*w for i in range(h)]
r=[[0]*w for i in range(h)]
for i in range(h):
  for j in range(w):
    if s[i][j]=='#':
      d[i][j]=0
      l[i][j]=0
    else:
      if i!=0:
        d[i][j]+=d[i-1][j]+1
      else:
        d[i][j]=1
      if j!=0:
        l[i][j]+=l[i][j-1]+1
      else:
        l[i][j]=1
for i in range(h)[::-1]:
  for j in range(w)[::-1]:
    if s[i][j]=='#':
      r[i][j]=0
      u[i][j]=0
    else:
      if i!=h-1:
        u[i][j]+=u[i+1][j]+1
      else:
        u[i][j]=1
      if j!=w-1:
        r[i][j]+=r[i][j+1]+1
      else:
        r[i][j]=1
ans=0
for i in range(h):
  for j in range(w):
    if s[i][j]=='.':
      ans=max(ans,u[i][j]+d[i][j]+l[i][j]+r[i][j]-3)
print(ans)