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

import bisect
from collections import defaultdict
N = int(input())
S = input()
Q = int(input())

dict = defaultdict(set)
for i in range(N):
    dict[S[i]].add(i)
# print(dict)

ans = []

for _ in range(Q):
    a, b, c = input().split()
    a = int(a)
    if a == 1:
        b = int(b) - 1
        for key in dict.keys():
            if b in dict[key]:
                dict[key].discard(b)
                dict[c].add(b)
                break
    elif a == 2:
        b = int(b) - 1
        c = int(c) - 1
        char_n = 0
        for key, value in dict.items():
            value = list(value)
            value.sort()
            x1 = bisect.bisect_left(value, b)
            x2 = bisect.bisect_right(value, c)
            if x2 - x1 > 0:
                char_n += 1
        ans.append(char_n)

for i in ans:
    print(i)


### FIXED CODE ###

# test!!!!!!!!!!!

from bisect import bisect_left, bisect_right

N = int(input())

S = list(input())

Q = int(input())

memo = {chr(ord('a') + i): [] for i in range(26)}

for key,val in enumerate(S):
    memo[val].append(key)

for q in range(Q):
    query = list(input().split())
    if query[0] == '1':
        i, x = int(query[1])-1, query[2]
        now = S[i]
        if now == x:
            continue
        memo[now].remove(i)
        next_i = bisect_left(memo[x], i)
        memo[x].insert(next_i, i)
        S[i] = x
    else:
        start, end = int(query[1])-1, int(query[2])-1
        tmp_cout = 0
        for alf_array in memo.values():
            if len(alf_array) == 0:
                continue
            ss = bisect_left(alf_array, start)
            gg = bisect_right(alf_array, end)
            if gg- ss > 0:
                tmp_cout += 1
        print(tmp_cout)
### BUGGY CODE ###

import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

def main():
    n,m,R = i_map()
    r = i_list()
    c = [[INF]*n for i in range(n)]
    for i in range(n):
        c[i][i] = 0

    for _ in range(m):
        a,b,d = i_map()
        a -= 1
        b -= 1
        c[a][b] = c[b][a] = d

    for k in range(n): # 経由
        for i in range(n): # 始点
            for j in range(n): # 終点
                c[i][j] = min(c[i][j], c[i][k] + c[k][j])

    r = list(itertools.permutations(r, R))

    ans = INF
    for i in r:
        trial = 0
        for k in range(len(i)-1):
            a = i[k] - 1
            b = i[k+1] - 1
            trial += c[a][b]
        ans = min(ans,trial)
    print(ans)




if __name__=="__main__":
    main()


### FIXED CODE ###

import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

def main():
    n,m,R = i_map()
    r = i_list()
    c = [[INF]*n for i in range(n)]
    for i in range(n):
        c[i][i] = 0

    for _ in range(m):
        a,b,d = i_map()
        a -= 1
        b -= 1
        c[a][b] = c[b][a] = d

    for k in range(n): # 経由
        for i in range(n): # 始点
            for j in range(n): # 終点
                c[i][j] = min(c[i][j], c[i][k] + c[k][j])

    r = list(itertools.permutations(r, R))

    ans = INF
    for i in r:
        trial = 0
        for k in range(len(i)-1):
            a = i[k] - 1
            b = i[k+1] - 1
            trial += c[a][b]
        ans = min(ans,trial)
    print(ans)




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

from math import factorial as fa
f=lambda a,b:fa(a)//(fa(a-b)*fa(b))
n,a,b,k=map(int,input().split())
v=998244353
l=[]

for i in range(n+1):
  if not (k-a*i)%b:
    j=(k-a*i)//b
    if 0<=j<=n+1:
      l.extend([(i,j)])

s=0
for (i,j) in l:
  s+=(f(n,i)*f(n,j))%v

print(s)

### FIXED CODE ###

n,a,b,k=map(int,input().split())
mod=998244353
s=0
fac=[1]*(n+1)
rev=[1]*(n+1)

for i in range(1,n+1):
  fac[i]=i*fac[i-1]%mod
  rev[i]=pow(fac[i],mod-2,mod)

f=lambda a,b:(fac[a]*rev[a-b]*rev[b])%mod

for i in range(n+1):
  j,r=divmod((k-a*i),b)
  if r==0 and 0<=j<=n:
    s+=(f(n,i)*f(n,j))%mod

