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

import sys
input = sys.stdin.readline
N = int(input())
S = input()
Q = int(input())

ide_ele = set()

def segfunc(x,y):
    return x|y

def init(init_val):
    #set_val
    for i in range(N):
        seg[i+num-1]=set((init_val[i]))
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    if x in seg[k]: return
    seg[k] = set((x))
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#num:n以上の最小の2のべき乗
num =2**(N-1).bit_length()
seg=[ide_ele]*2*num

init(S)

for _ in range(Q):
    t, a, b = input().split()
    if t == '1':
        a = int(a)
        update(a-1, b)
    else:
        a, b = int(a)-1, int(b)
        print(len(query(a,b)))


### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
S = input()
Q = int(input())

ide_ele = 0

def segfunc(x,y):
    return x|y

def init(init_val):
    #set_val
    for i in range(N):
        seg[i+num-1]=1<<(ord(init_val[i])-ord('a'))
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    x = 1<<(ord(x)-ord('a'))
    if x == seg[k]: return
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#num:n以上の最小の2のべき乗
num =2**(N-1).bit_length()
seg=[ide_ele]*2*num

init(S)

for _ in range(Q):
    t, a, b = input().split()
    if t == '1':
        a = int(a)
        update(a-1, b)
    else:
        a, b = int(a)-1, int(b)
        print(bin(query(a,b)).count('1'))
### BUGGY CODE ###

