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

#D
S=input()
Q=int(input())
t=1 # 1:正順,0:逆順
for _ in range(Q):
    q=input()
    if q[0]=='1':
        t=(t+1)%2
    else:
        __,f,c=q.split()
        if f=='1':
            if t==1:
                S=c+S
            else:
                S=S+c
        else:
            if t==1:
                S=S+c
            else:
                S=c+S
    # print(S)
print(S if t else S[::-1])

### FIXED CODE ###

#D
S=input()
Q=int(input())
t=1 # 1:正順,0:逆順
fro=''
bac=''
for _ in range(Q):
    q=input()
    if q[0]=='1':
        t=(t+1)%2
    else:
        __,f,c=q.split()
        if f=='1':
            if t==1:
                fro=c+fro
            else:
                bac=bac+c
        else:
            if t==1:
                bac=bac+c
            else:
                fro=c+fro
    # print(S)
ans=fro+S+bac
print(ans if t else ans[::-1])
### BUGGY CODE ###

n = int(input())
A = [int(x) for x in input().split()]

found = {}
for i, a in enumerate(A):
    if a in found:
        dup = a
        dup_1 = found[a]
        dup_2 = i
    found[a] = i

from functools import lru_cache

def gfp_inv(x, p):
    return pow(x, p - 2, p)

@lru_cache()
def fact(n, m, p):
    ret = 1
    for i in range(m, n + 1):
        ret = (ret * i) % p
    return ret

def comb(n, m):
    if m < 0 or n < m: return 0
    if n == m: return 1
    return fact(n, n - m + 1, p) * gfp_inv(fact(m, 1, p), p) % p

p = 10**9 + 7

intv = dup_2 - dup_1 - 1
for k in range(1, n + 2):
    ans = comb(n + 1, k)
    ans -= comb(n + 1 - intv - 2, k - 1)
    print(ans % p)

### FIXED CODE ###

n = int(input())
A = [int(x) for x in input().split()]

p = 10**9 + 7

found = {}
for i, a in enumerate(A):
    if a in found:
        dup = a
        dup_1 = found[a]
        dup_2 = i
    found[a] = i

from functools import lru_cache

@lru_cache(maxsize=None)
def gfp_inv(x, p):
    return pow(x, p - 2, p)

from itertools import chain, accumulate
memo_fact = list(chain([1], accumulate(range(1, 10**5 + 2), lambda a, x: a * x % p)))

def comb(n, m):
    if m < 0 or n < m: return 0
    if n == m: return 1
    return memo_fact[n] * gfp_inv(memo_fact[n - m], p) * gfp_inv(memo_fact[m], p) % p

intv = dup_2 - dup_1 - 1
for k in range(1, n + 2):
    ans = comb(n + 1, k)
    ans -= comb(n + 1 - intv - 2, k - 1)
    print(ans % p)
### BUGGY CODE ###

import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())))
Q = int(input())
BC= [list(map(int,input().split())) for _ in range(Q)]

ans = []

for b,c in BC:
    A[A == b] = c
    ans.append(np.sum(A))

print(*ans, sep='\n')



### FIXED CODE ###

import numpy as np

from collections import defaultdict
N = int(input())
A = tuple(map(int, input().split()))
Q = int(input())
BC= [list(map(int,input().split())) for _ in range(Q)]

counter = defaultdict(int)
for x in A:
    counter[x] += 1

total = sum(A)
for b, c in BC:
    total += (c - b) * counter[b]
    counter[c] += counter[b]
    counter[b] = 0
    print(total)
### BUGGY CODE ###


import sys
input = sys.stdin.readline
#区間の管理は　[a, b)で管理していることに注意

# INT_MIN = -10 ** 18
# MAX_N = 4 * 10 ** 5
# MAX_N = 20


# def init(n_):
#     #簡単にするために2のべき乗に揃える
#     n = 1
#     while n <= n_:
#         n *= 2
#     return n

#初期化
N = int(input())
# n = 1
# while n <= N:
#     n *= 2

