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

def main():
    import numpy as np
    s = list(reversed(input()))
    mod = 10**9+7
    memo = [0 for _ in [0]*13]
    m13 = [(10**i) % 13 for i in range(12)]
    memo[0] = 1
    for i in range(len(s)):
        memo2 = np.zeros(13)
        a = m13[i % 12]
        if s[i] == "?":
            list_ = np.array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
        else:
            list_ = np.array([int(s[i])])
        list_ = a*list_ % 13
        for l in list_:
            for j in range(13):
                memo2[(l+j) % 13] += memo[j]
        memo = memo2 % mod
    print(int(memo[5]))


main()

### FIXED CODE ###

s=list(reversed(input()))
mod=10**9+7
memo=[0 for _ in [0]*13]
m13=[(10**i)%13 for i in range(12)]
memo[0]=1
for i in range(len(s)):
    memo2=[0 for _ in [0]*13]
    a=m13[i%12]
    if s[i]=="?":
        list_=[0,1,2,3,4,5,6,7,8,9]
    else:
        list_=[int(s[i])]
    list_=[(a*j)%13 for j in list_]
    for l in list_:
        for j in range(13):
            memo2[(l+j)%13]+=memo[j]
    memo=[j%mod for j in memo2]
print(memo[5])
### BUGGY CODE ###

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

yoko = {}
tate = {}
tate_counter = [0 for i in range(W)]
for h in range(H):
    yoko_counter = 0
    for w in range(W):
        if S[h][w] == '#':
            for i in range(yoko_counter):
                yoko[(h, w - i - 1)] = yoko_counter
            for i in range(tate_counter[w]):
                tate[(h - i - 1, w)] = tate_counter[w]
            yoko_counter = 0
            tate_counter[w] = 0
            continue
        yoko_counter += 1
        tate_counter[w] += 1
    if yoko_counter > 0:
        for i in range(yoko_counter):
            yoko[(h, W - i - 1)] = yoko_counter
for w in range(W):
    if tate_counter[w] > 0:
        for i in range(tate_counter[w]):        
            tate[(H - i - 1, w)] = tate_counter[w]


max_score = 0
for h in range(H):
    for w in range(W):
        if (h,w) in yoko and (h,w) in tate:
            score = yoko[(h,w)] + tate[(h,w)] - 1
            if max_score < score:
                #print(h,w, score)
                max_score = score

print(max_score)


### FIXED CODE ###

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

left = [[-1 for j in range(W)] for i in range(H)]
right = [[W for j in range(W)] for i in range(H)]
up = [[-1 for j in range(W)] for i in range(H)]
down = [[H for j in range(W)] for i in range(H)]

# from left upper to right down
up_wall = [-1 for i in range(W)]
for h in range(H):
    left_wall = -1    
    for w in range(W):
        if S[h][w] == '#':
            left_wall = w
            up_wall[w] = h
        left[h][w] = left_wall
        up[h][w] = up_wall[w]

# from right down to left up
down_wall = [H for i in range(W)]
for h in range(H - 1, -1, -1):
    right_wall = W
    for w in range(W - 1, -1, -1):
        if S[h][w] == '#':
            right_wall = w
            down_wall[w] = h
        right[h][w] = right_wall
        down[h][w] = down_wall[w]

# print(left)
# print(right)
# print(up)
# print(down)

max_score = 0
for h in range(H):
    for w in range(W):
        left_score = (w - left[h][w])
        right_score = (right[h][w] - w)
        up_score = (h - up[h][w])
        down_score = (down[h][w] - h)
        score = left_score + right_score + up_score + down_score - 3
        # print(h, w, score, left_score, right_score, up_score, down_score)
        if max_score < score:
            max_score = score
print(max_score)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
L = [None] * Q
R = [None] * Q
for i in range(Q):
  L[i], R[i] = map(int, input().split())
  print((S[L[i] - 1:R[i]]).count('AC'))


### FIXED CODE ###

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

for i in range(N):
  t[i + 1] = t[i] + S[i:i + 2].count('AC')

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

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

for i in range(M):
  hoge = max(A)
  A[A.index(hoge)] = hoge//2