print(s%mod)
### BUGGY CODE ###

N = int(input())
ARR = [int(s) for s in input().split(" ")]
def calculate(n,arr):

    left = list([])
    right = list([])
    if n % 2 == 0:
        for index,ar in enumerate(arr):
            if index % 2 == 0:
                right.append(str(ar))
            else:
                left.insert(0,str(ar))
    else:
        for index,ar in enumerate(arr):
            if index % 2 == 0:
                left.insert(0,str(ar))
            else:
                right.append(str(ar))
    left.extend(right)

    return left

result = calculate(N,ARR)
print(" ".join(result))

### FIXED CODE ###

N = int(input())
ARR = [int(s) for s in input().split(" ")]
def calculate(n,arr):

    left = list([])
    right = list([])
    if n % 2 == 0:
        for index,ar in enumerate(arr):
            if index % 2 == 0:
                right.append(str(ar))
            else:
                left.append(str(ar))
    else:
        for index,ar in enumerate(arr):
            if index % 2 == 0:
                left.append(str(ar))
            else:
                right.append(str(ar))

    left.reverse()
    left.extend(right)

    return left

result = calculate(N,ARR)
print(" ".join(result))
### BUGGY CODE ###

import math
k=int(input())
d=0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            c=math.gcd(i,j)
            d+=math.gcd(c,l)
print(d)



### FIXED CODE ###

import math
k=int(input())
d=0
for i in range(1,k+1):
    for j in range(i+1,k+1):
        for l in range(j+1,k+1):
            c=math.gcd(i,j)
            d+=6*(math.gcd(c,l))
for i in range(1,k+1):
    for j in range(i+1,k+1):
        d+=6*(math.gcd(i,j))
for i in range(1,k+1):
    d+=i
print(d)
### BUGGY CODE ###

N=int(input())
A = list(map(int, input().strip().split()))
for i in range(1,N+1):
  c=0
  for j in range(len(A)):
    if A[j]==i:
      c+=1
  print(c)    



### FIXED CODE ###

n=int(input())
A = list(map(int, input().split()))
list=[0]*(n+2)

for i in range(n-1):
  list[A[i]]+=1
for i in range(1,n+1):
  print(list[i])
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 15 16:58:00 2019

@author: YudNK
"""
import bisect as bs

N, Q = map(int, input().split())
E = []
for i in range(N):
    s, t, x = map(int, input().split())
    a = [s - x, t - x, x] #イベント
    E.append(a)
E.sort(key = lambda x: x[2])
D = []
for i in range(Q):
    D.append(int(input()))

ans = [-1]*Q

for e in E:
    l = bs.bisect_left(D, e[0])
    r = bs.bisect_left(D, e[1])
    for i in range(l, r):
        if ans[i] == -1:
            ans[i] = e[2]
        else:
            pass
    
[print(i) for i in ans]

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 15 16:58:00 2019

@author: YudNK
"""
import bisect as bs

N, Q = map(int, input().split())
E = []
for i in range(N):
    s, t, x = map(int, input().split())
    a = [s - x, t - x, x] #イベント
    E.append(a)
E.sort(key = lambda x: x[2])
D = []
for i in range(Q):
    D.append(int(input()))

ans = [-1]*Q
check = [-1]*Q

for e in E:
    l = bs.bisect_left(D, e[0])
    r = bs.bisect_left(D, e[1])
    while l < r:
        if check[l] == -1:  
            ans[l] = e[2]
            check[l] = r
            l += 1
        else:
            l = check[l]
        
[print(i) for i in ans]
### BUGGY CODE ###

import statistics

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

for i in range(len(Xs)):
    Xs_i=Xs[:i]+Xs[i+1:]
    med=statistics.median(Xs_i)
    print(med)

### FIXED CODE ###

N=int(input())
Xs=list(map(int, input().split()))
nXs=sorted(Xs)

