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

H,W = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
B = [list(map(int,input().split())) for _ in range(H)]
dp = [[[False]*((H+W)*80) for _ in range(W)] for _ in range(H)]

dp[0][0][abs(A[0][0]-B[0][0])] = True
for h in range(H-1):
    for w in range(W-1):
        for v in range((H+W)*80):
            v1 = abs(A[h+1][w]-B[h+1][w])
            v2 = abs(A[h][w+1]-B[h][w+1])
            if dp[h][w][v]:
                dp[h+1][w][v1+v] = True
                dp[h+1][w][abs(v1-v)] = True
                dp[h][w+1][v2+v] = True
                dp[h][w+1][abs(v2-v)] = True

v0 = abs(A[H-1][W-1]-B[H-1][W-1])
for v in range((H+W)*80):
    if dp[H-1][W-2][v]:
        dp[H-1][W-1][v0+v] = True
        dp[H-1][W-1][abs(v0-v)] = True
    if dp[H-2][W-1][v]:
        dp[H-1][W-1][v0+v] = True
        dp[H-1][W-1][abs(v0-v)] = True

for v in range((H+W)*80):
    if dp[H-1][W-1][v]:
        ans = v
        break

print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
B = [list(map(int,input().split())) for _ in range(H)]
D = [[abs(A[h][w]-B[h][w]) for w in range(W)] for h in range(H)]
def cal():
    dp1 = [set() for _ in range(W)]
    dp2 = [set() for _ in range(W)]
    for h in range(H):
        for w in range(W):
            d = D[h][w]
            if h==0 and w==0:
                dp2[0].add(d)
            for v in dp1[w]:
                v1 = v+d
                v2 = v-d if v>=d else -v+d
                dp2[w].add(v1)
                dp2[w].add(v2)
            if 0 < w:
                for v in dp2[w-1]:
                    v1 = v+d
                    v2 = v-d if v>=d else -v+d
                    dp2[w].add(v1)
                    dp2[w].add(v2)
        dp1 = dp2
        dp2 = [set() for _ in range(W)]
    return min(dp1[W-1])
ans = cal()
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
for _ in range(M):
    b,c = list(map(int,input().split()))
    tmp = [c]*b
    A = sorted(A + tmp,reverse=1)[:N]
print(sum(A))

### FIXED CODE ###

import sys
input = sys.stdin.readline

def sol():
    N,M = list(map(int,input().split()))
    A = list(map(int,input().split()))
    tmp = sorted([list(map(int,input().split())) for _ in range(M)],key = lambda x:-x[1])

    t = []
    for a,b in tmp:
        t+=[b]*a
        
        if len(t) >=N:
            break

    A += t
    A.sort(reverse = 1)
    print(sum(A[:N]))

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

N = int(input())
S = input()

# 集合を使う
shugo = set()
for i in range(N - 2):
    for j in range(i+1, N -1):
        for k in range(j + 1, N):
            shugo.add(S[i] + S[j] + S[k])
print(len(shugo))

### FIXED CODE ###

N = int(input())
S = input()
flag = False
ans = 0
for i in range(1000):
    p = str(i).zfill(3)
    a = [-1, -1, -1]
    for j in range(len(S)):
        if p[0] == S[j]:
            a[0] = j
            break
    if a[0] != -1:
        for k in range(a[0] + 1, len(S)):
            if p[1] == S[k]:
                a[1] = k
                break
    else:
        continue
    if a[1] != -1:
        for l in range(a[1] + 1, len(S)):
            if p[2] == S[l]:
                a[2] = l
                break
    else:
        continue
    if a[2] != -1:
        ans += 1

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

from sys import stdin
N,Q=[int(x) for x in stdin.readline().rstrip().split()]
S=(stdin.readline().rstrip())
for i in range(Q):
    n1,n2=[int(x) for x in stdin.readline().rstrip().split()]
    print(S[n1-1:n2].count("AC"))

### FIXED CODE ###

from sys import stdin
N,Q=[int(x) for x in stdin.readline().rstrip().split()]
S=(stdin.readline().rstrip())
acc=[0]*N
cnt=0
flag=0
for index,i in enumerate(list(S)):
    if i == "C" and flag == 1:
        cnt+=1
        flag=0
    if i != "C":
        flag=0
    if i == "A":
        flag=1
    acc[index]=cnt