print(sum(A))

### FIXED CODE ###

import heapq
N,M = map(int,input().split())

A = list(map(int,input().split()))
H = []
for i in A:
  heapq.heappush(H, -int(i))
for i in range(M):
  a = heapq.heappop(H)
  heapq.heappush(H, -(-a//2))
print(-sum(H))
### BUGGY CODE ###

n = int(input())

nlll = []
for i in range(n):
    aaa = int(input())
    if aaa in nlll:
        nlll.remove(aaa)
    else:
        nlll.append(aaa)
        
print(len(nlll))

### FIXED CODE ###

n = int(input())

nlll = {}
    
for i in range(n):
    aaa = int(input())
    if aaa in nlll:
        del nlll[aaa]
    else:
        nlll.update({aaa:1})

sums = 0
for i in nlll.values():
    sums = sums + i
print(sums)
### BUGGY CODE ###

import bisect
from collections import deque

N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
que = deque(A)

for _ in range(M):
    max_value = que.pop()
    bisect.insort_right(que,max_value // 2)

print(sum(que))

### FIXED CODE ###

import heapq
import sys

def input():
    return sys.stdin.readline().strip()

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

    heapq.heapify(A)

    for _ in range(M):
        max_value = heapq.heappop(A) * (-1)
        heapq.heappush(A,max_value//2 * (-1))

    print(sum(A) * (-1))

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

n=int(input())

ans=0

a=[int(input()) for _ in range(n)]

b=sorted(a)

cnt=0
for i,v in enumerate(a):
    if i%2 != (b.index(v))%2:
        cnt+=1
print(cnt//2)

### FIXED CODE ###

n=int(input())

ans=0

a=[]
b=[]

for _ in range(n):
    x=int(input())
    a.append(x)
    b.append(x)
b.sort()

dic={}
for i,v in enumerate(b):
    dic[v]=i%2

cnt=0
for i,v in enumerate(a):
    if i%2 != dic[v]:
        cnt+=1
print(cnt//2)
### BUGGY CODE ###

L, R = map(int, input().split())
mn = 0
res = 2*(10**9)
for i in range(L, R + 1):
    for j in range(L, R + 1):
        if i == j: continue
        mn = (i * j) % 2019
        if mn < res:
            res = mn
print(res)

### FIXED CODE ###

L, R = map(int, input().split())

res = 2 * (10 ** 9)
if R - L > 2019:
	print(0)
else:
	for i in range(L, R + 1):
		for j in range(i + 1, R + 1):
			mod = (i * j) % 2019
			if mod < res: res = mod
	print(res)
### BUGGY CODE ###

import sys

def wf(d):
  for i in range(n):
    for j in range(n):#start
      for k in range(n):#end
        d[j][k]=min(d[j][k], d[j][i] + d[i][k])
  return d

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

d=[[sys.maxsize]*(n) for _ in range(n)]
e=[[sys.maxsize]*(n) for _ in range(n)]
for i in range(n):
  d[i][i] = 0
  e[i][i] = 0

for _ in range(m):
  a,b,c = map(int, input().split())
  d[a-1][b-1]=c
  d[b-1][a-1]=c

d=wf(d)
for i in range(n):
  for j in range(n):
    if d[i][j] <= l:
      e[i][j] = 1

e=wf(e)

q=int(input())
for _ in range(q):
  s,t = map(int, input().split())
  if e[s-1][t-1] == sys.maxsize:
    print(-1)
  else:
    print(e[s-1][t-1]-1)


### FIXED CODE ###

import sys
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

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

d=[[sys.maxsize]*(n) for _ in range(n)]
e=[[sys.maxsize]*(n) for _ in range(n)]
for i in range(n):
  d[i][i] = 0
  e[i][i] = 0

for _ in range(m):
  a,b,c = map(int, input().split())
  d[a-1][b-1]=c
  d[b-1][a-1]=c

d=floyd_warshall(csr_matrix(d))
for i in range(n):
  for j in range(n):
    if d[i][j] <= l:
      e[i][j] = 1

e=floyd_warshall(csr_matrix(e))

q=int(input())
for _ in range(q):
  s,t = map(int, input().split())
  if e[s-1][t-1] == sys.maxsize:
    print(-1)
  else:
    print(int(e[s-1][t-1]-1))
### BUGGY CODE ###

a,b,c,d = map(int,input().split())
mod = 998244353

dp = [[0] * (d+1) for i in range(c+1)]
dp[a][b] = 1

for i in range(a,c+1):
    for j in range(b,d+1):
        dp[i][j] += dp[i-1][j] * j + dp[i][j-1]*i - dp[i-1][j-1]*(i-1)*(j-1)
        dp[i][j] %=mod
print(dp[c][d])

### FIXED CODE ###

a,b,c,d = map(int,input().split())
mod = 998244353

dp = [[0] * (d+1) for i in range(c+1)]
dp[a][b] = 1

for i in range(a,c+1):
    for j in range(b,d+1):
        dp[i][j] += dp[i-1][j] * j + dp[i][j-1]*i - dp[i-1][j-1]*(i-1)*(j-1)
        dp[i][j] %=mod
print(dp[c][d])
### BUGGY CODE ###

inf = float('inf')

def accmulate(array):
    global cs
    cs = [0]*(len(array)+1)
    for i in range(len(array)):
        cs[i+1] = cs[i] + array[i]

def query(l,r):
    return cs[r+1] - cs[l]

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

accmulate(A)

dp = [[inf]*(N+1) for _ in range(N+1)]

for i in range(N):
    dp[i][i+1] = 0

for i in range(N-1):
    dp[i][i+2] = A[i] + A[i+1]

for b in range(3,N+1):
    for i in range(N-b+1):
        j = i + b
        for k in range(i+1,j):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + query(i,j-1))

ans = dp[0][N]
print(ans)

### FIXED CODE ###

inf = float('inf')

def accmulate(array):
    global cs
    cs = [0]*(len(array)+1)
    for i in range(len(array)):
        cs[i+1] = cs[i] + array[i]

def query(l,r):
    return cs[r+1] - cs[l]

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

accmulate(A)

dp = [[inf]*(N+1) for _ in range(N+1)]

for i in range(N):
    dp[i][i+1] = 0

for i in range(N-1):
    dp[i][i+2] = A[i] + A[i+1]

for b in range(3,N+1):
    for i in range(N-b+1):
        j = i + b
        for k in range(i+1,j):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + query(i,j-1))

ans = dp[0][N]
print(ans)
### BUGGY CODE ###

#C
N=int(input())
S=input()
even = "#"*N
odd = "."*N
eve_c=N-S.count('#')
odd_c=N-S.count('.')
ans=[]
for i in range(N):
    ans.append(S[:i+1].count('#')+S[i+1:].count('.'))

ans.append(eve_c)
ans.append(odd_c)
print(min(ans))

### FIXED CODE ###

#https://atcoder.jp/contests/tenka1-2019-beginner/submissions/5063821
from itertools import accumulate
N=int(input())
S=input()
black=[0]*N
white=[0]*N

for i,s in enumerate(S):
    if s=="#":
        black[i]=1
    elif s==".":
        white[i]=1
#累積和を取る
black =[0]+black
black =list(accumulate(black))
white =[0]+white[::-1]
white =list(accumulate(white))[::-1]

ans =[]

for i in range(N+1):
    ans.append(black[i]+white[i])
print(min(ans))
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))

ll=0
rr=10**9+1
for _ in range(10**5):
  #最も長い丸太がこれになる
  ans=(ll+rr)/2.0
  cnt=0
  for item in a:
    if item>ans:
	    cnt+=((-1*item)//ans)*(-1)-1
  if cnt<=k:
    rr=ans
  else:
    ll=ans
print(int((-1*ans//1)*(-1)))

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))

ll=0
rr=10**9+1
for _ in range(10**2):
  #最も長い丸太がこれになる
  ans=(ll+rr)/2.0
  cnt=0
  for item in a:
    if item>ans:
	    cnt+=((-1*item)//ans)*(-1)-1
  if cnt<=k:
    rr=ans
  else:
    ll=ans
print(int((-1*ans//1)*(-1)))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
#ABC122C
import sys
import copy
tmp = input().split()
hoge = list(map(lambda a: int(a), tmp))
n=hoge[0]
q=hoge[1]

s = input()

l=[]
r=[]
for i in range(0,q):
	tmp = input().split()
	hoge = list(map(lambda a: int(a), tmp))
	l.append(hoge[0])
	r.append(hoge[1])

#print(s)

for i in range(0,q):
#	print(l[i])
#	print(r[i])
	tmp=copy.deepcopy(s[l[i]-1:r[i]])
#	print(s[3:7])
#	print(s[l[i]:r[i]])

#	print(tmp)
	
	lentmp = len(tmp)
	sum = 0
	for j in range(0,lentmp-1):
		if(tmp[j]=="A")and(tmp[j+1]=="C"):
			sum+=1
	print(sum)




### FIXED CODE ###

# -*- coding: utf-8 -*-
#ABC122C
import sys
import copy
tmp = input().split()
hoge = list(map(lambda a: int(a), tmp))
n=hoge[0]
q=hoge[1]

s = input()

ans=[]
sum=0
#print(s)

for j in range(0,n-1):
	if(s[j]=="A")and(s[j+1]=="C"):
		sum+=1
	ans.append(sum)
	#print(s[j])
ans.append(sum)
ans.append(0)
#ans[n-1]=sum
#print(ans)
#print(ans)

l=[]
r=[]
sum=0
for i in range(0,q):
	tmp = input().split()
	hoge = list(map(lambda a: int(a), tmp))

	print(ans[hoge[1]-2]-ans[hoge[0]-2])
### BUGGY CODE ###

MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

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

    power = 10
    dic = [0] * 2019
    dic[0] = 1
    for _ in range(len(str(s))):
        x = s%power%2019
        dic[x] += 1
        power *= 10
    
    ans = 0
    for v in dic:
        ans += v*(v - 1)//2
    print(ans)
if __name__ == '__main__':
    main()

### FIXED CODE ###

MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def main():
    s = input()

    power = 1
    dic = [0] * 2019
    dic[0] = 1
    x = 0
    dic1 = {i:j for i,j in zip('0123456789',range(10))}
    for i in range(len(s)-1,-1,-1):
        x += power * dic1[s[i]]
        x %= 2019
        dic[x] += 1
        power *= 10
        power %= 2019
    
    ans = 0
    for v in dic:
        ans += v*(v - 1)//2
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

# ABC133-D

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy,numpy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  l=LI()

  left=[]
  a=[0]*n
  for i in range(n):
    b=copy.deepcopy(a)
    b[i]=1
    b[(i+1)%n]=1
    left.append(b)

  right=[]
  for x in l:
    right.append(x*2)

  return ' '.join(str(int(x)) for x in list(numpy.linalg.solve(left,right)))

print(main())


### FIXED CODE ###

import sys,collections

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  l=LI()

  # a1=(x1+x2)/2,a2=(x2+x3)/2,...,an=(xn+x1)/2
  # 2a1=x1+x2,2a2=x2+x3,...,2an=xn+x1
  # x1=S-(x2+x3+...+xn)
  # x1=S-2(a2+a4+...+an-1)
  # x2=2a1-x1
  # x3=2a2-x2
  # ...

  sm=sum(l)
  ans=[]
  tmp=0
  for i,x in enumerate(l):
    if i%2==1:
      tmp+=x
  x1=sm-2*tmp
  ans.append(x1)

  for ai in l[:-1]:
    xp=2*ai-x1
    ans.append(xp)
    x1=xp

  return ' '.join([str(x) for x in ans])

# main()
print(main())
### BUGGY CODE ###

import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict, OrderedDict
#すべてのkeyが用意されてる defaultdict(int)で初期化
#順序を保ったdict
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
n=int(input())
A=[]
# ans=0
for i in range(n):
    a=list(map(int,input().split()))
    A.append(a)
    # ans+=sum(a)

#ans//=2
miti=A[:]
for k in range(n):
    for i in range(k):
        for j in range(i):
            q=miti[i][j]
            w=miti[j][k]
            e=miti[k][i]
            q,w,e=sorted([[q,i,j],[w,j,k],[e,k,i]])
            if e[0]==inf:
                continue
            if sum([q[0],w[0],e[0]])==e[0]*2:
                miti[e[1]][e[2]]=inf
                miti[e[2]][e[1]]=inf
            elif q[0]+w[0]<e[0]:
                print(-1);exit()
ans=0
for i in range(n):
    for j in range(n):
        if miti[i][j]!=inf:
            ans+=miti[i][j]

print(ans//2)


### FIXED CODE ###

import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict, OrderedDict
#すべてのkeyが用意されてる defaultdict(int)で初期化
#順序を保ったdict
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
n=int(input())
A=[]
# ans=0
for i in range(n):
    a=list(map(int,input().split()))
    A.append(a)
    # ans+=sum(a)

#ans//=2
miti=[[] for i in range(n)]
for i in range(n):
    miti[i]=A[i][:]
    
for k in range(n):
    for j in range(k):
        for i in range(j):
            q=A[i][j]
            w=A[j][k]
            e=A[k][i]
            #print(i,j,k,"\t",q,w,e)
            # q,w,e=sorted([[q,i,j],[w,j,k],[e,k,i]])
            # if max(q,w,e)==inf: continue
            if q+w==e and q!=inf and w!=inf: miti[k][i]=inf;miti[i][k]=inf;continue
            if q+w<A[k][i] and q!=inf and w!=inf: print(-1);exit()
            if w+e==q and e!=inf and w!=inf: miti[i][j]=inf;miti[j][i]=inf;continue
            if w+e<A[i][j]  and e!=inf and w!=inf : print(-1);exit()
            if e+q==A[j][k] and q!=inf and e!=inf: miti[j][k]=inf;miti[k][j]=inf;continue
            if e+q<A[j][k] and q!=inf and e!=inf: print(-1);exit()
            
            
                
            
ans=0
for i in range(n):
    for j in range(n):
        if miti[i][j]!=inf:
            ans+=miti[i][j]

print(ans//2)
### BUGGY CODE ###

import math

def cf(x1,x2):
    cf=[]
    cf = [i for i in range(1,min(x1,x2)+1) if x1 % i == 0 and x2 % i == 0]
    return cf

def is_prime(q):
    q = abs(q)
    if q == 1: return True
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1

A, B = map(int, input().split())
lst = cf(A,B)

res = len([i for i in lst if is_prime(i)])

print(res)

### FIXED CODE ###

import math

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def is_prime(n):
    if n == 1: return True

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

A, B = map(int, input().split())
AY = make_divisors(A)
BY = make_divisors(B)
AB = set(AY) & set(BY)
AB = list(AB)
cnt = [i for i in range(len(AB)) if is_prime(AB[i])]
print(len(cnt))
### BUGGY CODE ###

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

while True:
  for i in range(n):
    if(list[i] % 2 == 0):
      list[i] = list[i] / 2
    else:
      break
  b += 1
     
print(b)
      

### FIXED CODE ###

n = int(input())
list = list(map(int, input().split()))
b = -1
cont = True

while cont:
  b += 1
  for i in range(n):
    if(list[i] % 2 == 0):
      list[i] = list[i] / 2
    else:
      cont = False
     
print(b)
### BUGGY CODE ###

from queue import PriorityQueue
from collections import defaultdict

n,m,s,t = map(int,input().split())
s-=1
t-=1
edge_a = defaultdict(set)
edge_b = defaultdict(set)
for i in range(m):
    u,v,a,b = map(int, input().split())
    u -= 1
    v -= 1
    edge_a[u].add((v, a))
    edge_a[v].add((u, a))
    edge_b[u].add((v, b))
    edge_b[v].add((u, b))

def djikstra(s,edges):
    n = len(edges)
    visited = {}
    q = PriorityQueue()
    while len(visited) != n:
        if len(visited) == 0:
            next_p = s
            visited[s] = 0
        else:
            while not q.empty():
                cost, to_ = q.get()
                if to_ not in visited:
                    visited[to_] = cost
                    next_p = to_
                    break
        for to_, cost in edges[next_p]:
            if cost >= 0 and to_ not in visited:
                q.put((visited[next_p] + cost, to_))
    return visited

cost_a = djikstra(s,edge_a)
cost_b = djikstra(t, edge_b)

ans = []
for i in range(n)[::-1]:
    nokori = 10**15 - cost_a[i] - cost_b[i]
    if len(ans) == 0:
        ans.append(nokori)
    else:
        ans.append(max(nokori, ans[-1]))
print(*ans[::-1], sep="\n")

### FIXED CODE ###

from heapq import heapify, heappop, heappush
from collections import defaultdict

n,m,s,t = map(int,input().split())
s-=1
t-=1
edge_a = defaultdict(set)
edge_b = defaultdict(set)
for i in range(m):
    u,v,a,b = map(int, input().split())
    u -= 1
    v -= 1
    edge_a[u].add((v, a))
    edge_a[v].add((u, a))
    edge_b[u].add((v, b))
    edge_b[v].add((u, b))

def djikstra(s,edges):
    n = len(edges)
    visited = {}
    q = []
    while len(visited) != n:
        if len(visited) == 0:
            next_p = s
            visited[s] = 0
        else:
            while q:
                cost, to_ = heappop(q)
                if to_ not in visited:
                    visited[to_] = cost
                    next_p = to_
                    break

        for to_, cost in edges[next_p]:
            if cost >= 0 and to_ not in visited:
                heappush(q, (visited[next_p] + cost, to_))
    return visited

cost_a = djikstra(s,edge_a)
cost_b = djikstra(t, edge_b)

ans = []
for i in range(n)[::-1]:
    nokori = 10**15 - cost_a[i] - cost_b[i]
    if len(ans) == 0:
        ans.append(nokori)
    else:
        ans.append(max(nokori, ans[-1]))
print(*ans[::-1], sep="\n")
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# abc 127 d
# input
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))
for i in range(m):
    s, l = map(int, input().split())
    for j in range(s):
        if a[j] < l:
            a[j] = l
    a = sorted(a)
# output
print(sum(a))


### FIXED CODE ###

# -*- coding: utf-8 -*-
# abc 127 d
from operator import itemgetter
# input
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
upd = []
for i in range(m):
    upd.append(list(map(int, input().split())))
upd.sort(key=itemgetter(1), reverse=True)
# print(upd)
# output
f = len(a)
p = 0
for t in upd:
    for i in range(p, p+t[0]):
        if p < f:
            if a[p] < t[1]:
                a[p] = t[1]
            else:
                break
        else:
            break
        p += 1
print(sum(a))
### BUGGY CODE ###

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

count = 0
count_i = 0
for i in range(0, n):
  for j in range(0, i+1):
    if p[i]<=p[j]:
      count_i=count_i + 1
  if count_i == i+1:
    count = count + 1
  count_i = 0

print(count)


### FIXED CODE ###

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

m=2*(10**5)+1
count = 0
for i in range(0, n):
  if p[i] <= m:
    m = p[i]
    count = count + 1

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

n = int(input())
a = [int(i) for i in input().split()]
b = []
for i in a:
    b.append(i)
    b = b[::-1]
print(*b)

### FIXED CODE ###

from collections import deque
n = int(input())
a = [int(i) for i in input().split()]
b = deque()
if n % 2 == 0:
    for i, j in enumerate(a):
        if (i + 1) % 2 == 0:
            b.appendleft(j)
        else:
            b.append(j)
else:
    for i, j in enumerate(a):
        if (i +1) % 2 == 0:
            b.append(j)
        else:
            b.appendleft(j)
print(*b)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
s_count = []
for i in range(len(s)):
  if s[i:i+2] == "AC":
    s_count.append(1)
  else:
    s_count.append(0)

for i in range(q):
  l,r = input().split()
  l = int(l)
  r = int(r)
  print(sum(s_count[l-1:r-1]))

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
s_count = [0]
for i in range(len(s)):
  if s[i:i+2] == "AC":
    s_count.append(s_count[i] + 1)
  else:
    s_count.append(s_count[i])

for i in range(q):
  l,r = map(int,input().split())
  count = s_count[r-1] - s_count[l-1]
  print(count)