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

class Puzzle():
  def __init__(self, mat, h,w,k):
    self.mat = mat
    self.h = h
    self.w = w
    # self.k = k
    self.k = min(k, 3)
    self.score = 0

  def calc(self, t):
    tmp_score = 0

    for i in range(self.h):
      for j in range(self.w):
        if self.mat[i][j] > 0:
          for k in range(self.w, -1, -1):
            if k-j >= self.k:
              s = set(self.mat[i][j:k])
              if len(s) == 1 and -1 not in s:
                tmp_score += list(s)[0] * (k-j)
                for l in range(j, k):
                  self.mat[i][l] = -1
            else:
              break

    if tmp_score == 0:
      return False
    else:
      self.score += pow(2, t) * tmp_score
      if self.score == 642: import pdb; pdb.set_trace()
      return True

  def flatten(self):
    pivot_mat = []
    for i in range(self.w):
      row = []
      for j in range(self.h):
        if self.mat[j][i] != -1:
          row.append(self.mat[j][i])

      short = self.h - len(row)
      if short > 0:
        row.reverse()
        for k in range(short):
          row.append(-1)
        row.reverse()
      
      pivot_mat.append(row)

    mat = [ [-1]*self.w for i in range(self.h) ]
    for i in range(self.h):
      for j in range(self.w):
        mat[i][j] = pivot_mat[j][i]

    self.mat = mat

h,w,k = map(int,input().split())
mat = []
for _ in range(h):
  mat.append([int(e) for e in list(input())])

res = 0
for i in range(h):
  for j in range(w):
    old = mat[i][j]
    mat[i][j] = -1
    puzzle = Puzzle(mat,h,w,k)
    puzzle.flatten()
    time = 0
    while True:
      if puzzle.calc(time):
        puzzle.flatten()
        time += 1
      else:
        break
    res = max(res, puzzle.score)
    mat[i][j] = old

print(res)

### FIXED CODE ###

from itertools import groupby

def calc(time):
  t = 0
  for i in range(h):
    gr = groupby(g[i])
    lst = []
    p = 0
    for key,it in gr:
      j = len(list(it))
      lst.append([p,key,j])
      p += j
    for j in range(len(lst)):
      if lst[j][1] == -1:
        continue
      if lst[j][2] >= K:
        t += (2**time)*lst[j][1]*lst[j][2]
        for k in range(lst[j][0],lst[j][0]+lst[j][2]):
          g[i][k] = 0

  return t

def flatten():
  for j in range(w):
    lst = []
    for i in range(h-1, -1, -1):
      if g[i][j] > 0:
        lst.append(g[i][j])

    lst += [-1] * (h - len(lst))

    for i in range(h-1, -1, -1):
      g[i][j] = lst[h-i-1]

h,w,K = map(int,input().split())
mat = [ [int(e) for e in list(input())] for _ in range(h) ]

res = 0
for i in range(h):
  for j in range(w):
    score = 0
    g = [ [ mat[n][m] for m in range(w) ] for n in range(h) ]
    g[i][j] = -1
    time = 0
    flatten()
    while True:
      s = calc(time)
      if s==0: break
      score += s
      flatten()
      time += 1
    res = max(res, score)

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

L, R = [int(n) for n in input().split()]

#L = L % 2019
#R = R % 2019

min_mod = 2019
for a in range(L, R):
    for b in range(a+1, R+1):
        min_mod = min(min_mod, (a * b) % 2019)

print(min_mod)

### FIXED CODE ###

L, R = [int(n) for n in input().split()]

if R - L >= 2019:
    print(0)
else:
    min_mod = 2019
    for a in range(L, R):
        for b in range(a+1, R+1):
            min_mod = min(min_mod, (a * b) % 2019)

    print(min_mod)
### BUGGY CODE ###

s=input()
n=int(input())
for i in range(n):
  a=list(map(str,input().split()))
  if a[0]=="1":
    s=s[::-1]
  else:
    if a[1]=="1":
      s=a[2]+s
    else:
      s+=a[2]
print(s)

### FIXED CODE ###

s=input()
q=int(input())
que=[]
count=0
left=[]
right=[]
for i in range(q):
  qu=list(map(str,input().split()))
  if qu[0]=="1":
    count+=1
  que.append(qu)