for j in range(Q):
    n1,n2=[int(x) for x in stdin.readline().rstrip().split()]
    print(acc[n2-1]-acc[n1-1])
### BUGGY CODE ###

from collections import deque
H,W,K = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())

maze = []
maze.append(["@"]*(W+2))
for _ in range(H):
  row = list(input())
  maze.append(["@"]+row+["@"])
maze.append(["@"]*(W+2))

q = deque([(x1,y1)])
depth = 0
while q:
  for i,j in q:
    maze[i][j] = "@"

  new_q = deque([])
  l = len(q)
  for _ in range(l):
    x,y = q.pop()
    if (x,y) == (x2,y2):
      print(depth)
      exit()

    # Up
    for i in range(1, K+1):
      if maze[x-i][y] == "@": break
      new_q.append((x-i, y))

    # Down
    for i in range(1, K+1):
      if maze[x+i][y] == "@": break
      new_q.append((x+i, y))

    # Left
    for i in range(1, K+1):
      if maze[x][y-i] == "@": break
      new_q.append((x, y-i))

    # Right
    for i in range(1, K+1):
      if maze[x][y+i] == "@": break
      new_q.append((x, y+i))

  q = new_q
  depth += 1

print(-1)

### FIXED CODE ###

from collections import deque
H,W,K = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())

maze = []
maze.append(["@"]*(W+2))
for _ in range(H):
  row = list(input())
  maze.append(["@"]+row+["@"])
maze.append(["@"]*(W+2))

q = deque([(x1,y1)])
depth = 0
while q:
  for i,j in q:
    maze[i][j] = "@"

  new_q = set()
  l = len(q)
  for _ in range(l):
    x,y = q.pop()
    if (x,y) == (x2,y2):
      print(depth)
      exit()

    # Up
    for i in range(1, K+1):
      if maze[x-i][y] == "@": break
      new_q.add((x-i, y))

    # Down
    for i in range(1, K+1):
      if maze[x+i][y] == "@": break
      new_q.add((x+i, y))

    # Left
    for i in range(1, K+1):
      if maze[x][y-i] == "@": break
      new_q.add((x, y-i))

    # Right
    for i in range(1, K+1):
      if maze[x][y+i] == "@": break
      new_q.add((x, y+i))

  q = deque(list(new_q))
  depth += 1

print(-1)
### BUGGY CODE ###

N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
dp=[[0 for j in range(W+1)] for i in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if j<w[i]:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i])
print(dp[N][W])


### FIXED CODE ###

import numpy as np
N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
dp=[0 for i in range(W+1)]
dp=np.array(dp)
for i in range(N):
    dp[w[i]:]=np.maximum(dp[w[i]:],dp[:W-w[i]+1]+v[i])
print(dp.max())
### BUGGY CODE ###

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

A.sort()
F.sort(reverse = True)

