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

import sys
readline = sys.stdin.readline
def main():
	limit = 10 ** 5
	n = int(input())
	a = []
	for _ in range(n):
		a.append(tuple(map(int,input().split())))
	a = tuple(a)

	play = [0 for _ in range(n)]
	flag = [True for _ in range(n)]
	count = 0
	ans = 0
	while True:
		break_flag = True
		for i in range(n):
			if flag[i]:
				num = a[i][play[i]]-1
				if flag[num] and a[num][play[num]]-1 == i:
					play[num] += 1
					play[i] += 1
					flag[num] = False
					flag[i] = False
					break_flag = False
					count += 1
		if break_flag:
			print(-1)
			sys.exit()
		ans += 1

		if count == n*(n-1)//2:
			break
		if ans > limit:
			print(-1)
			sys.exit()
		for i in range(n):
			if play[i] < n-1:
				flag[i] = True
			else:
				flag[i] = False

	if ans == 0:
		print(-1)
	else:
		print(ans)
if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys
readline = sys.stdin.readline
def main():
	limit = 10 ** 4
	n = int(input())
	a = []
	for _ in range(n):
		a.append(tuple(map(int,input().split())))
	a = tuple(a)

	play = [0 for _ in range(n)]
	flag = [True for _ in range(n)]
	count = 0
	ans = 0
	while True:
		break_flag = True
		for i in range(n):
			if flag[i]:
				num = a[i][play[i]]-1
				if flag[num] and a[num][play[num]]-1 == i:
					play[num] += 1
					play[i] += 1
					flag[num] = False
					flag[i] = False
					break_flag = False
					count += 1
		if break_flag:
			print(-1)
			sys.exit()
		ans += 1

		if count == n*(n-1)//2:
			break
		if ans > limit:
			print(n*(n-1)//2)
			sys.exit()
		for i in range(n):
			if play[i] < n-1:
				flag[i] = True
			else:
				flag[i] = False

	if ans == 0:
		print(-1)
	else:
		print(ans)
if __name__ == '__main__':
	main()
### BUGGY CODE ###

import numpy as np
INF = 10 ** 18
H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
dp = [INF for i in range(H + 1)]
dp = np.array(dp)
ab = np.array(ab)
dp[0] = 0

for i in range(N):
    for j in range(H):
        if j - ab[i][0] + 1 >= 0:
            dp[j + 1] = min(dp[j + 1], dp[j - ab[i][0] + 1] + ab[i][1])
        else:
            dp[j + 1] = min(dp[j + 1], dp[0] + ab[i][1])

print(dp[-1])

### FIXED CODE ###

INF = 10 ** 18
H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
dp = [INF for i in range(H + 1)]

dp[0] = 0

for i in range(N):
    for j in range(H):
        if j - ab[i][0] + 1 >= 0:
            dp[j + 1] = min(dp[j + 1], dp[j - ab[i][0] + 1] + ab[i][1])
        else:
            dp[j + 1] = min(dp[j + 1], dp[0] + ab[i][1])

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

import math
N = int(input())
for i in range(1,N+1):
    print(sum(1 for x in range(1,int(math.sqrt(i))) for y in range(1,int(math.sqrt(i))) for z in range(1,int(math.sqrt(i))) if x*x+y*y+z*z+x*y+y*z+z*x==i))

### FIXED CODE ###

a=[0]*int(input())
r=range(1,99)
for x in r:
    for y in r:
        for z in r:
            n=x*(x+y+z)+y*(y+z)+z*z-1
            if n<len(a):
                a[n]+=1
print(*a)
### BUGGY CODE ###

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


for a in A:
    if A.count(a)>1:
        print('NO')
        break
else :
    print('YES')

### FIXED CODE ###

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

if len(A)==len(set(A)):
        print('YES')
else :
    print('NO')
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
j = set(L)
ans = 0
for i in j:
    if L.count(i) >= i:
        ans += (L.count(i) - i)
    else:
        ans += L.count(i)
print(ans)

### FIXED CODE ###

import collections
input()
c = collections.Counter(list(map(int,input().split())))
ans = 0
for i,j in c.items():
        if j >= i:
            ans += j - i
        else:
            ans += j
print(ans)
### BUGGY CODE ###

def main():
    import collections
    import sys
    sys.setrecursionlimit(10**5)
    N = int(input())
    a = list(map(int, input().split()))
    A = [0]*4
    for x in a:
        A[x] += 1

    dp = [[[-1]*(N+1) for i in range(N+1)] for j in range(N+1)]
    # for i in range(1, L+1):
    dp[0][0][0] = 0

    def solve(c1, c2, c3):
        if dp[c1][c2][c3] >= 0:
            return(dp[c1][c2][c3])
        else:
            P = 1
            if c1 > 0:
                P += solve(c1-1, c2, c3) * (c1/N)
            if c2 > 0:
                P += solve(c1+1, c2-1, c3)*(c2/N)
            if c3 > 0:
                P += solve(c1, c2+1, c3-1)*(c3/N)
            P /= (1 - (N-c1-c2-c3)/N)
            dp[c1][c2][c3] = P

            return(P)

    print(solve(A[1], A[2], A[3]))


main()


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    a = A.count(1)
    b = A.count(2)
    c = A.count(3)
    floatN = N*1.0
    dp = [[[.0]*(N+1) for i in range(N+1)] for j in range(N+1)]

    for k in range(c+1):
        for j in range(b+c + 1 - k):
            for i in range(N + 1 - k - j):
                if i + j+k == 0:
                    continue
                dp[i][j][k] = floatN
                if i > 0:
                    dp[i][j][k] += dp[i-1][j][k] * i
                if j > 0:
                    dp[i][j][k] += dp[i+1][j-1][k] * j
                if k > 0:
                    dp[i][j][k] += dp[i][j+1][k-1] * k
                dp[i][j][k] /= (i+j+k)
    print(dp[a][b][c])


main()
### BUGGY CODE ###

import numpy as np
import sys

def frog2(h, K):
    c = np.full_like(h, 0)
    c[0] = 0
    c[1] = abs(h[0] - h[1])
    for i in range(2, len(c)):
        c[i] = min(c[i-k] + abs(h[i-k] - h[i]) for k in range(1, min(i+1, K+1)))
    return c[-1]


N, K = map(int, input().split())
h = np.array(list(map(int, input().split())))
print(frog2(h, K))

### FIXED CODE ###

import sys
import numpy as np
def frog2(h, K):
    c = np.full_like(h, 0)
    c[0] = 0
    c[1] = abs(h[0] - h[1])
    for i in range(2, len(c)):
        k = min(i, K)
        c[i] = np.min(c[i-k:i] + abs(h[i-k:i] - h[i]))
        # c[i] = min(c[i-k] + abs(h[i-k] - h[i]) for k in range(1, min(i+1, K+1)))
    return c[-1]


N, K = map(int, input().split())
h = np.array(list(map(int, input().split())))

print(frog2(h, K))
### BUGGY CODE ###

n, p = map(int, input().rstrip().split())
s = input().rstrip()

if p == 2 or p == 5:
    ans = 0
    for i in range(n):
        c = int(s[i])
        if c % p == 0:
            ans += i + 1
    print(ans)
else:
    cnt = [0] * p
    k = 0
    cnt[k] = 1
    for i in range(n):
        k = (int(s[-i - 1]) * (10**i) + k) % p
        cnt[k] += 1

    ans = 0
    for i in range(p):
        ans += cnt[i] * (cnt[i] - 1) // 2
    print(ans)


### FIXED CODE ###

n, p = map(int, input().rstrip().split())
s = input().rstrip()

if p == 2 or p == 5:
    ans = 0
    s = map(int, s)
    for i, c in enumerate(s):
        if c % p == 0:
            ans += i + 1
    print(ans)
else:
    s = s[::-1]
    cnt = [0] * p
    k = 0
    cnt[k] = 1
    w = 1
    for i, c in enumerate(map(int, s)):
        k = c * w + k
        w *= 10
        while k >= p:
            k -= p
        while w >= p:
            w -= p
        cnt[k] += 1

    ans = 0
    for i in range(p):
        ans += cnt[i] * (cnt[i] - 1) // 2
    print(ans)
### BUGGY CODE ###

n=int(input())
def luca(n):
  if n == 0:
    return 2
  if n == 1:
    return 1
  return luca(n-1) + luca(n-2)
print(luca(n))

### FIXED CODE ###

n=int(input())
def fibonacci(n):
    fib = [2, 1]
    for i in range(2, n):
        fib.append(fib[i - 2] + fib[i - 1])
        
    return fib[n -1]
print(fibonacci(n+1))
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import heapq

def main():
    H, W, M = map(int, readline().split())
    m = map(int,read().split())
    hw = list(zip(m,m))

    bR = [0] * (H+1)
    bC = [0] * (W+1)

    maxes = []
    heapq.heapify([])

    for (h, w) in hw:
        bR[h] += 1
        bC[w] += 1

    rmax = max(bR)
    cmax = max(bC)
    rmis = [i for i in range(H+1) if bR[i] == rmax]
    cmis = [i for i in range(W+1) if bC[i] == cmax]

    ans = rmax + cmax
    minus_flag = True
    for r in rmis:
        for c in cmis:
            if (r, c) not in hw:
                minus_flag = False
                break
    if minus_flag:
        ans -= 1

    
    # print(hw)
    # print(bR, bC)
    # print(rmax, cmax, rmis, cmis)
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import heapq

def main():
    H, W, M = map(int, readline().split())
    m = map(int,read().split())
    hw = list(zip(m,m))

    row_bombers = [0] * (H+1)
    col_bombers = [0] * (W+1)

    for (h, w) in hw:
        row_bombers[h] += 1
        col_bombers[w] += 1

    row_max = max(row_bombers)
    col_max = max(col_bombers)

    max_rows = [i for i in range(H+1) if row_bombers[i] == row_max]
    max_cols = [i for i in range(W+1) if col_bombers[i] == col_max]

    ans = row_max + col_max
    
    num_empty_cells_in_kouho = len(max_rows) * len(max_cols)
    for (h, w) in hw:
        if row_bombers[h] == row_max and col_bombers[w] == col_max:
            num_empty_cells_in_kouho -= 1

    if num_empty_cells_in_kouho == 0:
        ans -= 1
    
    print(ans)


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

import numpy as np

N_K = list(map(int, input().split()))
 
count = 0

a = np.array([i for i in range(1, N_K[0]+1)])
b = np.array([i for i in range(1, N_K[0]+1)])

for i in range(len(b)):
    count += sum(a % b[i] >= N_K[1])

    
'''
for a in range(1, N_K[0]+1):
  for b in range(1, N_K[0]+1):
    if a % b >= N_K[1]:
      count += 1
'''

print(count)

### FIXED CODE ###

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

for b in range(1, N+1):
	p = N // b
	r = N % b
	
	ans += p * max(0, b-K)
	ans += max(0, r-K+1)
	
print(ans-N*(not K))
### BUGGY CODE ###

import math

k = int(input())
cnt = 0

for l in range(1,k+1):
    for m in range(1,k+1):
        for n in range(1,k+1):
            tmp = math.gcd(l,m)
            if tmp == 1:
                cnt += 1
            else:
                cnt += math.gcd(tmp,n)
            
print(cnt)


### FIXED CODE ###

#C

import math

k = int(input())
cnt = 0

for i in range(1,k+1):
    for j in range(i,k+1):
        tmp = math.gcd(i,j)
        for l in range(1,k+1):
            if i != j:
                cnt += 2 * math.gcd(tmp,l)
            else:
                cnt += math.gcd(tmp,l)
            
print(cnt)
### BUGGY CODE ###

def factorization(n):
    lst, temp = [], n
    for i in range(2, int(n**0.5//1+1)):
        if temp %i ==0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            lst.append([i, cnt])
    if temp != 1:
        lst.append([temp, 1])
    return lst

mod = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))

soinsu = {}
factrized_a = []
for i in range(n):
    lst = factorization(a[i])
    factrized_a.append(lst)
    for sosu, josu in lst:
        try:
            before_josu = soinsu[sosu]
        except KeyError:
            before_josu = 0
        soinsu[sosu] = max(before_josu, josu)

ans = 0
for i in range(n):
    lst = factrized_a[i]
    copied_soinsu = soinsu.copy()
    for sosu, josu in lst:
        copied_soinsu[sosu] -= josu
    bi = 1
    for sosu, josu in copied_soinsu.items():
        bi = bi * (sosu**josu) % mod
    ans = (ans + bi) % mod

print(ans)

### FIXED CODE ###

import fractions
from functools import reduce

mod = 10**9 + 7

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

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

n = int(input())
a = list(map(int, input().split()))
a_ = []
for i in range(n):
    a_.append(pow(a[i], mod - 2, mod))

num_lcm = lcm(*a) % mod
ans = 0
for i in range(n):
    ans = (ans + num_lcm * a_[i] % mod) % mod

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

import sys
input = sys.stdin.readline

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

dp = [[0] * (N+1) for i in range(N+1)]
if (N - 1) % 2 == 0:
    fl = 1
else:
    fl = -1
for i in range(N):
    dp[i][i+1] = fl * A[i]


def func():
    for s in range(2, N+1):
        for l in range(N-s+1):
            r = l + s
            if (N - s) % 2 == 0:
                dp[l][r] = max(dp[l+1][r]+A[l], dp[l][r-1]+A[r-1])
            else:
                dp[l][r] = min(dp[l+1][r]-A[l], dp[l][r-1]-A[r-1])
    
func()
print(dp[0][N])

### FIXED CODE ###

import sys
input = sys.stdin.readline

def func():
    N = int(input())
    A = [int(i) for i in input().split()]

    dp = [[0] * (N+1) for i in range(N+1)]
    if (N - 1) % 2 == 0:
        fl = 1
    else:
        fl = -1
    for i in range(N):
        dp[i][i+1] = fl * A[i]

    for s in range(2, N+1):
        for l in range(N-s+1):
            r = l + s
            if (N - s) % 2 == 0:
                dp[l][r] = max(dp[l+1][r]+A[l], dp[l][r-1]+A[r-1])
                continue
            dp[l][r] = min(dp[l+1][r]-A[l], dp[l][r-1]-A[r-1])
                
    return dp[0][N]

print(func())
### BUGGY CODE ###

def main():
    N,K = map( int, input().split())
    P = list(input().split())
    expected = []
    for i,p in enumerate(P):
        ex = float(1/float(p))*float(float(p)*(float(p)+1)/2)
        expected.append(ex)
    
    max_ex = 0
    for i in range(N-K+1):
        sum_ex = sum(expected[i:i+K])
        if sum_ex>max_ex:
            max_ex = sum_ex

    print(max_ex)
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D
# CreatedDate:  2020-07-29 16:20:16 +0900
# LastModified: 2020-07-29 16:30:22 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd
from itertools import accumulate


def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    s = [(x+1)/2 for x in p]
#    print(s)
    s = list(accumulate(s))
    s.insert(0, 0)
    ans = 0
#    print(s)
    for i in range(n-k+1):
        ans = max(ans, s[i+k]-s[i])
    print(ans)



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

#2
n = int(input())
number = 0
for i in range(n+1) :
    if i**2 <= n :
        number = i**2
print(number)

### FIXED CODE ###

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

from itertools import combinations
n = int(input())
l = [int(i) for i in input().split()]
cnt = 0
h = []
for i in set(combinations(l, 3)):
  a, b, c = i
  if a < (b + c) and b < (c + a) and c < (a + b):
    cnt += 1
print(cnt)

### FIXED CODE ###

from collections import Counter
N = int(input())
L = Counter(int(i) for i in input().split())
maxL = max(L)
key = sorted(L.keys())
val = [L[i] for i in range(1, max(L) + 1)]
acc = [0] * (len(val) + 1)
for i in range(len(val)):
    acc[i + 1] = acc[i] + val[i]
cnt = 0
for a in key:
    cnt += L[a] * (L[a] - 1) * (L[a] - 2) // 6
    cnt += max(acc[min(2 * a - 1, maxL)] - acc[a], 0) * L[a] * (L[a] - 1) // 2
for i in range(len(key) - 1):
    for j in range(i + 1, len(key)):
        a, b = key[i], key[j]
        cnt += L[a] * L[b] * (L[b] - 1) // 2
for i in range(len(key) - 2):
    for j in range(i + 1, len(key) - 1):
        a, b = key[i], key[j]
        cnt += max(acc[min(a + b - 1, maxL)] - acc[b], 0) * L[a] * L[b]
print(cnt)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()

dp = [[0 for column in range(n)] for row in range(n)]
for i in range(n):
    dp[i][0] = 0
    for j in range(i + 1, n):
        if s[j-1] == 'A' and s[j] == 'C':
            dp[i][j] = dp[i][j-1] + 1
        else:
            dp[i][j] = dp[i][j-1]

for _ in range(q):
    i, j =  map(int, input().split())
    print(dp[i-1][j-1])

### FIXED CODE ###

n, q = map(int, input().split())
s = input()

dp = [0 for column in range(n)]

for j in range(1, n):
    if s[j-1] == 'A' and s[j] == 'C':
        dp[j] = dp[j-1] + 1
    else:
        dp[j] = dp[j-1]

for _ in range(q):
    i, j =  map(int, input().split())
    print(dp[j-1] - dp[i-1])
### BUGGY CODE ###

S = input()
Q = int(input())

n = S
# r = S
# for i in range(Q):
#     op = input().split()
#     if len(op) == 1:
#         n, r = r, n
#     elif op[1] == "1":
#         n = op[2] + n
#         r = r + op[2]
#     else:
#         n = n + op[2]
#         r = op[2] + r
# print(n)

mode = 0
operations = []
for i in range(Q):
    operations.append(input().split())
for op in operations:
    if len(op) == 1:
        mode += 1
        mode %= 2
    elif int(op[1]) + mode == 2:
        n = n + op[2]
    else:
        n = op[2] + n
if mode == 0:
    print(n)
else:
    print(n[::-1])

### FIXED CODE ###

from collections import deque
S = input()
Q = int(input())

n = S
mode = 0
operations = []
deq = deque(n)
for i in range(Q):
    operations.append(input().split())
for op in operations:
    if op[0] == "1":
        mode += 1
        mode %= 2
    elif int(op[1]) + mode == 2:
        deq.append(op[2])
    else:
        deq.appendleft(op[2])
if mode == 0:
    print("".join(deq))
else:
    print("".join(reversed(deq)))
### BUGGY CODE ###

k,s = map(int,input().split())
cnt=0
for z in range(0, k+1):
    for y in range(0, k+1):
        for x in range(0, k+1):
            if (x+y+z)==s:
                cnt+=1
print(cnt)

### FIXED CODE ###

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

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N)]
earn = 0
AB.sort(key=lambda x:x[1], reverse=True)
for day in reversed(range(M)):
    for i, ab in enumerate(AB):
        if ab[0] + day <= M:
            earn += ab[1]
            del AB[i]
            break
