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

#import sys
#print(sys.maxsize)
N,X,M=map(int,input().split())
#table=list(range(M))
#for i in range(M):
 #   table[i]=((table[i]%M)**2)%M
#print(table[471])
start=X%M
rireki=list()
rireki.append(start)
ss=0
for j in range(1,N):
    start=(start**2)%M
    if start in rireki:
        ss=rireki.index(start)
        break
    else:
        rireki.append(start)
nn=len(rireki)
rep=(N-ss)//(nn-ss)
nokori=N-ss-rep*(nn-ss)
loop=rireki[ss:]
#print(nn)
#print(rep)
#print(sum(loop))
#print(ss)
#print(nokori+rep*(nn-ss)+ss)
if 0 in rireki:
    goukei=sum(rireki)
else:
    goukei=rep*sum(loop)+sum(rireki[:ss])+sum(loop[:nokori])
print(goukei)

### FIXED CODE ###

#import sys
#print(sys.maxsize)
N,X,M=map(int,input().split())
#table=list(range(M))
#for i in range(M):
 #   table[i]=((table[i]%M)**2)%M
#print(table[471])
start=X%M
rset=set()
rireki=list()
rset.add(start)
rireki.append(start)
ss=0
for j in range(1,M+1):
    start=(start**2)%M
    if start in rset:
        ss=rireki.index(start)
        break
    else:
        rireki.append(start)
        rset.add(start)
nn=len(rireki)
rep=(N-ss)//(nn-ss)
nokori=N-ss-rep*(nn-ss)
loop=rireki[ss:]
#print(nn)
#print(rep)
#print(sum(loop))
#print(ss)
#print(nokori+rep*(nn-ss)+ss)
if 0 in rireki:
    goukei=sum(rireki)
else:
    goukei=rep*sum(loop)+sum(rireki[:ss])+sum(loop[:nokori])
print(goukei)
### BUGGY CODE ###

# coding=UTF-8
from collections import deque
from operator import itemgetter
from bisect import bisect_left, bisect
import itertools
import sys
import math
import numpy as np
import time
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


def ev(n):
    return 0.5*(n+1)


def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))

    ans = []
    for i in range(n - k + 1):
        ans.append(sum(map(ev, p[i: i + k])))
    print(max(ans))


if __name__ == '__main__':
    main()


### FIXED CODE ###

# coding=UTF-8
from collections import deque
from operator import itemgetter
from bisect import bisect_left, bisect
import itertools
import sys
import math
import numpy as np
import time
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


def ev(n):
    return 0.5*(n+1)


def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))

    p_ev = list(map(ev, p))

    s = np.cumsum(p_ev)
    s = np.insert(s, 0, 0)

    ans = []

    for i in range(n - k+1):
        ans.append(s[i + k] - s[i])

    print(max(ans))


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

n, m = map(int, input().split())
lrs = [ list(map(int, input().split())) for _ in range(m)]

cards = set([i for i in range(lrs[0][0], lrs[0][1]+1)])
for lr in lrs[1:]:
    tmp = set([i for i in range(lr[0], lr[1]+1)])
    cards.intersection_update(tmp)
    

print(len(cards))
        
    

### FIXED CODE ###

n, m = map(int, input().split())
lrs = [ list(map(int, input().split())) for _ in range(m)]

cards = [lrs[0][0], lrs[0][1]] # [min, max]

for lr in lrs[1:]:
    if (lr[1] < cards[0]) or (lr[0] > cards[1]):
        print(0)
        exit()

    cards[0] = max(cards[0], lr[0])
    cards[1] = min(cards[1], lr[1])
    

print(cards[1] - cards[0] + 1)
### BUGGY CODE ###

import fractions
import itertools
import collections

n = int(input().split()[0])
a_list = list(map(int, input().split()))