def solve(n):
    cnt = 0
    for i in range(N):
        cnt += max(0, A[i] - n // F[i])
    return cnt <= K

left = -1
right = 10 ** 12 + 1

while left + 1 < right:
    mid = (left + right) // 2
    if solve(mid):
        right = mid
    else:
        left = mid

print(right)

### FIXED CODE ###

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

A.sort()
F.sort(reverse = True)

def solve(n):
    cnt = 0
    for i in range(N):
        cnt += max(0, A[i] - n // F[i])
    return cnt <= K

left = -1
right = 10 ** 12 + 1

while left + 1 < right:
    mid = (left + right) // 2
    if solve(mid):
        right = mid
    else:
        left = mid

print(right)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
S = list(map(int, input().split()))
S.sort(reverse=True)
Closed = [False] * (1<<N)
Closed[0] = True
for _ in range(N):
    cnt = 0
    cnt_ = 0
    s_old = -1
    for i, s in enumerate(S):
        if s_old!=s:
            cnt += cnt_
            cnt_ = 0
        c = Closed[i]
        if c:
            cnt_ += 1
        elif cnt > 0:
            Closed[i] = True
            cnt -= 1
        s_old = s
if False in Closed:
    print("No")
else:
    print("Yes")


### FIXED CODE ###

N = int(input())
S = list(map(int, input().split()))
S.sort(reverse=True)
Closed = [False] * (1<<N)
Closed[0] = True
for _ in range(N):
    cnt = 0
    cnt_ = 0
    s_old = -1
    for i, s in enumerate(S):
        if s_old!=s:
            cnt += cnt_
            cnt_ = 0
        c = Closed[i]
        if c:
            cnt_ += 1
        elif cnt > 0:
            Closed[i] = True
            cnt -= 1
        s_old = s
if False in Closed:
    print("No")
else:
    print("Yes")
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
n = 1
for i in a:
    n *= i
if n > 10**18:
    n = -1
print(n)


### FIXED CODE ###

def main():

    N = int(input())
    A = list(map(int, input().split()))
    if 0 in A:
        print(0)
        return
    ans = 1
    for i in A:
        ans *= i
        if(ans > 1000000000000000000):
            print(-1)
            return
    print(ans)


main()
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
l=[0 for i in range(10**6+1)]
for i in range(n):
  l[a[i]]+=1
d={}
ans=0
for i in range(n):
  x=a[i]
  if x not in d:
    if l[a[i]]==1:
      flag=1
      for j in range(1,int(x**0.5)+2):
        if x%j==0:
          if x!=j and l[j]>0:
            flag=0
            break
          if x!=x//j and x%(x//j)==0 and l[x//j]>0:
            flag=0
            break
      if flag==1:
        ans+=1
        d[x]=1
      else:
        d[x]=0
  else:
    ans+=d[x]
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
if n!=1 and len(set(a))==1:
  print(0)
  exit()
l=[0 for i in range(10**6+1)]
for i in range(n):
  l[a[i]]+=1
if n!=1 and min(a)>max(a)/2:
  ct=0
  for i in range(len(l)):
    if l[i]==1:
      ct+=1
  print(ct)
  exit()
d={}
ans=0
for i in range(n):
  x=a[i]
  if x not in d:
    if l[a[i]]==1:
      flag=1
      for j in range(1,int(x**0.5)+2):
        if x%j==0:
          if x!=j and l[j]>0:
            flag=0
            break
          if x!=x//j and x%(x//j)==0 and l[x//j]>0:
            flag=0
            break
      if flag==1:
        ans+=1
        d[x]=1
      else:
        d[x]=0
  else:
    ans+=d[x]
print(ans)
### BUGGY CODE ###

def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    sump = 0
    ind = 0
    for i in range(n-k+1):
        for j in range(i, i+k):
            if sump < sum(p[i:i+k]):
                sump = sum(p[i:i+k])
                ind = i
    e = 0
    for i in range(ind, ind+k):
       e += (p[i]+1) / 2 
    print(e)
    
main()

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    ex = [0 for _ in range(n)]
    for i in range(n):
        ex[i] = (p[i]+1)/2
    
    sumex = sum(ex[:k])
    tmp = sum(ex[:k])
    for i in range(n-k):
        tmp = tmp + (ex[i+k] - ex[i])
        sumex = max(sumex, tmp)
    print(sumex)
    
main()
### BUGGY CODE ###

def resolve():
    '''
    code here
    '''
    N = int(input())
    A_list = [int(input()) for _ in range(N)]
 
    num_list = []
 
    for i in A_list:
        if i in num_list:
            num_list.remove(i)
        else:
            num_list.append(i)
 
    print(len(num_list))

if __name__ == "__main__":
    resolve()


### FIXED CODE ###


def resolve():
    '''
    code here
    '''
    import collections

    N = int(input())
    A_list = [int(input()) for _ in range(N)]
    cnt_dic = collections.Counter(A_list)

    cnt = 0
    for v in cnt_dic.values():
        if v % 2 == 1:
            cnt += 1

    print(cnt)

if __name__ == "__main__":
    resolve()
### BUGGY CODE ###

from collections import deque, defaultdict
import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        p, q, c = map(int, input().split())
        adj[p].append((q, c))
        adj[q].append((p, c))
    
    deq = deque()
    cost = [10 ** 7] * (N+1)
    seen = [defaultdict(int) for _ in range(N+1)]
    prev = defaultdict(list)
    deq.append(1)
    cost[1] = 0
    while deq:
        v = deq.pop()
        for uc in adj[v]:
            u, c = uc
            # print(v, u, c)
            # print(deq, prev, cost)
            # print(seen[4])
            if c in prev[v] and seen[u][c] == 0:
                if cost[u] == cost[v]:
                    prev[u].append(c)
                    deq.append(u)
                elif cost[u] > cost[v]:
                    cost[u] = cost[v]
                    deq.append(u)
                    prev[u] = [c]
                seen[v][c] = 1
            else:
                if cost[u] > cost[v] + 1:
                    cost[u] = cost[v] + 1
                    deq.appendleft(u)
                    prev[u] = [c]
                elif cost[u] == cost[v] + 1:
                    prev[u].append(c)
    
    print(cost[N]) if cost[N] < 10 ** 7 else print(-1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    N, M = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    c2v = {}
    v = N+1
    for _ in range(M):
        p, q, c = map(int, input().split())
        P = p*(10**7) + c
        Q = q*(10**7) + c
        if P not in c2v:
            c2v[P] = v
            adj[p].append((v, 1))
            adj.append([(p, 1)])
            v += 1
        if Q not in c2v:
            c2v[Q] = v
            adj[q].append((v, 1))
            adj.append([(q, 1)])
            v += 1
        adj[c2v[P]].append((c2v[Q], 0))
        adj[c2v[Q]].append((c2v[P], 0))

    que = deque()
    que.append(1)
    seen = [-1] * len(adj)
    seen[1] = 0
    while que:
        v = que.popleft()
        for u, cost in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + cost
                if cost:
                    que.append(u)
                else:
                    que.appendleft(u)
    print(seen[N] // 2)


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

import sys

A = list(map(int, sys.stdin.read().rstrip().split("\n")))
n = A[0]
del A[0]

#shellSort
cnt = 0

G = []
tg = 1
while tg <= n:
    G.append(tg)
    tg = 3 * tg + 1
G.reverse()

m = len(G)

for i in range(m):
    g = G[i]
    # insertionSort
    for j in range(g, n):
        k = j - g
        while (k >= 0) and (A[k] > A[k + g]):
            A[k + g], A[k] = A[k], A[k + g]
            k -= g
            cnt += 1

print(m)
print(*G)
print(cnt)
for i in A:
    print(i)

### FIXED CODE ###

import sys

def insertionSort(A, n, g):
    global cnt
    for i in range(g, n):
        v = A[i]
        j = i - g
        while (j >= 0) and (A[j] > v):
            A[j + g] = A[j]
            j = j - g
            cnt += 1
        A[j + g] = v

def shellSort(A, n):
    G = [i for i in [262913, 65921, 16577, 4193, 1073, 281, 77, 23, 8, 1] if i <= n]
    m = len(G)
    for k in range(m):
        insertionSort(A, n, G[k])
    return m, G

A = list(map(int, sys.stdin))
n = A[0]
del A[0]

cnt = 0

m, G = shellSort(A, n)

print(m)
print(*G)
print(cnt)
print("\n".join(map(str, A)))
### BUGGY CODE ###

import sys,heapq
input = sys.stdin.readline

N,M = list(map(int,input().split()))
A = sorted(list(map(int,input().split())),reverse = 1)
rep = []
for _ in range(M):
    b,c = list(map(int,input().split()))
    tmp = [-c]*b
    rep = rep+tmp
heapq.heapify(rep)

for i in range(N):
    A[i] = -1 * heapq.heappushpop(rep,-1*A[i])
print(sum(A))


### FIXED CODE ###

import sys
input = sys.stdin.readline

def sol():
    N,M = list(map(int,input().split()))
    A = list(map(int,input().split()))
    tmp = sorted([list(map(int,input().split())) for _ in range(M)],key = lambda x:-x[1])

    t = []
    for a,b in tmp:
        t+=[b]*a
        
        if len(t) >=N:
            break

    A += t
    A.sort(reverse = 1)
    print(sum(A[:N]))

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


import numpy as np

H,N=map(int,input().split())
weights=[list(map(int,input().split())) for _ in range(N)]
INF=100100101
#print(weight)
#print(value)

#print(weights)
dp=[INF for i in range(H+1)]
for i in range(H+1):
    if i==0:
        dp[i]=0
    else:
        for j in range(len(weights)):
            a=weights[j][0]
            b=weights[j][1]
            piv=max(0,i-a)  #use i-a's dp[] value as a pivot (if not exits(i-a<0), return dp[0])
            dp[i]=min(dp[i],dp[piv]+b) #the part which forcely treated as piv=0, returns min([weights]), other is treated as normal dp
    #print(dp)

print(dp[H])


### FIXED CODE ###


#import numpy as np

H,N=map(int,input().split())
weights=[list(map(int,input().split())) for _ in range(N)]
INF=100100101
#print(weight)
#print(value)

#print(weights)
dp=[INF]*(H+1)
for i in range(H+1):
    if i==0:
        dp[i]=0
    else:
        for j in weights:
            a=j[0]
            b=j[1]
            piv=max(0,i-a)  #use i-a's dp[] value as a pivot (if not exits(i-a<0), return dp[0])
            dp[i]=min(dp[i],dp[piv]+b) #the part which forcely treated as piv=0, returns min([weights]), other is treated as normal dp
    #print(dp)

print(dp[H])
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = sum(a)
#print(ans)
q = int(input())
b = []
c = []
from itertools import groupby
d = [[key,len(list(group))] for key,group in groupby(sorted(a))]

for j in range(q):
    b,c = map(int,input().split())
    
    for i in range(len(d)):
        if b==d[i][0]:
            d[i][0] = c
            ans = ans + ((c-b)*d[i][1])
    print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
s = sum(a)
#print(ans)
q = int(input())
import collections
cc = collections.Counter(a)
#print(cc)
for i in range(q):
    b,c = map(int,input().split())
    tmp = cc[b]
    cc[b] = 0
    s=s-b*tmp+c*tmp
    cc[c]+=tmp
    print(s)
### BUGGY CODE ###

import sys

N, M = map(int, sys.stdin.readline().split())
P = [None]*M
S = [None]*M
for i in range(M):
    string = sys.stdin.readline().split()
    P[i] = int(string[0])
    S[i] = string[1]


ac = [0]*N
AC = 0
WA = 0
for i in range(M):
    if S[i] == "AC":
        if ac[P[i]-1] == 0:
            ac[P[i]-1] += 1
            for j in range(i):
                if P[j] == P[i] and S[j] == "WA":
                    WA += 1

AC = sum(i > 0 for i in ac)
print(AC, WA)

### FIXED CODE ###

N, M = map(int, input().split())
P = [None]*M
S = [None]*M
for i in range(M):
    P[i], S[i] = input().split()
    P[i] = int(P[i])

AC = [0]*(N+1)
wa = [0]*(N+1)
WA = 0

for i in range(M):
    if S[i] == "WA":
        if AC[P[i]] == 0:
            wa[P[i]] += 1
    else:
        AC[P[i]] = 1

for i in range(N+1):
    WA += wa[i]*AC[i] 

print(sum(AC[1:]), WA)
### BUGGY CODE ###

import numpy as np
import itertools

def pd(s):
    #print(s)
    pass


# input
H, W, M = map(int, input().split())
ms = [
    [int(i) for i in input().split()]
    for m in range(M)
]
pd(f"{H=} {W=} {M=}")
pd(f"{ms=}")

rows = [0]*(H+1)
cols = [0]*(W+1)

def get_total(row, col):
    total = 0
    for m in ms:
        if (m[0] == row) or (m[1] == col):
            total += 1
            pd(f"o:{m[0]=} {m[1]=}")
        else:
            pd(f"x:{m[0]=} {m[1]=}")
    return total

for m in ms:
    pd(f"{m=}")
    rows[m[0]] += 1
    cols[m[1]] += 1

rows = np.array(rows)
max_rows = np.where(rows == rows.max())[0].tolist()
pd(f"{max_rows=}")

cols = np.array(cols)
max_cols = np.where(cols == cols.max())[0].tolist()
pd(f"{max_cols=}")

max_total = 0
p = itertools.product(max_rows, max_cols)
for v in p:
    max_total = max(get_total(v[0],v[1]), max_total)

print(max_total)

### FIXED CODE ###

import numpy as np
import itertools


def pd(s):
    #print(s)
    pass


# input
H, W, M = map(int, input().split())
ms = [
    [int(i) for i in input().split()]
    for m in range(M)
]
pd(f"{H=} {W=} {M=}")
pd(f"{ms=}")

rows = [0]*(H+1)
cols = [0]*(W+1)
bombs = {}
for m in ms:
    h = m[0]
    w = m[1]
    rows[h] += 1
    cols[w] += 1
    bombs[f"{h},{w}"] = True

rmax = max(rows)
cmax = max(cols)
rmax_hs = [i for i, v in enumerate(rows) if v == rmax]
cmax_wh = [i for i, v in enumerate(cols) if v == cmax]

for m in itertools.product(rmax_hs, cmax_wh):
    h = m[0]
    w = m[1]
    if f"{h},{w}" not in bombs:
        print(rmax + cmax)
        exit()
print(rmax + cmax - 1)
### BUGGY CODE ###

n=int(input())
a=input().split()
a=list(map(int,a))
i=0
ans=1
for calc in a:
    if(0 in a==True):
        print(0)
        exit()
    ans=ans*a[i]
    i+=1
    if(i==n):
        break
if(ans>1000000000000000000):
    print(-1)
else:
    print(ans)


### FIXED CODE ###

n=int(input())
a=input().split()
a=list(map(int,a))
ans=1
if(0 in a):
    print(0)
    exit()

for calc in a:
    ans*=calc
    if(ans>10**18):
        print(-1)
        exit()
if(ans>10**18):
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

from collections import Counter
S = list(input())
S.reverse()
MOD = 2019

t = [0]
for i in range(len(S)):
    q = (t[-1] + int(S[i]) * ((10**i) % MOD)) % MOD
    t.append(q)

cnt = Counter(t)
cnt_mc = cnt.most_common()

ans = 0
for _, j in cnt_mc:
    if j >= 2:
        ans += j * (j - 1) // 2
        
print(ans)

### FIXED CODE ###

from collections import Counter
S = list(input())
S.reverse()
MOD = 2019

t = [0]
r = 1
for i in range(len(S)):
    q = (t[-1] + (int(S[i]) * r) % MOD) % MOD
    t.append(q)
    r *= 10
    r %= MOD

cnt = Counter(t)
cnt_mc = cnt.most_common()

ans = 0
for _, j in cnt_mc:
    if j >= 2:
        ans += j * (j - 1) // 2
        
print(ans)
### BUGGY CODE ###

import bisect

s=input()
t=input()

condition=0

index=list()
for a in range(len(t)):
 index.append([i for i, x in enumerate(s) if x == t[a]])

b=0
loop=0
condition=0

for j in range(len(t)):
  c=bisect.bisect_left(index[j],b)
  #print(j,index[j],b,c,loop)
  if len(index[j])<1:
    print(-1)
    condition=1
    break
  elif j==0:
    b=index[0][0]    
  elif c<len(index[j])  and c != index[j][len(index[j])-1]:
     b=index[j][c]
     #print(j,b,loop)
  else:
     loop=loop+len(s)
     b=index[j][0]
     if loop == len(s)*(10**100):
       print(-1)
       break

if condition==0:
 print(b+loop+1)


        



### FIXED CODE ###

import bisect

s=input()
t=input()

#index=list()
#for a in range(len(t)):
# index.append([i for i, x in enumerate(s) if x == t[a]])

char_appear = {ch: [] for ch in 'abcdefghijklmnopqrstuvwxyz'}
for i, ch in enumerate(s):
    char_appear[ch].append(i)
#print(char_appear['a'])
      
b=0
loop=0
condition=0

for j in range(len(t)):
  if len(char_appear[t[j]])<1:
    print(-1)
    condition=1
    break
  c=bisect.bisect(char_appear[t[j]],b)
 # print(j,char_appear[t[j]],b,c,loop)
  if j<1:
    b=char_appear[t[0]][0]    
  elif c == len(char_appear[t[j]]): #or c==char_appear[t[j]][len(char_appear[t[j]])-1]: 
     loop +=1
     b=char_appear[t[j]][0]
     if loop==10**100:
        print(-1)
        condition=1
        break
  else:
     b=char_appear[t[j]][c]
     #print(j,b,loop)


if condition==0:
 print(b+loop*len(s)+1)