han=0
for i in range(q):
  if que[i][0]=="1":
    han+=1
  else:
    if que[i][1]=="1":  
      if (count-han)%2==0:
        left.append(que[i][2])
      else:
        right.append(que[i][2])
    elif que[i][1]=="2":  
      if (count-han)%2==0:
        right.append(que[i][2])
      else:
        left.append(que[i][2])
ls="".join(left[::-1])
rs="".join(right)
if count%2==0:
  print(ls+s+rs)
else:
  print(ls+s[::-1]+rs)
### BUGGY CODE ###

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


floor_num=[]
for x in range(N+1):
    floor_num.append(int(A*x/B)-A*int(x/B))

print(max(floor_num))

### FIXED CODE ###

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


floor_num=[]

if N >=B:
    floor_num.append(int(A*(B-1)/B))
else:  

        floor_num.append(int(A*N/B))


print(max(floor_num))
### BUGGY CODE ###

import numpy as np

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

ni = np.array([i for i in range(n)])

ap = a + ni
an = (a - ni) * -1
an.sort()
ans = 0
for j in an[::-1]:
  if j <= 0:break
  for i in ap:
    if j == i:
      ans += 1

print(ans)

### FIXED CODE ###

import numpy as np
from collections import Counter
n = int(input())
a = np.array(list(map(int, input().split())))
ni = np.array([i for i in range(n)])

ap = a + ni
an = (a - ni) * -1

cp = Counter(ap)
cn = Counter(an)

ans = 0
for i in cp.keys():
  ans += cp[i] * cn[i] 

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

# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from heapq import heappush,heappop,heapify
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
X,Y=[0]*N,[0]*N
dx,dy=defaultdict(list),defaultdict(list)
for i in range(N):
    X[i],Y[i]=map(int,input().split())
    dx[X[i]].append(i)
    dy[Y[i]].append(i)
ux,uy=list(set(X)),list(set(Y))
ux.sort()
uy.sort()
uxi={x:i for i,x in enumerate(ux)}
uyi={y:i for i,y in enumerate(uy)}
edge=[[] for i in range(N)]
for i,(x,y) in enumerate(zip(X,Y)):
    for index in dx[x]+dy[y]:
        edge[i].append((0,index))
    if uxi[x]>=1:
        for index in dx[ux[uxi[x]-1]]:
            edge[i].append((abs(ux[uxi[x]-1]-x),index))
    if uxi[x]<len(ux)-1:
        for index in dx[ux[uxi[x]+1]]:
            edge[i].append((abs(ux[uxi[x]+1]-x),index))
    if uyi[y]>=1:
        for index in dy[uy[uyi[y]-1]]:
            edge[i].append((abs(uy[uyi[y]-1]-y),index))
    if uyi[y]<len(uy)-1:
        for index in dy[uy[uyi[y]+1]]:
            edge[i].append((abs(uy[uyi[y]+1]-y),index))

def prim(n,edges):
    used=[False]*n
    used[0]=True
    edgelist=[]
    for edge in edges[0]:
        heappush(edgelist,edge)
    cost=0
    while edgelist:
        minedge=heappop(edgelist)
        if used[minedge[1]]:
            continue
        v=minedge[1]
        used[v]=True
        for edge in edges[v]:
            if not used[edge[1]]:
                heappush(edgelist,edge)
        cost+=minedge[0]
    return cost

print(prim(N,edge))

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from heapq import heappush,heappop,heapify
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
X,Y=[],[]
for i in range(N):
    x,y=map(int,input().split())
    X.append((y,i))
    Y.append((x,i))
X.sort(key=lambda t:t[0])
Y.sort(key=lambda t:t[0])
edge=[[] for i in range(N)]
for i in range(N-1):
    edge[X[i][1]].append((abs(X[i][0]-X[i+1][0]),X[i+1][1]))
    edge[X[i+1][1]].append((abs(X[i][0]-X[i+1][0]),X[i][1]))
    edge[Y[i][1]].append((abs(Y[i][0]-Y[i+1][0]),Y[i+1][1]))
    edge[Y[i+1][1]].append((abs(Y[i][0]-Y[i+1][0]),Y[i][1]))

def prim(n,edges):
    used=[False]*n
    used[0]=True
    edgelist=[]
    for edge in edges[0]:
        heappush(edgelist,edge)
    cost=0
    while edgelist:
        minedge=heappop(edgelist)
        if used[minedge[1]]:
            continue
        v=minedge[1]
        used[v]=True
        for edge in edges[v]:
            if not used[edge[1]]:
                heappush(edgelist,edge)
        cost+=minedge[0]
    return cost

