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

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

max_num = 0
j = 0
j_max = M
# A_sums=[0]
# B_sums=[0]
# for i in range(N):
#     A_sums.append(A_sums[i]+A[i])
# for i in range(M):
#     B_sums.append(B_sums[i]+B[i])


for i in range(N + 1):
    j = 0
    if sum(A[:i])>K:
        break
    while sum(A[:i]) + sum(B[:j_max]) > K:
        j_max -=1

    max_num = max(max_num, i + j_max)
print(max_num)


### FIXED CODE ###

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

max_num = 0
j = 0
j_max = M
A_sums=[0]
B_sums=[0]
for i in range(N):
    A_sums.append(A_sums[i]+A[i])
for i in range(M):
    B_sums.append(B_sums[i]+B[i])


for i in range(N + 1):
    j = 0
    if A_sums[i]>K:
        break
    while A_sums[i]+B_sums[j_max] > K:
        j_max -=1

    max_num = max(max_num, i + j_max)
print(max_num)
### BUGGY CODE ###

n=int(input())
s=input()
t=[-1]*n
for i in range(n):
  if s[i]=="D":t[i]=0
  elif s[i]=="M":t[i]=1
  elif s[i]=="C":t[i]=2

def solve(k):
  d_p=[0]*2*n
  d_m=[0]*2*n
  m_p=[0]*2*n
  m_m=[0]*2*n
  for i in range(n):
    if t[i]==0:
      d_p[i]+=1
      d_m[i+k]-=1
    if t[i]==1:
      m_p[i]+=1
      m_m[i+k]-=1
  dd=mm=dm=dmc=0
  for i in range(n):
    if d_p[i]:dd+=1
    if d_m[i]:dm-=mm;dd-=1
    if m_p[i]:dm+=dd;mm+=1
    if m_m[i]:mm-=1
    if t[i]==2:dmc+=dm
  return dmc

q=int(input())
k=list(map(int,input().split()))
for i in k:print(solve(i))

### FIXED CODE ###

import sys
input=sys.stdin.readline

n=int(input())
s=[ord(i)for i in input()]
t=[-1]*n
for i in range(n):
  if s[i]==68:
    t[i]=0
  elif s[i]==77:t[i]=1
  elif s[i]==67:t[i]=2

def solve(k):
  dd=mm=dm=dmc=0
  for i in range(n):
    if t[i]==0:dd+=1
    if i>=k and t[i-k]==0:dm-=mm;dd-=1
    if t[i]==1:dm+=dd;mm+=1
    if i>=k and t[i-k]==1:mm-=1
    if t[i]==2:dmc+=dm
  return dmc

q=int(input())
k=list(map(int,input().split()))
for i in k:print(solve(i))
### BUGGY CODE ###