def koyakusu(x):
    i = 1
    koyaku_list = []
    while i * i <= x:
        if x % i == 0:
            koyaku_list.append(i)
            koyaku_list.append(x//i)
        i += 1

    koyaku_list = list(set(koyaku_list))
    return koyaku_list

# 最大公約数の最大値
gcd_list = []
all_koyaku_list_list = []
for a in a_list:
    koyaku_list = koyakusu(a)
    # print('{}: {}'.format(a, koyaku_list))
    all_koyaku_list_list.append(koyaku_list)

all_koyaku_list = list(itertools.chain.from_iterable(all_koyaku_list_list))
c = collections.Counter(all_koyaku_list)

kouho_list = [k for k, v in c.items() if v in [n, n-1]]
# print(kouho_list)
ans = max(kouho_list)

print(ans)


### FIXED CODE ###

import fractions
import itertools
import collections

n = int(input().split()[0])
a_list = list(map(int, input().split()))
sorted_list = sorted(a_list)
min_a, second_min_a = sorted_list[0], sorted_list[1]

def koyakusu(x):
    i = 1
    koyaku_list = []
    while i * i <= x:
        if x % i == 0:
            koyaku_list.append(i)
            koyaku_list.append(x//i)
        i += 1

    koyaku_list = list(set(koyaku_list))
    return koyaku_list

kouho_list = []
# print('{}: {}'.format(min_a, koyakusu(min_a)))
kouho_list += koyakusu(min_a)

# print('{}: {}'.format(second_min_a, koyakusu(second_min_a)))
kouho_list += koyakusu(second_min_a)
kouho_list = list(set(kouho_list))
# print(kouho_list)
ans_kouho_list = []

for kouho in kouho_list:
    x_list = [x for x in a_list if x % kouho == 0]
    # print('kouho {} ({})'.format(kouho, len(x_list)))
    if len(x_list) >= n-1:
        ans_kouho_list.append(kouho)
# print(ans_kouho_list)
ans = max(ans_kouho_list)

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

h, w = map(int, input().split())
map_list = []
for _ in range(h):
    map_list.append(list(input()))
x_list = [1, 0, -1, 0]
y_list = [0, 1, 0, -1]
ans = 0
q = []
for y in range(h):
    for x in range(w):
        if map_list[y][x] == "#":
            q.append([y, x])
black_num = len(q)
map_size = h * w
while (black_num < map_size):
    q_list = []
    for y, x in q:
        for i in range(4):
            new_y = y + y_list[i]
            new_x = x + x_list[i]
            if (new_y >= 0) & (new_y < h) & (new_x >= 0) & (new_x < w):
                if map_list[new_y][new_x] == ".":
                    map_list[new_y][new_x] = "#"
                    black_num += 1
                    q_list.append([new_y, new_x])
    q = q_list.copy()
    ans += 1
print(ans)

### FIXED CODE ###

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

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

moves = [(0,1),(0,-1),(1,0),(-1,0)] #全方向調べる

ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  
print(ans)
### BUGGY CODE ###

from numba import njit
import numpy as np

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

@njit
def main(A):
  count = np.zeros(10**6 + 10, np.int32)
  
  for i in range(N):
    a = A[i]
    #if count[a] > 1:
    #  continue
    count[::a] += 1
    
  ans = 0
  for i in range(N):
    ans += count[A[i]] == 1
    
  #print(count[:100])
  return ans
  
  
  
print(main(np.array(A, np.int32)))

### FIXED CODE ###

from numba import njit
import numpy as np

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

@njit
def main(A):
  count = np.zeros(10**6 + 10, np.int32)
  
  for i in range(N):
    a = A[i]
    if count[a] > 1:
      continue
    count[::a] += 1
    
  ans = 0
  for i in range(N):
    ans += count[A[i]] == 1
    
  #print(count[:100])
  return ans
  
print(main(np.array(A, np.int32)))
### BUGGY CODE ###

n,k=map(int,input().split())
s=[]
data=set(s)
for i in range(k):
    x,y=map(int,input().split())
    while(1):
        data.add(x)
        if(x>=y):
            break
        x+=1
        
dp=[0 for i in range(n+1)]
dp[1]=1
for i in range(1,n):
    for j in data:
        if(i+j<=n):
            dp[i+j]+=dp[i]
            dp[i+j]%=998244353
print(dp[n]%998244353)

### FIXED CODE ###

n,k=map(int,input().split())
dp=[0 for i in range(n+1)]
dp[1]=1
accum=[0 for i in range(n+1)]
accum[1]=1
s=[]
for i in range(k):
    x,y=map(int,input().split())
    s.append([x,y])
for i in range(2,n+1):
    for j in s:
        l,r=j
        tmpl=i-r
        tmpr=i-l
        if(tmpl<1):
            tmpl=1
        if(tmpr>=i):
            tmpr=i-1
        if(tmpr<0):
            continue
        dp[i]+=accum[tmpr]-accum[tmpl-1]
        dp[i]%=998244353
    accum[i]=dp[i]+accum[i-1]
    accum[i]%=998244353
print(dp[n]%998244353)
### BUGGY CODE ###

# スペース区切りの整数入力
h,n = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

#下から順に最小の積み上げを作る
bsum=[0]
for i in range(1,h+1):
    min_bsum = 9999999999999
    for atk in range(n):
        min_bsum = min(min_bsum,bsum[max(0,i-a[atk])]+b[atk])
    bsum.append(min_bsum)
 
#指定のHのコストを表示
print(bsum[h])

### FIXED CODE ###

# スペース区切りの整数入力
h,n = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

#下から順に最小の積み上げを作る
bsum=[0]
for i in range(1,h+1):
    min_bsum = 9999999999999
    for atk in range(n):
        if bsum[max(0,i-a[atk])]+b[atk] < min_bsum:
            min_bsum = bsum[max(0,i-a[atk])]+b[atk]
    bsum.append(min_bsum)

#指定のHのコストを表示
print(bsum[h])
### BUGGY CODE ###

import sys
n, m = map(int, input().split())
a = [int(sys.stdin.readline()) for _ in range(m)]
mod = 1000000007
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = dp[0] if not 1 in a else 0
for i in range(2, n + 1):
    if not i in a:
        dp[i] = (dp[i - 1] + dp[i - 2]) % mod
    else:
        dp[i]=  0
print(dp[n])


### FIXED CODE ###

n, m = map(int, input().split())
mod = 1000000007
a = [True] * (n + 1)
for i in range(m):
    a[int(input())] = False
dp = [0] * (n + 1)
dp[0] = 1

dp[1] = dp[0] if a[1] else 0

for i in range(2, n + 1):
    if a[i]:
        dp[i] = (dp[i - 1] + dp[i - 2]) % mod

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

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

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
S = []
s = 0
for i in range(N):
    s += A[i]
    S.append(s)
ans = 0
S.sort()
x = S[0]
j = 1
if x == 0:
    ans += 1
for i in range(1,N):
    y = S[i]
    if y == 0:
        ans += 1
    if x == y:
        ans += j
        j += 1
    else:
        x = y
        j = 1
print(ans)
### BUGGY CODE ###

from math import ceil, log2
class SegTree:
    ide_ele = 0
    def __init__(self, init_val):
        n = len(init_val)
        self.num = 2**ceil(log2(n))
        self.seg = [self.ide_ele] * (2 * self.num - 1)

    def segfunc(self, x, y):
        return max(x, y)

    def update(self, k, x):
        k += self.num - 1
        self.seg[k] = x
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

    def query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.ide_ele
        if a <= l and r <= b:
            return self.seg[k]
        else:
            vl = self.query(a, b, k*2+1, l, (l+r)//2)
            vr = self.query(a, b, k*2+2, (l+r)//2, r)
            return self.segfunc(vl, vr)


n, k = map(int, input().split())
a = [int(input()) for _ in range(n)]
M=300001
st = SegTree([0]*M)
res = 0
for i in a:
    min_a = max(i-k, 0)
    max_a = min(i+k, M)
    s = st.query(min_a, max_a+1, 0, 0, st.num)
    st.update(i, max(s, 0)+1)
    res = max(res, max(s, 0) + 1)

print(res)


### FIXED CODE ###

from math import ceil, log2
import sys
z=sys.stdin.readline


# SegTreeの関数
def segfunc(x, y):
    return max(x, y)


# 単位元
# min->inf, max->-inf, add->0, mul->1
ide_ele = -1


# セグメント木
class SegTree:

    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセットする
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


n, k = map(int, z().split())
a = [int(z()) for _ in range(n)]
M=300001
st = SegTree([0]*M, max, 0)
res = 0
for i in a:
    min_a = max(i-k, 0)
    max_a = min(i+k, M)
    s = st.query(min_a, max_a+1)
    st.update(i, max(s, 0)+1)
    res = max(res, max(s, 0) + 1)

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

s=input()
l=len(s)
mod=10**9+7
dp=[[0 for j in range(13)] for i in range(l+1)]
dp[0][0]=1
for i in range(1,l+1):
  if s[i-1]=='?':
    for j in range(10):
      for k in range(13):
        dp[i][(k*10+j)%13]+=dp[i-1][k]%mod
  else:
    for k in range(13):
      dp[i][(k*10+int(s[i-1]))%13]+=dp[i-1][k]%mod
print(dp[-1][5]%mod)

### FIXED CODE ###

s=input()
l=len(s)
mod=10**9+7
dp=[[0 for j in range(13)] for i in range(l+1)]
dp[0][0]=1
for i in range(1,l+1):
  if s[i-1]=='?':
    for j in range(10):
      for k in range(13):
        dp[i][(k*10+j)%13]+=dp[i-1][k]%mod
  else:
    for k in range(13):
      dp[i][(k*10+int(s[i-1]))%13]+=dp[i-1][k]%mod
print(dp[-1][5]%mod)
### BUGGY CODE ###

def divisor(n):
    ret = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ret.append(i)
            if i*i != n:
                ret.append(n//i)
    return ret

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

m = 10**6 + 1
c = [0]*m
for i in a:
    c[i] += 1

ans = 0
for i in a:
    if c[i] > 1:
        continue
    for j in divisor(i):
        if j == i:
            if c[j] > 1:
                break
        else:
            if c[j] > 0:
                break
    else:
        ans += 1
print(ans)

### FIXED CODE ###

from collections import Counter

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    c = Counter(a)
    used = set()
    m = 10**6 + 1
    cnt = [0]*m
    ans = 0
    for ai in a:
        if c[ai]>1:
            if ai not in used:
                used.add(ai)
                for i in range(ai, m, ai):
                    cnt[i] += 1
        else:
            if cnt[ai] == 0:
                ans += 1
                for i in range(ai, m, ai):
                    cnt[i] += 1
    print(ans)

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

n=int(input())
l=list(map(int, input().split()))
s=set(l)
d=dict()

for x in s:
    d[x] = l.count(x)

d2=dict()

for x in l:

    if x in d2.keys():
        print(d2[x])
    else:
        sum = 0
        for key in d.keys():
            a = d[key]
            if key == x:
                a -= 1

            sum += (a*(a - 1)) // 2

        print(sum)
        d2[x]=sum

### FIXED CODE ###

n=int(input())
l=list(map(int, input().split()))
s=set(l)
d=dict()

for x in l:
    d[x]=0
for x in l:
    d[x]+=1


sum = 0
for key in d.keys():
    a = d[key]
    sum += (a*(a - 1)) // 2


for x in l:
    print(sum - d[x] +1)
### BUGGY CODE ###

H,W,M=map(int,input().split())
L=[]
bh=[0]*(H+1)
bw=[0]*(W+1)
mh,mw=[0,[]],[0,[]]
for _ in range(M):
    h,w=map(int,input().split())
    L.append((h,w))
    bh[h]+=1
    bw[w]+=1
    if bh[h]>mh[0]:
        mh=[bh[h],[h]]
    elif bh[h]==mh[0]:
        mh[1].append(h)
    if bw[w]>mw[0]:
        mw=[bw[w],[w]]
    elif bw[w]==mw[0]:
        mw[1].append(w)
ans=mh[0]+mw[0]
n=0
for h,w in L:
    if h in mh[1] and w in mw[1]:
        n+=1
if n==len(mh[1])*len(mw[1]):
    ans-=1
print(ans)

### FIXED CODE ###

H,W,M=map(int,input().split())
L=[]
bh=[0]*(H+1)
bw=[0]*(W+1)
for _ in range(M):
    h,w=map(int,input().split())
    L.append((h,w))
    bh[h]+=1
    bw[w]+=1
p,q=max(bh),max(bw)
num=len(list(filter(p.__eq__, bh)))*len(list(filter(q.__eq__,bw)))
num-=len(list(filter(lambda x: bh[x[0]]==p and bw[x[1]]==q, L)))
ans=p+q-1
if num>0:
    ans+=1
print(ans)
### BUGGY CODE ###

N, M = [int(s) for s in input().split(' ')]
As = [int(s) for s in input().split(' ')]
As.sort()
for m in range(M):
    B, C = [int(s) for s in input().split(' ')]
    for b in range(B):
        As[b] = max(As[b], C)
    As.sort()
print(sum(As))



### FIXED CODE ###

N, M = [int(s) for s in input().split(' ')]
As = [int(s) for s in input().split(' ')]
CBs = []
for m in range(M):
    B, C = [int(s) for s in input().split(' ')]
    CBs.append((C, B))
As.sort(reverse=True)
CBs.sort(reverse=True)
CBs.append((0, 0))
ret = 0
a = 0
bc = 0
n = 0
while n < N:
    C, B = CBs[bc]
    if As[a] < C:
        bc += 1
        pick = min(N - n, B)
        ret += pick * C
        n += pick
    else:
        ret += As[a]
        a += 1
        n += 1
print(ret)
### BUGGY CODE ###

X = int(input())

now = 0
cnt = 0
while now < X:
  cnt += 1
  now = int(now*1.01)
print(cnt)

### FIXED CODE ###

X = int(input())
 
now = 100
cnt = 0
while now < X:
  cnt += 1
  now += int(now*0.01)
print(cnt)
### BUGGY CODE ###

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

if n % k == 0:
  print(0)
else: 
  ans = n
  while ans > abs(n-k):
    n = abs(n - k)
    ans = min(n, ans)
  print(ans)

### FIXED CODE ###

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

if n % k == 0:
  print(0)
else: 
  ans = n % k
  #print(ans)
  while ans > k//2:
    n = abs(ans - k)
    ans = min(n, ans)
  print(ans)
### BUGGY CODE ###

N=int(input())
sum=1
i=list(map(int,input().split()))
for cnt in range(N):
  sum=sum*i[cnt]
if sum>1000000000000000000:
	sum=-1
print(sum)

### FIXED CODE ###

N=int(input())
sum=1
i=list(map(int,input().split()))
if 0 in i:
  sum=0
else:
	for cnt in range(N):
		sum=sum*i[cnt]
		if sum>1000000000000000000:
			sum=-1
			break
print(sum)
### BUGGY CODE ###

N = int(input())
a = [int(i) for i in input().split()]

s = set(a)
rem = 0
for i in s:
    c = a.count(i)
    if i<c:
        rem += c-i
    elif i>c:
        rem += c

print(rem)

### FIXED CODE ###

from collections import Counter

N = int(input())
a = [int(i) for i in input().split()]

C = Counter(a)
ans = 0

for i in C:
    if C[i] > i:
        ans += C[i]-i
    elif C[i] < i:
        ans += C[i]

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


N = int(input())
S = []

ans = 0

for i in range(N):
    S.append(input())

for i in range(N):
    s_i = S[i]

    for j in range(i+1, N):
        s_j = S[j]

        if sorted(s_i) == sorted(s_j):
            ans += 1


print(ans)

### FIXED CODE ###


def combain(X, Y):
    return int(( X * (X - 1)) / Y)

N = int(input())
S = []

ans = 0

for i in range(N):
    S.append(sorted(input()))

S.sort()

ans = 0

X = 1
for i in range(N-1):
    if S[i] == S[i+1]:
        X += 1
    elif X > 1:
        C = combain(X, 2)
        X = 1
        ans += C

if X > 1:
    C = combain(X, 2)
    X = 1
    ans += C
    
print(ans)
### BUGGY CODE ###


def resolve():
    S = input()
    sub = "BW"
    cnt = 0
    st = S.find("B")
    S = S[st:]
    while True:
        res = S.find(sub)
        if res == -1:
            break
        cnt += 1
        S = S[:res] + "WB" + S[res+2:]
    print(cnt)


if __name__ == "__main__":
    resolve()

### FIXED CODE ###


def resolve():
    S = input()
    sub = "BW"
    cnt = 0
    sum = 0

    # 左端からのWと右端からのBは無関係のため除外
    st = 0
    end = 0
    for i, s in enumerate(S):
        if s == "B":
            break
        else:
            st += 1

    for i, s in enumerate(S[::-1]):
        #print(s)
        if s == "W":
            break
        else:
            end += 1

    #print(st, end)
    S = S[st:len(S)-end]
    #print(S)

    foundB = False
    for i, s in enumerate(S):
        if s == "B":
            cnt += 1
            foundB = True
        elif s == "W":
            sum += cnt
            foundB = False
        
        #print(s, cnt, sum)

    print(sum)


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

import heapq
def solve():
  n = int(input())
  a = list(int(i) for i in input().split())
  an = []
  a2n = a[n:2*n]
  a3n = []
  for i in range(n):
    heapq.heappush(an,a[i])
    heapq.heappush(a3n,-1*a[i+2*n])
  ta2n = a2n
  suman = [sum(an)]
  suma3n = [-1*sum(a3n)]
  for i in range(n):
    tmp = ta2n[i]
    heapq.heappush(an,tmp)
    heapq.heappop(an)
    suman.append(sum(an))
  for i in range(n):
    tmp = ta2n[n-i-1]
    heapq.heappush(a3n,-1*tmp)
    heapq.heappop(a3n)
    suma3n.append(-1 * sum(a3n))

  ans = -10000000000000000
  for i in range(n+1):
    tmpans = suman[i]-suma3n[n-i]
    ans = max(ans,tmpans)
  print(ans)
solve()

### FIXED CODE ###

import heapq
def solve():
  n = int(input())
  a = list(int(i) for i in input().split())
  an = []
  a2n = a[n:2*n]
  a3n = []
  for i in range(n):
    heapq.heappush(an,a[i])
    heapq.heappush(a3n,-1*a[i+2*n])
  ta2n = a2n
  
  tmpsuman = sum(an)
  tmpsuma3n = -1*sum(a3n)
  
  suman = [tmpsuman]
  suma3n = [tmpsuma3n]
  
  for i in range(n):
    tmp = ta2n[i]
    tmpsuman += tmp
    heapq.heappush(an,tmp)
    tmpsuman -= heapq.heappop(an)
    
    suman.append(tmpsuman)
  for i in range(n):
    tmp = ta2n[n-i-1]
    tmpsuma3n += tmp
    heapq.heappush(a3n,-1*tmp)
    tmpsuma3n -= -1*heapq.heappop(a3n)
    suma3n.append(tmpsuma3n)

  ans = -10000000000000000
  for i in range(n+1):
    tmpans = suman[i]-suma3n[n-i]
    ans = max(ans,tmpans)
  print(ans)
solve()
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

S = input()
cnt = 0
for i in range(len(S)-3):
	for j in range(i+3, len(S)+1):
		if int(S[i:j])%2019 == 0:
			cnt += 1

print(cnt)

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

S = input()
n = len(S)
s = [0]
for i, x in enumerate(S):
	s.append(int(S[i])*pow(10, n-i-1, 2019)%2019)

tmp = 0
t = []
for x in s:
	tmp = (tmp+x)%2019
	t.append(tmp)

ans = 0
for v in Counter(t).values():
	ans += v*(v-1)//2
print(ans)