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

from operator import itemgetter
import sys
def read():
    return sys.stdin.readline().rstrip()
def main():
    N, Q = map(int, read().split())
    C = list(map(int, read().split()))
    E = []

    D = [-1] * (N + 1)
    for i in range(N):
        D_i = D[C[i]]
        if D_i != -1:
            E.append((D_i, i, -1))
        D[C[i]] = i

    for i in range(Q):
        l, r = map(int, input().split())
        E.append((l - 1, r - 1, i))

    E.sort(key=lambda tup: tup[0], reverse=True)

    # Binary Indexed Tree (Fenwick Tree)
    class BIT:
        def __init__(self, n):
            self.n = n
            self.data = [0] * (n + 1)
            self.el = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.data[i]
                i -= i & -i
            return s

        def add(self, i, x):
            # assert i > 0
            self.el[i] += x
            while i <= self.n:
                self.data[i] += x
                i += i & -i

        def get(self, i, j=None):
            if j is None:
                return self.el[i]
            return self.sum(j) - self.sum(i)

    ANS = [0] * Q
    d = BIT(N)
    for e in E:
        if e[2] == -1:
            d.add(e[1], 1)
        else:
            ANS[e[2]] = e[1] - e[0] + 1 - d.sum(e[1])

    for i in range(Q):
        print(ANS[i])

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import defaultdict
import sys
def read():
    return sys.stdin.readline().rstrip()
def main():
    N, Q = map(int, read().split())
    C = list(map(int, read().split()))
    E = defaultdict(list)

    D = [-1] * (N + 1)
    for i in range(N):
        D_i = D[C[i]]
        if D_i != -1:
            E[D_i].append((D_i, i))
        D[C[i]] = i

    F = defaultdict(list)
    for i in range(Q):
        l, r = map(int, input().split())
        F[l-1].append((r - 1, i))



    # Binary Indexed Tree (Fenwick Tree)
    class BIT:
        def __init__(self, n):
            self.n = n
            self.data = [0] * (n + 1)
            self.el = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.data[i]
                i -= i & -i
            return s

        def add(self, i, x):
            # assert i > 0
            self.el[i] += x
            while i <= self.n:
                self.data[i] += x
                i += i & -i

        def get(self, i, j=None):
            if j is None:
                return self.el[i]
            return self.sum(j) - self.sum(i)

    ANS = [0] * Q
    d = BIT(N)
    for x in range(N - 1, -1, -1):
        for e in E[x]:
            d.add(e[1], 1)
        for f in F[x]:
            ANS[f[1]] = f[0] - x + 1 - d.sum(f[0])

    for i in range(Q):
        print(ANS[i])

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

from collections import Counter

N = int(input())
S = [[]for _ in range(10)]
for _ in range(N):
    s = input()
    S[len(s)-1].append(Counter(s))

ans = 0
for _ in range(10):
    for i in range(len(S[_])):
        for j in range(i+1, len(S[_])):
            if S[_][i] == S[_][j]:
                ans += 1
print(ans)

### FIXED CODE ###

from collections import defaultdict

N = int(input())
S = defaultdict(int)
ans = 0
for _ in range(N):
    s = input()
    sl = []
    for n in s:
        sl.append(n)
    sl.sort()
    s = ''.join(sl)
    S[s] += 1

for value in S.values():
    ans += value * (value-1)//2
print(ans)
### BUGGY CODE ###

import math


def get_min(num_step):
    res = float("inf")
    for i in range(1, min(num_step, K)+1):
        cost = costs[num_step-i] + abs(steps[num_step] - steps[num_step-i])
        if cost < res:
            res = cost
    return res


N, K = map(int, input().split(" "))
steps = list(map(int, input().split(" ")))
costs = [None] * N
costs[0] = 0

for i in range(1, N):
    costs[i] = get_min(i)

print(costs[N-1])


### FIXED CODE ###

import math


def get_min(num_step):
    res = float("inf")
    for i in range(1, min(num_step, K)+1):
        cost = costs[num_step-i] + abs(steps[num_step] - steps[num_step-i])
        if cost < res:
            res = cost
    return res


N, K = map(int, input().split(" "))
steps = list(map(int, input().split(" ")))
costs = [None] * N
costs[0] = 0