print(prim(N,edge))
### BUGGY CODE ###

import math
n = int(input())
rootn = int(math.sqrt(n))
ct = 0
for i in range(rootn,n+1):
  if n%i == 0:
    tmp = i
    while tmp//10 != 0:
     ct += 1  
     tmp = tmp//10   
    break
print(ct+1)

### FIXED CODE ###

import math
n = int(input())
rootn = int(math.sqrt(n))
ct = 0
for i in reversed(range(1,rootn+1)):
  if n%i == 0:
    tmp = n//i
    while tmp//10 != 0:
     ct += 1  
     tmp = tmp//10   
    break
print(ct+1)
### BUGGY CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
s = [" "] + lc()
q = ni()
k = list(li())

d__ = [0]*(n+1)
dm_ = [0]*(n+1)
dmc = [0]*(n+1)
_m_ = [0]*(n+1)

def find_ans(k:int):
    ans = 0
    
    for i in range(1, n+1):
        d__[i] = d__[i-1]
        dm_[i] = dm_[i-1]
        dmc[i] = dmc[i-1]
        _m_[i] = _m_[i-1]
        
    
            
        if i-k+1 > 0:
            if s[i-k+1] == 'D':
                d__[i] -= 1
                dm_[i] -= _m_[i]
                
            elif s[i-k+1] == 'M':
                _m_[i] -= 1
                
        if s[i] == 'D':
            d__[i] += 1    
        
        elif s[i] == 'M':
            dm_[i] += d__[i]
            _m_[i] += 1
            
        elif s[i] == 'C':
            ans += dm_[i-1]
            
    return ans
        
for ki in k:
    print(find_ans(ki))

### FIXED CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
s = " " + ns()
q = ni()
k = list(li())

def find_ans(k:int):
    cnt = [0,0,0]
    ans = 0
    
    for i in range(1, n+1):
        
        if s[i] == 'C':
            ans += cnt[2]

        if i-k+1 > 0:
            if s[i-k+1] == 'D':
                cnt[0] -= 1
                cnt[2] -= cnt[1]
                
            elif s[i-k+1] == 'M':
                cnt[1] -= 1
                
        if s[i] == 'D':
            cnt[0] += 1    
        
        elif s[i] == 'M':
            cnt[2] += cnt[0]
            cnt[1] += 1

            
    return ans
        
for ki in k:
    print(find_ans(ki))
### BUGGY CODE ###


def main():
    n,m = map(int,input().split())
    ab = [[0] * n for i in range(n)]
    for _ in range(m):
        a,b = map(int,input().split())
        ab[a-1][b-1] = 1

    for mid in range(1,n):
        if ab[0][mid] == 1 and ab[mid][n-1]:
            print('POSSIBLE')
            return
    print('IMPOSSIBLE')

if __name__ == '__main__':
    main()


### FIXED CODE ###

n,m = map(int,input().split())
ab = [[-1] for i in range(n)]
for i in range(m):
    a, b = map(int,input().split())
    if ab[a-1][-1] == -1:
        ab[a-1][-1] = b-1
    else:
        ab[a-1].append(b-1)
flg = False
for i, mid in enumerate(ab[0]):
    if n-1 in ab[mid]:
        flg = True
        break

if flg :print('POSSIBLE')
else:print('IMPOSSIBLE')
### BUGGY CODE ###

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

L.sort()
L2 = [(l, 1) for l in L]
LR = []
#print(L)

from bisect import bisect_left

ans = 0
for i, a in enumerate(L):
    for j, b in enumerate(L[i+1:]):
        j=i+1+j
        L2.append((abs(a-b), 0))
        L2.append((a+b, 0))
        LR.append((abs(a-b), a+b, i, j))

L2.sort()
L_dict = {}

cnt = 0
for v, f in L2:
    if f == 0:
        L_dict[v] = cnt
    else:
        cnt += 1
        
ans = 0
for l, r, i, j in LR:
    x = max(L_dict[l], j+1)
    y = max(L_dict[r], j+1)
    ans += y-x
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
L = list(map(int, input().split()))

L.sort()
#print(L)

from bisect import bisect_right,bisect_left