print(earn)


### FIXED CODE ###

import heapq
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N)]
earn = 0
AB.sort(key=lambda x:x[0])
pos=0
cando=[]
for remain in range(M+1):
    for i in range(pos,len(AB)):
        if AB[i][0] <= remain:
            heapq.heappush(cando, -AB[i][1])
            pos=i+1
        else:
            pos=i
            break
    if cando:
        earn-=heapq.heappop(cando)
print(earn)
### BUGGY CODE ###

from collections import Counter
import sys
sys.setrecursionlimit(10**7)
n = int(input())
B = list(map(int, input().split()))
c = Counter(B)
A = []
ans = -1
history = []


def dfs(i):
    if i == n+1:
        if A == B:
            global ans
            ans = history[::]
        return 0
    for j in range(1, i+1):
        if not c[j]:
            continue
        c[j] -= 1
        history.append(j)
        A.insert(j-1, j)
        dfs(i+1)
        A.pop(j-1)
        history.pop()
        c[j] += 1


dfs(1)
if ans == -1:
    print(ans)
else:
    print(*ans, sep='\n')


### FIXED CODE ###

n = int(input())
B = list(map(int, input().split()))
A = []
for b in B:
    A.insert(b-1, b)
if all(A[i] <= i+1 for i in range(n)):
    C = []
    for a in A:
        C.insert(a-1, a)
    if B == C:
        print(*A, sep='\n')
    else:
        print(-1)