for i in range(1, N):
    costs[i] = get_min(i)

print(costs[N-1])
### BUGGY CODE ###

s = input()
ls = len(s)
while True:
    f = False
    for i in range(len(s)-1):
        if (s[i] =='0' and s[i+1] =='1') or (s[i] =='1' and s[i+1] =='0'):
            s = s[0:i] + s[i+2:]
            f = True
            break
    if f == False:
        break
print(ls-len(s))

### FIXED CODE ###

s = list(input())
print(min(s.count('1'), s.count('0'))*2)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import re

def comb(n, k):
        a = [0] * 100
        if (n - k < k):
                k = n - k
        if (k == 0):
                return 1
        if (k == 1):
                return n
        if (k > 100):
                return 0
        for i in range(1, k):
                a[i] = i + 2
        for i in range(3, (n - k + 2)):
                a[0] = i
                for j in range(1, k):
                        a[j] += a[j - 1]
        return a[k - 1]

n = int(raw_input())
a = map(int, re.split("\s", raw_input()))
left = 0
right = 0
mask = 10**9 + 7

for i in range(0, n + 1):
        x = a.index(a[i])
        if a[i] in a[x+1:]:
                left = i
                right = a[x+1:].index(a[i]) + x + 1
                break

for i in range(1, n + 2):
        ans = comb(n + 1, i)
        ans -= comb(left + n - right, i - 1)
        print ans % mask

### FIXED CODE ###

# -*- coding: utf-8 -*-

from collections import Counter
import re

def pow(a, x):
        y = 1
        p = a % mask
        n = x
        while (n > 0):
                if ((n % 2) == 0):
                        p = (p * p) % mask
                        n /= 2
                else:   
                        y = (y * p) % mask
                        n -= 1
        return y

n = int(raw_input())
a = map(int, re.split("\s", raw_input()))
left = 0
right = 0

mask = 10**9 + 7
invm = 10**9 + 5

com = [1]*(n+2)
inv = [1]*(n+2)

tmp = 1 
for i in range(1, n+2):
        tmp = (tmp * i) % mask
        com[i] = tmp
        inv[i] = pow(tmp, invm) % mask

counter = Counter(a)
dup = counter.most_common(1)[0][0]
left = a.index(dup)
right = a[left+1:].index(dup) + left + 1

for i in range(1, n + 2):
        ans = (com[n + 1] * (inv[i] * inv[n + 1 - i]))

        if ((left + n - right - i + 1) >= 0):
                ans -= (com[left + n - right] * inv[i - 1] * inv[left + n - right - i + 1])
        print ans % mask
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
nedan_list = []
append = nedan_list.append
for i in range(n):
  price = a[i]
  append((i, price))
  while price > 1:
    price = price >> 1
    append((i, price))

nedan_list.sort(key=lambda x:x[1], reverse=True)
count = 0
saisyo_list = [True]*n
for e in nedan_list[m:]:
  if saisyo_list[e[0]]:
    saisyo_list[e[0]] = False
    count += e[1]
print(count)


### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a) 

for i in range(m):
  max_ = -heapq.heappop(a)
  d = max_ // 2
  heapq.heappush(a, -d)

c = 0
for i in range(len(a)):
  c -= heapq.heappop(a)
print(c)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
B=[]*N
for i in range(1,N+1):
    B.append(A.index(i)+1)
for i in range(N):
    print(B[i],end=" ")
    

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
AA=[]
for i in range(N):
    AA.append([A[i],i+1])
AA.sort()
for j in range(N):
    print(AA[j][1],end=" ")
### BUGGY CODE ###

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

for i in range(Q):
    Query = list(input().split())
    if Query[0] == "1" :
        S = S[::-1]
    if Query[0] == "2" :
        if Query[1] == "1" :
            S = Query[2] + S
        elif Query[1] == "2" :
            S = S + Query[2]

print(S)

### FIXED CODE ###

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

T = ""
for i in range(Q) :
    Query = list(input().split())
    if Query[0] == "1" :
        S, T = T, S
    elif Query[0] == "2" :
        if Query[1] == "1" :
            T = T + Query[2]
        elif Query[1] == "2" :
            S = S + Query[2]