medL=nXs[len(nXs)//2-1]
medR=nXs[len(nXs)//2]

if medL == medR:
    for i in range(N):
        print(medL)
else:
    for i in Xs:
        if i<=medL:
            print(medR)
        else:
            print(medL)
### BUGGY CODE ###

import sys
import numpy as np

read = lambda : sys.stdin.readline().rstrip('\n')
tint = lambda x: [int(x) for x in x.split()]
ttuple = lambda x: tuple(int(x) for x in x.split())

def main():
    n, k = tint(read())
    stones = ttuple(read())
    inf = 10**9
    dp = np.array([inf]*n)
    dp[0] = 0
    for i in range(n):
        for t in range(1, k+1):
            step = i+t
            if step < n:
                #dp[step] = min(dp[step], dp[i]+abs(stones[i]-stones[step]))
                v = dp[i]+abs(stones[i]-stones[step])
                if v < dp[step]:
                    dp[step] = v
    print(dp[-1])


if __name__ == '__main__':    
    main()


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = tuple(map(int, input().split()))
    INF = 10 ** 9
    dp = [INF] * n
    dp[0] = 0
    for i in range(n):
        for j in range(1, k + 1):
            i_j = i + j
            if i_j < n:
                x = dp[i] + abs(h[i] - h[i_j])
                if dp[i_j] > x:
                    dp[i_j] = x
    print(dp[-1])


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

n=int(input())
a=[]
for i in range(n):
  a.append(int(input())-1)
i=0
seen=[]
out=0
while i!=1:
  out+=1
  i=a[i]
  if i in seen:
    out=-1
    break
  seen.append(i)
print(out)


### FIXED CODE ###

n=int(input())
a=[]
for i in range(n):
  a.append(int(input())-1)
i=0

out=0
kai=0
while i!=1:
  kai+=1
  out+=1
  i=a[i]
  if kai>n:
    out=-1
    break

print(out)
### BUGGY CODE ###

import itertools
X, Y, Z, K = map(int, input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]

D = []
for a, b in itertools.product(A, B):
    d = a + b
    D.append(d)
D.sort(reverse = True)

E = []
for c, d in itertools.product(C, D[:K]):
    e = c + d
    E.append(e)
    
E.sort(reverse = True)
for e in E[:K]:
    print(e)

### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = sorted([int(i) for i in input().split()], reverse = True)
B = sorted([int(i) for i in input().split()], reverse = True)
C = sorted([int(i) for i in input().split()], reverse = True)

D = []
for i in range(X):
    for j in range(Y):
        if (i + 1) * (j + 1) > K:
            break
        for k in range(Z):
            if (i + 1) * (j + 1) * (k + 1) > K:
                break
            D.append(A[i] + B[j] + C[k])
            #print(A[i] + B[j] + C[k], i, j, k)
            
D.sort(reverse = True)
for d in D[:K]:
    print(d)
### BUGGY CODE ###

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

ab = []
for i in range(n):
    a, b = map(int, input().split())
    ab.append([a, b])

INF = 1 << 60
dp = [INF for _ in range(h+10001)]

dp[0] = 0

for i in range(1, h+10001):
    for j in range(n):
        if(i >= ab[j][0]):
            dp[i] = min(dp[i-ab[j][0]] + ab[j][1], dp[i])

res = INF
for i in range(h, h+10001):
    res = min(res, dp[i])
print(res)


### FIXED CODE ###

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

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

INF = 1 << 60
dp = [INF for _ in range(h+10001)]

dp[0] = 0

for i in range(1, h+10001):
    for j in range(n):
        if(i >= ab[j][0]):
            dp[i] = min(dp[i-ab[j][0]] + ab[j][1], dp[i])

res = INF
for i in range(h, h+10001):
    res = min(res, dp[i])
print(res)
### BUGGY CODE ###

N,Y = map(int, input().split())


a = Y//10000
b = Y//5000
c = Y//1000

flag = False

for i in range(a+1):
    if flag == True:
        break
    if i>N:
        break
    for j in range(b+1-2*i):
        if flag == True:
            break
        if i+j > N:
            break
        for k in range(c+1-10*i-5*j):
            if (i + j + k) > N:
                break
            if i+j+k == N:
                if i*10000+j*5000+k*1000 == Y:
                    flag = True
                    s = i
                    t = j
                    u = k

if flag == True:
    print(s,t,u)
else:
    print(-1,-1,-1)

### FIXED CODE ###

N,Y = map(int, input().split())


a = Y//10000
b = Y//5000

flag = False

for i in range(a+1):
    if flag == True:
        break
    for j in range(b+1):
        if N-i-j<0:
            break
        if i*10000+j*5000+(N-i-j)*1000 == Y:
            flag = True
            s = i
            t = j
            u = N-i-j
            break

if flag == True:
    print(s,t,u)
else:
    print(-1,-1,-1)
### BUGGY CODE ###

inputNum = int(input())

if 2 <= inputNum <= 10**5:
    list = list(map(int, input().split()))
    val = 1
    for item in list:
        val = val * item
    if 0 <= val <= 10**18:
        print(val)
    elif 10**18 < val:
        print(-1)


### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int,input().split()))
    if 0 in a: 
        print(0)
        return
    ans = 1
    for ai in a:
        ans *= ai
        if ans > 10**18:
            print(-1)
            return
    print(ans)
    
if __name__ =="__main__":
    main()
### BUGGY CODE ###

a = int(input())
numl = [i for i in range(2,a+1)] + [1]
ans = 0
for i in range(a):
    ans += (i+1) % numl[i]
print(ans)

### FIXED CODE ###

a = int(input())
print(a*(a-1)//2)
### BUGGY CODE ###

K, S = map(int, input().split())
count = 0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x + y + z == S:
                count += 1
print(count)

### FIXED CODE ###

K, S = map(int, input().split())
count = 0
for x in range(K+1):
    for y in range(K+1):
        z = S - x - y
        if 0<=z and z<=K:
            count += 1
print(count)
### BUGGY CODE ###

n = int(input())
V = [int(v) for v in input().split()]

V1 = [V[n] for n in range(0, n, 2)] #v1, v3, v5, ...
V2 = [V[n] for n in range(1, n, 2)] #v2, v4, v6, ...

V1_set = list(set(V1))
V1_cnt = [[0, 0]] #V1に一種類しか数字が存在しなかったときのために
for i in V1_set:
  i_cnt = V1.count(i)
  V1_cnt += [[i, i_cnt]]
V1_cnt.sort(key=lambda x: x[1], reverse=True)
  
V2_set = list(set(V2))
V2_cnt = [[0, 0]] #V2に一種類しか数字が存在しなかったときのために
for i in V2_set:
  i_cnt = V2.count(i)
  V2_cnt += [[i, i_cnt]]
V2_cnt.sort(key=lambda x: x[1], reverse=True)

mxnum_V1_cnt = V1_cnt[0][0] #V1の中で一番出現回数多い数字
mxnum_V2_cnt = V2_cnt[0][0] #V2の中で一番出現回数多い数字
if mxnum_V1_cnt != mxnum_V2_cnt:
  ans = n - (V1_cnt[0][1] + V2_cnt[0][1])
else:
  ans = n - max(V1_cnt[0][1] + V2_cnt[1][1], V1_cnt[1][1] + V2_cnt[0][1])

print(ans)

### FIXED CODE ###

n = int(input())
V = [int(v) for v in input().split()]

V1 = [V[n] for n in range(0, n, 2)] #v1, v3, v5, ...
V2 = [V[n] for n in range(1, n, 2)] #v2, v4, v6, ...

mx_V1 = max(V1)
V1_cnt = [[0, 0]] # V1に一種類しか数字が存在しなかったときのために
for i in range(1, mx_V1+1):
  V1_cnt.append([i, 0])
for v in V1:
  V1_cnt[v][1] += 1  
V1_cnt.sort(key=lambda x: x[1], reverse=True)

mx_V2 = max(V2)
V2_cnt = [[0, 0]] # V2に一種類しか数字が存在しなかったときのために
for j in range(1, mx_V2+1):
  V2_cnt.append([j, 0])
for v in V2:
  V2_cnt[v][1] += 1  
V2_cnt.sort(key=lambda x: x[1], reverse=True)

mxnum_V1_cnt = V1_cnt[0][0] #V1の中で一番出現回数多い数字
mxnum_V2_cnt = V2_cnt[0][0] #V2の中で一番出現回数多い数字
if mxnum_V1_cnt != mxnum_V2_cnt:
  ans = n - (V1_cnt[0][1] + V2_cnt[0][1])
else:
  ans = n - max(V1_cnt[0][1] + V2_cnt[1][1], V1_cnt[1][1] + V2_cnt[0][1])

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

def main():
  w = input()
  s = collections.deque(w)
  n = int(input())
  
  order = True
  for _ in range(n):
    q = list(input_list_str())
    if len(q) == 1:
      order = False if order else True
      continue
    t, f, c = q
    if int(f) == 1:
      if order:
        w = c + w
      else:
        w = w + c
    else:
      if order:
        w = w + c
      else:
        w = c + w
  if order is False:
    w = w[::-1]
  print(w)

    
def input_list():
  return map(int, input().split())

def input_list_str():
  return map(str, input().split())

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

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

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

import math
import fractions
import collections
from functools import reduce
main()

### FIXED CODE ###

def main():
  w = input()
  s = collections.deque(w)
  n = int(input())
  
  reverse_count = 0
  for i in range(n):
    t = list(input_list_str())
    if len(t) == 1:
      reverse_count = 1 - reverse_count
      continue
    q, f, c = t
    if int(f) + reverse_count == 2:
      s.append(c)
    else:
      s.appendleft(c)
  if reverse_count == 1:
    s.reverse()
  print(''.join(s))

    
def input_list():
  return map(int, input().split())

def input_list_str():
  return map(str, input().split())

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

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

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

import math
import fractions
import collections
from functools import reduce
main()
### BUGGY CODE ###

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

diff_dic = {}
diff_dic[('R', 'G')] = []
diff_dic[('R', 'B')] = []
diff_dic[('G', 'R')] = []
diff_dic[('G', 'B')] = []
diff_dic[('B', 'G')] = []
diff_dic[('B', 'R')] = []

R_lst = [0] * N
G_lst = [0] * N
B_lst = [0] * N

r_cnt = 0
g_cnt = 0
b_cnt = 0
for i in range(N):
    if S[i] == 'R':
        r_cnt += 1
    elif S[i] == 'G':
        g_cnt += 1
    else:
        b_cnt += 1

    R_lst[i] = r_cnt
    G_lst[i] = g_cnt
    B_lst[i] = b_cnt

    for j in range(i + 1, N):
        if S[i] == 'R':
            if S[j] != 'R':
                diff_dic[('R', S[j])].append((j, j - i))

        elif S[i] == 'G':
            if S[j] != 'G':
                diff_dic[('G', S[j])].append((j, j - i))

        elif S[i] == 'B':
            if S[j] != 'B':
                diff_dic[('B', S[j])].append((j, j - i))


cnt = 0

for t in [('R', 'G'), ('G', 'R')]:
    for j, d in diff_dic[t]:
        if j < N - 1:
            if b_cnt - B_lst[j] > 0:
                cnt += b_cnt - B_lst[j]
                if j + d < N and S[j + d] == 'B':
                    cnt -= 1

for t in [('G', 'B'), ('B', 'G')]:
    for j, d in diff_dic[t]:
        if j < N - 1:
            if r_cnt - R_lst[j] > 0:
                cnt += r_cnt - R_lst[j]
                if j + d < N and S[j + d] == 'R':
                    cnt -= 1

for t in [('B', 'R'), ('R', 'B')]:
    for j, d in diff_dic[t]:
        if j < N - 1:
            if g_cnt - G_lst[j] > 0:
                cnt += g_cnt - G_lst[j]
                if j + d < N and S[j + d] == 'G':
                    cnt -= 1

print(cnt)


### FIXED CODE ###

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

diff_dic = {}
diff_dic[('R', 'G')] = []
diff_dic[('R', 'B')] = []
diff_dic[('G', 'R')] = []
diff_dic[('G', 'B')] = []
diff_dic[('B', 'G')] = []
diff_dic[('B', 'R')] = []

R_lst = [0] * N
G_lst = [0] * N
B_lst = [0] * N

r_cnt = 0
g_cnt = 0
b_cnt = 0

cnt = 0
for i in range(N):
    if S[i] == 'R':
        r_cnt += 1
    elif S[i] == 'G':
        g_cnt += 1
    else:
        b_cnt += 1

    R_lst[i] = r_cnt
    G_lst[i] = g_cnt
    B_lst[i] = b_cnt

    for j in range(i):
        d = i - j
        if (S[i] == 'R' and S[j] == 'G') or (S[i] == 'G' and S[j] == 'R'):
            if j - 1 >=0 and B_lst[j - 1] > 0:
                cnt += B_lst[j - 1]
                if j - d >= 0 and S[j - d] == 'B':
                    cnt -= 1

        if (S[i] == 'G' and S[j] == 'B') or (S[i] == 'B' and S[j] == 'G'):
            if j - 1 >=0 and R_lst[j - 1] > 0:
                cnt += R_lst[j - 1]
                if j - d >= 0 and S[j - d] == 'R':
                    cnt -= 1

        if (S[i] == 'B' and S[j] == 'R') or (S[i] == 'R' and S[j] == 'B'):
            if j - 1 >= 0 and G_lst[j - 1] > 0:
                cnt += G_lst[j - 1]
                if j - d >= 0 and S[j - d] == 'G':
                    cnt -= 1

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

# cook your dish here
n,k=input().split()
n=int(n)
k=int(k)
l=list(map(int,input().split()))
m=[]
for j in range(n):
    s=1
    for i in range(j,j+k):
        s=s*l[i]
    if len(m)!=0:
        if s>m[-1]:
            print("Yes")
        else:
            print("No")
    m.append(s)        
                
    if j+k==n:
        break


    

### FIXED CODE ###

# cook your dish here
n,k=input().split()
n=int(n)
k=int(k)
l=list(map(int,input().split()))
for j in range(n):
    if k+j==n:
        break
    if l[k+j]>l[j]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import math

k = int(input()) + 1
ans = 0

for a in range(1, k):
    for b in range(1, k):
        for c in range(1, k):
            #print(a, b, c)
            ans += math.gcd(a, math.gcd(b, c))

print(ans)


### FIXED CODE ###

import math

k = int(input()) + 1
ans = 0

for a in range(1, k):
    for b in range(1, k):
        d = math.gcd(a, b)
        for c in range(1, k):
            ans += math.gcd(d, c)

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

# sys.stdin.readline()
import sys
import time
input = sys.stdin.readline
import math

N,M = (int(x) for x in input().split())
A = list(map(int, input().split()))
# A.sort(reverse=True)

# t1 = time.time()
for i in range(M):
    a = max(A) // 2
    j = A.index(max(A))
    A[j] = a
    # A[0] = A[0]//2
    # A.sort(reverse=True)
    if sum(A) <1:
        break

print(sum(A))

### FIXED CODE ###

# sys.stdin.readline()
import sys
import time
input = sys.stdin.readline
import math
import heapq

N,M = (int(x) for x in input().split())
A = list(map(int, input().split()))
A = [-i for i in A]
# print(A)
heapq.heapify(A)
# print(heapq.heappop(A))

# t1 = time.time()
for i in range(M):
    a = -heapq.heappop(A) // 2
    heapq.heappush(A, -a)
    # j = A.index(max(A))
    # A[j] = a
    # A[0] = A[0]//2
    # A.sort(reverse=True)
    # if sum(A) <1:
    #     break

print(-sum(A))
### BUGGY CODE ###

# coding: utf-8

import math
from functools import reduce

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

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

ans = 0

for a in range(N):
  for b in range(N):
    for c in range(N):
      #print(gcd(a + 1, b + 1, c + 1))
      ans += gcd(a + 1, b + 1, c + 1)

print(ans)

### FIXED CODE ###

# coding: utf-8

import math
from functools import reduce

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

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

ans = 0

for a in range(N):
  for b in range(N):
    for c in range(N):
      #print(gcd(a + 1, b + 1, c + 1))
      ans += gcd(a + 1, b + 1, c + 1)

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

def resolve():
    S = list(input())
    rem = [0 for _ in range(2019)]
    v = 0
    rem[0] += 1
    n_p = 0
    for i in range(len(S)-1, -1, -1):
        v = (10**n_p)*int(S[i]) + v
        v %= 2019
        rem[v] += 1
        n_p += 1
    ans = 0
    for r in rem:
        ans += r*(r-1)//2
    print(ans)
        



if '__main__' == __name__:
    resolve()


### FIXED CODE ###

def resolve():
    S = list(input())
    rem = [0 for _ in range(2019)]
    v = 0
    rem[0] += 1
    p = 1
    for i in range(len(S)-1, -1, -1):
        v = p*int(S[i]) + v
        v %= 2019
        rem[v] += 1
        p = (p*10)%2019

    ans = 0
    for r in rem:
        ans += r*(r-1)//2
    print(ans)
        



if '__main__' == __name__:
    resolve()