else:
    print(-1)
### BUGGY CODE ###

import sys
def main():
    input = sys.stdin.readline
    def inputs():
        return (int(x) for x in input().split())
    N,M = inputs()
    E={i:[] for i in range(1,N+1)}
    for i in range(M):
        L,R,D = inputs()
        E[L].append((R,D))
        E[R].append((L,-D))
    visited = {i: False for i in range(1,N+1)}
    dis = [0]*(N+1)
    while False in visited.values():
        stk = [(list(visited.values()).index(False) + 1, -1, 0)]
        flag = True
        while stk:
            v, p, d = stk.pop()
            #print(v,p)
            if visited[v]:
                if dis[v]!=dis[p]+d:
                    print("No")
                    exit()
                continue
            visited[v] = True
            dis[v]=dis[p]+d
            for u,d in E[v]:
                if u != p:
                    stk.append((u,v,d))
    print("Yes")
main()

### FIXED CODE ###

import sys
def main():
    input = sys.stdin.readline
    def inputs():
        return (int(x) for x in input().split())
    N,M = inputs()
    E={i:[] for i in range(1,N+1)}
    for i in range(M):
        L,R,D = inputs()
        E[L].append((R,D))
        E[R].append((L,-D))
    visited = {i: False for i in range(1,N+1)}
    dis = [0]*(N+1)
    for i in range(1,N+1):
        if not visited[i]:
            stk = [( i, -1, 0)]
            while stk:
                v, p, d = stk.pop()
                #print(v,p)
                if visited[v]:
                    if dis[v]!=dis[p]+d:
                        print("No")
                        exit()
                    continue
                visited[v] = True
                dis[v]=dis[p]+d
                for u,d in E[v]:
                    if u != p:
                        stk.append((u,v,d))
    print("Yes")