T = T[::-1]
T = T + S
print(T)
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
AC=[]
for i in range(N):
    if S[i]=='A' and i<N-1:
        if S[i+1]=='C':
            AC.append(i)

for _ in range(Q):
    l,r=map(int,input().split())
    l-=1
    r-=1
    ans=0
    for ac in AC:
        if l<=ac<r:
            ans+=1
        if ac>=r:
            break
    print(ans)

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
AC=[0]*N

cnt=0
for i in range(N-1):
    if S[i]+S[i+1]=='AC':
        AC[i]=cnt
        cnt+=1
        AC[i+1]=cnt
    else:
        AC[i],AC[i+1]=cnt,cnt

for _ in range(Q):
    l,r=map(int,input().split())
    print(AC[r-1]-AC[l-1])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=1
for i in a:
  b*=i
if b>10**18:
  print(-1)
else:
  print(b)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
if 0 in a:
  print(0)
  exit()
t=1
for i in a:
  t*=i
  if t>10**18:
    print("-1")
    exit()
print(t)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    H,N = map(int,input().split())
    AB = [[int(i) for i in input().split()] for _ in range(N)]

    dp = [float("inf")] * (H+1)

    dp[H] = 0

    for i in range(H,-1,-1):
        for j in range(N):
            tmp = max(0,i-AB[j][0])
            dp[tmp] = min(dp[tmp], dp[i]+AB[j][1])

    print(dp[0])

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    H,N = map(int,input().split())
    AB = [[int(i) for i in input().split()] for _ in range(N)]

    dp = [float("inf")] * (H+1)

    dp[H] = 0

    for i in range(H,-1,-1):
        for j in range(N):
            tmp = max(0,i-AB[j][0])
            dp[tmp] = min(dp[tmp], dp[i]+AB[j][1])

    print(dp[0])

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

N=int(input())
A=[''.join(sorted(input())) for i in range(N)]
B=list(map(A.count,set(A)))

ans=0
for b in B:
    if b==2:ans+=1
    else:ans+=b*(b-1)//2
print(ans)



### FIXED CODE ###

N=int(input())
d={}
for i in range(N):
    l=[0]*26
    for s in input():
        l[ord(s)-97]+=1
    l=tuple(l)
    if l in d:d[l]+=1
    else:d[l]=1

ans=0
for c in d:
    if d[c]==2:ans+=1
    elif d[c]!=1:ans+=d[c]*(d[c]-1)//2
print(ans)
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
 
route = []
for _ in range(H):
  route.append(input())
  
wall = set()
start = []
for y, r in enumerate(route):
  for x, w in enumerate(r):
    if w == '#':
      wall.add((x, H-y-1))
    else:
      start.append((x, H-y-1))

score = -1
for xy in start:
  d = deque()
  d.append((xy[0],xy[1],0))
  step = 0
  already = set() | wall
  while len(d) > 0:
    now = d.popleft()
    already.add(now[:-1])
    step = now[2]+1
    x,y = now[0]-1, now[1]
    if (x, y) not in already and x >= 0:
      d.append((x, y, step))
    x, y = x+1, y-1
    if (x, y) not in already and y >= 0:
      d.append((x, y, step))
    x, y = x+1, y+1
    if (x, y) not in already and x < W:
      d.append((x, y, step))
    x, y = x-1, y+1
    if (x, y) not in already and y < H:
      d.append((x, y, step))
  score = max(step-1, score)
  
print(score)

### FIXED CODE ###

from collections import deque
import copy
H, W = map(int, input().split())
 
route = []
for _ in range(H):
  route.append(input())
  
wall = set()
start = set()
for y, r in enumerate(route):
  for x, w in enumerate(r):
    if w == '.':
      start.add((x, y))

score = -1
ssize = [(-1,0),(0,-1),(1,0),(0,1)]
for xy in start:
  d = deque()
  d.append((xy+(0,)))
  step = 0
  can = copy.deepcopy(start)
  can.remove(xy)
  while len(d) > 0:
    now = d.popleft()
    step = now[2]
    for xs, ys in ssize:
      nxt = (now[0]+xs, now[1]+ys)
      if nxt in can:
        d.append(nxt+(step+1,))
        can.remove(nxt)
  score = max(step, score)
  
print(score)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
ans = 0

