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

import numpy as np
from itertools import combinations

N = int(input())

P = [np.array(list(map(int,input().split())), dtype=float) for _ in range(N)]

d2 = lambda v: np.sum(np.square(v))

def radius(A,B,C):
    a = d2(B-C)
    b = d2(C-A)
    c = d2(A-B)

    r = float('inf')
    if c > 4*d2((A+B)/2 - C):
        r = min(r, c)

    if a > 4*d2((B+C)/2 - A):
        r = min(r, a)

    if b > 4*d2((C+A)/2 - B):
        r = min(r, b)

    if r != float('inf'):
        return np.sqrt(r)/2

    U = a*(b+c-a)*A + b*(c+a-b)*B + c*(a+b-c)*C
    v = a*(b+c-a) + b*(c+a-b) + c*(a+b-c)
    U /= v
    r = np.linalg.norm(U-A)
    return r

if N == 2:
    print(np.linalg.norm(P[0]-P[1])/2)
else:
    print(max(radius(a,b,c) for a,b,c in combinations(P,3)))


### FIXED CODE ###

import numpy as np
from itertools import combinations

N = int(input())

P = [np.array(list(map(int,input().split())), dtype=float) for _ in range(N)]

d2 = lambda v: np.sum(np.square(v))

def radius(A,B,C):
    a = d2(B-C)
    b = d2(C-A)
    c = d2(A-B)

    r = float('inf')
    if c > d2(A+B - 2*C):
        r = min(r, c)

    if a > d2(B+C - 2*A):
        r = min(r, a)

    if b > d2(C+A - 2*B):
        r = min(r, b)

    if r != float('inf'):
        return np.sqrt(r)/2

    U = a*(b+c-a)*A + b*(c+a-b)*B + c*(a+b-c)*C
    v = a*(b+c-a) + b*(c+a-b) + c*(a+b-c)
    U /= v
    r = np.linalg.norm(U-A)
    return r

if N == 2:
    print(np.linalg.norm(P[0]-P[1])/2)
else:
    print(max(radius(a,b,c) for a,b,c in combinations(P,3)))
### BUGGY CODE ###

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

for i in range(n):
  j = i + 1
  b = a.count(j)
  print(b)


### FIXED CODE ###

import numpy as np

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

b = np.zeros(shape=(n), dtype=np.int)

for i in a:
  b[i-1] += 1

for i in range(n):
  print(b[i])
### BUGGY CODE ###

import sys
import numpy as np


def main():
    x, y, z, k = [int(n) for n in input().split()]
    a = sorted([int(n) for n in input().split()], reverse=True)
    b = sorted([int(n) for n in input().split()], reverse=True)
    c = sorted([int(n) for n in input().split()], reverse=True)
    result = [a[ai] + b[bi] + c[ci]
              for ai in range(x) for bi in range(y) for ci in range(z)
              if (ai + 1) * (bi + 1) * (ci + 1) <= k]
    print(*(sorted(result, reverse=True))[:k], sep="\n")


main()


### FIXED CODE ###

import sys


def main():
    x, y, z, k = [int(n) for n in input().split()]
    va = sorted([int(n) for n in input().split()], reverse=True)
    vb = sorted([int(n) for n in input().split()], reverse=True)
    xy = min(x*y, k)
    vab = (sorted([a + b for a in va for b in vb], reverse=True))[:xy]
    vc = sorted([int(n) for n in input().split()], reverse=True)
    xyz = min(x*y*z, k)
    print(*((sorted([ab + c for ab in vab for c in vc], reverse=True))[:xyz]), sep="\n")


main()
### BUGGY CODE ###

import sys

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

    t = 0
    while True:
        for i in range(N):
            if A[i] % 2 == 0:
                A[i] = A[i]/2
            else:
                print(t)
                sys.exit
        t += 1

main()

### FIXED CODE ###

import sys

def main():
    N = int(input())
    A = [int(_) for _ in input().split()]

    t = 0
    while True:
        for i in range(N):
            if A[i] % 2 == 0:
                A[i] //= 2
            else:
                print(t)
                sys.exit()
        t += 1

main()
### BUGGY CODE ###

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