ans = 0
for i, a in enumerate(L[:-2]):
    for j, b in enumerate(L[i+1:-1]):
        j=i+1+j
        #print(a+b, abs(a-b), i, j)
        #for k, c in enumerate(L[j+1:]):
        #    if abs(a-b) < c and c < a+b:
        #        ans += 1
        #    if c >= a+b:
        #        break
        l = bisect_left(L, abs(a-b),j+1)
        r = bisect_left(L, a+b,j+1)
        #print(r-l)
        ans += r-l
print(ans)
### BUGGY CODE ###

n = int(input())
h = str(input())
h = list(h)
h2 = list(h)
def mojiretu(n, h):
    for i in range(0, len(h) - 1):
            if h[i] == h[i + 1]:
                h2.remove(h[i])
    return len(h2)
print(mojiretu(n,h))

### FIXED CODE ###

n = int(input())
h = str(input())
h = list(h)
h2 = []
def mojiretu(n, h):
    h2.append(h[0])
    for i in range(1, len(h)):
            if h[i] != h[i - 1]:
                h2.append(h[i])
    return len(h2)
print(mojiretu(n,h))
### BUGGY CODE ###

N = int(input())
def prime_dict(n):
    a = {}
    if n%2 == 0:
        a[2] = 1
        n//=2
    while n%2 == 0:
        a[2] += 1
        n //= 2
    f = 3
    while f*f <= n:
        if n%f == 0:
            if f not in a:
                a[f] = 1
            else:
                a[f] += 1
        else:
            f += 2
    if n!= 1:
        a[n] = 1
    return a
primes = prime_dict(N)
ans = 0
for k,v in primes.items():
    now = 1
    while now*(now+1)//2 <= v:
        now += 1
    ans += now-1
print(ans)



### FIXED CODE ###

from collections import Counter
N = int(input())
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
ans = 0
primes = prime_factorize(N)
pc = Counter(primes)
for v in pc.values():
    now = 1
    while now*(now+1)//2 <= v:
        now += 1
    ans += now-1
print(ans)
### BUGGY CODE ###

n = int(input())
count = 0
for l in range(1, n+1):
  for i in range(1, l):
    for j in range(1, l):
      for k in range(1, l):
        if (i+j+k)**2-(i*j+j*k+i*k) == l:
          count +=1
  print(count)
  count = 0    

### FIXED CODE ###

n = int(input())
count = 0
a = [0]*(10**5)
for i in range(1, 100):
  for j in range(1, 100):
    for k in range(1, 100):
      a[(i+j+k)**2-(i*j+j*k+i*k)] += 1


for i in range(n):
  print(a[i+1])
### BUGGY CODE ###

N = int(input())
S = list(map(str, input()))

opposite = [0 for _ in range(N)]

for i in range(N):
	if S[i] == "E":
		for j in range(0, i):
			opposite[j] += 1
	else:
		for j in range(i + 1, N):
			opposite[j] += 1
print(min(opposite))

### FIXED CODE ###

N = int(input())
S = list(map(str, input()))
ret = float("inf")
west = [0 for _ in range(N + 2)]
east = [0 for _ in range(N + 2)]

for i in range(1, N + 1):
	if S[i - 1] == "W":
		west[i] = west[i - 1] + 1
	else:
		west[i] = west[i - 1]
for i in range(N, 0, -1):
	if S[i - 1] == "E":
		east[i] = east[i + 1] + 1
	else:
		east[i] = east[i + 1]
	ret = min(east[i] + west[i] - 1, ret)

print(ret)
### BUGGY CODE ###

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

### FIXED CODE ###

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

if any(a[j] == 0 for j in range(n)):
    ans = 0
else:
    for i in range(n):
        ans *= a[i]
        if ans > 10 ** 18:
            ans = -1
            break
print(ans)
### BUGGY CODE ###

import collections
import math

n = int(input())

f_list = [[]]*(10**7+1) # すべて素数扱い

def get_ans(t):
    c = collections.Counter(t)
    v_list = c.values()
    ans = 1
    for v in v_list:
        ans *= v+1
    return ans

