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

h,w=map(int,input().split())
sl=[input() for i in range(h)]
ll=[[0]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if sl[i][j]=='.':
            for k in range(j,-1,-1):
                if sl[i][k]=='.':
                    ll[i][j]+=1
                else:
                    break
rl=[[0]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if sl[i][j]=='.':
            for k in range(j,w):
                if sl[i][k]=='.':
                    rl[i][j]+=1
                else:
                    break
ul=[[0]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if sl[i][j]=='.':
            for k in range(i,-1,-1):
                if sl[k][j]=='.':
                    ul[i][j]+=1
                else:
                    break
dl=[[0]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if sl[i][j]=='.':
            for k in range(i,h):
                if sl[k][j]=='.':
                    dl[i][j]+=1
                else:
                    break
ans=0
for i in range(h):
    for j in range(w):
            ans=max(ans,ll[i][j]+rl[i][j]+ul[i][j]+dl[i][j]-3)
print(ans)

### FIXED CODE ###

h,w=map(int,input().split())
sl=[input() for i in range(h)]
ll=[[0]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if sl[i][j]=='.':
            if j==0:
                ll[i][j]=1
            else:
                ll[i][j]=ll[i][j-1]+1
        else:
            ll[i][j]=0
rl=[[0]*w for i in range(h)]
for i in range(h):
    for j in range(w-1,-1,-1):
        if sl[i][j]=='.':
            if j==w-1:
                rl[i][j]=1
            else:
                rl[i][j]=rl[i][j+1]+1
        else:
            rl[i][j]=0
ul=[[0]*w for i in range(h)]
for j in range(w):
    for i in range(h):
        if sl[i][j]=='.':
            if i==0:
                ul[i][j]=1
            else:
                ul[i][j]=ul[i-1][j]+1
        else:
            ul[i][j]=0
dl=[[0]*w for i in range(h)]
for j in range(w):
    for i in range(h-1,-1,-1):
        if sl[i][j]=='.':
            if i==h-1:
                dl[i][j]=1
            else:
                dl[i][j]=dl[i+1][j]+1
        else:
            dl[i][j]=0
ans=0
for i in range(h):
    for j in range(w):
            ans=max(ans,ll[i][j]+rl[i][j]+ul[i][j]+dl[i][j]-3)
print(ans)
### BUGGY CODE ###

N=int(input())
S=input()
ans=0
for i in range(1000):
    one=str(i//100)
    two=str((i%100)//10)
    three=str(i%10)
    f1,f2,f3=False,False,False
    ptr=0
    for j in range(ptr,N-2):
        if S[j]==one:
            f1=True
            ptr=j+1
            break
    for j in range(ptr,N-1):
        if S[j]==two:
            f2=True
            ptr=j+1
            break
    for j in range(ptr,N):
        if S[j]==three:
            f3=True
            break
    if f1 and f2 and f3:
        ans+=1
print(ans)

### FIXED CODE ###

N=int(input())
S=input()
ans=0
for i in range(1000):
    one=str(i//100)
    two=str((i%100)//10)
    three=str(i%10)
    f1,f2,f3=False,False,False
    ptr=0
    for j in range(ptr,N-2):
        if S[j]==one:
            f1=True
            ptr=j+1
            break
    if f1:
        for j in range(ptr,N-1):
            if S[j]==two:
                f2=True
                ptr=j+1
                break
        if f2:
            for j in range(ptr,N):
                if S[j]==three:
                    f3=True
                    ans+=1
                    break
print(ans)
### BUGGY CODE ###

nums = list(map(int, input().split()))

ok = False
count = 1
while not ok:    
    if  (count % nums[0] == 0) and (count % nums[1] == 0):
        ok = True
        break
    count += 1
print(count)

### FIXED CODE ###

from fractions import gcd

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

print(A * B // gcd(A, B))
### BUGGY CODE ###

import copy


def main():
    n = int(input())
    s = [["" for j in range(10)] for i in range(n)]
    for i in range(n):
        s[i] = list(input())

    cnt = 0
    for i in range(n):
        cnt += count_anagram(s[i], copy.copy(s[i+1: n]))

    print(cnt)


def anagram(list1, list2):
    if not list1:
        return True

    if list1[0] in list2:
        list2.remove(list1[0])
        list1.pop(0)
        return anagram(list1, list2)
    else:
        return False


def count_anagram(s, str_list):
    cnt = 0
    for t in str_list:
        u, v = copy.copy(s), copy.copy(t)
        if anagram(u, v):
            cnt += 1
    return cnt


if __name__ == '__main__':
    main()


### FIXED CODE ###

import collections

n = int(input())
s = ["".join(sorted(input())) for i in range(n)]

counter = collections.Counter(s)

ans = 0
for i in counter.values():
   if i > 0:
        ans += i * (i - 1) // 2

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

import numpy as np
N , K ,Q = map(int, input().split())
s = sorted([int(input())-1 for _ in range(Q)])
initializer_list = np.full(N,K,dtype='int')
for i in s:
    tmp = initializer_list[i]
    initializer_list -=1
    initializer_list[i] = tmp

for i in initializer_list:
    if i > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

import numpy as np
N , K ,Q = map(int, input().split())
initializer_list = [0] * N
for _ in range(Q):
    i = int(input())-1
    initializer_list[i] += 1
    

[print('Yes') if (Q - initializer_list[i] < K) else print('No')  for i in range(N)]
### BUGGY CODE ###

import fractions
import functools
N=int(input())
A=[int(i) for i in input().split()] 
max_gcd=functools.reduce(fractions.gcd, A)
for i in range(N):
	tmp=A.copy()
	tmp.pop(i)
	gcd=functools.reduce(fractions.gcd, tmp)
	if max_gcd<gcd:
		max_gcd=gcd
print(max_gcd)


### FIXED CODE ###

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

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

N = int(input())
A = [int(a) for a in input().split()]

# GCDの結合則を利用する
# 左端、右端からの累積GCDを求めておくと、Aiを取り除いた場合のGCDがすぐに計算できる。
# つまり、
# L(i): n=0,...,iまでのGCD 
# R(i): n=i,...,N-1までのGCD
# このとき、Aiを除いた全体のGCDは、GCD(L(i-1), R(i+1))で計算できる。

L = [0] * N
R = [0] * N

L[0] = A[0]
R[-1] = A[-1]
for i in range(1, N):
    L[i] = gcd(L[i-1], A[i])
    idx = N-1-i
    R[idx] = gcd(R[idx+1], A[idx])

mx = 0
for i in range(N):
    if i == N-1:
        v = L[N-2]
    elif i == 0:
        v = R[1]
    else:
        v = gcd(R[i+1], L[i-1])
    mx = max(v, mx)
print(mx)
### BUGGY CODE ###

from heapq import *
from collections import defaultdict
INF = float('inf')
class Prim:

    def __init__(self,N):#Nはグラフのノード数
        self.N = N
        self.cost = defaultdict(list)
        self.used = [False for _ in range(N)]
    
    def setcost(self,u,v,w):
        self.cost[u].append([v,w])
    
    def prim(self):
        que = []
        heapify(que)
        used = self.used
        for e in self.cost[0]:
            heappush(que,[e[1],e[0]])
        used[0] = True
        res = 0
        while que:
            p = heappop(que)
            cos,v = p
            if used[v]:continue
            self.used[v] = True
            for e in self.cost[v]:
                if not used[e[0]]:
                    heappush(que,[e[1],e[0]])      
            res += cos
        return res

def main():
    N = int(input())
    cost = []
    for i in range(N):
        x,y = map(int,input().split())
        cost.append((x,y,i))
    prim = Prim(N)
    x = sorted(cost,key=lambda x: x[0])
    y = sorted(cost,key=lambda x: x[1])
    for i in range(N-1):
        a,b,u = x[i]
        c,d,v = x[i+1]
        prim.setcost(u,v,min(abs(a-c),abs(b-d)))
        prim.setcost(v,u,min(abs(a-c),abs(b-d)))
        e,f,s = y[i]
        g,h,t = y[i+1]
        prim.setcost(s,t,min(abs(e-g),abs(f-h)))
        prim.setcost(t,s,min(abs(e-g),abs(f-h)))
    ans = prim.prim()
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

from heapq import *
from collections import defaultdict
INF = float('inf')
class Prim:

    def __init__(self,N):#Nはグラフのノード数
        self.N = N
        self.cost = defaultdict(list)
        self.used = [False for _ in range(N)]
    
    def setcost(self,u,v,w):
        self.cost[u].append((v,w))
        self.cost[v].append((u,w))
    
    def prim(self):
        que = []
        heapify(que)
        used = self.used
        for e in self.cost[0]:
            heappush(que,[e[1],e[0]])
        used[0] = True
        res = 0
        while que:
            p = heappop(que)
            cos,v = p
            if used[v]:continue
            self.used[v] = True
            for e in self.cost[v]:
                if not used[e[0]]:
                    heappush(que,[e[1],e[0]])      
            res += cos
        return res

def main():
    N = int(input())
    cost = []
    for i in range(N):
        x,y = map(int,input().split())
        cost.append((x,y,i))
    prim = Prim(N)
    x = tuple(sorted(cost,key=lambda x: x[0]))
    y = tuple(sorted(cost,key=lambda x: x[1]))
    for i in range(N-1):
        a,b,u = x[i]
        c,d,v = x[i+1]
        w = min(abs(a-c),abs(b-d))
        prim.setcost(u,v,w)
        e,f,s = y[i]
        g,h,t = y[i+1]
        u = min(abs(e-g),abs(f-h))
        prim.setcost(s,t,u)
    ans = prim.prim()
    print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

LIMIT = 10 ** 18

res = 1

for a in A:
    res = res * a

if res > LIMIT:
    print('-1')
else:
    print(res)

### FIXED CODE ###

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

LIMIT = 10 ** 18

zeroflg = 0
for a in A:
    if a == 0:
        zeroflg = 1
        break

if zeroflg == 1:
    res = 0
else:
    res = 1
    for a in A:
        if a == 0:
            res = 0
            break
        if res > LIMIT:
            break
    
        res = res * a

# res = math.exp(sum([math.log(a) for a in A]))

# X = np.array(A)
# res = X.prod()
#
# print(X)

# for a in A:
#     math.log(a)
#
#     res = res * a

if res > LIMIT:
    print('-1')
else:
    print(res)
### BUGGY CODE ###

n=int(input().strip())
a=list(map(int, input().split()))
b=[]
for i in range(n):
    b.append(a[i])
    b=b[::-1]
print(' '.join(map(str, b)))

### FIXED CODE ###

from collections import deque
n=int(input().strip())
a=list(map(int, input().split()))
b = deque()
for i in range(n):
    if i%2==0:
        b.append(a[i])
    else:
        b.appendleft(a[i])
b=list(b)
if n%2==1:
    b=b[::-1]
print(' '.join(map(str, b)))
### BUGGY CODE ###

n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
import numpy as np
num = np.array(a, dtype=np.int64)
ans = np.array([], dtype=np.int64)
for i in range(n-1):
    ans = np.insert(ans, 0, num[i] * num[i+1:])
ans = np.sort(ans)
print(int(ans[k-1]))

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    inf = 10**20
    #mod = 10**9 + 7

    N,k = map(int, input().split())
    zero, p, n = 0, [], []
    a = list(map(int, input().split()))
    for i in a:
        if i==0:
            zero += 1
        elif i > 0:
            p.append(i)
        else:
            n.append(i)
    p.sort()
    n.sort(reverse=True)

    #決め打ち二分探索
    #rはk個以上作れる, lはk個作れない
    l, r = -inf, inf
    while r - l > 1:
        mid = (l + r) // 2
        cnt = 0
        #0以上とき0の分足す
        if mid >= 0:
            cnt += zero*(zero-1)//2 + zero*(N-zero)
        
        if mid > 0:
            #負数足す
            cnt += len(n) * len(p)
            #p, nについてそれぞれ尺取り法で調べる
            for a in (p, n):
                left, right = 0, len(a)-1
                while left < right:
                    #a[l]*a[r]は小さくなっていきmid以下になったらそこから数える
                    while left<right and a[left]*a[right]>mid:
                        right -= 1
                    cnt += right - left
                    #lは最小から始まるのでrの値をリセットする必要はない
                    left += 1
        else:
            right = len(n) - 1
            for left in range(len(p)):
                while right>=0 and p[left]*n[right]<=mid:
                    right -= 1
                cnt += len(n) - right - 1
        
        if cnt >= k:
            r = mid
        else:
            l = mid

    print(r)



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

# https://atcoder.jp/contests/abc063/submissions/5323989 参照

def func(idx, points, N, lst_s, dp):
    # base case
    if idx == N:
        if points % 10 == 0:
            return 0
        else:
            return points
    
    # check memo
    if dp.get((idx, points)):
        return dp[(idx, points)]
    
    # recursive
    f1 = func(idx + 1, points, N, lst_s, dp)
    f2 = func(idx + 1, points + lst_s[idx], N, lst_s, dp)
    ret = max(f1, f2)
    dp[(idx, points)] = ret

    return ret


N = int(input())
lst_s = [int(input()) for _ in range(N)]
dp = {}
ans = func(0, 0, N, lst_s, dp)
print(ans)

### FIXED CODE ###

N = int(input())
lst_s = [int(input()) for _ in range(N)]
lst_s.sort()
max_grade = sum(lst_s)
ans = 0


if max_grade % 10 != 0:
    ans = max_grade
else:
    for s in lst_s:
        tmp_grade = max_grade - s
        if tmp_grade % 10 != 0:
            ans = max(ans, tmp_grade)

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

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

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

board_w = [[0 for i in range(w)] for i in range(h)]
board_h = [[0 for i in range(h)] for i in range(w)]

# 横、縦の順に走査
for i in range(h):
    cnt_continue = 0
    for j, c in enumerate(s[i]):
        if c == ".":
            cnt_continue += 1
        elif cnt_continue > 0:
            for k in range(1, cnt_continue+1):
                board_w[i][j-k] = cnt_continue
            cnt_continue = 0
        if j == w - 1:
            for k in range(cnt_continue):
                board_w[i][j-k] = cnt_continue
            cnt_continue = 0

s = list(map(list, zip(*s)))

for i in range(w):
    cnt_continue = 0
    for j, c in enumerate(s[i]):
        if c == ".":
            cnt_continue += 1
        elif cnt_continue > 0:
            for k in range(1, cnt_continue+1):
                board_h[i][j-k] = cnt_continue
            cnt_continue = 0
        if j == h - 1:
            for k in range(cnt_continue):
                board_h[i][j-k] = cnt_continue
            cnt_continue = 0

board_h = list(map(list, zip(*board_h)))
ans = 0

for i in range(h):
    for j in range(w):
        v = int(board_w[i][j]) + int(board_h[i][j])
        ans = max(ans, v)

print(ans-1)

### FIXED CODE ###

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

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

board_w = [[0 for _ in range(w)] for _ in range(h)]
board_h = [[0 for _ in range(w)] for _ in range(h)]

# 右、左、上、下の順に走査
for i in range(h):
    cnt_continue = 0
    for j in range(w):
        if s[i][j] == "#":
            cnt_continue = 0
        else:
            cnt_continue += 1
            board_w[i][j] = cnt_continue

    for j in reversed(range(w-1)):
        if board_w[i][j] == 0:
            continue
        board_w[i][j] = max(board_w[i][j], board_w[i][j+1])

for i in range(w):
    cnt_continue = 0
    for j in range(h):
        if s[j][i] == "#":
            cnt_continue = 0
        else:
            cnt_continue += 1
            board_h[j][i] = cnt_continue

    for j in reversed(range(h-1)):
        if board_h[j][i] == 0:
            continue
        board_h[j][i] = max(board_h[j][i], board_h[j+1][i])


ans = 0

for i in range(h):
    for j in range(w):
        v = board_w[i][j] + board_h[i][j] - 1
        ans = max(ans, v)

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

from collections import Counter

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

s = input()

if 10 % p == 0:
    ans = sum(i + 1 for i, x in enumerate(s) if int(x) % p == 0)
    print(ans)
else:
    li = [0] * (n + 1)
    for i, x in enumerate(s[::-1]):
        li[i+1] = (li[i] + (int(x) * (10**(i+1)) % p)) % p

    ans = 0
    c = Counter(li[1:])
    ans = sum(v * (v - 1) for v in c.values()) // 2
    ans += c[0]
    print(ans)


### FIXED CODE ###

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

s = input()

if 10 % p == 0:
    ans = sum(i + 1 for i, x in enumerate(s) if int(x) % p == 0)
    print(ans)
else:
    counter = [0] * p
    counter[0] = 1
    cur = 0
    p10 = 1
    ans = 0
    for x in s[::-1]:
        cur = (cur + int(x) * p10) % p
        ans += counter[cur]
        counter[cur] += 1
        p10 *= 10
        p10 %= p
    print(ans)
### BUGGY CODE ###

mod=10**9+7
def gcd(x,y):
    if x<y:
        x,y=y,x
    #x>y
    if x%y==0:
        return y
    else:
        return gcd(y,x%y)
def egcd(a, b):
    (x,lastx)=(0,1)
    (y,lasty)=(1,0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
def inv(x):
    return egcd(x,mod)[0]%mod
N=2*10**5+10
B,W=map(int,input().split())
Blist=[0 for i in range(N+1)]
Wlist=[0 for i in range(N+1)]
Fact=[0 for i in range(N+1)]
Finv=[0 for i in range(N+1)]
Exp2=[0 for i in range(N+1)]
Fact[0]=1;Finv[0]=1
Exp2[0]=1
for i in range(N):
    Exp2[i+1]=(Exp2[i]*2)%mod
for i in range(N):
    Fact[i+1]=(Fact[i]*(i+1))%mod
    Finv[i+1]=inv(Fact[i+1])
def C(n,k):
    if k<0 or n<k:
        return 0
    else:
        return (Finv[k]*(Fact[n]*Finv[n-k])%mod)%mod
Blist[0]=1;Wlist[0]=1
for i in range(N):
    Blist[i+1]=(2*Blist[i]-C(i,B-1))%mod
    Wlist[i+1]=(2*Wlist[i]-C(i,W-1))%mod
#print(Blist[:B+W])
#print(Wlist[:B+W])
ans=[0 for i in range(B+W)]
for i in range(B+W):
    ans[i]=(Blist[i]-Wlist[i]+Exp2[i])%mod
    ans[i]=(ans[i]*inv(Exp2[i+1]))%mod
for line in ans:
    print(line)


### FIXED CODE ###

mod=10**9+7
def gcd(x,y):
    if x<y:
        x,y=y,x
    #x>y
    if x%y==0:
        return y
    else:
        return gcd(y,x%y)
def egcd(a, b):
    (x,lastx)=(0,1)
    (y,lasty)=(1,0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
def inv(x):
    return egcd(x,mod)[0]%mod
N=2*10**5+10
B,W=map(int,input().split())
Blist=[0 for i in range(N+1)]
Wlist=[0 for i in range(N+1)]
Fact=[0 for i in range(N+1)]
Finv=[0 for i in range(N+1)]
Exp2=[0 for i in range(N+1)]
Fact[0]=1;Finv[0]=1
Exp2[0]=1
for i in range(N):
    Exp2[i+1]=(Exp2[i]*2)%mod
for i in range(N):
    Fact[i+1]=(Fact[i]*(i+1))%mod
    Finv[i+1]=inv(Fact[i+1])
def C(n,k):
    if k<0 or n<k:
        return 0
    else:
        return (Finv[k]*(Fact[n]*Finv[n-k])%mod)%mod
Blist[0]=1;Wlist[0]=1
for i in range(N):
    Blist[i+1]=(2*Blist[i]-C(i,B-1))%mod
    Wlist[i+1]=(2*Wlist[i]-C(i,W-1))%mod
#print(Blist[:B+W])
#print(Wlist[:B+W])
ans=[0 for i in range(B+W)]
for i in range(B+W):
    ans[i]=(Blist[i]-Wlist[i]+Exp2[i])%mod
    ans[i]=(ans[i]*inv(Exp2[i+1]))%mod
for line in ans:
    print(line)
### BUGGY CODE ###

s=input()
k=int(input())
st=""
sum=0
for i in range(k):
    st=st+s
for x in range(len(st)-1):
    if(st[x]==st[x+1]):
        st=st[:x+1]+"#"+st[x+2:]
        sum+=1
print(sum)


### FIXED CODE ###

def solve(t):
    same=0
    count=0
    for i in range(len(t)):
        same+=1
        if i==len(t)-1 or t[i]!=t[i+1]:
            count+=same//2
            same=0
    return count

s=input()
k=int(input())
f=True
for i in range(len(s)-1):
    if s[i]!=s[i+1]:
        f=False
if f==True:
    print(len(s)*k//2)
else:
    st=s+s;
    scount=solve(s)
    stcount=solve(st)
    print(scount+(stcount-scount)*(k-1))
### BUGGY CODE ###

for _ in range(int(input())):
    X = input()
    Y = input()
    dp = [[0] * (len(Y)+1) for x in range(len(X)+1)]
    for x in range(1, len(X) + 1):
        for y in range(1, len(Y) + 1):
            if X[x-1] == Y[y-1]:
                dp[x][y] = dp[x-1][y-1] + 1
            elif dp[x-1][y] > dp[x][y-1]:
                dp[x][y] = dp[x-1][y]
            else:
                dp[x][y] = dp[x][y-1]
    print(dp[-1][-1])


### FIXED CODE ###

def ser(X, Y):
    dp = [[0] * (len(Y)+1) for x in range(len(X)+1)]
    for i, x in enumerate(X, 1):
        tmp = dp[i]
        pre = dp[i-1]
        for j, y in enumerate(Y, 1):
            if x == y:
                tmp[j] = pre[j-1] + 1
            elif pre[j] < tmp[j-1]:
                tmp[j] = tmp[j-1]
            else:
                tmp[j] = pre[j]
    return(dp[-1][-1])

for _ in range(int(input())):
    X, Y = input(), input()
    print(ser(X, Y))
### BUGGY CODE ###

from itertools import combinations
from collections import deque


def find_index_by_value(a, val):
    for i, items in enumerate(a):
        if val in items:
            return i
    return -1


def count_reachale(a):
    reachable = 0
    for s in a:
        if len(s) > 1:
            reachable += len(s) * (len(s) - 1) // 2
    return reachable


n, m = map(int, input().split())
edges = []
node_group = [{n} for n in range(1, n + 1)]

for _ in range(m):
    a, b = map(int, input().split())
    edges.append((a, b))

ans = deque()
not_reachable = n * (n - 1) // 2
ans.append(n * (n - 1) // 2)

for _ in range(m - 1):
    a, b = edges.pop()
    ia = find_index_by_value(node_group, a)
    ib = find_index_by_value(node_group, b)
    if ia != ib:
        node_group[ia] |= node_group[ib]
        node_group.pop(ib)
    count = not_reachable - count_reachale(node_group)
    ans.appendleft(count)

for _ in range(len(ans)):
    print(ans.popleft())




### FIXED CODE ###

def find_index_by_value(a, val):
    for i, items in enumerate(a):
        if val in items:
            return i
    return -1


def num_reachable(n):
    return n * (n - 1) // 2


n, m = map(int, input().split())
edges = []

for _ in range(m):
    a, b = map(int, input().split())
    edges.append((a, b))

size = [1 for _ in range(n + 1)]
group = [i for i in range(n + 1)]


def find_group(x):
    c = []
    p = x
    while True:
        pp = group[p]
        if pp == p:
            break
        else:
            c.append(p)
            p = pp
    for i in c:
        group[i] = pp
    return pp

# find_group = lambda x: x if x == group[x] else find_group(group[x])

ans = []
not_reachable = n * (n - 1) // 2
reachable_node = []
ans.append(not_reachable)

count = not_reachable
reachable = 0
for _ in range(m - 1):
    a, b = edges.pop()
    if count > 0:
        ra = find_group(a)
        rb = find_group(b)
        if rb != ra:
            s_ra = size[ra]
            s_rb = size[rb]
            new_size = s_ra + s_rb
            reachable += num_reachable(new_size) - num_reachable(s_ra) - num_reachable(s_rb)
            size[ra] = new_size
            group[rb] = ra
        count = not_reachable - reachable
    ans.append(count)

for _ in range(len(ans)):
    print(ans.pop())
### BUGGY CODE ###

# coding: utf-8

# 17:36-18:18 give up => kaisetu
# -18:46


def main():
    S = input() + "0"
    N = len(S)

    q = 2019

    res = [0] * N
    num = 0
    p = 0
    for i in range(N-1, -1, -1):
        num += int(S[i]) * 10**p
        res[i] = num % q
        p += 1

    cnt = [0] * q
    for r in res:
        cnt[r] += 1

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

    return ans


print(main())


### FIXED CODE ###

# coding: utf-8

# 17:36-18:18 give up => kaisetu
# -18:46 - 18:52 chudan
# -20:21


def main():
    S = input() + "0"
    # S = "1" * 10**5 + "0"
    N = len(S)
    S = list(map(int, S))

    q = 2019

    res = [0] * N
    num = 0
    p = 1
    pow_memo = {0: (10**0) % q}
    for i in range(N-2, -1, -1):
        pow_memo[p] = (pow_memo[p-1] * 10) % q
        num = (num + (S[i] % q) * pow_memo[p]) % q
        res[i] = num
        p += 1

    cnt = [0] * q
    for r in res:
        cnt[r] += 1

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

    return ans


print(main())