for i in range(min(l), max(l)+1):
    ans = max(l.count(i-1) + l.count(i) + l.count(i+1), ans)

print(ans)

### FIXED CODE ###

from collections import Counter

n = int(input())
l = list(map(int, input().split()))
c = Counter(l)
s = set(l)
ans = 0

for i in s:
    ans = max(c[i-1] + c[i] + c[i+1], ans)
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(a) for a in input().split()]
mod = 10**9+7
SUM = 0

maxA = max(A)
d = 0
while 1:
    if maxA < 2**d:
        break
    d += 1

BitA = [[0]*d for _ in range(N)]
for i in range(N):
    BitA[i] = list(map(int, format(bin(A[i])[2:], '0>{}'.format(d))))

BitSumB = 0
for i in range(d):
    tmp = sum([BitA[j][i] for j in range(N)])
    BitSumB += 2 ** (d-i-1) * (tmp * (N - tmp))
    BitSumB = BitSumB % mod

print(BitSumB)

### FIXED CODE ###

N = int(input())
A = [int(a) for a in input().split()]
mod = 10**9+7
SUM = 0

maxA = max(A)
d = 0
while 1:
    if maxA < 2**d:
        break
    d += 1

BitSumB = 0
for i in range(d):
    tmp = 0
    for n in range(N):
        tmp += (A[n] >> i) & 1
    BitSumB += (2**i) * tmp * (N - tmp)



"""
BitA = [[0]*d for _ in range(N)]
for i in range(N):
    BitA[i] = list(map(int, format(bin(A[i])[2:], '0>{}'.format(d))))

BitSumB = 0
for i in range(d):
    tmp = sum([BitA[j][i] for j in range(N)])
    BitSumB += 2 ** (d-i-1) * (tmp * (N - tmp))
    #BitSumB = BitSumB % mod
"""

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

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
assert len(A) == N
assert len(B) == M
# K分以内に読む数の最大化

cumA = []
cumB = []
sumA = 0
sumB = 0
for a in A:
  sumA += a
  cumA.append(sumA)
for b in B:
  sumB += b
  cumB.append(sumB)

maximum = 0
for maxA,timeA in enumerate([0]+cumA):
  if timeA <= K:
   timeB = K - timeA
   maxB = [i for i,b in enumerate(cumB) if b <= timeB]
   maxB = max(maxB) + 1 if len(maxB) else 0
   maximum = max(maximum, maxA + maxB)
print(maximum)

### FIXED CODE ###

N , M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a,b=[0],[0]
for i in range(N): a.append(a[i] + A[i])
for i in range(M): b.append(b[i] + B[i])
ans,j=0,M
for i in range(N+1):
  if a[i]>K:
    break
  while b[j] > K - a[i]:
    j -= 1
  ans = max(ans, i+j)
print(ans)
### BUGGY CODE ###

import heapq

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

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

for _ in range(M):
    A.sort(reverse=True)
    A[0] //= 2
print(sum(A))


### FIXED CODE ###

import heapq

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

A=list(map(lambda x: int(x)*(-1), input().split()))

heapq.heapify(A)