n = 262144
data = [0] * (2 * n - 1)

def update(k, a):
    k = k + n - 1
    # data[k] = a
    while k >= 0:
        data[k] = max(a, data[k])
        k = (k - 1) // 2
        # data[k] = max(data[2 * k + 1], data[2 * k + 2])

def query(a, b, k = 0, l = 0, r = n):
    if r <= a or b <= l:
        return 0
    elif a <= l and r <= b:
        return data[k]
    else:
        return max(query(a, b, 2 * k + 1, l, (l + r)//2), query(a, b, 2 * k + 2, (l + r)//2, r))

H = tuple(map(int, input().split()))
A = tuple(map(int, input().split()))

# ans = 0

dp = [A[0]] + [0] * (N - 1)
update(H[0] - 1, A[0])
for i in range(1, N):
    # h = int(input())
    # a = int(input())
    dp[i] = query(0, H[i] - 1) + A[i]
    # h = H[i]
    # a = A[i]
    # tmp = query(1, h + 1) #[1, h)での最大値
    # print (h, tmp)
    update(H[i] - 1, dp[i])
    # ans = max(ans, tmp + a)
    # print (data)

print (max(dp))

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    #区間の管理は　[a, b)で管理していることに注意

    # INT_MIN = -10 ** 18
    # MAX_N = 4 * 10 ** 5
    # MAX_N = 20


    # def init(n_):
    #     #簡単にするために2のべき乗に揃える
    #     n = 1
    #     while n <= n_:
    #         n *= 2
    #     return n

    #初期化
    N = int(input())
    # n = 1
    # while n <= N:
    #     n *= 2

    n = 262144
    data = [0] * (2 * n - 1)

    def update(k, a):
        k = k + n - 1
        # data[k] = a
        while k >= 0:
            data[k] = max(a, data[k])
            k = (k - 1) // 2
            # data[k] = max(data[2 * k + 1], data[2 * k + 2])

    def query(a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        elif a <= l and r <= b:
            return data[k]
        else:
            return max(query(a, b, 2 * k + 1, l, (l + r)//2), query(a, b, 2 * k + 2, (l + r)//2, r))

    H = tuple(map(int, input().split()))
    A = tuple(map(int, input().split()))

    # ans = 0

    dp = [A[0]] + [0] * (N - 1)
    update(H[0] - 1, A[0])
    for i in range(1, N):
        # h = int(input())
        # a = int(input())
        dp[i] = query(0, H[i] - 1, 0, 0, n) + A[i]
        # h = H[i]
        # a = A[i]
        # tmp = query(1, h + 1) #[1, h)での最大値
        # print (h, tmp)
        update(H[i] - 1, dp[i])
        # ans = max(ans, tmp + a)
        # print (data)

    print (query(0, N, 0, 0, n))

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

from collections import defaultdict
import sys

input = sys.stdin.readline

def main():
    N = int(input())
    raw_number = list(map(int, input().split()))
    numbers = defaultdict(int)

    for num in raw_number:
        numbers[num] += 1

    Q = int(input())

    for _ in range(Q):
        a, b = list(map(int, input().split()))
        numbers[b] += numbers[a]
        numbers.pop(a)
        print(sum([v*k for (k, v) in numbers.items()]))
    
main()

### FIXED CODE ###

class Counter(dict):
    def __missing__(self, i):
        return 0

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

total = sum(a)

bucket = Counter()

for item in a:
    bucket[item] += 1

for i in range(q):
    b, c = map(int, input().split())
    taken = bucket[b]
    total -= bucket[b]*b
    bucket[c] += bucket[b]
    bucket[b] = 0
    total += taken*c
    print(total)
### BUGGY CODE ###

from collections import deque

N=int(input())
deg=[0 for v in range(N+1)];deg[0]=None
out=[set() for v in range(N+1)];deg[0]=None
for e in range(1,N):
    a,b=map(int,input().split())
    out[a].add((b,e));out[b].add((a,e))
for v in range(N+1):
    deg[v]=len(out[v])
# print(out) #DB
# print(deg) #DB

K=max(deg[1:])
# print(K) #DB

vcol=[set() for v in range(N+1)];vcol[0]=None # 頂点vから出る辺に含まれる色
ecol=[0 for e in range(N)];ecol[0]=None # 辺eの色
#r=[False for v in range(N+1)];r[0]=None # その頂点にたどり着いたか→vcolで代用

q=deque()
q.append(1)
while q:
    u=q.popleft() # 今いる頂点
    for vs in out[u]: # 今いる頂点の隣にある頂点と，その頂点に行くための辺の番号
        #if not vcol[vs[0]]: # その頂点にまだ辿り着いていなければ（書き換え後）→更に条件を変える
        #if not r[vs[0]]: # その頂点にまだ辿り着いていなければ
        for col in range(1,K+1): # 各色を順に選び
            if col not in vcol[u]: # その色が，今いる頂点から生える辺にまだ使われていなければ
                ecol[vs[1]]=col # その辺をその色で塗り
                vcol[u].add(col) # 今いる頂点から生える辺の色の集合に加え
                vcol[vs[0]].add(col) # 進んだ先の頂点から生える辺の色の集合に加える。
                break
        out[vs[0]].remove((u,vs[1])) # 辺を壊して戻れないようにする    
        # r[vs[0]]=True # その頂点にたどり着いたこととし（削る）
        q.append(vs[0]) # その頂点をキューに加える。
    

# print(vcol) #DB
# print(ecol) #DB

print(K)
for ecoli in ecol[1:]:
    print(ecoli)

### FIXED CODE ###

# アイデア：（これまでどおり）BFS。
# まず頂点に色を塗り，次に，その頂点から出る辺に色を塗ってゆく。
# 頂点に塗られた色及び「その頂点から出る何本目の辺か」によって，その辺に塗る色を決定する。
# 頂点に入ってくるときには，その際に取った辺の色を頂点に塗る。

from collections import deque

N=int(input())
d={} # 辺の両端の頂点→辺の番号を辿れるようにしておく
out=[set() for v in range(N+1)];out[0]=None # 隣接リスト，頂点の番号も問題文どおり1-initial,1~N
for i in range(1,N): # 問題文どおり辺の番号は1-initial,1~N-1
    u,v=map(int,input().split())
    out[u].add(v);out[v].add(u)
    u,v=min(u,v),max(u,v);d[(u,v)]=i
K=max([len(out[v]) for v in range(1,N+1)])
    
vcol=[0 for v in range(N+1)];vcol[0]=None
ecol=[0 for e in range(N)];ecol[0]=None

vr=[False for v in range(N+1)];vr[0]=None

q=deque()
q.append(1);vr[1]=True
vcol[1]=1 # 頂点1を色1で塗る
while q:
    u=q.popleft() # 今いる頂点    
    i=1 # その頂点から塗り始める何本目の辺か(1-initial),1<=i<=K
    for v in out[u]:
        if not vr[v]:
            col=(vcol[u]+i-1)%K+1
            vcol[v]=ecol[d[(min(u,v),max(u,v))]]=col
            vr[v]=True
            q.append(v)
            i+=1

print(K)
for i in range(1,N):
    print(ecol[i])
### BUGGY CODE ###

s = input()
n = len(s)

a = [0]*2019
count = 0
val = 10
for i in range(n):
    tmp = int(s[n-i-1:n]) % 2019
    count = count + a[tmp]
    a[tmp] = a[tmp] + 1
    if(tmp == 0):
        count = count + 1
    val = val * 10

print(count)

### FIXED CODE ###

s = input()[::-1]
n = len(s)

a = [0]*2019
a[0] = 1
count = 0
val = 1
current = 0
for c in s:
    current = (current + val * int(c)) % 2019
    count += a[current%2019]
    a[current%2019] += 1
    val = val * 10 % 2019

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

a = input().split()
n = int(a[0])
m = int(a[1])
qq = int(a[2])
ll = list()
r = list()

for _ in range(m):
    a = input().split()
    ll.append(int(a[0]))
    r.append(int(a[1]))

p = list()
q = list()

for _ in range(qq):
    a = input().split()
    p.append(int(a[0]))
    q.append(int(a[1]))

x = [[0 for _ in range(n)] for _ in range(n)]

for i in range(m):
    x[ll[i] - 1][r[i] - 1] += 1

c = [[0 for _ in range(n)] for _ in range(n)]

for i in range(n):
    for j in range(n):
        c[i][j] = x[i][j]
        if 0 < j:
            c[i][j] += c[i][j - 1]

for i in range(qq):
    r = 0

    for j in range(p[i] - 1, q[i]):
        r += c[j][q[i] - 1]
        if 1 < p[i]:
            r -= c[j][p[i] - 2]

    print(r)


### FIXED CODE ###

a = input().split()
n = int(a[0])
m = int(a[1])
qq = int(a[2])

x = [[0] * n for _ in range(n)]

for _ in range(m):
    a = input().split()
    x[int(a[0]) - 1][int(a[1]) - 1] += 1

c = list()

for i in range(n):
    c.append(list())
    for j in range(n):
        a = x[i][j]

        if 0 < j:
            a += c[i][j - 1]

        c[i].append(a)

z = list()

for i in range(n):
    z.append(list())
    for j in range(n):
        a = c[i][j]

        if 0 < i:
            a += z[i - 1][j]

        z[i].append(a)

for _ in range(qq):
    r = 0
    a = input().split()
    p = int(a[0])
    q = int(a[1])

    if 0 < q:
        r += z[q - 1][q - 1]

    if 0 < q and 1 < p:
        r -= z[q - 1][p - 2] + z[p - 2][q - 1]

    if 1 < p:
        r += z[p - 2][p - 2]

    print(r)
### BUGGY CODE ###

#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 2019
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

S = input()
N = len(S)
# lS = list(map(int, list(S)))
# print(lS)

d = defaultdict(int)
d[0] += 1
cnt = 0
nums = [0]*(N+1)
for i in range(N):
    m = 10**(N-i-1)
    val = int(S[i]) * m
    val %= MOD
    nums[i+1] = (val + nums[i])%MOD
    cnt += d[nums[i+1]]
    d[nums[i+1]] += 1
# nums.append(0)
# nums.reverse()
# print(nums)

# for i in range(N):
#     nums[i+1] += nums[i]
#     nums[i+1] %= MOD
#     # print(nums[i+1])
#     # print(d[nums[i+1]])
#     d[nums[i+1]] += 1
# # print(nums)
print(cnt)

### FIXED CODE ###

#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 2019
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

S = input()
N = len(S)

d = defaultdict(int)
d[0] += 1
# nums = [0]*(N+1)
m = 0
last = 0
dd = 1
for i in range(N):
    m += int(S[N-i-1])*dd
    m %= MOD
    # val = (int(S[i])*m + nums[i])%MOD
    # cnt += d[val]
    dd = (dd*10)%MOD
    d[m] += 1

cnt = 0
for i, v in d.items():
    cnt += v*(v-1)//2
print(cnt)
### BUGGY CODE ###

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

class UnionFind(object):
    def __init__(self, N):
        self.parent = [i for i in range(N)]

    def root(self, A):
        if self.parent[A] == A:
            return A
        self.parent[A] = self.root(self.parent[A]) #経路縮約
        return self.parent[A]

    def connect(self, A, B):
        A = self.root(A)
        B = self.root(B)
        self.parent[A] = B
        
uni1 = UnionFind(N)
for _ in range(K):
    p, q = map(int, input().split())
    if uni1.root(p-1) != uni1.root(q-1):
        uni1.connect(p-1,q-1)

uni2 = UnionFind(N)
for _ in range(L):
    r, s = map(int, input().split())
    if uni2.root(r-1) != uni2.root(s-1):
        uni2.connect(r-1,s-1)

# print (uni1.parent)
# print (uni2.parent)

ans = dict()
key_list = []
for i in range(N): #各都市を検索
    root1 = uni1.root(i) #都市の親を探す
    root2 = uni2.root(i)
    key = str(root1) + '_' + str(root2) #2つの親を連結したものをkeyとする
    key_list.append(key) #リストにkeyを足しておく(=i番目の都市が属するグループとして前からメモ)
    if key in ans.keys(): #dict andに親の組を記録していく
        ans[key] += 1
    else:
        ans[key] = 1
    
for i in range(N):
    print (ans[key_list[i]], end = ' ') #i番目の都市の親の組はkeyで読み出せる
print ()


### FIXED CODE ###

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

class UnionFind(object):
    def __init__(self, N):
        self.parent = [i for i in range(N)]

    def root(self, A):
        if self.parent[A] == A:
            return A
        self.parent[A] = self.root(self.parent[A]) #経路縮約
        return self.parent[A]

    def connect(self, A, B):
        A = self.root(A)
        B = self.root(B)
        self.parent[A] = B
        
uni1 = UnionFind(N)
for _ in range(K):
    p, q = map(int, input().split())
    if uni1.root(p-1) != uni1.root(q-1):
        uni1.connect(p-1,q-1)

uni2 = UnionFind(N)
for _ in range(L):
    r, s = map(int, input().split())
    if uni2.root(r-1) != uni2.root(s-1):
        uni2.connect(r-1,s-1)

# print (uni1.parent)
# print (uni2.parent)

ans = dict()
key_list = []
for i in range(N):
    root1 = uni1.root(i)
    root2 = uni2.root(i)
    key = str(root1) + '_' + str(root2)
    key_list += [key]
    if key in ans.keys():
        ans[key] += 1
    else:
        ans[key] = 1
    
for i in range(N):
    print (ans[key_list[i]], end = ' ')
print ()






# for i in range(1, N+1):
#     ans = 0
#     for j in range(1, N+1):
#         # print (uni1.root(i), uni1.root(j), uni2.root(i), uni2.root(j))
#         if uni1.root(i) == uni1.root(j) and uni2.root(i) == uni2.root(j):
#             ans += 1
#     print (ans, end = ' ')
print ()

# print (uni1.parent)
# print (uni2.parent)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n, m = [int(item) for item in input().split()]
if m % 2 != 0:
    print(-1)
    exit()
vset = set()
edge = [[] for _ in range(n)]
for i in range(m):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)
 
ans = []
def dfs(prev, n):
    if prev < n:
        key = str(prev) + "_" + str(n)
        if key in vset:
            return 0 
        else:
            vset.add(key)
    else:
        key = str(n) + "_" + str(prev)
        if key in vset:
            return 0 
        else:
            vset.add(key)
    child_num = 0
    for v in edge[n]:
        if prev == v:
            continue
        if dfs(n, v) == 1:
            child_num += 1
            ans.append([n+1, v+1])
    if child_num % 2 == 0:
        return 1
    else:
        ans.append([n+1, prev+1])
        return 0
 
dfs(-1, max(0, n - 2))
print("\n".join([str(f) + " " + str(t) for f, t in ans]))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, m = [int(item) for item in input().split()]
if m % 2 != 0:
    print(-1)
    exit()
visited_e = [False] * m
visited_v = [False] * n
edge = [[] for _ in range(n)]
for i in range(m):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    edge[a].append([b, i])
    edge[b].append([a, i])
 
ans = []
def dfs(prev, n):
    if visited_v[n]:
        return 1
    visited_v[n] = True
    child_num = 0
    for v, index in edge[n]:
        if visited_e[index]:
            continue
        visited_e[index] = True
        if dfs(n, v) == 1:
            child_num += 1
            ans.append([n+1, v+1])
    if child_num % 2 == 0:
        return 1
    else:
        ans.append([n+1, prev+1])
        return 0
 
dfs(-1, 0)
print("\n".join([str(f) + " " + str(t) for f, t in ans]))
### BUGGY CODE ###

H, W = map(int, input().split())
MAP = [list('#' for i in range(W + 2)) for j in range(H + 2)]
for i in range(H):
    line = list(input())
    for j, dot in enumerate(line):
        MAP[i + 1][j + 1] = dot
L = [[0 for j in range(W + 2)] for i in range(H + 2)]


def line(MAP):
    for i in range(1, H + 2):
        before = 0
        for j in range(1, W + 2):
            if MAP[i][j] == '#':
                for x in range(before + 1, j):
                    L[i][x] = j - before - 1
                before = j


def column(MAP2):
    for j in range(1, W + 2):
        before = 0
        for i in range(1, H + 2):
            if MAP2[i][j] == '#':
                for y in range(before + 1, i):
                    global ans
                    ans = max(ans, i - before - 1 + L[y][j])
                before = i


line(MAP)
ans = 0
column(MAP)
print(ans - 1)

### FIXED CODE ###

def main ():
    H, W = map(int, input().split())
    MAP = [list('#' for i in range(W + 2)) for j in range(H + 2)]
    for i in range(H):
        line = list(input())
        for j, dot in enumerate(line):
            MAP[i + 1][j + 1] = dot
    L = [[0 for j in range(W + 2)] for i in range(H + 2)]


    def line(MAP):
        for i in range(1, H + 2):
            before = 0
            for j in range(1, W + 2):
                if MAP[i][j] == '#':
                    for x in range(before + 1, j):
                        L[i][x] = j - before - 1
                    before = j


    def column(MAP2):
        ans = 0
        for j in range(1, W + 2):
            before = 0
            for i in range(1, H + 2):
                if MAP2[i][j] == '#':
                    for y in range(before + 1, i):
                        ans = max(ans, i - before - 1 + L[y][j])
                    before = i
        return ans - 1

    line(MAP)
    column(MAP)
    print(column(MAP))

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

#import time

nk = [int(x) for x in input().strip().split()]
d = []
for i in range(nk[0]):
    d_tmp = input().strip().split()
    d.append([int(d_tmp[0]), int(d_tmp[1]), int(d_tmp[2] == 'B')])

n1 = nk[0]
k1 = nk[1]

check_x = [0] * n1 * 4
check_y = [0] * n1 * 4
for i in range(n1):
    check_x[i * 4 + 1] = d[i][0] - k1 + 1
    check_x[i * 4 + 2] = d[i][0]
    check_y[i * 4 + 1] = d[i][1] - k1 + 1
    check_y[i * 4 + 2] = d[i][1]
check_x = list(set(check_x))
check_y = list(set(check_y))

#d = tuple(d)
n = 0
#t = time.clock()
#for i in range(k1):
#    for j in range(k1):
for i in check_x:
    for j in check_y:
        n_tmp = [0, 0]
        for k in range(n1):
            x = (d[k][0] - i) // k1 % 2
            y = (d[k][1] - j) // k1 % 2
#            if x == y:
#                n_tmp[1 - d[k][2]] += 1
#            else:
#                n_tmp[d[k][2]] += 1
            n_tmp[(x == y) ^ d[k][2]] += 1
        if n_tmp[0] > n:
            n = n_tmp[0]
        if n_tmp[1] > n:
            n = n_tmp[1]
#print(time.clock() - t)
print(n)


### FIXED CODE ###

import numpy as np

def getBoundary(p, k, k2):
    if p - k + 1 >= 0:
        return [(p - k + 1, p + 1)]
    else:
        return [(0, p + 1), ((p - k + 1) % k2, k2)]

n, k = map(int, input().strip().split())
k2 = k * 2
b = [[0 for i in range(k2 + 1)] for j in range(k2 + 1)]

for i in range(n):
    x_str, y_str, c_str = input().strip().split()
    x = int(x_str) % k2
    y = (int(y_str) + (c_str == 'B') * k) % k2
    for xb, xe in getBoundary(x % k2, k, k2):
        for yb, ye in getBoundary(y % k2, k, k2):
            b[xb][yb] += 1
            b[xb][ye] -= 1
            b[xe][yb] -= 1
            b[xe][ye] += 1
    for xb, xe in getBoundary((x + k) % k2, k, k2):
        for yb, ye in getBoundary((y + k) % k2, k, k2):
            b[xb][yb] += 1
            b[xb][ye] -= 1
            b[xe][yb] -= 1
            b[xe][ye] += 1

arr_b = np.array(b)
for i in range(k2):
    arr_b[i + 1] += arr_b[i]
for j in range(k2):
    arr_b[:, j + 1] += arr_b[:, j]
print(arr_b.max())
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))

ans = 0
for i in range(60):
    t = 2**i
    B = [A[j]&t for j in range(N)]
    c = B.count(0)
    ans += c*(N-c)*(t%MOD)%MOD

print(ans%MOD)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
B = [0]*60
C = [0]*60

for i in range(60):
    for j in range(N):
        if (A[j]>>i)&1 == 0:
            C[i] += 1
        else:
            B[i] += 1

ans = 0
for i in range(60):
    ans += B[i]*C[i]*2**i%MOD
print(ans%MOD)
### BUGGY CODE ###

N, K = map(int,input().split())
A = list(map(int,input().split()))
S = 1
for i in range(K):
    S *= A[i]
for i in range(N-K):
    s = S / A[i] * A[i+K]
    if  S < s:
        print("Yes")
    else:
        print("No")
    S = s



### FIXED CODE ###

N, K = map(int,input().split())
A = list(map(int,input().split()))
for i in range(N-K):
    if  A[i] < A[i+K]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
cnt = n//2
ans=abs(sum(a[:cnt]) - sum(a[cnt:]))
for i in range(1,cnt):
    if ans > abs(sum(a[:cnt+i]) - sum(a[cnt+i:])):
        ans = abs(sum(a[:cnt+i]) - sum(a[cnt+i:]))
for i in range(1,cnt):
    if ans > abs(sum(a[:cnt-i]) - sum(a[cnt-i:])):
        ans = abs(sum(a[:cnt-i]) - sum(a[cnt-i:]))
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=10**100
x=sum(a)
b=0
for i in a[:-1]:
   b+=i
   x-=i
   ans=min(ans,abs(x-b))
print(ans)
### BUGGY CODE ###

from collections import deque

n = int(input())
result = deque()
func = {'insert':result.appendleft,\
        'delete':result.remove,\
        'deleteFirst':result.popleft,\
        'deleteLast':result.pop}

for i in range(n):
    c = input().split()
    if len(c) > 1:
        try:
            func[c[0]](int(c[1]))
        except:
            continue
    else:
        func[c[0]]()

print(*result)


### FIXED CODE ###

from collections import deque
import sys

n = int(input())
result = deque()
func = {'insert':result.appendleft,\
        'delete':result.remove,\
        'deleteFirst':result.popleft,\
        'deleteLast':result.pop}

for line in sys.stdin.readlines():
    c = line.split()
    if len(c) > 1:
        try:
            func[c[0]](int(c[1]))
        except:
            continue
    else:
        func[c[0]]()

print(*result)
### BUGGY CODE ###

S = input()

moji = ''
cnt = 0

lst = [0] * 2020
lst[0] = 1

for s in S[::-1]:
    moji = s + moji
    r = int(moji) % 2019
    cnt += lst[r]
    lst[r] += 1

print(cnt)


### FIXED CODE ###

S = input()

num = 0

r_lst = [0] * 2019
r_lst[0] = 1
cnt = 0
for i, s in enumerate(S[::-1]):
    num = (num + pow(10, i, 2019) * int(s)) % 2019
    cnt += r_lst[num]

    r_lst[num] += 1


print(cnt)