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

import sys
from functools import reduce
from math import gcd

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    
    pairwise = True
    used = [False] * (max(A) + 1)
    
    for a in A:
        for i in range(2, int(a ** 0.5) + 1):
            if a % i == 0:
                if used[i]:
                    pairwise = False
                else:
                    used[i] = True
                    while a % i == 0:
                        a //= i
        if a != 1:
            if used[a]:
                pairwise = False
                break
            else:
                used[a] = True


    g = reduce(gcd, A)

    if pairwise:
        print('pairwise coprime')
    else:
        if g == 1:
            print('setwise coprime')
        else:
            print('not coprime')


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from functools import reduce
from math import gcd

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    used = [False] * (max(A) + 1)
    pairwise = True
    for a in A:
        for i in range(2, int(a ** 0.5) + 1):
            if a % i == 0:
                if used[i]:
                    pairwise = False
                else:
                    used[i] = True
                    while a % i == 0:
                        a //= i
        if a != 1:
            if used[a]:
                pairwise = False
                break
            else:
                used[a] = True


    g = reduce(gcd, A)

    if pairwise:
        print('pairwise coprime')
    else:
        if g == 1:
            print('setwise coprime')
        else:
            print('not coprime')


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

N, Q = map(int, input().split())
S = input()

for _ in range(0, Q):
    l, r = map(int, input().split())
    sub = S[l-1:r]
    print(sub.count('AC'))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()

hit = [0] * N

for i in range(0, N - 1):
    hit[i + 1] = hit[i]

    if S[i:i+2] == 'AC':
        hit[i + 1] += 1

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

import sys
input = sys.stdin.readline
n, m = map(int, input().split())

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

for i in range(m):
  a, b = map(int, input().split())
  c = 0
  for j in list(map(int, input().split())):
    c += 1<<(j-1)
  
  for k in range(1<<n):
    dp[k|c] = min(dp[k|c], dp[k]+a)
    
if dp[-1] == float('inf'):
  print(-1)