for _ in range(M):
    temp_min = heapq.heappop(A)
    heapq.heappush(A, (-1)*(-temp_min//2))
print(-sum(A))
### BUGGY CODE ###

S = input()
S = S[::-1]

# i~nまでの値をmod2019したときの数
ls = [0for i in range(2019)]

# 0文字の時
ls[0] += 1

x = 0
for i in range(len(S)):
    x += int(S[i])*10**i
    ls[x%2019] += 1

count = 0
for x in ls:
    count += x*(x-1)/2

print(int(count))



### FIXED CODE ###

S = input()
digits = list(map(int,S))
# S = S[::-1]→これが時間かかる

# i~nまでの値をmod2019したときの数
# ls = [0for i in range(2019)]
ls = [0] * 2019

# 0文字の時
ls[0] += 1

x = 0
pow10 = 1
count = 0
for i in reversed(digits):
    x += i*pow10
    x %= 2019
    count += ls[x]
    ls[x] += 1
    pow10 *= 10
    pow10 %= 2019

# for x in ls:
#     count += x*(x-1)/2

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

# -*- coding: utf-8 -*-

n, m = input().split()
x = input().split()
y = input().split()
width = []
for i in range(len(x)-1):
    for j in range(i+1,len(x)):
        width.append(abs(int(x[i])-int(x[j])))

height = []
for i in range(len(y)-1):
    for j in range(i+1,len(y)):
        height.append(abs(int(y[i])-int(y[j])))

sum = 0
for w in width:
    for h in height:
        sum = sum + w * h
print(sum % (10 ** 9 + 7))

### FIXED CODE ###

# -*- coding: utf-8 -*-

n, m = list(map(int, input().split()))
x = list(map(int, input().split()))
y = list(map(int, input().split()))

def sum_length(x, n):
    all_sum = 0
    prev_sum = 0
    for i in range(1, n):
        cur_sum = prev_sum + (x[i] - x[i-1]) * i
        all_sum = all_sum + cur_sum
        prev_sum = cur_sum
    return all_sum

sumx = sum_length(x, n)
sumy = sum_length(y, m)
print(sumx * sumy % 1000000007)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

#input
N = int(input())

#output
minimum = 0
ans = N-1
for i in range(1, N+1):
    if float.is_integer(N/i):
        a = i
        b = int(N/i)
        c = a+b-2
        ans = min(c, ans)
        
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

#input
N = int(input())

#output
import math
M = int(math.sqrt(N))

ans = N
for i in reversed(range(1, M+1)):
    if float.is_integer(N/i):
        a = i
        b = int(N/i)
        c = a + b -2
        ans = min(ans, c)
        
print(ans)
### BUGGY CODE ###

import sys
import collections
import math

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))


x = ni()
s=[]
for i in range(x):
    si=ns()
    if si not in s:
        s.append(si)
print(len(s))


### FIXED CODE ###

import sys
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))


x = ni()
s= [[[] for j in range(26)] for i in range(26)]
sum=0
for i in range(x):
    si=ns()
    sn1=ord(si[0:1])-97
    if len(si)==1:
        sn2=0
    else:
        sn2 = ord(si[1:2]) - 97
    if si not in s[sn1][sn2]:
       s[sn1][sn2].append(si)
for s1 in s:
    for s2 in s1:
        sum+=len(s2)
print(sum)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
sum = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        sum += a[i] * a[j]
print(sum % (10**9 + 7))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
sum = sum(a)
s = 0
c = 0
for i in range(n - 1):
    s += a[i]
    c = (c + (a[i] * (sum - s)))  % (10**9 + 7)
print(c)
### BUGGY CODE ###

M=998244353
d=[0]*90301
d[0]=1
e=[0]*90301
e[0]=1
z=1
s=0
for _ in range(input()):
	a=input();s+=a;i=s;z*=3
	while~i:d[i]+=d[i]+d[i-a]%M;e[i]+=e[i-a]%M;i-=1