main()
### BUGGY CODE ###

s = input()
cnt = 0
for i in range(len(s)):
	for j in range(i + 1, len(s) + 1):
		k = int(s[i:j])
		if k % 2019 == 0 and k != 0:
			#print(i, j)
			cnt += 1
print(cnt)

### FIXED CODE ###

import collections
import math

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def naive(s):
	cnt = 0
	for i in range(len(s)):
		for j in range(i + 1, len(s) + 1):
			k = int(s[i:j])
			if k % 2019 == 0 and k != 0:
				#print(i, j)
				cnt += 1
	return cnt

def main(s):
	nums = [0]
	cur = 0
	p = 0.1
	for i in range(len(s)):
		p = int(p * 10) % 2019
		cur = (cur + int(s[len(s) - 1 - i]) * p) % 2019
		nums.append(cur)
	d = dict(collections.Counter(nums))
	a = [val for key, val in d.items() if val >= 2]
	return sum([comb(x, 2) for x in a])	

s = input()
print(main(s))
### BUGGY CODE ###

from collections import Counter

n = int(input())
s = []
for i in range(n):
    s.append(Counter(input()))

ans = 0
while s != []:
    string = s.pop()
    s_new = []
    temp = 1
    for mojiretu in s:
        if string == mojiretu:
            temp += 1
        else:
            s_new.append(mojiretu)
    ans += temp * (temp-1) // 2
    s = s_new