Big=10**9+7
_=list(map(int,input().split(" ")))
N=_[0]
K=_[1]
gcd_list=[0 for _ in range(K)]
for i in range(K):
  s=K-i-1
  gcd_list[s]=(((K//(K-i))**N)%Big-(sum(gcd_list[2*s+1::s+1]))%Big)%Big
answer=[(x+1)*gcd_list[x]%Big for x in range(K)]
print(sum(answer)%Big)

### FIXED CODE ###

Big=10**9+7
_=list(map(int,input().split(" ")))
N=_[0]
K=_[1]
gcd_list=[0 for _ in range(K)]
for i in range(K):
  s=K-i-1
  gcd_list[s]=(pow(K//(K-i), N, Big)-(sum(gcd_list[2*s+1::s+1]))%Big)%Big
answer=[(x+1)*gcd_list[x]%Big for x in range(K)]
print(sum(answer)%Big)
### BUGGY CODE ###

S = list(input())

cnt = 0
for i in range(len(S)):
    if S[i] == "W":
        cnt += S[:i].count("B")
        
print(cnt)

### FIXED CODE ###

S = list(input())

cnt = 0
b = 0
for s in S:
    if s == "B":
        b += 1
    else:
        cnt += b
        
print(cnt)
### BUGGY CODE ###

# coding: utf-8

# 標準入力 <int>
N = int(input())

# 標準入力 <int> list[]
P = list(map(int, input().split()))

count = 0

for i in range(N):
    if min(P[0:i + 1]) == P[i]:
        count += 1

print(count)


### FIXED CODE ###

# coding: utf-8

# 標準入力 <int>
N = int(input())

# 標準入力 <int> list[]
P = list(map(int, input().split()))

count = 0
comp = 2 * (10**5)

for i in range(N):
    if comp >= P[i]:
        count += 1
        comp = P[i]

print(count)
### BUGGY CODE ###

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

dp = [-1]*((n+1)*(n+1)*(n+1))
dp[0] = 0

def dfs(i, j, k, n):
    tmp = k*(n+1)**2  + j*(n+1)**1 + i*(n+1)**0
    if dp[tmp] != -1:
        return dp[tmp]
    res = 1
    if k > 0:
        res += (k/n) * dfs(i, j, k-1, n)
    if j > 0:
        res += (j/n) * dfs(i, j-1, k+1, n)
    if i > 0:
        res += (i/n) * dfs(i-1, j+1, k, n)
    dp[tmp] = (n/(i+k+j)) * res
    return dp[tmp]

cnt1 = a.count(1)
cnt2 = a.count(2)
cnt3 = a.count(3)

dfs(cnt3, cnt2, cnt1, n)
print(dp[cnt1*(n+1)**2  + cnt2*(n+1)**1 + cnt3*(n+1)**0])

### FIXED CODE ###

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

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

cnt1 = a.count(1)
cnt2 = a.count(2)
cnt3 = a.count(3)

for i in range(cnt3 + 1):
    for j in range(cnt3 + cnt2 + 1 - i):
        for k in range(cnt3 + cnt2 + cnt1 + 1 - i - j):
            if i + j + k == 0:
                continue
            res = 1
            if k > 0:
                res += (k/n) * dp[i][j][k-1]
            if j > 0:
                res += (j/n) * dp[i][j-1][k+1]
            if i > 0:
                res += (i/n) * dp[i-1][j+1][k]
            dp[i][j][k] = (n/(i+k+j)) * res

print(dp[cnt3][cnt2][cnt1])
### BUGGY CODE ###

# E - Sum of gcd of Tuples (Hard)
# https://atcoder.jp/contests/abc162/tasks/abc162_e

MOD = 10 ** 9 + 7

n, k = map(int, input().split())
dic = {}

ans = 0
for i in range(k, 0, -1):
  num = pow(k // i, n, MOD)
  for key, val in dic.items():
    if key % i == 0:
      num -= val
  dic[i] = num
  ans += num * i
  ans %= MOD

print(ans)



### FIXED CODE ###

# E - Sum of gcd of Tuples (Hard)
# https://atcoder.jp/contests/abc162/tasks/abc162_e

MOD = 10 ** 9 + 7

n, k = map(int, input().split())
dic = [0] * (k + 1)

ans = 0
for i in range(k, 0, -1):
  dic[i] = pow(k // i, n, MOD)

for i in range(k, 0, -1):
  for j in range(i * 2, k + 1, i):
    dic[i] -= dic[j]
    dic[i] %= MOD

ans = 0
for i in range(1, k + 1):
  ans += dic[i] * i
  ans %= MOD

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

a=int(input())
C=list()
last=[[]for i in range(2*100002)]
for i in range(a):
    C.append(int(input()))

ans=[1]*a
last[C[0]].append(0)
#print(last,ans)
for i in range(1,a):
    ans[i]=ans[i-1]
    if C[i]==C[i-1]:
        continue
    for j in last[C[i]]:
        if j==0:
            ans[i]+=1
        else:
            ans[i]+=ans[j-1]
    last[C[i]].append(i)

print(ans[a-1] % 1000000007)


### FIXED CODE ###

a = int(input())
C = list()
last = [-1] * 2 * 100002
for i in range(a):
    C.append(int(input()))

ans = [1] * a
last[C[0]] = 0
# print(last,ans)
for i in range(1, a):
    ans[i] = ans[i - 1]
    if C[i] == C[i - 1]:
        continue
    if last[C[i]] != -1:
        ans[i] += ans[last[C[i]]]
    last[C[i]] = i

print(ans[a - 1] % 1000000007)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

# きれいさ、おいしさ、人気度、でそれぞれ正負のどちらを目指すかを決める
# たとえば、人気度だけ負を目指す場合
# i個目のケーキを食べることで「きれいさの正の値 + おいしさの正の値 + 人気度 * -1」が
# 大きくなるときだけ更新するDPを考える
# dp[i] = [値, (きれいさ,おいしさ,人気度)]

N,M = map(int,readline().split())
cakes = [None] * N
for i in range(N):
  cakes[i] = list(map(int,readline().split()))

INF = -(10 ** 15)
ans = INF
for i in range(2 ** 3):
  base = [-1,-1,-1]
  for j in range(3):
    if (i >> j) & 1:
      base[j] = 1
  dp = [None] * (M + 1)
  for j in range(M + 1):
    dp[j] = [INF,[INF,INF,INF]]
  dp[0] = [0,[0,0,0]]
  for j in range(N):
    x,y,z = cakes[j]
    for k in range(M-1,-1,-1):
      if dp[k][0] == INF:
        continue
      newx = dp[k][1][0] + x * base[0]
      newy = dp[k][1][1] + y * base[1]
      newz = dp[k][1][2] + z * base[2]
      if dp[k + 1][0] < newx + newy + newz:
        dp[k + 1][0] = newx + newy + newz
        dp[k + 1][1][0] = newx
        dp[k + 1][1][1] = newy
        dp[k + 1][1][2] = newz
  if ans < dp[M][0]:
    ans = dp[M][0]
    
print(ans)  


### FIXED CODE ###

N,M=map(int,input().split())
cakes=[None]*N
for i in range(N):
  x,y,z=map(int,input().split())
  cakes[i]=[x,y,z]
  
# x,y,zをそれぞれマイナスに伸ばすかプラスに伸ばすか、2*3通りをすべて試す。
ans=0
for i in range(2**3):
  plus_or_minus=[1]*3
  for j in range(3):
    if (i>>j)&1:
      plus_or_minus[j]=1
    else:
      plus_or_minus[j]=-1
  # 買った個数に対して、プラスマイナスへの伸びが最も大きい買い方を保持
  dp=[None for j in range(M+1)]
  dp[0]=[0,0,0]
  
  for c in range(len(cakes)):
    for j in range(c+1,-1,-1):
      if j<len(dp)-1 and dp[j]!=None:
        if dp[j+1]==None:
          dp[j+1]=[None]*3
          dp[j+1][0]=dp[j][0]+cakes[c][0]
          dp[j+1][1]=dp[j][1]+cakes[c][1]
          dp[j+1][2]=dp[j][2]+cakes[c][2]
        else:
          diff=0
          for k in range(3):
            diff+=((dp[j][k]+cakes[c][k])*plus_or_minus[k])-(dp[j+1][k]*plus_or_minus[k])
          if diff>0:
            dp[j+1][0]=dp[j][0]+cakes[c][0]
            dp[j+1][1]=dp[j][1]+cakes[c][1]
            dp[j+1][2]=dp[j][2]+cakes[c][2]
  if abs(dp[-1][0])+abs(dp[-1][1])+abs(dp[-1][2])>ans:
    ans=abs(dp[-1][0])+abs(dp[-1][1])+abs(dp[-1][2])

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

from collections import deque

N,M=map(int,input().split())
# 頂点の番号は0-initialのまま扱う
E=set() # 辺から成るset
for i in range(M):
    u,v=map(int,input().split())
    E.add((u,v))
S,T=map(int,input().split())

d1=[set() for i in range(N+1)] # d1[i]=頂点iからの距離が1であるような頂点vから成るset
for e in E:
    u=e[0];v=e[1]
    d1[u].add(v)

d2=[set() for i in range(N+1)] # d2[i]=頂点iからの距離が2であるような頂点vから成るset
for e in E:
    u=e[0];v=e[1]
    d2[u].update(d1[v])

d3=[set() for i in range(N+1)]
for e in E:
    u=e[0];v=e[1]
    d3[u].update(d2[v])
'''
print(e)
print(d1)
print(d2)
print(d3)
'''
dis=[-1 for i in range(N+1)];dis[S]=0 # 頂点Sからの距離
# WFS
q=deque() # 遅ければlistで実装
q.append(S)
while q:
#    print(q) #DB
#    print(dis) #DB
    u=q.popleft()
    vs=[v for v in d3[u] if dis[v]==-1]
    for v in vs:
        dis[v]=dis[u]+1
    q.extend(vs)

print(dis[T])

### FIXED CODE ###

from collections import deque

N,M=map(int,input().split())
a=[[[] for j in range(N)] for i in range(3)] # 0-indexのグラフが3つある
for i in range(M):
    u,v=map(lambda x:int(x)-1,input().split())
    a[0][u].append((1,v))
    a[1][u].append((2,v))
    a[2][u].append((0,v))
S,T=map(lambda x:int(x)-1,input().split())
# print(a)

r=[[-3 for j in range(N)] for i in range(3)]
q=deque()
q.append((0,S));r[0][S]=0
while q:
    ui,uj=q.popleft()
    for vi,vj in a[ui][uj]:
        if r[vi][vj]==-3:
            r[vi][vj]=r[ui][uj]+1
            q.append((vi,vj))
# print(r)
print(r[0][T]//3)
### BUGGY CODE ###

from scipy.misc import comb
N = int(input())
a = [int(x) for x in input().split()]
ans1 = max(a)
a.remove(ans1)
maxkouho = -1
ans2 = -1
for k in a:
    kouho = comb(ans1, k, exact=True)
    if kouho > maxkouho:
        ans2 = k
        #print(ans2)
        maxkouho = comb(ans1, k, exact=True)
print(ans1, ans2)


### FIXED CODE ###

N = int(input())
a = [int(x) for x in input().split()]
ans1 = max(a)
a.remove(ans1)
b = sorted(a, reverse=True)
ans2 = b[0]
for i in range(N - 2):
    if abs((ans1 / 2) - b[i]) > abs((ans1 / 2) - b[i+1]):
        ans2 = b[i + 1]
    else:
        break

# print(b)
print(ans1, ans2)
### BUGGY CODE ###

from collections import deque


def max_heapify(A, i):
    H = len(A) - 1
    l, r = i * 2 + 1, i * 2 + 2
    if l <= H and A[l] > A[i]:
            largest = l
    else:
        largest = i
    if r <= H and A[r] > A[largest]:
        largest = r

    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        max_heapify(A, largest)


def build_max_heap(A):
    for i in range(len(A) // 2, -1, -1):
        max_heapify(A, i)


def insert(S, k):
    S.append(k)
    build_max_heap(S)


def extract(S):
    res = S.popleft()
    build_max_heap(S)
    return res

S = deque()
while True:
    cmd = input().split()
    if cmd[0] == "insert":
        insert(S, int(cmd[1]))
    elif cmd[0] == "extract":
        print(extract(S))
    else:
        break

### FIXED CODE ###

import heapq


hq = []
while True:
    cmd = input().split()
    if cmd[0] == "insert":
        heapq.heappush(hq, -int(cmd[1]))
    elif cmd[0] == "extract":
        print(-heapq.heappop(hq))
    else:
        break
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
b = []
c = []
for i in range(len(a)):
  x = a[i]
  if x in b:
    c[b.index(x)].append(i)
  else:
    b.append(x)
    c.append([i])
d = []
for i in range(len(a)):
  x = a[i]
  xc = c[b.index(x)]
  d.append(xc[(xc.index(i)+1)%len(xc)])
#print(d)
count = 0
now = 0
while now != 0 or count == 0:
  past = now
  now = ( d[past] + 1 ) % n
  if now - 1 <= past:
    count += 1
  #print(past,now,count)
limit = k % count
#print(count,limit)
count = 0
now = 0
while True:
  past = now
  now = ( d[past] + 1 ) % n
  if now - 1 <= past:
    if count == limit - 2:
      break
    count += 1
#print(d,past,a)
ans = []
for i in range(-n+past,n):
  x = a[i%n]
  #print(x)
  if x in ans:
    ans = ans[:ans.index(x)]
  else:
    ans.append(x)
#print(ans)
ans2 = list(map(str,ans))
print(' '.join(ans2))

### FIXED CODE ###

#17:43
n,k = map(int,input().split())
a = list(map(lambda x: int(x)-1, input().split()))
mx = max(a) + 1
num = [[] for _ in range(mx)]
leg = [0 for _ in range(mx)]
for i in range(n):
  num[a[i]].append(i)
  leg[a[i]] += 1
#print(num)
nex = [0 for _ in range(n)]
for j in range(mx):
  nu = num[j]
  le = leg[j]
  for li in range(le-1):
    nex[nu[li]] = nu[li+1]+1
  if nu:
    nex[nu[-1]] = nu[0]+n+1
#print(nex)
unit = 0
now = 0
while True:
  tmp = nex[now]
  unit += tmp // n
  now = tmp % n
  #print(tmp,now)
  if now == 0:
    break
#print(unit)
k %= unit
k *= n
#print(k)
if k == 0:
  exit()
while True:
  tmp = nex[now]
  if k - (tmp-now) > 0:
    k -= tmp - now
    now = tmp % n
  else:
    ans = a[-k:]
    break
  #print(k)
l = len(ans)
seen = [0 for _ in range(mx)]
ans2 = []
for li in range(l):
  if seen[ans[li]] == 1:
    while True:
      p = ans2.pop()
      seen[p] = 0
      if p == ans[li]:
        break
  else:
    ans2.append(ans[li])
    seen[ans[li]] = 1
print(' '.join(map(lambda x:str(x+1),ans2)))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
D - Lamp
https://atcoder.jp/contests/abc129/tasks/abc129_d

"""
import sys


def solve(H, W, grid):
    res_x = [[0]*W for _ in range(H)]
    x, y = 0, 0
    while y < H:
        while x < W:
            if grid[y][x] == '#':
                x += 1
                continue
            rx = x
            while rx < W and grid[y][rx] != '#':
                rx += 1
            for xx in range(x, rx):
                res_x[y][xx] = rx-x
            x = rx
        x = 0
        y += 1

    res_y = [[0]*W for _ in range(H)]
    x, y = 0, 0
    while y < H:
        while x < W:
            if grid[y][x] == '#' or res_y[y][x] != 0:
                x += 1
                continue
            dy = y
            while dy < H and grid[dy][x] != '#':
                dy += 1
            for yy in range(y, dy):
                if res_y[yy][x] == 0:
                    res_y[yy][x] = dy-y
            x += 1
        x = 0
        y += 1

    ans = 0
    for y in range(H):
        for x in range(W):
            t = res_x[y][x] + res_y[y][x] - 1
            if t > ans:
                ans = t
    return ans


def main(args):
    H, W = map(int, input().split())
    grid = [input() for _ in range(H)]
    ans = solve(H, W, grid)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


### FIXED CODE ###

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



"""
import sys


def solve(H, W, grid):
    res_x = [[0]*W for _ in range(H)]
    x, y = 0, 0
    while y < H:
        while x < W:
            if grid[y][x] == '#':
                x += 1
                continue
            rx = x
            while rx < W and grid[y][rx] != '#':
                rx += 1
            for xx in range(x, rx):
                res_x[y][xx] = rx-x
            x = rx
        x = 0
        y += 1

    res_y = [[0]*W for _ in range(H)]
    x, y = 0, 0
    while y < H:
        while x < W:
            if grid[y][x] == '#' or res_y[y][x] != 0:
                x += 1
                continue
            dy = y
            while dy < H and grid[dy][x] != '#':
                dy += 1
            for yy in range(y, dy):
                if res_y[yy][x] == 0:
                    res_y[yy][x] = dy-y
            x += 1
        x = 0
        y += 1

    ans = 0
    for y in range(H):
        for x in range(W):
            t = res_x[y][x] + res_y[y][x] - 1
            if t > ans:
                ans = t
    return ans


def main(args):
    H, W = map(int, input().split())
    grid = [input() for _ in range(H)]
    ans = solve(H, W, grid)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])
### BUGGY CODE ###

R,G,B,N = map(int, input().split())

ans = int(0)
x = int(N//R)

for i in range(x+1):
    t = N-i*R
    y = int(t//G)
    for j in range(y+1) :
        s = int(N-R*i-G*j)
        if s%B==0 : ans +=1

print(ans)

### FIXED CODE ###

R,G,B,N = map(int, input().split())

ans = int(0)
x = int(N//R)

for i in range(x+1):
    t = N-i*R
    y = int(t//G)
    for j in range(y+1) :
        s = int(t-G*j)
        if s%B==0 : ans +=1

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

from collections import deque
N,M,K = list(map(int,input().split()))
G1 = [[] for i in range(N)]
G2 = [[] for i in range(N)]
for i in range(M):
    A,B = list(map(int,input().split()))
    G1[A-1].append(B-1)
    G1[B-1].append(A-1)

for i in range(K):
    A,B = list(map(int,input().split()))
    G2[A-1].append(B-1)
    G2[B-1].append(A-1)

Block = [0]*N
Friend = [0]*N
Network = [0]*N
out = [0]*N

for i in range(N):
    Friend[i] = len(G1[i])

Done = [0]*N
for i in range(N):
    s = i
    if Done[s]!=0:
        continue
    L = []
    que = deque([s])
    Done[s] = 1
    L.append(s)
    while que:
        v = que.popleft()
        for w in G1[v]:
            if Done[w]==1:
                continue
            Done[w] = 1
            que.append(w)
            L.append(w)
    NL = len(L)
    for j in L:
        Network[j] = NL-1
        Block[j] = len(set(L)&set(G2[j]))

for i in range(N):
    out[i] = Network[i]-Block[i]-Friend[i]
print(*out)

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N, M, K = map(int, input().split())
Network = UnionFind(N)
Friend = [0] * N
BlockInNetwork = [0] * N

for _ in range(M):
    a, b = map(int, input().split())
    Network.union(a-1, b-1)
    Friend[a-1] += 1
    Friend[b-1] += 1

for _ in range(K):
    c, d = map(int, input().split())
    if Network.same(c-1, d-1):
        BlockInNetwork[c-1] += 1
        BlockInNetwork[d-1] += 1

out = [0]*N
for i in range(N):
    out[i]=Network.size(i)-Friend[i]-BlockInNetwork[i] - 1
print(*out)
### BUGGY CODE ###

def solve():
    s = input()

    cnt = 0
    for i in range(0, len(s)):
        nr = int(s[0:i]) if i else -1
        nl = int(s[i:])
        # print(nr, nl)
        if nr % 2019 == 0:
            # print('&')
            cnt = cnt + 1
        if nl % 2019 == 0:
            # print('s')
            cnt = cnt + 1

        if len(str(nr)) > 4:
            for j in range(i-4, 0, -1):
                # print('  ', s[j:i])
                nt = int(s[j:i])
                if nt % 2019 == 0:
                    cnt = cnt + 1

    print(cnt)


if __name__ == '__main__':
    solve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())
 
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
 
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
 
INF = float('inf')
 
def solve():
    S = list(map(int, list(input())))
 
    S = S[::-1]
    # print(S)
    n = len(S)
    mod = 2019
 
    #
    A = [0] * (n)
    a = 1
    for i in range(n):
        A[i] = S[i] * a
        a = a * 10 % mod
    # print(A)
 
    # 累積和
    R = [0] * (n+1)
    for j in range(n):
        R[j+1] = (R[j] + A[j]) % mod
    # print(R)
 
    # 個数を数える
    cnt = {}
    ans = 0
    for l in range(0, n+1):
        r = R[l]
        ans = ans + cnt.get(r, 0)
        cnt[r] = cnt.setdefault(r, 0) + 1
    print(ans)
 
if __name__ == '__main__':
    solve()
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
x=10**9+7
if len(set(a))!=len(a) or len(set(b))!=len(b):
  print(0)
else:
  a.sort()
  b.sort()
  L=[]
  for i in range(n):
    l=[]
    for j in range(m):
      l.append(0)
    L.append(l)
  if m*n in a and m*n in b:
    L[a.index(m*n)][b.index(m*n)]=m*n
    ct=1
    ctn=1
    ctm=1
    for k in range(m*n-1,0,-1):
      if k in a and k in b:
        L[a.index(k)][b.index(k)]=k
        ct*=1
        ctn+=1
        ctm+=1
      elif k in a or k in b:
        if k in a:
          ct*=ctm
          ctn+=1
        if k in b:
          ct*=ctn
          ctm+=1
      else:
        ct*=(ctm*ctn-m*n+k)
      if ct==0:
        break
      ct=ct%x
    print(ct)
  else:
    print(0)

### FIXED CODE ###

import bisect
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
x=10**9+7
if len(set(a))!=len(a) or len(set(b))!=len(b):
  print(0)
else:
  a.sort()
  b.sort()
  L=[]
  for i in range(n):
    l=[]
    for j in range(m):
      l.append(0)
    L.append(l)
  if m*n in a and m*n in b:
    L[a.index(m*n)][b.index(m*n)]=m*n
    ct=1
    ctn=1
    ctm=1
    A=set(a)
    B=set(b)
    for k in range(m*n-1,0,-1):
      if k in A and k in B:
        L[bisect.bisect_left(a,k)][bisect.bisect_left(b,k)]=k
        ct*=1
        ctn+=1
        ctm+=1
      elif k in A:
          ct*=ctm
          ctn+=1
      elif k in B:
          ct*=ctn
          ctm+=1
      else:
        ct*=(ctm*ctn-m*n+k)
      if ct==0:
        break
      ct=ct%x
    print(ct)
  else:
    print(0)
### BUGGY CODE ###

import collections
S=input()
l=len(S)
t=0
p=0
m=[]
ss=[0]
for i in range(l):
    m.append(int(S[i])*(10**(l-1-i))%2019)
    ss.append((ss[i]+m[i])%2019)

k=collections.Counter(ss)

for i in k.values():
    t+=(i-1)
print(t)



### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

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

print(ans) # 答えの出力
### BUGGY CODE ###

#D問題
import heapq
N,M = map(int,input().split())
AB = []
for i in range(N):
    ab = list(map(int,input().split()))
    heapq.heappush(AB,ab)
    
ans = 0
cand = []
for i in range(M):
    for ab in AB:
        if ab[0] <= (i+1):
            heapq.heappush(cand,10**5-ab[1])
            ind = AB.index(ab)
            del AB[ind]
    
    if len(cand) >= 1:
        cd = heapq.heappop(cand)
        ans+=(10**5-cd)
    
print(ans)

### FIXED CODE ###

#D問題
import heapq
N,M = map(int,input().split())
AB = []
for i in range(N):
    ab = list(map(int,input().split()))
    heapq.heappush(AB,ab)
    
ans = 0
cand = []
for i in range(M):
    while AB:
        ab = heapq.heappop(AB)
        if ab[0] <= (i+1):
            heapq.heappush(cand,10**5-ab[1])
        else:
            heapq.heappush(AB,ab)
            break
    
    if len(cand) >= 1:
        cd = heapq.heappop(cand)
        ans+=(10**5-cd)
    
print(ans)