i=s
while i*2>=s:z=(z-d[i]*3)%M;i-=1
z+=~s%2*e[s//2]*3
print z%M

### FIXED CODE ###

M=998244353
N=int(input())
d=[0]*90001
d[0]=1
e=[0]*90001
e[0]=1
z=1
s=0
for _ in range(N):
	a=int(input())
	i=s
	while i>=0:
		d[i+a]+=d[i]%M
		d[i]*=2
		e[i+a]+=e[i]%M
		i-=1
	s+=a
	z=z*3%M
for i in range(s+1>>1,s+1):
	z-=d[i]*3
	z%=M
print([(z+e[s//2]*3)%M,z][s%2])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
l_1 = []
l_2 = []

for i in range(N):
  if A[i] < (10**5)*2:
    l_1.append(A[i]+i)
    l_2.append(i-A[i])
  
for num in range(min(l_2), max(l_2)+1):
  ans += l_1.count(num)*l_2.count(num)
      
print(ans)

### FIXED CODE ###

from collections import defaultdict
 
n = int(input())
a = list(map(int, input().split()))
ap = defaultdict(int)
for i in range(n):
    ap[i - a[i]] += 1

ans= 0
for i in range(n):
    ans += ap[a[i] + i]
print(ans)
### BUGGY CODE ###

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

m, m_index = 0, 0
for i in range(N-K+1):
    total =sum(P[i:i+K])
    if total > m:
        m = total
        m_index = i

expected = 0
for p in P[m_index:m_index+K]:
    expected += sum(list(range(1, p+1)))/p
print(expected)

### FIXED CODE ###

from itertools import accumulate


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


expected = [(a+1)/2 for a in A]
accum_expected = list(accumulate(expected))
accum_expected.insert(0, 0)

ans = 0
for i in range(K, N+1):
    ans = max(ans, accum_expected[i]-accum_expected[i-K])
print(ans)
### BUGGY CODE ###

import copy
import numpy as np
from math import factorial

def num_choice_2(N):
    if N > 1:
        return N * (N - 1) // 2
    else:
        return 0

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

nums = np.zeros(N, dtype=int)
for a_i in A:
    nums[a_i - 1] += 1

comb_default = np.array([num_choice_2(x) for x in nums])
comb_selected = np.array([num_choice_2(x - 1) for x in nums])

for i in range(N):
    ans = comb_selected[A[i] - 1]
    ans += np.sum(comb_default[:A[i] - 1]) + np.sum(comb_default[A[i]:])

    print(ans)

### FIXED CODE ###

def n_c_2(n):
    if n < 1:
        return 0
    else:
        return n * (n - 1) // 2

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

n_balls = [0 for _ in A]
for a_i in A:
    n_balls[a_i - 1] += 1

n_combinations = [n_c_2(n) for n in n_balls]
total_combinations = sum(n_combinations)

for i, a_i in enumerate(A):
    diff = n_c_2(n_balls[a_i - 1]) - n_c_2(n_balls[a_i - 1] - 1)
    print(total_combinations - diff)
### BUGGY CODE ###

import sys
from heapq import heappop, heappush

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    ch, cw = map(int, input().split())
    ch -= 1
    cw -= 1
    fh, fw = map(int, input().split())
    fh -= 1
    fw -= 1

    M = [[-1 for w in range(W)] for h in range(H)]
    Edge = [[[] for w in range(W)] for h in range(H)]
    for h in range(H):
        s = input().strip("\n")
        for w in range(W):
            if s[w] == "#":
                M[h][w] = -2
    for h in range(H):
        for w in range(W):
            if M[h][w] == -1:
                for dh in range(-2, 3):
                    for dw in range(-2, 3):
                        if 0<=h+dh<H and 0<=w+dw<W and M[h+dh][w+dw] == -1 and abs(dh)+abs(dw)>0:
                            if abs(dh)+abs(dw)==1:
                                Edge[h][w].append((0, h+dh, w+dw))
                            else:
                                Edge[h][w].append((1, h+dh, w+dw))


    q = []
    heappush(q, (0, ch, cw))
    while q:
        dist, h, w = heappop(q)
        if M[h][w] == -1:
            M[h][w] = dist
            for dd, nh, nw in Edge[h][w]:
                if M[nh][nw] == -1: heappush(q, (dist+dd, nh, nw))
    print(M[fh][fw])
    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    sh, sw = map(int, input().split())
    sh -= 1
    sw -= 1
    fh, fw = map(int, input().split())
    fh -= 1
    fw -= 1

    S = [input().strip("\n") for _ in range(H)]

    q = deque()
    P = [[-1 for _ in range(W)] for h in range(H)]
    q.append((0, sh, sw))
    while q:
        d, h, w = q.popleft()
        if P[h][w] == -1:
            P[h][w] = d
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    if 0<=h+dh<H and 0<=w+dw<W and S[h+dh][w+dw] == "." and P[h+dh][w+dw] == -1:
                        if abs(dh) + abs(dw) == 1:
                            q.appendleft((d, h+dh, w+dw))
                        else:
                            q.append((d+1, h+dh, w+dw))
    print(P[fh][fw])
    

    return 0

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

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

### FIXED CODE ###

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

S = str(input())
ans = 0
for i in range(len(S)-4):
    for j in range(i+4,len(S)+1):
        if(int(S[i:j]) % 2019 == 0):
            ans += 1
print(ans)

### FIXED CODE ###

S = str(input())
# 余りのリスト
counts = [0] * 2019
n, d = 0, 1

for s in S[::-1]:
    n += int(s) * d
    d *= 10
    n %= 2019
    d %= 2019
    counts[n] += 1
ans = counts[0]
for count in counts:
    ans += count * (count - 1) // 2
print(ans)