print(ans)

### FIXED CODE ###

n = int(input())
lst = []
dic = {}
for i in range(n):
    s = list(input())
    s.sort()
    s = ''.join(s)
    if s not in dic.keys():
        dic[s] = 1
    else:
        dic[s] += 1

ans = 0
for i in dic.values():
    ans += i * (i-1) // 2

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

K,S = map(int,input().split())
ans = 0
for k in range(0,K+1):
    for i in range(0,K+1):
        for j in range(0,K+1):
            if k+i+j==S:
                ans+=1
print(ans)

### FIXED CODE ###

K,S = map(int,input().split())
ans = 0
for k in range(0,K+1):
    for i in range(0,K+1):
        if S-(k+i)<=K and S-(k+i)>=0:
            ans+=1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
S = list(input().strip())
assert 1 <= N <= 4000
assert N == len(S)
r = S.count("R")
g = S.count("G")
b = S.count("B")
total = 0

for j in range(1, N-1):
    for i in range(j):
        k = 2*j-i
        if k < len(S):
            if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
                total += 1
print(r*g*b-total)


### FIXED CODE ###

n = int(input())
s = input()
r,g,b =0,0,0
ls = len(s)
for i in range(ls):
    if s[i]=='R':
        r+=1
    elif s[i]=='G':
        g+=1
    elif s[i]=='B':
        b+=1
cnt =0
for j in range(1,ls-1):
    for i in range(j):
        k = 2*j-i
        if k<ls:
            if s[i]!=s[j] and s[i]!=s[k] and s[j]!=s[k]:
                cnt+=1
print(r*g*b-cnt)