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

import itertools

N = int(input())

for h, n in itertools.product(range(1, 3501), range(1, 3501)):
    if (4*n*h-N*(n+h)) == 0:
        continue
    elif N*h*n % (4*n*h-N*(n+h)) == 0 and N*h*n // (4*n*h-N*(n+h)) > 0:
        break

print(h, n, N*h*n // (4*n*h-N*(n+h)))

### FIXED CODE ###

import itertools

N = int(input())

for h, n in itertools.product(range(1, 3501), range(1, 3501)):
    if (4*n*h-N*(n+h)) == 0:
        continue
    elif N*h*n % (4*n*h-N*(n+h)) == 0 and N*h*n // (4*n*h-N*(n+h)) > 0:
        break

print(h, n, N*h*n // (4*n*h-N*(n+h)))
### BUGGY CODE ###

from itertools import accumulate

n = int(input())
s = input()

black = [0] * (n+1)
white = [0] * (n+1)
ans = [0] * (n+1)
for i in range(n+1):
  black[i] = s[:i].count("#")
  white[i] = s[i:].count(".")
  ans[i] = black[i] + white[i]
print(min(ans))

### FIXED CODE ###

n = int(input())
s = str(input())
x = s.count('.')

res = x

for c in s:
    if c == '#':
        x += 1
    else:
        x -= 1
    res = min(res , x)
print(res)
### BUGGY CODE ###

import re
def MAIN():
    T = input()
    P = input()
    pat = re.compile(P)
    t = 0
    ans = []
    while True:
        t = pat.search(T, t)
        if t is None:
            break
        ans.append(t.span()[0])
        t = t.span()[0] + 1
    if ans:
        print("\n".join(map(str, ans)))
MAIN()



### FIXED CODE ###

def kmpTable(w):
    lw = len(w)
    nx = [-1] * (lw + 1)
    j = -1
    for i in range(lw):
        while j >= 0 and w[i] != w[j]:
            j = nx[j]
        j += 1
        nx[i + 1] = j
    return tuple(nx)
def kmpSearch(s, w):
    ls = len(s)
    start = 0
    w_idx = 0
    ret = []
    nx = kmpTable(w)
    while start + w_idx < ls:
        if s[start + w_idx] == w[w_idx]:
            w_idx += 1
            if w_idx == len(w):
                ret.append(start)
                start = start + w_idx - nx[w_idx]
                w_idx = nx[w_idx]
        else:
            if w_idx == 0:
                start += 1
            else:
                start = start + w_idx - nx[w_idx]
                w_idx = nx[w_idx]
    return ret
T = input()
P = input()
ans = kmpSearch(T, P)

if ans:
    print(*ans, sep="\n")
#    print("\n".join(map(str, ans)))
### BUGGY CODE ###

x = input()

while True:
  print('Yes')

### FIXED CODE ###

x = int(input())

print('Yes' if x >= 30 else 'No')
### BUGGY CODE ###

import itertools
from collections import Counter
import numpy as np

n = int(input())
l = list(input())
l = list(Counter(l).values())

ans = n

for i in range(2, len(l)+1):
    conbis = list(itertools.combinations(l, i))
    for conbi in conbis:
        ans += np.prod(conbi)

print(ans%(10**9 + 7))

### FIXED CODE ###

from collections import Counter

n = int(input())
l = list(input())
l = list(Counter(l).values())

ans = 1

for i in l:
    ans *= i+1
print((ans-1)%(10**9+7))
### BUGGY CODE ###

import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 8)


N, K = map(int, input().split())
M = 998244353
S = set()
for _ in range(K):
    L, R = map(int, input().split())
    for i in range(L, R + 1):
        S.add(i)


@lru_cache(None)
def dp(i):
    if i < 1:
        return 0
    elif i == 1:
        return 1
    else:
        res = 0
        for d in S:
            res += dp(i - d)
            res %= M
        return res
print(dp(N) % M)


### FIXED CODE ###

N, K =map(int,input().split())
K = [tuple(map(int,input().split())) for i in range(K)]
M = 998244353

dp = [0] * N
dp[1] = 1
prefix = [1] * N

for i in range(1, N):
    cur = 0
    for L, R in K:
        a = i - R
        b = i - L
        if b < 0:
            continue
        cur += prefix[b] - (prefix[a - 1] if a - 1 >= 0 else 0)
    dp[i] = cur % M
    prefix[i] = prefix[i - 1] + dp[i]
    prefix[i] %= M
print(dp[N - 1])
### BUGGY CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
ans = []
kitaiti = 0
max_key = -1
for i in range(len(p)):
    sum_p = sum(p[i:i+k])
    if max_key <= sum_p:
        max_key = sum_p
        key = i
ans_list = p[key:key+k]
for i in ans_list:
    kitaiti += (((1+i)/2)*i)*i**-1
print(kitaiti)


### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
p_kitaiti = [(1+p[i])/2 for i in range(n)]
ans = sum(p_kitaiti[:k])
number = sum(p_kitaiti[:k])
for i in range(k,n):
    number = number + p_kitaiti[i] - p_kitaiti[i-k]
    ans = max(ans,number)
print(ans)
### BUGGY CODE ###

from decimal import Decimal
N = int(input())
numlist = [0] * (N + 1)
log2 = [0] * (N + 1)
log5 = [0] * (N + 1)
acc = [[0 for i in range(19)] for j in range(19)]
Ans = 0

for i in range(1,N+1):
  numlist[i] = Decimal(input()) * 1000000000

  wk = numlist[i]
  for cnt in range(1,19):
    if wk % 2 == 0:
      log2[i] += 1
      wk = wk // 2
    else:
      break

  for cnt in range(1,19):
    if wk % 5 == 0:
      log5[i] += 1
      wk = wk // 5
    else:
      break

  acc[log2[i]][log5[i]] += 1
    
for i in range(0,19):
  for j in range(0,19): 
    for k in range(0,19):
      for l in range(0,19):
        if (i + k) >= 18 and (j + l) >= 18 and (i < k or (i == k and j <= l)):
          #if acc[i][j] > 0 and acc[k][l] > 0:
          if True:
            Ans += acc[i][j] * acc[k][l]
            #if i >= 17 and j >= 9:
              #print("+["+str(i)+","+str(j)+"]["+str(k)+","+str(l)+"]")
              #print(str(acc[i][j])+"*"+str(acc[k][l]))
            #print("+:" + str(acc[i][j] * acc[k][l]))
            if i >= 9 and j >= 9 and i == k and j == l:
              Ans -= int((acc[i][j] * (acc[i][j] + 1)) / 2)
              #print("-["+str(i)+","+str(j)+"]["+str(k)+","+str(l)+"]")
              #print("-:" + str(acc[i][j]))


print(int(Ans))
#print(acc)

#s = sum(sum(acc,[]))
#print(s)


### FIXED CODE ###

from decimal import Decimal
N = int(input())
#numlist = [0] * (N + 1)
log2 = [0] * (N + 1)
log5 = [0] * (N + 1)
acc = [[0 for i in range(19)] for j in range(19)]
Ans = 0

for i in range(1,N+1):
  #numlist[i] = Decimal(input()) * 1000000000
  wk = Decimal(input())
  wk = int(wk * 1000000000)

  #wk = numlist[i]
  for cnt in range(1,19):
    if wk % 2 == 0:
      log2[i] += 1
      wk = wk // 2
    else:
      break

  for cnt in range(1,19):
    if wk % 5 == 0:
      log5[i] += 1
      wk = wk // 5
    else:
      break

  acc[log2[i]][log5[i]] += 1
    
for i in range(0,19):
  for j in range(0,19): 
    for k in range(i,19):
      for l in range(0,19):
        if (i + k) >= 18 and (j + l) >= 18 and (i < k or (i == k and j <= l)):
          if acc[i][j] > 0 and acc[k][l] > 0:
            Ans += acc[i][j] * acc[k][l]
            if i >= 9 and j >= 9 and i == k and j == l:
              Ans -= int((acc[i][j] * (acc[i][j] + 1)) / 2)

print(int(Ans))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

n = int(input())
x = input()
z = '1' * n
o = '0' * n

if (z == x):
  u = n - 1
  d = n - 1
elif (z == o):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  d = tmp - 1

def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def toggle(i):
  if (i == '1'):
    return '0'
  else:
    return '1'


def solve(i, count):
  if (i <= n and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


ans = [0] * (2 * 10 ** 5 + 1)
for i in range(1, 2 * 10 ** 5):
  ans[i] = solve(i, 0)
for i in range(n):
  if(i == 0):
    _x = toggle(x[0]) + x[1: n]
  elif (i == n - 1):
    _x = x[:i] + toggle(x[n - 1])
  else:
    _x = x[:i] + toggle(x[i]) + x[i + 1 :n]
  print(solve(int(_x, 2),0))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

n = int(input())
x = input()
z = '1' * n
o = '0' * n
X = int(x, 2)

if (n == 1 and x == '1'):
  print(0)
  exit()

if (z == x):
  u = n - 1
  d = n - 1
elif (o == x):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  d = tmp - 1


def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def solve(i, count):
  if (i <= 2 * 10**5 and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


def solve2(i, div):
  if (i <= 2 * 10**5):
    return ans[i]
  else:
    return ans[i % div] + 1


ans = [0] * (2 * 10 ** 5 + 4)
_u = (2 * 10 ** 5) // u
U = X % u + (u * _u) + u
if(d != 0):
  _d = (2 * 10 ** 5) // d
  D = X % d + (d * _d) * 2 + d * 2
Us = [0] * (2 * 10 ** 5)
Ds = [0] * (2 * 10 ** 5)
for i in range(1, 2 * 10 ** 5 + 4):
  ans[i] = solve(i, 0)
Us[0] = 1 % u
if(d != 0):
  Ds[0] = 1 % d
for i in range(1, 2 * 10 ** 5):
  Us[i] = (Us[i - 1] * 2) % u
  if(d != 0):
    Ds[i] = (Ds[i-1] * 2) % d

for i in range(n):
  if(x[i] == '0'):
    print(solve2(U + Us[n-i-1], u))
  else:
    if (d == 0):
      print(0)
    else:
      print(solve2(D - Ds[n-i-1], d))
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(5)]
ninzu = [n,0,0,0,0,0]
count = 0
while True:
    if ninzu[5] == n:
        break
    count += 1
    for i,number in enumerate(a[::-1]):
        i = 4-i
        if number>=ninzu[i]:
            ninzu[i+1] += ninzu[i]
            ninzu[i] = 0
        else:
            ninzu[i+1] += number
            ninzu[i] -= number
print(count)

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(5)]
min_a = min(a)
ans = 4
ans += n//min_a
if n%min_a != 0:
    ans += 1
print(ans)
### BUGGY CODE ###

class Dict(object):

    m1 = 2 ** 25 - 1
    m2 = 3

    def __init__(self):
        self._dict = ["" for _ in range(self.m1)]

    def insert(self, k):
        i = 0

        while True:
            ix = self._h(k, i)
            if self._dict[ix] == "":
                self._dict[ix] = k
                return
            else:
                i += 1

    def find(self, k):
        i = 0

        while True:
            ix = self._h(k, i)
            if self._dict[ix] == k:
                return ix
            elif self._dict[ix] == "":
                return -1
            else:
                i += 1

    def _h(self, k, i):
        return self._h1(k) + i * self._h2(k)

    def _h1(self, k):
        return k % self.m1

    def _h2(self, k):
        return k % self.m2 + 1


def to_int(s):
    _s = s[::]

    ret = 0
    i = 1
    for e in _s:
        if e == 'A':
            ret += 1 * i
        elif e == 'C':
            ret += 2 * i
        elif e == 'G':
            ret += 3 * i
        elif e == 'T':
            ret += 4 * i
        i *= 4

    return ret


if __name__ == '__main__':
    n = int(input())

    d = Dict()

    for _ in range(n):
        cmd, val = input().split()

        if cmd == "insert":
            d.insert(to_int(val))
        else:
            ans = "yes" if d.find(to_int(val)) != -1 else "no"
            print(ans)

### FIXED CODE ###

M = 1046527
L = 14
H = [""] * M
 
def getChar(ch):
    if ch == 'A':
        return 1
    elif ch == 'C':
        return 2
    elif ch == 'G':
        return 3
    elif ch == 'T':
        return 4
    else:
        return 0
 
def getKey(strings):
    Sum = 0
    p = 1
    for i in xrange(len(strings)):
        Sum += p * getChar(strings[i])
        p *= 5
 
    return Sum
 
def h1(key):
    return key % M
 
def h2(key):
    return 1 + (key % (M-1))
 
def find(strings):
    key = getKey(strings)
    i = 0
    while True:
        h = (h1(key) + i * h2(key)) % M
        if H[h] == strings:
            return 1
        elif len(H[h]) == 0:
            return 0
        else:
            i += 1
    return 0
 
def insert(strings):
    key = getKey(strings)
    i = 0
    while True:
        h = (h1(key) + i * h2(key)) % M
        if H[h] == strings:
            return 1
        elif len(H[h]) == 0:
            H[h] = strings
            return 0
        else:
            i += 1
    return 0
 
def main():
    n = input()
    for i in xrange(n):
        com = raw_input().split()
        if com[0][0] == 'i':
            insert(com[1])
        else:
            if find(com[1]):
                print 'yes'
            else:
                print 'no'
    return 0
 
main()
### BUGGY CODE ###

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

def main():
	n=II()
	s=input().rstrip().decode()
	li=[0]*n
	for i in range(n):
		if s[i]=="D":
			li[i]=1
		elif s[i]=="M":
			li[i]=2
		elif s[i]=="C":
			li[i]=3
	
	q=II()
	K=LI()
	for k in K:
		D=0
		M=0
		DM=0
		ans=0
		
		for i in range(n):
			if li[i]==1:
				D+=1
			elif li[i]==2:
				M+=1
				DM+=D
			elif li[i]==3:
				ans+=DM
			
			if i-k+1>=0:
				if li[i-k+1]==1:
					D-=1
					DM-=M
				elif li[i-k+1]==2:
					M-=1
		print(ans)
		


if __name__ == "__main__":
	main()


### FIXED CODE ###

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

def main():
	n=II()
	s=input().rstrip().decode()
	li=[0]*n
	for i in range(n):
		if s[i]=="D":
			li[i]=1
		elif s[i]=="M":
			li[i]=2
		elif s[i]=="C":
			li[i]=3
	
	q=II()
	K=LI()
	for k in K:
		D=0
		M=0
		DM=0
		ans=0
		
		for i in range(n):
			if li[i]==1:
				D+=1
			elif li[i]==2:
				M+=1
				DM+=D
			elif li[i]==3:
				ans+=DM
			
			if i-k+1>=0:
				if li[i-k+1]==1:
					D-=1
					DM-=M
				elif li[i-k+1]==2:
					M-=1
		print(ans)
		


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

from collections import Counter

H,W,M = map(int, input().split())
h = [0]*M
w = [0]*M
for i in range(M):
    h[i], w[i] = map(int, input().split())
ch = Counter(h).most_common()
mh = []
mnh = ch[0][1]
for ch1 in ch:
    if mnh == ch1[1]:
        mh.append(ch1[0])
        continue
    else:
        break
    break
cw = Counter(w).most_common()
mw = []
mnw = cw[0][1]
for cw1 in cw:
    if mnw == cw1[1]:
        mw.append(cw1[0])
        continue
    else:
        break
    break
for h1 in mh:
    for w1 in mw:
        if (h1,w1) not in zip(h,w):
            print(mnh+mnw)
            exit()
print(mnh+mnw-1)

### FIXED CODE ###

from collections import defaultdict

H, W, M = map(int, input().split())
h = [0] * M
w = [0] * M

nh = [0] * H  # number of h == i+1
nw = [0] * W  # number of w == i+1
dic = defaultdict(bool)

for i in range(M):
    h[i], w[i] = map(int, input().split())
    h[i] -= 1
    w[i] -= 1
    nh[h[i]] += 1
    nw[w[i]] += 1
    dic["{}-{}".format(h[i],w[i])] = True

mnh = max(nh)
mnw = max(nw)

mh = [i for i, nh1 in enumerate(nh) if nh1 == mnh]
mw = [i for i, nw1 in enumerate(nw) if nw1 == mnw]

for h1 in mh:
    for w1 in mw:
        if not dic["{}-{}".format(h1,w1)]:
            print(mnh + mnw)
            exit()
print(mnh + mnw - 1)
### BUGGY CODE ###

class UnionFind:
    def __init__(self, n, p):
        '木の初期化をする'
        # zero-index
        self.p  = [-1] * n
        self.rank = [1]*n
        # one -index
        self.g  = [set([i]) for i in range(n+1)]
        self.gp = [set([i]) for i in p]

    def find(self, x):
        'x の親を返す'
        if self.p[x] == -1:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def unite(self, x, y):
        'rankの低い親を高い方のの親にする'
        if not self.same(x,y):
            x = self.find(x)
            y = self.find(y)
            if self.rank[x] > self.rank[y]:
                x,y = y,x
            elif self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.g[y+1] = self.g[y+1] | self.g[x+1]
            self.gp[y+1]= self.gp[y+1]| self.gp[x+1]
            self.p[x] = y # x の親を y にする
            return True
        else:
            return False

    def same(self, x, y):
        return self.find(x) == self.find(y)

def main():
    n,m = map(int,input().split())
    p = [0] + list(map(int,input().split()))

    uf = UnionFind(n,p)
    for i in range(m):
        x,y = map(int,input().split())
        uf.unite(x-1,y-1)

    parent = set()
    for i in range(n):
        parent.add(uf.find(i))
    ans = 0
    for i in parent:
        ans += len(uf.g[i+1]) + len(uf.gp[i+1]) - len(uf.g[i+1] | uf.gp[i+1])
    print(ans)
main()


### FIXED CODE ###

class UnionFind:
    def __init__(self, n, p):
        '木の初期化をする'
        # zero-index
        self.p  = [-1] * n
        self.rank = [1]*n

    def find(self, x):
        'x の親を返す'
        if self.p[x] == -1:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def unite(self, x, y):
        'rankの低い親を高い方のの親にする'
        if not self.same(x,y):
            x = self.find(x)
            y = self.find(y)
            if self.rank[x] > self.rank[y]:
                x,y = y,x
            elif self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.p[x] = y # x の親を y にする
            return True
        else:
            return False

    def same(self, x, y):
        return self.find(x) == self.find(y)

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

    uf = UnionFind(n,p)
    for i in range(m):
        x,y = map(int,input().split())
        uf.unite(x-1,y-1)

    ans = 0
    for i,j in enumerate(p):
        ans += uf.same(i, j-1)
    print(ans)
main()
### BUGGY CODE ###

K=int(input())
ans=0
runrun = 0
i =1
while runrun < K:
    if i < 10:
        runrun +=1
        ans = i
    else:
        a = list(map(int,str(i)))
        for j in range(1,len(a)):
            tmp = 0
            if abs(a[j]-a[j-1])<=1:
                tmp +=1
        if tmp == len(a)-1:
            runrun +=1
            ans = i 
    i +=1
print(ans)
          


### FIXED CODE ###

k=int(input())
cand=[[1,2,3,4,5,6,7,8,9]]
for _ in range(9): #上記の操作を9回繰り返せば10^5個以上のルンルン数を列挙できる
 tmp=[]
 for val in cand[-1]:
   if val%10!=0: #末尾が0のときは(末尾-1)を付け加えた数はルンルン数にならない
     tmp.append(val*10+(val%10-1))
   tmp.append(val*10+(val%10))
   if val%10!=9: #末尾が9のときは(末尾+1)を付け加えた数はルンルン数にならない
     tmp.append(val*10+(val%10+1))
 cand.append(tmp)
ans=[]
for i in range(len(cand)):
 for val in cand[i]:
   ans.append(val)
ans=sorted(ans)
print(ans[k-1])
### BUGGY CODE ###

#for _ in range(int(input())):
s = input()
q = int(input())
b=0
for _ in range(q):
    qi = input().split(' ')
    #print(len(qi))
    if(len(qi)==1):
        b=b^1
    else:
        fi = int(qi[1])
        if(fi==1):
            if(b==0):
                s=qi[2]+s
            else:
                s=s+qi[2]
        elif(fi==2):
            if(b==0):
                s=s+qi[2]
            else:
                s=qi[2]+s
if(b==1):
    s=s[::-1]

print(s)
    
            
    
    

### FIXED CODE ###

#for _ in range(int(input())):
s = input()
q = int(input())
b=0
f,l="",""
for _ in range(q):
    qi = input().split(' ')
    #print(len(qi))
    if(len(qi)==1):
        b=b^1
    else:
        fi = int(qi[1])
        if(fi==1):
            if(b==0):
                f=f+qi[2]
            else:
                l=l+qi[2]
        elif(fi==2):
            if(b==0):
                l=l+qi[2]
            else:
                f=f+qi[2]
s = f[::-1]+s+l
if(b==1):
    s=s[::-1]

print(s)
### BUGGY CODE ###

N=int(input())
s_list=[]
for i in range(N):
    s_list.append(input())

s_list2=["".join(sorted(x)) for x in s_list]
c=0
for i in range(len(s_list2)):
    for j in range(i+1,N):
        if s_list2[i]==s_list2[j]:
            c+=1
print(c)

### FIXED CODE ###

N=int(input())
s_list=[]
for i in range(N):
    s_list.append(input())
s_list2=["".join(sorted(x)) for x in s_list]

dic={}
for s in s_list2:
    if s not in dic.keys():
        dic[s]=1
    else:
        dic[s]+=1
    
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

c=0
for x in dic.items():
    if x[1]>=2:
        c+=cmb(x[1],2)
print(c)
### BUGGY CODE ###

n = int(input())
al = list(map(int, input().split()))
ans = []
for i in range(1, n+1):
    ans.append(al.index(i) + 1)
print(*ans)

### FIXED CODE ###

n = int(input())
al = list(map(int, input().split()))
ans = [0] * n
for i in range(n):
    ans[al[i] - 1] = i + 1
print(*ans)
### BUGGY CODE ###

def main():
    s = input()

    len_s = len(s)

    if len_s <=3:
        print(0)
        exit()
    
    count = 0

    for i in range(0,len_s-3):
        for j in range(i+3,len_s):
            if int(s[i:j+1]) % 2019 == 0:
                count += 1
                break

    print(count)

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

    count = 0

    mods = [0] * 2019
    mods[0] = 1
    current = 0
    x = 1
    for s in S:
        current = (current + x * int(s)) % 2019
        count += mods[current % 2019]
        mods[current % 2019] += 1
        x = x * 10 % 2019

    print(count)

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

import sys
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

def main():
    #n = int(stdin.readline().rstrip())
    n,m = map(int, stdin.readline().rstrip().split())
    x = list(map(int, stdin.readline().rstrip().split()))
    #numbers = [[int(c) for c in l.strip().split()] for l in sys.stdin]
    #word = [stdin.readline().rstrip() for _ in range(n)]
    #number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]
    #zeros = [[0] * w for i in range(h)]
    if n>m:
        print(0)
        exit()
    spl = n-1
    sa = [0]*(m-1)
    x.sort()
    for i in range(m-1):
        sa[i] = x[i+1] - x[i]
    for i in range(spl):
        sa.remove(max(sa))
    print(sum(sa))



main()


### FIXED CODE ###

import sys
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

def main():
    #n = int(stdin.readline().rstrip())
    n,m = map(int, stdin.readline().rstrip().split())
    x = list(map(int, stdin.readline().rstrip().split()))
    #numbers = [[int(c) for c in l.strip().split()] for l in sys.stdin]
    #word = [stdin.readline().rstrip() for _ in range(n)]
    #number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]
    #zeros = [[0] * w for i in range(h)]
    if n>m:
        print(0)
        exit()
    spl = n-1
    sa = [0]*(m-1)
    x.sort()
    for i in range(m-1):
        sa[i] = x[i+1] - x[i]
    sa.sort()
    i = m-n
    print(sum(sa[:i]))



main()