if M % N == 0:    print(M//N)
else:
    for i in range(N,M//2+1):
        if M % i == 0:
            print(M//i)
            break
    else:
        print(1)


### FIXED CODE ###

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

if M % N == 0:    print(M//N)
elif M//N > 100000:
    for i in range(N,M//2+1):
        if M % i == 0:
            print(M//i)
            break
    else:
        print(1)
else:
    m = M//N
    for i in range(2,m)[::-1]:
        if M % i == 0:
            print(i)
            break
    else:
        print(1)
### BUGGY CODE ###

def string_formation():
    s = str(input().strip())
    q = int(input())
    for _ in range(q):
        line = input().strip().split()
        op = int(line[0])
        if op == 1:
            s = ''.join(reversed(s))
        elif op == 2:
            pos = int(line[1])
            if pos == 2:
                s += line[2]
            elif pos == 1:
                s = line[2] + s
    return s

print(string_formation())

### FIXED CODE ###

S = input()
Q = int(input())
flip = 0
head = []
tail = []
for i in range(Q):
  Query = input().split()
  if len(Query) == 3:
    T,F,C = Query
    F = int(F)-1
    if F^flip == 1:
      tail.append(C)
    else:
      head.append(C)
  else:
    flip ^= 1
if flip:
  head, tail = tail, head
  S = S[::-1]
head = ''.join(head[::-1])
tail = ''.join(tail)
print(head+S+tail)
### BUGGY CODE ###

s = input()
mod = 10 ** 9 + 7

l = len(s)
s = [int(e) if e != "?" else -1 for e in s]
dp = [[0] * 13 for _ in range(l + 1)]
dp[0][0] = 1

for i in range(l):
	for k in range(10):
		if s[i] == -1 or s[i] == k:
			for j in range(13):
				nj = (j * 10 + k) % 13
				dp[i+1][nj] += dp[i][j]
				dp[i+1][nj] %= mod

ans = dp[l][5]
print(ans)


### FIXED CODE ###

s = input()
mod = 10 ** 9 + 7

l = len(s)
s = [int(e) if e != "?" else -1 for e in s]
dp = [[0] * 13 for _ in range(l + 1)]
dp[0][0] = 1

for i in range(l):
	for k in range(10):
		if s[i] == -1 or s[i] == k:
			for j in range(13):
				nj = (j * 10 + k) % 13
				dp[i+1][nj] += dp[i][j]
				dp[i+1][nj] %= mod

ans = dp[l][5]
print(ans)
### BUGGY CODE ###

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

dp = [float('inf')] * n
dp[0] = 0

for i in range(n):
    for j in range(k+1):
        num = i+j
        if num >= n: break
        else: 
            dp[num] = min(dp[num], dp[i]+abs(h[num]-h[i]))

print(dp[-1])


### FIXED CODE ###

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

dp = [float('inf')] * n
dp[0] = 0

for i in range(n):
    for j in range(k+1):
        num = i+j
        if num >= n: break
        else: 
            dp[num] = min(dp[num], dp[i]+abs(h[num]-h[i]))

print(dp[-1])
### BUGGY CODE ###


def main():
    N = int(input())

    A = [tuple(map(int, input().split())) for _ in range(N)]

    # check = [[True] + [False] * (N - 2) for _ in range(N)] #True準備完了、False試合不可
    check = [0] * N #i番目の次の相手のindex

    ans = 0
    i = 0
    tmp = 0
    count = 0
    while tmp < 2 * N + 2:
        if i % N == 0:
            ans += 1
            flag  = [True] * N #試合をしたかどうかチェック
            i = 0
            
        if check[i] >= N - 1 or flag[i] == False:
            i += 1
            tmp += 1
            continue
        b = A[i][check[i]] - 1
        # print (b)
        if A[b][check[b]] - 1 == i and flag[b]: #試合できる時
            check[i] += 1
            check[b] += 1
            flag[i] = False
            flag[b] = False
            tmp = 0
            count += 1
            if count == (N * (N - 1))//2:
                print (ans)
                exit()
        i += 1
        tmp += 1
    print (-1)
    return 
            
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque

N = int(input())
A = [list(reversed(list(map(lambda x: int(x) - 1, input().split())))) for _ in range(N)]
B = {i: row for i, row in enumerate(A)}

# print (A)
# print (B)

end = 0

for k in range(8000):
    used = set()
    dels = []
    for i, q in B.items():
        if not q:
            continue
        if i in used:
            continue
        j = q[-1]
        if j in used:
            continue
        if A[j][-1] == i:
            A[j].pop()
            A[i].pop()
            used.add(i)
            used.add(j)
            if not A[i]:
                end += 1
                dels.append(i)
            if not A[j]:
                end += 1
                dels.append(j)
    if not used:
        print (-1)
        exit()
    
    if end == N:
        print (k + 1)
        exit()
    
    for i in dels:
        del B[i]
        
print (N * (N - 1) // 2)
### BUGGY CODE ###

A,B,C,D = map(int,input().split())
cnt = 0
for num in range(A,B+1):
    if num%C != 0 and num%D != 0:
        cnt += 1
print(cnt)

### FIXED CODE ###

import fractions

a, b, c, d = map(int, input().split())

lcm = c*d // fractions.gcd(c,d)


b_num = b - (b//c + b//d - b//lcm)
a_num = a-1 - (a-1)// c - (a-1)//d + (a-1) // lcm

ans = b_num - a_num
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
city = []
for i in range(N):
    x,y = map(int,input().split())
    city.append([x,y,i])
side = []
city.sort(key=lambda x:x[0])
for i in range(N-1):
    side.append([city[i+1][0] - city[i][0],city[i][2] ,city[i+1][2]])

city.sort(key=lambda x:x[1])
for i in range(N-1):
    side.append([city[i+1][1] - city[i][1],city[i][2] ,city[i+1][2]])
side.sort()
node = [[i,[i]]for i in range(N)]
ans = 0
for cost,a,b in side:
    if node[a][0] != node[b][0]:
        ans += cost
        c,d = node[node[a][0]],node[node[b][0]]
        if len(c[1]) < len(d[1]):
            for i in c[1]:
                node[i][0] = d[0]
            d[1] = d[1] + c[1]
        else:
            for i in d[1]:
                node[i][0] = c[0]
            c[1] = d[1] + c[1]
print(ans)
            





### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
cityx = [[0,i]for i in range(N)]
cityy = [[0,i]for i in range(N)]
for i in range(N):
    x,y = map(int,input().split())
    cityx[i][0] = x
    cityy[i][0] = y

cityx.sort()
cityy.sort()
side = []
for i in range(N-1):
    side.append([cityx[i+1][0]-cityx[i][0], cityx[i+1][1], cityx[i][1]])
    side.append([cityy[i+1][0]-cityy[i][0], cityy[i+1][1], cityy[i][1]])
side.sort()
ans = 0
per = [i for i in range(N)]
rank = [0]*N
def find(x):
    if per[x] == x:
        return x
    else:
        per[x] = find(per[x])
        return per[x]

ans = 0

for cost,x,y in side:
    x = find(x)
    y = find(y)
    if x != y:
        ans += cost
        if rank[x] < rank[y]:
            per[x] = y
        else:
            per[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

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

N = int(input())
g = {}
for i in range(1,N+1):
    g[i] = []
def dfs(g,start,end):
    stack = [(start, [start],0)]
    while stack:
        (v, path, length) = stack.pop()
        for next,l in g[v]:
            if next in path: continue
            if next == end:
                return length + l
            else:
                stack.append((next, path + [next], length + l))

for i in range(N-1):
    a, b, c = map(int,input().split())
    g[a].append((b,c))
    g[b].append((a,c))
Q, K = map(int,input().split())

for q in range(Q):
    x, y = map(int,input().split())
    print(dfs(g,x,K) + dfs(g,K,y))

### FIXED CODE ###

N = int(input())
g = {i: [] for i in range(1, N+1)}    

l = [0] * (N + 1)

for i in range(N-1):
    a, b, c = map(int,input().split())
    g[a].append((b,c))
    g[b].append((a,c))

Q, K = map(int,input().split())

stack = [K]

while len(stack):
    v = stack.pop()
    for c,ln in g[v]:
        if l[c] != 0:
            continue
        l[c] = l[v] + ln
        stack.append(c)

for q in range(Q):
    x, y = map(int,input().split())
    print(l[x] + l[y])
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
def maxHeapify(A, i):
    l = i * 2 + 1
    r = i * 2 + 2
    if l < n:
        largest = l
        if r < n and A[r] > A[l]:
            largest = r
        if A[largest] > A[i]:
            A[i], A[largest] = A[largest], A[i]
            maxHeapify(A, largest)
def insert(S, k):
    global n
    S[n] = k
    n += 1
    i = n - 1
    p = (i - 1) // 2
    while i > 0 and S[i] > S[p]:
        S[i], S[p] = S[p], S[i]
        i = p
        p = (i - 1) // 2
def extractMax(S):
    global n
    if n == 1:
        n -= 1
        return S[0]
    ans = S[0]
    n -= 1
    S[0] = S[n]
    i = 0
    while True:
        l = i * 2 + 1
        r = i * 2 + 2
        if l >= n:
            break
        largest = l
        if r < n and A[r] > A[l]:
            largest = r
        if A[largest] > A[i]:
            A[i], A[largest] = A[largest], A[i]
            i = largest
        else:
            break
    return ans
A = [0] * 2000000
n = 0
for s in sys.stdin:
    if s[2] == "s":
        insert(A, int(s[7:]))
    elif s[2] == "t":
        print(extractMax(A))
    else:
        break



### FIXED CODE ###

import sys
from heapq import heapify, heappush, heappop
hq = []
S = []
for s in sys.stdin:
    if s[2] == "s":
        heappush(hq, -int(s[7:]))
    elif s[2] == "t":
        S.append(-heappop(hq))
    else:
        break
print("\n".join(map(str, S)))
### BUGGY CODE ###

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

flag = 0
while True:
    ab = abs(N - K)
    if N > ab:
        N = ab
    else:
        break

print(N)


### FIXED CODE ###

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

flag = 0
if K == 1:
    print(0)
    quit()
if K == 2:
    if N % 2:
        print(1)
        quit()
    else:
        print(0)
        quit()

i = N // K
N = N - K * i
while True:
    i = N // K
    ab = abs(N - K)
    if N > ab:
        N = ab
    else:
        break

print(N)
### BUGGY CODE ###

from operator import mul
from functools import reduce

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)

    mem_key = str(n) + '-' + str(r)
    if mem_key in mem:
        return mem[mem_key]

    val = fact[n] * factinv[r] * factinv[n-r] % p
    mem[mem_key] = val
    return val

MOD = 10 ** 9 + 7
N, K = map(int, input().split())
if K == 1:
    print(0)
    exit()

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

N = len(A)
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    factinv.append((factinv[-1] * inv[-1]) % MOD)

ans = 0
sum_num = 0
mem = {}
for i in range(N - (K - 1)):
    for j in range(i+K-1, N):
        ans += ((A[j] - A[i]) * cmb(j-i-1, K-2, MOD)) % MOD
print(ans % MOD)


### FIXED CODE ###

MOD = 10 ** 9 + 7

def ncr(n, r, mod=MOD):
    return (fct[n] * invf[r] * invf[n - r]) % mod


def make_tables(n, mod=MOD):
    fct = [1 for _ in range(n + 1)]
    invf = [1 for _ in range(n + 1)]

    for i in range(2, n + 1):
        fct[i] = (fct[i - 1] * i) % mod
        invf[i] = divmod(fct[i])
    return fct, invf


def divmod(a, mod=MOD):
    return pow(a, mod - 2, mod)


N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
for i in range(N):
    A[i] %= MOD

fct, invf = make_tables(N, mod=MOD)

ans = 0
for i in range(N - K + 1):
    ans += ((A[-1-i] - A[i]) % MOD * ncr(N - i - 1, K - 1)) % MOD
print(ans % MOD)
### BUGGY CODE ###

from queue import deque
H,W = map(int,input().split())
CH,CW = map(int,input().split())
DH,DW = map(int,input().split())
DH,DW = DH-1,DW-1
S=[]
for i in range(H):
    S.append(list(map(lambda x:0 if x=='.' else -1, input().strip())))

def walk(h,w,n):
    r = []
    q = deque([(h,w)])
    while q:
        x = q.pop()
        r.append(x)
        h,w = x
        if h == DH and w == DW:
            print(n-1)
            exit()
        if h > 0 and S[h-1][w] == 0:
            S[h-1][w] = n
            q.append((h-1,w))
        if h < H-1 and S[h+1][w] == 0:
            S[h+1][w] = n
            q.append((h+1,w))
        if w > 0 and S[h][w-1] == 0:
            S[h][w-1] = n
            q.append((h,w-1))
        if w < W-1 and S[h][w+1] == 0:
            S[h][w+1] = n
            q.append((h,w+1))
    return r

warp = 1
q = deque([(CH-1,CW-1)])
while len(q) > 0:
    n = []
    while len(q) > 0:
        h,w = q.pop()
        n+=walk(h,w,warp)
    warp += 1
    if len(n) == 0:
        break
    for h,w in n:
        for ah in range(max(0,h-2),min(H,h+3)):
            for aw in range(max(0,w-2),min(W,w+3)):
                if ah == DH and aw == DW:
                    print(warp-1)
                    exit()
                if S[ah][aw] == 0:
                    S[ah][aw] = warp
                    q.append((ah,aw))

print(-1)


### FIXED CODE ###

from queue import deque
H,W = map(int,input().split())
CH,CW = map(int,input().split())
DH,DW = map(int,input().split())
DH,DW = DH-1,DW-1
S=[]
for i in range(H):
    S.append(list(map(lambda x:0 if x=='.' else -1, input().strip())))

def walk(h,w,n):
    r = []
    q = deque([(h,w)])
    while q:
        x = q.pop()
        r.append(x)
        h,w = x
        if h == DH and w == DW:
            print(n-1)
            exit()
        if h > 0 and S[h-1][w] == 0:
            S[h-1][w] = n
            q.append((h-1,w))
        if h < H-1 and S[h+1][w] == 0:
            S[h+1][w] = n
            q.append((h+1,w))
        if w > 0 and S[h][w-1] == 0:
            S[h][w-1] = n
            q.append((h,w-1))
        if w < W-1 and S[h][w+1] == 0:
            S[h][w+1] = n
            q.append((h,w+1))
    return r

warp = 1
q = deque([(CH-1,CW-1)])
while len(q) > 0:
    n = []
    while len(q) > 0:
        h,w = q.pop()
        n+=walk(h,w,warp)
    warp += 1
    if len(n) == 0:
        break
    for h,w in n:
        for ah in range(max(0,h-2),min(H,h+3)):
            for aw in range(max(0,w-2),min(W,w+3)):
                if ah == DH and aw == DW:
                    print(warp-1)
                    exit()
                if S[ah][aw] == 0:
                    S[ah][aw] = warp
                    q.append((ah,aw))

print(-1)
### 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)]

for i in range(Q):
    b, c = bc[i]
    a[a == b] = c
    print(np.sum(a))

### FIXED CODE ###

from collections import Counter

N = int(input())
a = Counter(map(int, input().split()))
Q = int(input())

sum_a = sum(a.elements())

for i in range(Q):
    b, c = map(int, input().split())
    a[c] += a[b]
    sum_a += (c-b) * a[b]
    a[b] = 0
    print(sum_a)
### BUGGY CODE ###

# from operator import mul
# from functools import reduce

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

hyouten_count = N - K

result_list = []

for i in range(K-1, N):
    # num = reduce(mul, A[0:i])
    # print(num)
    result = 1
    for j in range(K):
        result = result * A[i - j]
    # print(result)
    result_list.append(result)


for n in range(1, len(result_list)):
    if result_list[n] > result_list[n-1]:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

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


for i in range(K, N): # 3, 5
    if A[i] > A[i-K]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import sys
import bisect
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
d = int(input())
graph = [0 for i in range(n+1)]
for i in range(n-1):
  x = bisect.bisect_right(a,a[i]+d)
  if x == i:
    continue
  graph[i+1] = x
group = [0]*(n+1)
row = [[]]
cnt = 0
stack = []
for i in range(1,n+1):
  if group[i] == 0:
    stack.append(i)
    cnt += 1
    row.append([])
    while stack:
      x = stack.pop()
      row[cnt].append(x)
      group[x] = cnt
      if x != n:
        stack.append(graph[x])
q = int(input())
for _ in range(q):
  l,r = map(int,input().split())
  if l>r:
    l,r = r,l
  x = group[l]
  yl = bisect.bisect_left(row[x],l)
  yr = bisect.bisect_left(row[x],r)
  print(yr-yl)

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
d = int(input())
graph = [[0 for i in range(n+1)] for j in range(18)]
for i in range(n):
  x = bisect.bisect_right(a,a[i]+d)
  graph[0][i+1] = x
for j in range(1,18):
  for i in range(n):
    t = graph[j-1][i+1]
    graph[j][i+1] = graph[j-1][t]
q = int(input())
for _ in range(q):
  x,y = map(int,input().split())
  x,y = min(x,y),max(x,y)
  ans = 0
  for j in range(18)[::-1]:
    if graph[j][x] < y:
      ans += 2**j
      x = graph[j][x]
    if j == 0 and x < y:
      ans += 1
  print(ans)
### BUGGY CODE ###

H,W = map(int,input().split())
S = []
for i in range(H):
    S += [['#'] + list(input()) + ['#']]
S = [['#' for i in range(W+2)]] + S + [['#' for i in range(W+2)]]

ans,v = 0,[0 for i in range(W)]
for i in range(1,W+1):
    k = 1
    while S[k][i] == '.':
        k += 1
    v[i-1] = k - 1

for i in range(1,H+1):
    dot = 1
    while S[i][dot] == '.':
            dot += 1
    dot -= 1
    for j in range(1,W+1):
        if S[i][j] == '#':
            k = j+1
            while S[i][k] == '.':
                k += 1
            dot = k - j - 1

            k = i+1
            while S[k][j] == '.':
                k += 1
            v[j-1] = k - i - 1 
        else:
            if ans < dot + v[j-1]:    ans = dot + v[j-1]
print(ans-1)    



### FIXED CODE ###

H,W = map(int,input().split())
height, width_max, ans = [0] * (W+1), [0] * (W+1), 0
for i in range(H):
    s = input() + '#'
    length = 0
    for j in range(W+1):
        if s[j] == '.':
            length += 1
            height[j] += 1
        else:
            if length > 0:
                for k in range(j-length, j):
                    if width_max[k] < length:
                        width_max[k] = length
                length = 0
            if height[j] > 0:
                temp = width_max[j] + height[j] - 1
                if ans < temp:
                    ans = temp
                width_max[j], height[j] = 0, 0
for j in range(W):
    if height[j] > 0:
        temp = width_max[j] + height[j] - 1
        if ans < temp:
            ans = temp
print(ans)
### BUGGY CODE ###

s = input()[::-1]
n = len(s)
amari = [0]*2019
amari[0] = 1

temp = 0
d = 1
for char in s:
    temp += int(char)*10*d
    amari[temp%2019] += 1
    d *= 10

ans = 0
for i in amari:
    ans += i*(i-1)/2

print(int(ans))

### FIXED CODE ###

s = input()[::-1]
n = len(s)
amari = [0]*2019
amari[0] = 1

temp = 0
d = 1
for char in s:
    temp += int(char)*d
    temp %= 2019
    d *= 10
    d %= 2019  
    amari[temp] += 1

ans = 0
for i in amari:
    ans += i*(i-1)/2

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

import collections
from operator import mul
from functools import reduce
n = int(input())
l = list(map(int, input().split()))
ans = 0
for i in range(n):
  ans = 0
  temp = l.copy()
  temp.pop(i)
  c = collections.Counter(temp)
  for j in c.most_common():
    if j[1] > 1:
      r = min(2, j[1] - 2)
      numer = reduce(mul, range(j[1], j[1] - r, -1), 1)
      denom = reduce(mul, range(1, r + 1), 1)
      ans += numer // denom
  print(ans)


### FIXED CODE ###

n = int(input())
b = list(map(int, input().split()))
l = [0]*n
for i in range(n):
  l[b[i]-1] += 1
l2 = sum([i*(i-1)//2 for i in l])
for i in b:
  print(l2-(l[i-1]-1))
### BUGGY CODE ###

import bisect

N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))
ans = sum(A)
for _ in range(M):
    b, c = map(int, input().split())
    index = bisect.bisect_left(A, c)
    index = min(index, b)
    for i in range(index):
        ans += c - A[i]
        A[i] = c
    if index > 0:
        A = sorted(A)

print(ans)



### FIXED CODE ###

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

bc = [list(map(int, input().split())) for _ in range(M)]

ans = sum(A)

bc = sorted(bc, key=lambda i: i[1], reverse=True)

i = 0
for b, c in bc:
    for _ in range(b):
        if A[i] > c:
            break
        ans += c - A[i]
        i += 1
        if i >= N:
            break
    else:
        continue
    break

print(ans)