else:
  print(dp[-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
n, m = map(int, input().split())

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

for i in range(m):
  a, b = map(int, input().split())
  c = 0
  for j in list(map(int, input().split())):
    c += 1<<(j-1)
  
  for k in range(1<<n):
    dp[k|c] = min(dp[k|c], dp[k]+a)
    
if dp[-1] == float('inf'):
  print(-1)
else:
  print(dp[-1])
### BUGGY CODE ###

n,m,k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

counter = 0
ans = 0

for i in range(n+1):
    if sum(A[:i])>k:
        break
    for j in range(m+1):
        if sum(A[:i])+sum(B[:j])<=k:
            ans = max(ans, i+j)
        else:
            break
            
print(ans)

### FIXED CODE ###

import bisect

n,m,k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A_cum = [0]
B_cum = [0]

for i in range(n):
  A_cum.append(A_cum[i]+A[i])
  
for i in range(m):
  B_cum.append(B_cum[i]+B[i])

ans = 0  
for i in range(n+1):
  rest = k-A_cum[i]
  if rest<0:
    continue
  
  ans = max(ans, bisect.bisect_right(B_cum, rest)-1+i)
  
print(ans)
### BUGGY CODE ###

n,q =map(int,input().split())
s=input()
p=[[int(j) for j in input().split()] for _ in range(q)]
for _ in range(q):
    print(s[p[_][0]-1:p[_][1]].count("AC"))

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
count=[0]*N
for i in range(1,N):
    count[i]+=count[i-1]
    if S[i-1:i+1]=="AC":count[i]+=1
for i in range(Q):
    l,r=map(int,input().split())
    print(count[r-1]-count[l-1])
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
B_C = [list(map(int, input().split())) for j in range(M)]

B_C = sorted(B_C, key=lambda x:x[1], reverse=True)

D = []
for j in range(M):
    D += [B_C[j][1]] * B_C[j][0]

A.sort()

for i in range(N):
    if A[i] < D[i]:
        A[i] = D[i]
    else:
        break
    if i == len(D) - 1:
        break

print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
B_C = [list(map(int, input().split())) for j in range(M)]

B_C = sorted(B_C, key=lambda x:x[1], reverse=True)

B = [B_C[j][0] for j in range(M)]
C = [B_C[j][1] for j in range(M)]

D = []
for j in range(M):
    D += [C[j]] * B[j]
    if len(D) >= N:
        break

A.sort()

for i in range(N):
    if A[i] < D[i]:
        A[i] = D[i]
    else:
        break
    if i == len(D) - 1:
        break

print(sum(A))
### BUGGY CODE ###

def E(i,y):
    if i==1:
        return 5*y
    else:
        return (2*i+1)*y

def ceil(a,b):
    return -((-a)//b)
N,X=map(int,input().split())
x=[int(i) for i in input().split()]
a=[0]
for i in range(N):
    a.append(a[-1]+x[i])
ans=10**50
for k in range(1,N+1):
    tmp=(N+k)*X
    for i in range(N//k):
        tmp+=E(i+1,a[N-i*k]-a[N-i*k-k])
        #print(k,i,tmp)
    if N%k!=0:
        tmp+=E(N//k+1,a[N-(N//k)*k])
    #print(tmp)
    if ans>tmp:
        ans=tmp
print(ans)

### FIXED CODE ###

def E(i,y):
    if i==1:
        return 5*y
    else:
        return (2*i+1)*y

def ceil(a,b):
    return -((-a)//b)
N,X=map(int,input().split())
x=[int(i) for i in input().split()]
a=[0]
for i in range(N):
    a.append(a[-1]+x[i])
ans=10**50
for k in range(1,N+1):
    tmp=(N+k)*X
    for i in range(N//k):
        tmp+=E(i+1,a[N-i*k]-a[N-i*k-k])
        #print(k,i,tmp)
    if N%k!=0:
        tmp+=E(N//k+1,a[N-(N//k)*k])
    #print(tmp)
    if ans>tmp:
        ans=tmp
print(ans)
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_left, bisect_right

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
A = LIST()

# b = A[K:]

B = []
tmp = 1
for a in A[:K]:
    tmp *= a
for i in range(N - K):
    tmp2 = tmp / A[i] * A[K + i]
    if tmp < tmp2:
        print("Yes")
    else:
        print("No")
    # print(tmp, tmp2)
    tmp = tmp2


### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_left, bisect_right

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
A = LIST()

# b = A[K:]

B = []
tmp = 1
# for a in A[:K]:
#     tmp *= a
tmp = 1
for i in range(N - K):
    tmp2 = tmp / A[i] * A[K + i]
    if tmp < tmp2:
        print("Yes")
    else:
        print("No")
    # print(tmp, tmp2)
    tmp = 1
### BUGGY CODE ###

n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
dp=[0]*n
if 1 not in a:
    dp[0]=1
else:
    dp[0]=0
for i in range(1,n):
    if i+1 in a:
        continue
    if i==1:
        dp[i]=dp[i-1]+1
        continue
    dp[i]=dp[i-1]+dp[i-2]
print(dp[-1]%((10**9)+7))

### FIXED CODE ###

n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
dp=[None]*(n+1)
dp[0]=1
dp[1]=1
if 1 in a:
    dp[1]=0
for i in a:
    dp[i]=0
for i in range(2,n+1):
    if dp[i]!=0 :
        dp[i]=dp[i-1]+dp[i-2]
print(dp[-1]%(10**9+7))
### BUGGY CODE ###

x,y,z,k = map(int,input().split())
A = list(map(int , input().split()))
B = list(map(int , input().split()))
C = list(map(int , input().split()))
A = sorted(A,reverse = True)
B = sorted(B,reverse = True)
C = sorted(C,reverse = True)
AB = []
ABC = []
for i in A:
        for j in B:
                AB.append(i+j)
AB.sort(reverse = True)
AB = AB[:k]
for i in range(min(k,len(AB))):
        for j in range(z):
                ABC.append(AB[i]+C[j])
ABC.sort(reverse = True)
for i in range(k):
        print(ABC[i])

### FIXED CODE ###

x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
lisa.sort(reverse=True)
lisb.sort(reverse=True)
lisc.sort(reverse=True)
an = []
ans = []
for num in lisb:
    for nu in lisa:
        an.append(num+nu)
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for num in lisc:
    for nu in an:
        ans.append(num+nu)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###


if __name__ == '__main__':
    n,m = list(map(int, input().split()))
    a = list(map(int, input().split()))
    a.sort()
    for i in range(m):
        b, c = list(map(int, input().split()))
        for j in range(b):
            if(a[j] < c):
                a[j] = c
        a.sort()

    print(sum(a))


### FIXED CODE ###


if __name__ == '__main__':
    n,m = list(map(int, input().split()))
    a = list(map(int, input().split()))
    bc = []
    for i in range(m):
        bc.append(list(map(int, input().split())))

    bc.sort(key=lambda x: x[1], reverse=True)
    a.sort()

    bcn = 0
    for i in range(n):
        if(a[i] < bc[bcn][1]):
            a[i] = bc[bcn][1]
            bc[bcn][0] -= 1
            if(bc[bcn][0] == 0):
                bcn += 1
                if(bcn == m):
                    break

    print(sum(a))
### BUGGY CODE ###

h,w=map(int,input().split())

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

route={i:10**3 for i in range(10)}
route[1]=0
route[-1]=0
nonFixPosi=set([0,2,3,4,5,6,7,8,9])
FixPosi=set([1])

while len(nonFixPosi)>0:
  for i in nonFixPosi:
    temp=[route[i]]
    for j in FixPosi:
      temp.append(r[i][j]+route[j])
    route[i]=min(temp)
  
  minKey=[]
  minValue=10*4
  for i in nonFixPosi:
    if route[i]==minValue:
      minKey.append(i)
    elif route[i]<minValue:
      minKey=[i]
      minValue=route[i]
  for item in minKey:
    nonFixPosi.remove(item)
    FixPosi.add(item)
  #print(FixPosi)
#print(route)

result=0
for _ in range(h):
  k=list(map(int,input().split()))
  for item in k:
    result+=route[item]
    
print(result)


### FIXED CODE ###

import collections

h,w=map(int,input().split())

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

route={i:10**3 for i in range(10)}
route[1]=0
nonFixPosi=set([0,2,3,4,5,6,7,8,9])
FixPosi=set([1])

for _ in range(11):
  for i in nonFixPosi:
    temp=[route[i]]
    for j in FixPosi:
      temp.append(r[i][j]+route[j])
    route[i]=min(temp)
  
  minKey=[]
  minValue=10**4
  for i in nonFixPosi:
    if route[i]==minValue:
      minKey.append(i)
    elif route[i]<minValue:
      minKey=[i]
      minValue=route[i]
  for item in minKey:
    nonFixPosi.remove(item)
    FixPosi.add(item)
  if len(nonFixPosi)<=0:
    break
    
result=[]
for _ in range(h):
  result+=list(map(int,input().split()))
k=collections.Counter(result)
#print(k)
val=0
for i in range(10):
  val+=k[i]*route[i]

print(val)
### BUGGY CODE ###

L, R = map(int, input().split())
ans = []

def calc_mod(x, y):
    return (x%2019) * (y%2019) % 2019

for i in range(L, R):
    for j in range(i+1, R+1):
        ans.append(calc_mod(i, j))

print(min(ans))

### FIXED CODE ###

import sys
L, R = map(int, input().split())
ans = []

def calc_mod(x, y):
    return x * y % 2019

left = L % 2019
right = R % 2019

if R-L > 2019:
    print(0)
    sys.exit(0)

elif left > right:
    print(0)
    sys.exit(0)

elif left==0 or right==0:
    print(0)
    sys.exit(0)

for i in range(left, right):
    for j in range(i+1, right+1):
        ans.append(calc_mod(i, j))

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

n,k,*a = map(int,open(0).read().split())
c = [0]
visit = [False]*n
visit[0] = True
for i in range(n):
  nt = a[c[-1]]-1
  if visit[nt]:
    ws = c.index(nt)
    wst = c[:ws]
    wrt = c[ws:]
    wr = len(wrt)
  else:
    c.append(nt)
    visit[nt] = True
if ws > k:
  ans = wst[k]
else:
  ans = wrt[(k-ws)%wr]
print(ans+1)

### FIXED CODE ###

def main():
  n,k,*a = map(int,open(0).read().split())
  c = [0]
  visit = [False]*n
  visit[0] = True
  for i in range(n):
    nt = a[c[-1]]-1
    if visit[nt]:
      ws = c.index(nt)
      wst = c[:ws]
      wrt = c[ws:]
      wr = len(wrt)
      break
    else:
      c.append(nt)
      visit[nt] = True
  if ws > k:
    ans = wst[k]
  else:
    ans = wrt[(k-ws)%wr]
  print(ans+1)
main()
### BUGGY CODE ###

r,g,b,n = map(int,input().split())
ans = 0
cnt = 0
for i in range(n//r+1):
    ans = 0
    for j in range((n-i*r)//g+1):
        for k in range((n-i*r-j*g)//b+1):
            ans = i*r+j*g+k*b
            if ans == n:
                cnt += 1
print(cnt)

### FIXED CODE ###

r,g,b,n = map(int,input().split())
ans = 0
cnt = 0
for i in range(n//r+1):
    ans = 0
    for j in range((n-i*r)//g+1):
        ans = i*r+j*g
        a = (n-ans)/b
        if a % 1 == 0:
            cnt +=1
print(cnt)
### BUGGY CODE ###


n = int(input())
stl = []
for i in range(n):
    od, st = input().split()
    if od == 'insert':
        stl.append(st)
    else:
        if st in stl:
            print('yes')
        else:
            print('no')

### FIXED CODE ###

n = int(input())
dic = set()

for i in range(n):
    o = input().split()
    if o[0] == 'insert':
        dic.add(o[1])
    elif o[1] in dic:
        print('yes')
    else:
        print('no')
### BUGGY CODE ###

import bisect
N, M = map(int, input().split())
a = []
number = []
flag = 0
for i in range(M):
    A, B = map(int, input().split())
    a.append([A, B])
    a.append([B, A])
    number.append(A)
    number.append(B)
a.sort()
b = a[:]
b.reverse()
one = []
two = []
for i in range(M):
    if a[i][0] == 1:
        one.append(a[i][1])
    else:
        break

for i in range(M):
    if b[i][0] == N:
        two.append(b[i][1])

for i in range(len(one)):
    for j in range(len(two)):
        if one[i] == two[j]:
            flag = 1
            print("POSSIBLE")
            break
    if flag == 1:
        break

if flag == 0:
    print("IMPOSSIBLE")


### FIXED CODE ###

import sys

N, M = map(int, input().split())
ship = [[] for i in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())
    ship[a].append(b)
    ship[b].append(a)

flag = 0
for i in ship[1]:
    if N in ship[i]:
        flag = 1
if flag == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

n = int(input())
targetlist = [i+1 for i in range(n)]
cnt=0
import itertools
for i in itertools.product(targetlist,targetlist,targetlist):
    if (i[0]*i[1])+i[2] == n:
        cnt+=1
print(cnt)

### FIXED CODE ###

n = int(input())
ans = 0
'''
A*B<=N-1となるAとBの組み合わせが何通りあるかを調べること
この考えを導きだせるかが、この問題を解くカギとなる
Cの最小値1を右辺に移項してN-1となっている
不等式となっている点がポイント
Cの最小値1としておけばAとBの組み合わせを全部考えることができる
次に、AとBどちらでも良いが、あるA（もしくはB）が1つの値を決めたときに、
それに対応するB（もしくはA）が何通りあるかを計算して、A（もしくはB）の値をn-1まで
計算して足してあげれば答えとなる
とてもシンプルなコードだけどこれでACとなるはず
'''

for i in range(1,n):
    #print(i, (n-1)//i)
    ans += (n-1)//i
print(ans)
### BUGGY CODE ###

def main(n,k,p):
    res = 0
    #期待値リスト
    kitai = [0]*n
    for i in range(len(p)):
        kitai[i] = (p[i]+1) / 2
    for i in range(k-1,len(p)):
        res = max(res, sum(kitai[i-k+1:i+1]))
    return res

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

### FIXED CODE ###

def main(n,k,p):
    res = 0
    #期待値リスト
    kitai = [0] * n
    ruiseki = [0] * n
    kitai[0] = (p[0] + 1) / 2
    ruiseki[0] = kitai[0]
    if n == 1:
        return kitai[0]
    else:
        for i in range(1, len(p)):
            kitai[i] = (p[i] + 1) / 2
            ruiseki[i] = ruiseki[i-1] + kitai[i]
    for i in range(k-1, len(ruiseki)):
        res = max(res, ruiseki[i] - (ruiseki[i-k] if (i-k) >= 0 else 0))
    return res


n,k = map(int, input().split())
p = list(map(int,input().split()))
print(main(n,k,p))
### BUGGY CODE ###

s = input()
n = len(s)
flag = True
while(flag):
    for i in range(len(s)-1):
        if s[i]!=s[i+1]:
            s = s[:i]+s[i+2:len(s)]
            break
    else:
        flag=False
print(n-len(s))

### FIXED CODE ###

S = input()
stack = []
count = 0
for s in S:
    if (not stack) or stack[-1]==s:
        stack.append(s)
    else:
        stack.pop()
        count += 2
print(count)
### BUGGY CODE ###

n,m=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(m)]
from itertools import combinations
#union-find召喚
par=[-1]*n
def find(x):
    if par[x]<0:
        return x
    else:
        par[x]=find(par[x])
        return par[x] #ここ覚えていなかった
def unite(x,y):
    x=find(x)
    y=find(y)
    if x==y:
        False
    else:
        if par[x]>par[y]:#sizeの大きいほうがxにしたい
            x,y=y,x
        par[x]+=par[y]
        par[y]=x
        return True
def same(x,y):
    return find(x)==find(y)
def size(x):
    return -par[find(x)]
comb=list(combinations(range(n),2))
ans=[]

for i in range(m):
    count=0
    num=m-i-1
    unite(AB[num][0]-1,AB[num][1]-1)
    for kumiawase in comb:
        if same(kumiawase[0],kumiawase[1]):
            count+=1
    ans.append(count)
ans=list(reversed(ans))
for i in range(len(ans)-1):
    print(ans[0]-ans[i+1])
print(ans[0])

### FIXED CODE ###

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

par = [-1] * (n + 1)


def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


def size(x):
    X = find(x)
    return -par[X]


def unite(x, y):
    if find(x) == find(y):
        return False
    X = find(x)
    Y = find(y)
    if size(X) < size(Y):
        x, y = y, x
        X = find(x)
        Y = find(y)
    par[X] += par[Y]
    par[Y] = X
    return True


def is_same(x, y):
    return find(x) == find(y)


def calc(a):
    return a * (a - 1) // 2


goukei = calc(n)
ans = [-1] * (m + 1)
ans[-1] = calc(n)
cnt = 0
AB = [list(map(int, input().split())) for _ in range(m)]
for i in range(m - 1, -1, -1):
    a, b = AB[i]
    if is_same(a, b):
        ans[i] = goukei - cnt
    else:
        A = size(a)
        B = size(b)
        cnt += calc(A + B) - calc(A) - calc(B)
        unite(a, b)
        ans[i] = goukei - cnt
print(*ans[1::], sep="\n")
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left


def solve():
  N = int(input())
  An = [int(input()) for _ in range(N)]
  if N==1:
    return 1
  else:
    ret = [An[0]]
    for a in An[1:]:
      idx = bisect_left(ret,a)
      if idx == 0:
        ret = [a] + ret
      else:
        ret[idx-1] = a
    return len(ret)


print(solve())

### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from collections import deque


def solve():
  N = int(input())
  An = [int(input()) for _ in range(N)]
  if N==1:
    return 1
  else:
    ret = deque([An[0]])
    for a in An[1:]:
      idx = bisect_left(ret,a)
      if idx == 0:
        ret.appendleft(a)
      else:
        ret[idx-1] = a
    return len(ret)


print(solve())
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
edge = {}
edge[0, 1] = min(A[0], A[1])
edge[1, 0] = min(A[0], A[1])
ans = A[0]
max_edge_list = [(0, 1), (1, 0)]
for i in range(2, N):
    x, y = max_edge_list[0]
    ans += edge[(x, y)]
    del edge[(x, y)]
    edge[x, i] = A[i]
    edge[i, y] = A[i]
    max_edge_list.append((x, i))
    max_edge_list.append((i, y))
    max_edge_list.remove((x, y))
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
edge = {}
edge[0, 1] = min(A[0], A[1])
edge[1, 0] = min(A[0], A[1])
ans = A[0]
max_edge_list = [(0, 1), (1, 0)]
idx = 0
for i in range(2, N):
    x, y = max_edge_list[idx]
    ans += edge[(x, y)]
    #del edge[(x, y)]
    edge[x, i] = A[i]
    edge[i, y] = A[i]
    max_edge_list.append((x, i))
    max_edge_list.append((i, y))
    #max_edge_list.pop(0)
    idx += 1
print(ans)
### BUGGY CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
s = input()
s = s.replace('B', '1')
s = s.replace('W', '0')
s = list(s)

# print(s)
cnt = 0
def bsort(a):
    global cnt
    for i in range(len(a)-1):
        for j in range(i, len(a)):
            if int(a[j-1]) > int(a[j]):
                cnt += 1
                a[j-1] = '0'
                a[j] = '1'

bsort(s)
print(cnt)
            



### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
s = input()
# s = s.replace('B', '1')
# s = s.replace('W', '0')
# s = list(s)
index = 0
sum = 0
for e,c in enumerate(s):
    if c == 'W':
        sum += e - index
        index += 1
        

        
# # print(s)
# cnt = 0
# def bsort(a):
#     global cnt
#     for i in range(len(a)-1):
#         for j in range(i, len(a)):
#             if int(a[j-1]) > int(a[j]):
#                 cnt += 1
#                 a[j-1] = '0'
#                 a[j] = '1'

# bsort(s)
print(sum)
### BUGGY CODE ###

from sys import exit

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

S = input()

AC = []
for i in range(len(S) - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        AC.append(i)

ans = []

for i in range(Q):
    li, ri = map(int, input().split())

    count = 0
    for ac in AC:
        if ac < li - 1:
            count += 1
        else:
            break
    for ac in reversed(AC):
        if ri - 1 < ac + 1:
            count += 1
        else:
            break
    print(len(AC) - count)


### FIXED CODE ###

from sys import exit

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

S = input()

AC = [0] * N

c = 0

for i in range(N - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        c += 1
    AC[i + 1] = c

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

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

### FIXED CODE ###

from collections import Counter

s=input()[::-1]
ans=0
lst=[0]
num=0
p=1
for i in s:
    lst.append((int(i)*p+lst[-1])%2019)
    p=p*10%2019

ans=sum(x*(x-1)//2 for x in Counter(lst).values())
print(ans)