import math
import collections
def f(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n = n//f
        else:f += 2
    if n != 1:
        a.append(n)
    return a

n = int(input())
s = set()
d = dict()
for i in range(n):
    c = collections.Counter(f(int(input())))
    for x,y in zip(c.keys(),c.values()):

        if x not in s :
            s.add(x)
            d[x] = y
        else:
            d[x] = max(y,d[x])
b = [ x**y for x,y in zip(d.keys(),d.values())]
ans = 1
for i in b:
    ans *= i
print(ans)

### FIXED CODE ###

import fractions
n = int(input())
ans = 1
for i in range(n):
    a = int(input())
    ans = ans // fractions.gcd(ans,a) * a
print(ans)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

MAX = 10**18
MIN = -MAX

import numpy as np

def main():
  n, k = map(int, input().strip().split())
  As = list(map(int, input().strip().split()))
  As.sort()
  
  def count(l, r, a, x):
    mid = (l+r)//2
    if a > 0:
      if r - l <=1:
        return r - (1 if a**2 <= x else 0)
      if a * As[mid] <= x:
        return count(mid, r, a, x)
      else:
        return count(l, mid, a, x)
    else:
      if r - l <=1:
        return n - r - (1 if a**2 <= x else 0)
      if a * As[mid] <= x:
        return count(l, mid, a, x)
      else:
        return count(mid, r, a, x)
      
  def bs(l, r):
    mid = (l+r) // 2
    if r - l <= 1:
      return r
    tot = 0
    for A in As:
      tot += count(-1, n, A, mid)
    tot //= 2
    if tot < k:
      return bs(mid, r)
    else:
      return bs(l, mid)
  print(bs(MIN-1, MAX+1))
    
if __name__=='__main__':
  main()



### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

MAX = 10**18
MIN = -MAX

def main():
  n, k = map(int, input().strip().split())
  As = list(map(int, input().strip().split()))
  As.sort()

  Ans, Aps, Azs = [], [], []
  for A in As:
    if A > 0:
      Aps.append(A)
    elif A == 0:
      Azs.append(A)
    else:
      Ans.append(A)

  def count(xs, ys, ub):
    c = 0
    r = len(ys) - 1
    for l in range(len(xs)):
      while  r >= 0 and xs[l] * ys[r] > ub:
        r -= 1
      c += r+1
    return c 

  def bs(l, r):
    while True:
      mid = (l+r) // 2
      if r - l <= 1:
        return r
      
      tot = 0      
      tot += count(Aps, Aps, mid) - sum([1 for A in Aps if A**2 <= mid])
      tot += count(Ans[::-1], Ans[::-1], mid) - sum([1 for A in Ans if A**2 <= mid])
      tot //= 2

      if mid >=0:
        tot += (len(Aps) + len(Ans)) * len(Azs) + (len(Azs) * (len(Azs) - 1)) // 2
      tot += count(Aps[::-1], Ans, mid)
      
      if tot < k:
        l = mid
      else:
        r = mid
  
  print(bs(MIN-1, MAX+1))
    
    
if __name__=='__main__':
  main()
### BUGGY CODE ###


from itertools import permutations, product

N = int(input())
S = list(input())

R_indices = [i for i in range(N) if S[i] == "R"]
G_indices = [i for i in range(N) if S[i] == "G"]
B_indices = [i for i in range(N) if S[i] == "B"]

count = 0
for indices_1, indices_2, indices_3 in permutations([R_indices, G_indices, B_indices]):
    j_idx_prev = -1
    for i in indices_1:
        j_idx = len(indices_2)
        ng = j_idx_prev
        while j_idx - ng > 1:
            m = (j_idx + ng) // 2
            if i < indices_2[m]:
                j_idx = m
            else:
                ng = m

        j_idx_prev = j_idx - 1
        k_idx_prev = -1
        for j in indices_2[j_idx:]:
            k_idx = len(indices_3)
            ng = k_idx_prev
            while k_idx - ng > 1:
                m = (k_idx + ng) // 2
                if j < indices_3[m]:
                    k_idx = m
                else:
                    ng = m

            k_idx_prev = k_idx - 1
            for k in indices_3[k_idx:]:
                if j - i != k - j:
                    count += 1

print(count)


### FIXED CODE ###

N = int(input())
S = list(input())

r_num = S.count("R")
g_num = S.count("G")
b_num = S.count("B")

count = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        k = j * 2 - i
        if k >= N:
            continue
        si, sj, sk = S[i], S[j], S[k]
        if si != sj and sj != sk and sk != si:
            count += 1

print(r_num * g_num * b_num - count)
### BUGGY CODE ###

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


### FIXED CODE ###

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

import sys
readline = sys.stdin.readline

def main():
	n = int(input())
	s = tuple(input())

	ans = 0
	r = []
	g = []
	b = []
	for i in range(3):
		if s[i] == 'R':
			r.append(i)
		elif s[i] == 'G':
			g.append(i)
		else:
			b.append(i)

	for i in range(3,n):
		if s[i] == 'R':
			r.append(i)
		elif s[i] == 'G':
			g.append(i)
		else:
			b.append(i)

		for j in range(i-2):
			if s[i] == s[j]:
				continue
			elif 'R' not in [s[i],s[j]]:
				for k in r:
					if k - j != i - k and k > j:
						ans += 1
			elif 'G' not in [s[i],s[j]]:
				for k in g:
					if k - j != i - k and k > j:
						ans += 1
			elif 'B' not in [s[i],s[j]]:
				for k in b:
					if k - j != i - k and k > j:
						ans += 1

	print(ans)

if __name__ == '__main__':
	main()


### FIXED CODE ###

import sys
import bisect
readline = sys.stdin.readline

def main():
	n = int(input())
	s = tuple(input())

	ans = 0
	r = []
	g = []
	b = []
	for i in range(3):
		if s[i] == 'R':
			r.append(i)
		elif s[i] == 'G':
			g.append(i)
		else:
			b.append(i)

	for i in range(3,n):
		if s[i] == 'R':
			r.append(i)
		elif s[i] == 'G':
			g.append(i)
		else:
			b.append(i)

		for j in range(i-2):
			if (j-i) % 2 == 0:
				if s[i] == s[j]:
					continue
				elif 'R' not in [s[i],s[j]]:
					ans += bisect.bisect_left(r,i) - bisect.bisect_left(r,j)
					index = bisect.bisect_left(r,j + (i-j)//2 )
					if index < len(r):
						if r[index] == j + (i-j)//2:
							ans -= 1
				elif 'G' not in [s[i],s[j]]:
					ans += bisect.bisect_left(g,i) - bisect.bisect_left(g,j)
					index = bisect.bisect_left(g,j + (i-j)//2 )
					if index < len(g):
						if g[index] == j + (i-j)//2:
							ans -= 1
				elif 'B' not in [s[i],s[j]]:
					ans += bisect.bisect_left(b,i) - bisect.bisect_left(b,j)
					index = bisect.bisect_left(b,j + (i-j)//2 )
					if index < len(b):
						if b[index] == j + (i-j)//2:
							ans -= 1
			else:
				if s[i] == s[j]:
					continue
				elif 'R' not in [s[i],s[j]]:
					ans += bisect.bisect_left(r,i) - bisect.bisect_left(r,j)

				elif 'G' not in [s[i],s[j]]:
					ans += bisect.bisect_left(g,i) - bisect.bisect_left(g,j)

				elif 'B' not in [s[i],s[j]]:
					ans += bisect.bisect_left(b,i) - bisect.bisect_left(b,j)


	print(ans)

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

h,w = map(int,input().split())
s=[]
for i in range(h):
    s.append(list(input()) )

l=[[0]*w for _ in range(h)]
for i in range(h):
    count=0
    for j in range(w):
        if s[i][j] ==".":
            count+=1
        else:
            count=0
        l[i][j]=count
        
r=[[0]*w for _ in range(h)]
for i in range(h-1,-1,-1):
    count=0
    for j in range(w-1,-1,-1):
        if s[i][j] ==".":
            count+=1
        else:
            count=0
        r[i][j]=count
                
d=[[0]*w for _ in range(h)]
for j in range(w-1,-1,-1):
    count=0
    for i in range(h-1,-1,-1):
        if s[i][j] ==".":
            count+=1
        else:
            count=0
        d[i][j]=count
                
u=[[0]*w for _ in range(h)]
for j in range(w):
    count=0
    for i in range(h):
        if s[i][j] ==".":
            count+=1
        else:
            count=0
        u[i][j]=count

ans=[[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        ans[i][j] = l[i][j]+ r[i][j]+ u[i][j]+ d[i][j]-3
print( max( max(ans[i]) for i in range(h)) )

### FIXED CODE ###

#d

def main():
    h,w = map(int,input().split())
    s=[]
    for i in range(h):
        s.append(list(input()) )
    
    l=[[0]*w for _ in range(h)]
    for i in range(h):
        count=0
        for j in range(w):
            if s[i][j] ==".":
                count+=1
            else:
                count=0
            l[i][j]=count
            
    r=[[0]*w for _ in range(h)]
    for i in range(h-1,-1,-1):
        count=0
        for j in range(w-1,-1,-1):
            if s[i][j] ==".":
                count+=1
            else:
                count=0
            r[i][j]=count
                    
    d=[[0]*w for _ in range(h)]
    for j in range(w-1,-1,-1):
        count=0
        for i in range(h-1,-1,-1):
            if s[i][j] ==".":
                count+=1
            else:
                count=0
            d[i][j]=count
                    
    u=[[0]*w for _ in range(h)]
    for j in range(w):
        count=0
        for i in range(h):
            if s[i][j] ==".":
                count+=1
            else:
                count=0
            u[i][j]=count
    
    ans=[[0]*w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            ans[i][j] = l[i][j]+ r[i][j]+ u[i][j]+ d[i][j]-3
    print( max( max(ans[i]) for i in range(h)) )

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

H, W = map(int, input().split())
def sc(s):
    b = None
    nc = 0
    kk = []
    for i, c in enumerate(s):
        if c == ".":
            if c == b:
                nc += 1
            else:
                si = i
        else:
            if b == ".":
                ei = i
                kk.append((si, ei))
        b = c
    return kk
d = []
d2 = [[0] * W for _ in range(H)]
d3 = [[0] * W for _ in range(H)]
for h in range(H):
    s = input().strip() + "#"
    d.append(s)
    r = sc(s)
    for ss, tt in r:
        for i in range(ss, tt):
            d2[h][i] = tt - ss
for i in range(W):
    s = ""
    for j in range(H):
        s += d[j][i]
    s += "#"
    r = sc(s)
    for ss, tt in r:
        for k in range(ss, tt):
            d3[k][i] = tt - ss
r = 0
for i in range(H):
    for j in range(W):
        r = max(r, d2[i][j] + d3[i][j]-1)
print(r)


### FIXED CODE ###

H, W = map(int, input().split())
import sys
input = sys.stdin.readline
def sc(s):
    b = None
    nc = 0
    kk = [0]*len(s)
    for i, c in enumerate(s):
        if c == ".":
            if c == b:
                nc += 1
            else:
                si = i
        else:
            if b == ".":
                for j in range(si, i):
                    kk[j] = i - si
            nc = 0
        b = c
    return kk
d = []
d2 = []
d3 = []
for h in range(H):
    s = input().strip()
    d.append(s)
    d2.append(sc(s+"#"))

d = list(zip(*d))
for s in d:
    d3.append(sc("".join(s)+"#"))
r = 0
for i in range(H):
    for j in range(W):
        r = max(r, d2[i][j] + d3[j][i]-1)
print(r)
### BUGGY CODE ###

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

INF = float('inf')
dp = [INF] * (N)
dp[0] = 0

for i in range(1,N):
    for j in range(max(0,i-K),i):
        # print(h[j],':',h[i])
        dp[i] = min(dp[i], dp[j]+abs(h[j]-h[i]))
    # print(dp)
print(dp[-1])


### FIXED CODE ###

import numpy as np

N,K = map(int, input().split())
h = np.array(list(map(int, input().split())))
dp = np.full(N,10**10)
dp[0] = 0
for i in range(1,N):
    start = max(0,i-K)
    dp[i] = np.min(dp[start:i]+np.abs(h[i]-h[start:i]))
print(int(dp[-1]))
### BUGGY CODE ###

f = lambda: list(map(int,input().split()))

n,m = f()
a = f()
a = [sum(a[:i])%m for i in range(n+1)]
ans = 0
from collections import Counter
for v in Counter(a).values():
    ans += v*(v-1)//2
print(ans)

### FIXED CODE ###

f = lambda: list(map(int,input().split()))

n,m = f()
a = f()
b = [0]
for i in range(n):
    b.append((b[-1]+a[i])%m)

ans = 0
from collections import Counter
for v in Counter(b).values():
    ans += v*(v-1)//2
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
h_list = list(map(int, input().split()))
costs = [0] * n
costs[1] = abs(h_list[0] - h_list[1])
start = 0
for i in range(2, n):
    tmp = []
    v = h_list[i]
    start = max(0, i-k)
    for l in range(start, i):
        tmp.append(abs(v - h_list[l])+costs[l])
        if abs(v - h_list[l]) == 0:
            break
    costs[i] = min(tmp)
print(costs[-1])


### FIXED CODE ###

n, k = map(int, input().split())
h_list = list(map(int, input().split()))
costs = [0] * n
costs[1] = abs(h_list[0] - h_list[1])
start = 0
for i in range(2, n):
    tmp = []
    v = h_list[i]
    start = max(0, i-k)
    costs[i] = min(abs(v - h_j) + c for h_j, c in zip(h_list[start:i], costs[start:i]))
    # for l in range(start, i):
    #     tmp.append(abs(v - h_list[l])+costs[l])
    #     if abs(v - h_list[l]) == 0:
    #         break
    # costs[i] = min(tmp)
print(costs[-1])
### BUGGY CODE ###

def resolve():
    import collections
    n, m = map(int, input().split())
    hw = [[0]*(n+1) for _ in range(n+1)]
    for i in range(m):
        a, b = map(int, input().split())
        hw[a][b] = 1
        hw[b][a] = 1
    dis = [0] * (n+1)
    arr = [-1] * (n+1)
    que = collections.deque([1])
    while len(que) != 0:
        a = que.popleft()
        test = hw[a]
        for i in range(len(test)):
            if test[i] == 1:
                if arr[i] == -1:
                    arr[i] = a
                    que.append(i)
    if 0 in arr[2:]:
        print("No")
    else:
        print("Yes")
        for i in range(2, len(arr)):
            print(arr[i])
 
resolve()

### FIXED CODE ###

def resolve():
    import collections
    n, m = map(int, input().split())
    hw = [[0] for _ in range(n+1)]
    for i in range(m):
        a, b = map(int, input().split())
        hw[a].append(b)
        hw[b].append(a)

    dis = [0] * (n+1)
    arr = [-1] * (n+1)
    que = collections.deque([1])
    while len(que) != 0:
        a = que.popleft()
        test = hw[a]
        for i in range(len(test)):
            if test[i] != 0:
                goal = test[i]
                if arr[goal] == -1:
                    arr[goal] = a
                    que.append(goal)
    if 0 in arr[2:]:
        print("No")
    else:
        print("Yes")
        for i in range(2, len(arr)):
            print(arr[i])
resolve()
### BUGGY CODE ###

N = int(input())

l = len(str(N))
a = 0

for i in range(l):
  a += N % 10
  N = N // 10
  
if a % 9 == 0:
  print("Yes")

else:
  print("No")

### FIXED CODE ###

N = int(input())

l = str(N)
A = list(map(int, l))
a = sum(A)
  
if a % 9 == 0:
  print("Yes")

else:
  print("No")
### BUGGY CODE ###

S = input()
p = 10 ** 9 + 7
DP = [[0 for j in range(4)] for i in range(len(S) + 1)]
DP[len(S)][3] = 1
for i in range(len(S) - 1, -1, -1):
  for j in range(3, -1, -1):
    if j == 3:
      DP[i][j] = DP[i + 1][3] * (3 if S[i] == '?' else 1)
    else:
      DP[i][j] += DP[i + 1][j + 1] * (1 if S[i] == chr(65 + j) or S[i] == '?' else 0)
      DP[i][j] += DP[i + 1][j] * (3 if S[i] == '?' else 1)
      DP[i][j] % p
print(DP[0][0] % p)

### FIXED CODE ###

S = input()
p = 10 ** 9 + 7
DP = [0, 0, 0, 1]
dp = [0] * 4
for i in range(len(S) - 1, -1, -1):
  for j in range(3, -1, -1):
    if j == 3:
      dp[j] = DP[3] * (3 if S[i] == '?' else 1) % p
    elif S[i] == '?':
      dp[j] = (3 * DP[j] + DP[j + 1]) % p
    elif S[i] == chr(65 + j):
      dp[j] = (DP[j] + DP[j + 1]) % p
    else:
      dp[j] = DP[j]
  DP = [x for x in dp]
print(DP[0] % p)
### BUGGY CODE ###

H, W = map(int, input().split())
S = [input() for _ in range(H)]

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        else:
            cnt = 1 # 光の数 自分も含む

            flg = True
            k = 1
            while flg:
                if i-k < 0:
                    flg = False
                    break
                else:
                    if S[i-k][j] == '#':
                        flg = False
                        break
                    else:
                        cnt += 1
                k += 1

            flg = True
            k = 1
            while flg:
                if j-k < 0:
                    flg = False
                    break
                else:
                    if S[i][j-k] == '#':
                        flg = False
                        break
                    else:
                        cnt += 1
                k += 1

            flg = True
            k = 1
            while flg:
                if i+k >= H:
                    flg = False
                    break
                else:
                    if S[i+k][j] == '#':
                        flg = False
                        break
                    else:
                        cnt += 1
                k += 1

            flg = True
            k = 1
            while flg:
                if j+k >= W:
                    flg = False
                    break
                else:
                    if S[i][j+k] == '#':
                        flg = False
                        break
                    else:
                        cnt += 1
                k += 1

            ans = max(cnt, ans)

print(ans)


### FIXED CODE ###

import numpy as np
H, W = map(int, input().split())
S = np.array([list(input()) for _ in range(H)]) == '.'
us = np.zeros((H,W), dtype=int)    # .の連続数を格納用
ds = np.zeros((H,W), dtype=int)    # .の連続数を格納用
ls = np.zeros((H,W), dtype=int)    # .の連続数を格納用
rs = np.zeros((H,W), dtype=int)    # .の連続数を格納用

for h in range(1,H):
    us[h, :] = (us[h-1, :] + 1) * S[h-1, :]
for h in range(H-2, -1, -1):
    ds[h, :] = (ds[h+1, :] + 1) * S[h+1, :]
for w in range(1,W):
    ls[:, w] = (ls[:, w-1] + 1) * S[:, w-1]
for w in range(W-2, -1, -1):
    rs[:, w] = (rs[:, w+1] + 1) * S[:, w+1]

ans = ((us + ds + ls + rs)*S).max() + 1
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
s = input()
for i in range(m):
  l, r = map(int, input().split())
  print(s[l-1:r].count('AC'))

### FIXED CODE ###

import bisect
n, q = map(int, input().split())
s = input()
t = []
for i in range(n-1):
  if s[i:i+2] == "AC":
    t.append(i+1)
for j in range(q):
  l, r = map(int, input().split())
  x = bisect.bisect_left(t, l)
  y = bisect.bisect_right(t, r-1)
  print(y-x)
### BUGGY CODE ###

def func(s,x):
    last=[0]*26
    score=0
    for i,v in enumerate(x,1):
        last[v]=i
        c=0
        for j in range(26):
            c+=s[j]*(i-last[j])
        score+=s[i*26+v]-c
    return score
def main():
    d,*s=map(int,open(0).read().split())
    x=[t-1for t in s[26*-~d:d*27+26]]
    for d,q in zip(*[iter(s[27*-~d:])]*2):
        x[d-1]=q-1
        print(func(s,x))
main()

### FIXED CODE ###

from numba import njit
from numpy import int64
@njit('i8(i8[:],i8[:])',cache=True)
def func(s,x):
    last=[0]*26
    score=0
    for i,v in enumerate(x,1):
        last[v]=i
        c=0
        for j in range(26):
            c+=s[j]*(i-last[j])
        score=score+s[i*26+v]-c
    return score
def main():
    d,*s=map(int,open(0).read().split())
    s=int64(s)
    x=s[26*-~d:d*27+26]-1
    for d,q in s[27*-~d:].reshape(-1,2):
        x[d-1]=q-1
        print(func(s,x))
main()
### BUGGY CODE ###

S=input()

N=len(S)
d={}
for i in range(2019):
    d[i]=0

d[0] = 1

for i in range(N):
    s=S[N-1-i:]
    d[int(s)%2019]+=1


ans = 0
for k in d.keys():
    v = d[k]
    if v > 1:
        ans += v*(v-1)//2
print(ans)

### FIXED CODE ###

S=input()

N=len(S)
d={}
for i in range(2019):
    d[i]=0

d[0] = 1

mod=0
dig=1

for i in range(N):
    #s=S[N-1-i:]
    #d[int(s)%2019]+=1
    mod += dig * int(S[N-1-i])
    mod %= 2019
    d[mod] += 1
    dig *= 10
    dig %= 2019


ans = 0
for k in d.keys():
    v = d[k]
    if v > 1:
        ans += v*(v-1)//2
print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
lst = []
lst2 = []
lst3 = []

for _ in range(M):
  lst.append(list(map(int,input().split())))

#print(lst)

for i in range(M):
  for j in range(min(lst[i]),max(lst[i])+1):
    lst2.append(j)

#print(lst2)

for k in range(1,N+1):
  lst3.append(lst2.count(k))
  
#print(lst3)

print(lst3.count(M))



### FIXED CODE ###

N,M = map(int, input().split())
B = []
C = []

for _ in range(M):
  tmp1,tmp2 = map(int,input().split())
  B.append(tmp1)
  C.append(tmp2)

p = max(B)
q = min(C)
res = q - p + 1
if res < 0:
  res = 0
print(res)
### BUGGY CODE ###

import itertools

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

a = list(itertools.combinations(range(1,n+1),3))

ans = 0
for i in a:
    if (s[i[0]-1] != s[i[1]-1] and  s[i[2]-1] != s[i[1]-1] and  s[i[0]-1] != s[i[2]-1] and (i[2]-i[1] != i[1] - i[0])):
        #print(i)
        ans +=1

print(ans)

### FIXED CODE ###

import itertools
n = int(input())
s = str(input())
r = {}
b = {}
g = {}
for i in range(len(s)):
    if s[i] == 'R':
        r[i+1] = s[i]
    elif s[i] == 'B':
        b[i+1] = s[i]
    else:
        g[i+1] = s[i]
ans = len(r) * len(b) * len(g)
for i in r.keys():
    for j in b.keys():
        diff = abs(j-i)
        minb = min(i,j)-diff
        maxb = max(i,j)+diff
        if maxb in g.keys():
            ans -= 1
        if minb in g.keys():
            ans -= 1
        if((i+j)%2==0):
            if((i+j)//2 in g.keys()):
                ans -=1
print(ans)