ans = 0
for i in range(2, n+1):
    tmp = [i] # 約数のリスト
    if i % 2 == 0:
        tmp = f_list[i//2]+[2]
    else:
        f = 3
        while f*f <= i:
            if i % f == 0:
                tmp = f_list[i//f]+[f]
                break
            else:
                f += 2
    f_list[i] = tmp
    ans += i*get_ans(tmp)
print(ans+1)

### FIXED CODE ###

import collections
import math

n = int(input())
ans = 0

for i in range(1,n+1):
    tail = (n // i)
    ans += (tail)*(tail+1)//2*i
print(ans)
### BUGGY CODE ###

max_d = 15001

# Acceptance of input
import sys

file_input = sys.stdin

V, E = map(int, file_input.readline().split())

D = [[max_d] * V for i in range(V)]

for line in file_input:
    s, t, d = map(int, line.split())
    D[s][t] = d

# Full search with bit mask
def tsp(v, b):
    if b == (1 << V) - 1:
        return D[v][0]
    
    res = max_d
    for t, d in enumerate(D[v]):
        if b & (1 << t) or d == max_d:
            continue
        res = min(res, d + tsp(t, b | (1 << t)))
        
    return res

# Output
ans = tsp(0, 1)

if ans == max_d:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import sys

file_input = sys.stdin

V, E = map(int, file_input.readline().split())

no_route = 15001

# (v-1) th vertex is excluded
dp = [[no_route] * (V - 1) for i in range(1 << (V - 1))]

adj = [[] for i in range(V)]

for line in file_input:
    s, t, d = map(int, line.split())
    if s == V - 1:
        # Record the distance from the (v-1) th vertex to the adjacent vertex
        dp[1 << t][t] = d
    else: 
        # Store distance from source, not target
        adj[t].append((s, d))

# DP
for b in range(1, 1 << (V - 1)):
    for i in range(V - 1):
        b_i = 1 << i
        if b & b_i:
            pre_bit = b ^ b_i
            dp_pre = dp[pre_bit]
            for s, d in adj[i]:
                pre_rec = dp_pre[s]
                if pre_rec != no_route:
                    dp[b][i] = min(dp[b][i], pre_rec + d)

ans = no_route

# A state where all vertices other than (v-1) have been visited.
dp_comp = dp[(1 << (V - 1)) - 1]

for s, d in adj[V - 1]:
    comp_rec = dp_comp[s]
    if comp_rec != no_route:
        ans = min(ans, comp_rec + d)

if ans == no_route:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

N, M = map(int, input().split(" "))
stores = dict()

for i in range(N):
    Ai, Bi = map(int, input().split(" "))
    if Ai in stores:
        stores[Ai] += Bi
    else:
        stores[Ai] = Bi

price = 0
for i in range(1, 10000000000):
    if i in stores:
        if M <= stores[i]:
            price += i * M
            break
        else:
            price += i * stores[i]
            M -= stores[i]
print(price)

### FIXED CODE ###

N, M = map(int, input().split(" "))
stores = []

for i in range(N):
    Ai, Bi = map(int, input().split(" "))
    stores.append((Ai, Bi))    

price = 0
for a, b in sorted(stores, key=lambda x: x[0]):
    if M <= b:
        price += a * M
        break
    else:
        price += a * b
        M -= b
print(price)
### BUGGY CODE ###

nkq = list(map(int, input().split()))
n = nkq[0]
k = nkq[1]
q = nkq[2]
aes = []
for _ in range(q):
    aes.append(int(input()))

points = [k] * n
for a in aes:
    for i in range(n):
        if (a-1) == i:
            points[i] = points[i]
        else:
            points[i] = points[i] -1
for i in range(n):
    if points[i] > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

import numpy as np
nkq = list(map(int, input().split()))


n = nkq[0]
k = nkq[1]
q = nkq[2]
aes = []
for _ in range(q):
    aes.append(int(input()))
    


points = np.zeros(n)  + (k - q)
for a in aes:
    points[a-1] = points[a-1] + 1

for p in points:
    if p > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

H,W,D = map(int,input().split())
A = [[] for _ in range(H)]
posi = [[]] * (H * W)

for _ in range(H):
  a = list(map(int,input().split()))
  A[_] = a
  for i,j in enumerate(a):
    k = i + 1
    t = _ + 1
    posi[j - 1] = [t,k]

Q = int(input())

dist = [0] * (H * W)
acdist = [0] * (H * W)

for _ in range(0,H * W - D):
  dist[_] = abs(posi[_ + D][0] - posi[_][0]) + abs(posi[_ + D][1] - posi[_][1])

for d in range(0,H * W - D):
   acdist[d] = sum([dist[i] for i in range(d,H * W,D)])

for i in range(Q):
  l,r = map(int,input().split())
  print(acdist[l - 1] - acdist[r - 1])

### FIXED CODE ###

H,W,D = map(int,input().split())
posi = [[]] * (H * W)

for _ in range(H):
  a = list(map(int,input().split()))
  for i,j in enumerate(a):
    posi[j - 1] = [_ + 1,i + 1]

Q = int(input())

acdist = [0] * (H * W)

for _ in range(0,H * W - D):
  acdist[_ + D] += acdist[_] + abs(posi[_ + D][0] - posi[_][0]) + abs(posi[_ + D][1] - posi[_][1])

for i in range(Q):
  l,r = map(int,input().split())
  print(acdist[r - 1] - acdist[l - 1])
### BUGGY CODE ###

from collections import deque
S = (input())
cnt = deque([0]*2019)
cnt.appendleft(1)
n = 0
t = 1
for i in reversed(S):
    x = int(i)
    n += x*t
    cnt[n%2019] += 1
    t *= 10
cnt2 = [i*(i-1)//2 for i in cnt]
print(sum(cnt2))

### FIXED CODE ###

S = input()
cnt = [0]*2019
cnt[0] = 1
n = 0
t = 1
for i in reversed(S):
    n += int(i)*t
    n %= 2019
    cnt[n] += 1
    t *= 10
    t %= 2019
print(sum(i*(i-1)//2 for i in cnt))
### BUGGY CODE ###

r1,c1,r2,c2=map(int,input().split())

mod=10**9+7
f=[1]
for i in range(2*10**6+7):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod

def F(r,c):
  ans=0
  for i in range(r+c+1):
    ans+=2**i
    ans%=mod
  d=0
  s=0
  for i in range(r-1,-1,-1):
    s+=comb((r-i-1)+c,c)
    d+=2**i*s
    s%=mod
    d%=mod
  ans=(ans+(mod-d))%mod
  d=0
  s=0
  for i in range(c-1,-1,-1):
    s+=comb((c-i-1)+r,r)
    d+=2**i*s
    s%=mod
    d%=mod
  ans=(ans+(mod-d))%mod
  return ans

ans=F(r2,c2)
ans=(ans+(mod-F(r2,c1-1)))%mod
ans=(ans+(mod-F(r1-1,c2)))%mod
ans+=F(r1-1,c1-1)
print(ans%mod)

### FIXED CODE ###

r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
f=[1]
for i in range(2*10**6+7):f+=[f[-1]*(i+1)%mod]
ans=0
for i in range(c1,c2+1):
  d=((r2+1)*f[i+r2+1]%mod)*f[r1]
  d%=mod
  d=(d+(mod-((r1*f[r2+1]%mod)*f[i+r1])%mod))%mod
  d*=pow((((i+1)*f[i]%mod)*f[r1]%mod)*f[r2+1]%mod,mod-2,mod)
  d%=mod
  ans+=d
  ans%=mod
print(ans)
### BUGGY CODE ###

from itertools import combinations

N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))

V_C = []
diff = 0

for i in range(N):
    V_C.append([V[i], C[i]])

for i in range(1, N+1):
    combs = list(combinations(V_C, i))
    for comb in combs:
        price = 0
        cost = 0
        for c in comb:
            price += c[0]
            cost += c[1]
            p_c = price - cost
            if p_c > diff:
                diff = p_c

print(diff)


### FIXED CODE ###

N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))

V_C = zip(V, C)
ans = 0

for x in V_C:
    diff = x[0] - x[1]
    ans += diff if diff >= 0 else 0

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

S = input()
Q = int(input())
flag = 0
for _ in range(Q):
    q = list(input().split())
    if q[0] == "1":
        flag += 1
    else:
        if flag%2 == 0:
            if q[1] == "1":
                S = q[2]+S
            else:
                S = S+q[2]
        else:
            if q[1] == "1":
                S = S+q[2]
            else:
                S = q[2]+S
if flag%2 == 0:
    print(S)
else:
    S = S[::-1]
    print(S)

### FIXED CODE ###

S = input()
Q = int(input())
flag = 0
H = ""
for _ in range(Q):
    q = list(input().split())
    if q[0] == "1":
        flag += 1
    else:
        if flag%2 == 0:
            if q[1] == "1":
                H = H+q[2]
            else:
                S = S+q[2]
        else:
            if q[1] == "1":
                S = S+q[2]
            else:
                H = H+q[2]
H = H[::-1]
H = H+S
if flag%2 == 0:
    print(H)
else:
    H = H[::-1]
    print(H)