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

N = int(input())
A = list(map(int, input().split()))
ans = 1
for i in A:
    ans *= i
print(ans if ans <= 10**18 else -1)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
if 0 in A:
    print(0)
    exit(0)
for i in range(N):
    ans *= A[i]
    if ans > 10**18:
        print(-1)
        break
else:
    print(ans)
### BUGGY CODE ###

N,W = map(int,input().split())
l = [list(map(int,input().split()))for i in range(N)]
dp = [[0]*(W + 1) for i in range(N)]
for i in range(l[0][0],W + 1):
    dp[0][i] = l[0][1]
for i in range(1,N):
    for j in range(W + 1):
        if l[i][0] > j:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - l[i][0]] + l[i][1])
print(dp[N - 1][W])

### FIXED CODE ###

import numpy as np
N,W = map(int,input().split())
l = [list(map(int,input().split()))for i in range(N)]
dp = np.zeros(shape=(N,W + 1),dtype = int)
for i in range(l[0][0],W + 1):
    dp[0][i] = l[0][1]
for i in range(1,N):
    weight = l[i][0]
    value = l[i][1]
    dp[i][:weight] = dp[i - 1][:weight]
    dp[i][weight:] = np.maximum(dp[i - 1][weight:], value + dp[i - 1][:-weight])
print(dp[N - 1][W])
### BUGGY CODE ###

# xor battle

def Normalize(A):
    A.sort(reverse=True)
    start_point = 0
    for i in range(60, -1, -1):
        X = 1 << i
        for j in range(start_point, len(A)):
            if A[j] >> i & 1:
                A[start_point], A[j] = A[j], A[start_point]
                for k in range(len(A)):
                    if A[k] >> i & 1 and k != start_point:
                        A[k] ^= A[start_point]
                start_point += 1
                break

# 最高位のbit を取得

def highest_bit(X):
    cnt = 0
    V = X
    while V & 1 == 0:
        cnt += 1
        V >>= 1
    return cnt


def solve():
    N = int(input())
    a = list(map(int, input().split()))
    player = input()

    p0, p1 = [], []

    for i in range(N):
        if player[i] == "0":
            p0.append(a[i])
        else:
            p1.append(a[i])
    Normalize(p0)
    Normalize(p1)

    for v in p0:
        bit = highest_bit(v)
        for j in range(len(p1)):
            if (v >> bit) & (p1[j] >> bit):
                p1[j] ^= v

    res = 0

    for x in p1:
        res ^= x

    print(res & 1)
    
    return


def main():
    T = int(input())
    for i in range(T):
        solve()
    return


if __name__ == "__main__":
    main()

### FIXED CODE ###

# xor battle


def is_included(base, X):
    base.sort(reverse=True)
    V = X
    for x in base:
        V = min(V, V ^ x)
    return V


def solve():
    N = int(input())
    a = list(map(int, input().split()))[::-1]
    player = input()[::-1]
    basement = [0]
    for i in range(N):
        v = a[i]
        K = is_included(basement, v)
        if player[i] == "0":
            if K == 0:
                pass
            else:
                basement.append(K)
        else:
            if K == 0:
                pass
            else:
                return 1

    return 0


def main():
    T = int(input())
    for i in range(T):
        A = solve()
        print(A)
    return


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

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

for i in range(Q):
    l,r=map(int,input().split())
    l,r=l-1,r-1 #リストのインデックスとの整合
    count_list.append(S[l:r+1].count('AC'))
for k in count_list:
    print(k)

### FIXED CODE ###

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

# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop, heapify
from collections import defaultdict
import copy
 
N,Q=map(int, sys.stdin.readline().split())
 
S=[]
event=[]
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	event.append(  ( s-x ,1, x) )	#Start
	event.append(  ( t-x,-1, x) )	#End


for i in range(Q):
	d=int(sys.stdin.readline().strip())
	event.append(  (d ,0, i) )

event.sort(key=lambda x:(x[0]) )

stop=set()

ans=defaultdict(lambda: -1) 

for s,flag,x in event:
	if flag==1:
		stop.add(x)
	elif flag==-1:
		try:
			stop.remove(x)
		except:
			pass
	elif flag==0:
		if stop:
			ans[x]=min(stop)
		else:
			ans[x]=-1


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


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right

N,Q=map(int, sys.stdin.readline().split())

S=[]
event=[]	#x, s, t
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	heappush( event, (x, max(0,s-x) , max(0,t-1-x)) )


D=[ int(sys.stdin.readline().strip()) for _ in range(Q) ]
D.sort()
ans=[ float("inf") for _ in range(Q) ]

Next=[ i+1 for i in range(Q) ]	#Next


while event:
	x,s,t=heappop(event)
	start=bisect_left(D,s)
	end=bisect_right(D,t)

	i=start
	while i<end:
		ans[i]=min(ans[i],x)
		next=Next[i]
		Next[i]=end
		i=next

for x in ans:
	if x==float("inf"):
		print -1
	else:
		print x
### BUGGY CODE ###

def solve():
    S = input()
    T = input()
    len_t = len(T)
    len_s = len(S)
    dp = [[0] * (len_t + 1) for _ in range(len_s + 1)]
    for i, s in enumerate(S):
        pre_dp_i = dp[i]
        dp_i = dp[i+1]
        for j, t in enumerate(T):
            tmp_dp = max((pre_dp_i[j] + 1) * (s == t),
                         pre_dp_i[j+1],
                         dp_i[j])
            dp_i[j+1] = tmp_dp
    res = ''
    while len_t > 0 and len_s > 0:
        current = dp[len_s][len_t]
        if current == dp[len_s - 1][len_t]:
            len_s -= 1
        elif current == dp[len_s][len_t - 1]:
            len_t -= 1
        else:
            res = S[len_s - 1] + res
            len_s -= 1
            len_t -= 1
    return res


if __name__ == "__main__":
    answer = solve()
    print(answer)


### FIXED CODE ###

def solve():
    S = input()
    T = input()
    len_t = len(T)
    len_s = len(S)
    dp = [[0] * (len_t + 1) for _ in range(len_s + 1)]
    for i, s in enumerate(S):
        pre_dp_i = dp[i]
        dp_i = dp[i+1]
        for j, t in enumerate(T):
            tmp_dp = max((pre_dp_i[j] + 1) * (s == t),
                         pre_dp_i[j+1],
                         dp_i[j])
            dp_i[j+1] = tmp_dp
    res = ''
    while len_t > 0 and len_s > 0:
        current = dp[len_s][len_t]
        if current == dp[len_s - 1][len_t]:
            len_s -= 1
        elif current == dp[len_s][len_t - 1]:
            len_t -= 1
        else:
            res = S[len_s - 1] + res
            len_s -= 1
            len_t -= 1
    return res


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

K, S = map(int, input().split())
XYZ = []

for x in range(K + 1):
  for y in range(K + 1):
    for z in range(K + 1):
      if x + y + z == S:
        n = [x, y, z]
        XYZ.append(n)

print(len(XYZ))

### FIXED CODE ###

K, S = map(int, input().split())

ans = 0
for i in range(K + 1):
  for j in range(K + 1):
    if i + j == S:
      ans += 1
    elif 0 <= S - (i + j) <= K:
      ans += 1
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
for i in range(N-1):
    for j in range(i, N-1):
        if A[j] < 0:
            A[j], A[j+1] = A[j]*-1, A[j+1]*-1
print(sum(A))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mn = len(list(filter(lambda x: x < 0, A)))
ans = [-A[i] if A[i] < 0 else A[i] for i in range(N)]
if mn % 2 == 0:
    print(sum(ans))
else:
    print(sum(ans)-min(ans)*2)
### BUGGY CODE ###

s = input()
Q = int(input())
rev_count = 0

for i in range(Q):
    a = input()
    if a[0] == "1":
        rev_count += 1
    else:
        b = a.split()
        if rev_count % 2 == 0:
            if b[1] == "1":
                s = b[2] + s
            else:
                s = s + b[2]
        else:
            if b[1] == "1":
                s = s + b[2]
            else:
                s = b[2] + s

if rev_count % 2 == 0:
    print(s)
else:
    print(s[::-1])

### FIXED CODE ###

# from fractions import gcd
# mod = 10 ** 9 + 7
# N = int(input())
# a = list(map(int,input().split()))
# a,b,c = map(int,input().split())
# ans = [0] * N
# math.ceilで切り上げ
# dp = [[0] * 4 for i in range(3)] #2次元配列初期化
# dp = [[[0] * 2 for i in range(3)] for j in range(5)]
# (ord('A'))でASCII出力 Aは65
import math
import statistics
import string
import sys
from array import array
from collections import deque

def intinput():
    return int(input())
def listintinput():
    return list(map(int, input().split()))
def splitintinput():
    return map(int, input().split())
def factorialsurplus(x, y, z):  # xからyまでの階乗をzで割ったあまりを求める
    ret = 1
    for i in range(x, y + 1):
        ret = (ret * i) % z
    return (ret)
def isprime(x):
    if x == 1:
        return False
    if x == 2:
        return True
    sq = int(math.sqrt(x))
    for i in range(2,sq+1):
        if x % i == 0:
            return False
    return True
def hcfnaive(a,b):#最大公約数 math.gcdが使えない時の手段として入れとく。pythonが更新されたらいらなくなるはず
    if(b==0):
        return a
    else:
        return hcfnaive(b,a%b)

s = deque()
s.append(input())
Q = int(input())
rev_count = 0

for i in range(Q):
    a = input()
    if a[0] == "1":
        rev_count += 1
    else:
        b = a.split()
        if rev_count % 2 == 0:
            if b[1] == "1":
                s.appendleft(b[2])
            else:
                s.append(b[2])
        else:
            if b[1] == "1":
                s.append(b[2])
            else:
                s.appendleft(b[2])

if rev_count % 2 == 0:
    print(''.join(s))
else:
    a = ''.join(s)
    print(a[::-1])
### BUGGY CODE ###

from functools import reduce
import sys
sys.setrecursionlimit(20000)

def gcd(a,b):
    while b != 0:
        a, b = b, a % b
    return a

def lcm_base(a, b):
    return a * b / gcd(a, b)

def lcm_numbers(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

N = int(input())
A = list(map(int, input().split()))
B = [0 for _ in range(N)]
mod = 10**9+7

ll = lcm_list(A)

for i in range(N):
    B[i] = (ll//A[i])%mod
print(int(sum(B)%mod))


### FIXED CODE ###

from fractions import gcd

def lcm(c,d):
    return c//gcd(c,d)*d
mod=10**9+7
n=int(input())
a=[int(i) for i in input().split()]
l=a[0]
for i in range(1,n):
    l=lcm(l,a[i])
ans=0
for i in range(n):
    ans+=l//a[i]
    #ans%=mod
print(ans%mod)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
cnt = 0
for i in range(1,N+1):
    print(A.index(i)+1, end=' ')

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ls = [0]*N
for i,x in enumerate(A):
    ls[x-1] = str(i+1)
print(' '.join(ls))
### BUGGY CODE ###

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

train = []

for _ in range(m):
    l,r = map(int,input().split())
    train.append([l,r])

for _ in range(q):
    p,q = map(int,input().split())
    ans = 0
    for l,r in train:
        if p<=l and q>=r:
            ans += 1
    print(ans)


### FIXED CODE ###

import itertools

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

lr = [[0 for i in range(n)] for j in range(n)]
for _ in range(m):
    l,r = map(int,input().split())
    lr[l-1][r-1] += 1

acc_lr = []
for l in lr:
    acc_lr.append([0] + list(itertools.accumulate(l)))

for _ in range(q):
    l,r = map(int,input().split())
    ans = 0
    for ls in acc_lr[l-1:r]:
        ans += ls[r] - ls[l-1]
    print(ans)
### BUGGY CODE ###

import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
n, k = map(int, input().split())
a = list(map(int, input().split()))
rui = [1]
t = 1
for i in range(n):
    t *= a[i]
    if i < k:
        rui += [t]
    else:
        rui += [t // rui[i - k + 1]]
        if rui[i + 1] > rui[i]:
            print('Yes')
        else:
            print('No')
#print(rui)


### FIXED CODE ###

import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(k, n):
    if a[i] > a[i - k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n = int(input())
l = [1]*(n+1)
l[0] = 0

for i in range(2,n+1):
    f=i
    while(f<=n):
        l[f] += 1
        f += i

    l[i] = l[i]*i

print(sum(l))


### FIXED CODE ###

from numba import njit
@njit("i8(i8)")

def f(n):

    
    l = [1]*(n+1)
    l[0] = 0
    ans = l[1]
    for i in range(2,n+1):
        for j in range(i,n+1,i):
            l[j] += 1

        ans += (l[i]*i)
    return ans

n = int(input())
print(f(n))
### BUGGY CODE ###

import sys
from collections import deque
def input(): return sys.stdin.readline().strip()


def main():
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        A.append(list(map(int, input().split())))
    B = []
    for _ in range(H):
        B.append(list(map(int, input().split())))
    
    """
    明らかなdp臭。
        dp[i][j] = (マス(0, 0)から(i, j)に進むときの偏りとしてありうるものの集合)
    とおく。(0<=i<=H-1, 0<=j<=W-1, 0<=d<=80)
    """

    dp = [[set([]) for _ in range(W)] for _ in range(H)]
    dp[0][0].add(abs(A[0][0] - B[0][0]))
    for i in range(1, H):
        diff = A[i][0] - B[i][0]
        for val in dp[i - 1][0]:
            dp[i][0].add(abs(val + diff))
            dp[i][0].add(abs(val - diff))
    for j in range(1, W):
        diff = A[0][j] - B[0][j]
        for val in dp[0][j - 1]:
            dp[0][j].add(abs(val + diff))
            dp[0][j].add(abs(val - diff))

    for i in range(1, H):
        for j in range(1, W):
            diff = A[i][j] - B[i][j]
            for val in dp[i - 1][j]:
                dp[i][j].add(abs(val + diff))
                dp[i][j].add(abs(val - diff))
            for val in dp[i][j - 1]:
                dp[i][j].add(abs(val + diff))
                dp[i][j].add(abs(val - diff))
    
    print(min(dp[H - 1][W - 1]))


   


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import deque
def input(): return sys.stdin.readline().strip()


def main():
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        A.append(list(map(int, input().split())))
    B = []
    for _ in range(H):
        B.append(list(map(int, input().split())))
    
    """
    明らかなdp臭。
        dp[i][j] = (マス(0, 0)から(i, j)に進むときの偏りとしてありうるものの集合)
    とおく。(0<=i<=H-1, 0<=j<=W-1, 0<=d<=80)

    残念ながらPypyだとsetでdp値を保持しているとTLEするので、setではなくビットで偏りの値を管理する
    ただし-diffの方向にビットシフトするとき0桁目以下が切り捨てられてしまうので、最初から適当に
    offsetで桁の水増しをしておく
    """

    offset = 80 * 164

    dp = [[0] * W for _ in range(H)]
    dp[0][0] |= 1 << (A[0][0] - B[0][0] + offset)
    dp[0][0] |= 1 << (B[0][0] - A[0][0] + offset)
    for i in range(1, H):
        diff = abs(A[i][0] - B[i][0])
        dp[i][0] |= dp[i - 1][0] << diff
        dp[i][0] |= dp[i - 1][0] >> diff
    for j in range(1, W):
        diff = abs(A[0][j] - B[0][j])
        dp[0][j] |= dp[0][j - 1] << diff
        dp[0][j] |= dp[0][j - 1] >> diff

    for i in range(1, H):
        for j in range(1, W):
            diff = abs(A[i][j] - B[i][j])
            dp[i][j] |= dp[i - 1][j] << diff
            dp[i][j] |= dp[i - 1][j] >> diff
            dp[i][j] |= dp[i][j - 1] << diff
            dp[i][j] |= dp[i][j - 1] >> diff
    
    ans1 = offset
    while not (dp[H - 1][W - 1] & (1 << ans1)):
        ans1 += 1
    ans2 = offset
    while not (dp[H - 1][W - 1] & (1 << ans2)):
        ans2 -= 1
    print(min(ans1 - offset, offset - ans2))


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

h,w = map(int,input().split())
maps = [ input() for _ in range(h)]
ans = 0
for x in range(w):
    for y in range(h):
        if maps[y][x] == "#":
            continue
        else:
            tmpans = 0
            for u in range(y,-1,-1):
                if maps[u][x] == "#":
                    break
                else:
                    tmpans += 1
            for d in range(y+1, h):
                if maps[d][x] == "#":
                    break
                else:
                    tmpans += 1
            
            for l in range(x,-1,-1):
                if maps[y][l] == "#":
                    break
                else:
                    tmpans += 1
            for r in range(x+1,w):
                if maps[y][r] == "#":
                        break
                else:
                    tmpans += 1
                    
            ans = max(tmpans,ans)
print(ans-1)

### FIXED CODE ###

h,w = map(int,input().split())
maps = [ input() for _ in range(h)]
ans = 0

U = [[0 for _ in range(w)] for _  in range(h)]
D = [[0 for _ in range(w)] for _  in range(h)]
L = [[0 for _ in range(w)] for _  in range(h)]
R = [[0 for _ in range(w)] for _  in range(h)]

for y in range(h):
    for x in range(w):
        if maps[y][x] == "#":
            U[y][x],L[y][x] = 0,0
        else:
            if y == 0 and x >= 1:
                U[0][x] = 1
                L[y][x] += 1 + L[y][x-1]
            elif x == 0 and y >= 1: 
                U[y][x] += 1 + U[y-1][x]
                L[y][0] = 1
            elif x == 0 and y == 0:
                U[y][x] = 1
                L[y][x] = 1
            else:
                U[y][x] += 1 + U[y-1][x]
                L[y][x] += 1 + L[y][x-1]

for y in range(h-1,-1,-1):
    for x in range(w-1,-1,-1):
        if maps[y][x] == "#":
            D[y][x],R[y][x] = 0,0
        else:
            if y == h-1 and x < w-1:
                D[y][x] = 1
                R[y][x] += 1 + R[y][x+1]
            elif x == w-1 and y < h-1:
                D[y][x] += 1 + D[y+1][x]
                R[y][x] = 1
            elif  x == w-1 and y == h-1:
                D[y][x] = 1
                R[y][x] = 1
            else:
                D[y][x] += 1 + D[y+1][x]
                R[y][x] += 1 + R[y][x+1]

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans,L[i][j]+R[i][j]+U[i][j]+D[i][j] - 3)
print(ans)
### BUGGY CODE ###

N = int(input())
li = []
for n in range(N):
    i = input()
    if i in li:
        pass
    else:
        li.append(i)
print(len(li))

### FIXED CODE ###

N = int(input())
li = []
count = 0
for n in range(N):
    i = input()
    li.append(i)
print(len(set(li)))
### BUGGY CODE ###

import sys
from collections import Counter
from collections import defaultdict

N=input()

fact= [1]
fact_tmp = 1
for i in range(1, N+1):
    fact_tmp *= i
    fact.append(fact_tmp) 
 
def ncr(n,r):
	if n < 0 or r < 0 or n < r:	return 0
	else:	return (fact[n]/fact[r]/fact[n-r])

C=defaultdict(lambda: 0) 
for i in range(N):
	s=sys.stdin.readline().strip()
	s=list(s)
	s.sort()
	s="".join(s)
	C[s]+=1
ans=0

for i in C.values():
	ans+=ncr(i,2)

print ans


### FIXED CODE ###

import sys
from collections import Counter
from collections import defaultdict

N=input()

C=defaultdict(lambda: 0) 
for i in range(N):
	s=sys.stdin.readline().strip()
	s=list(s)
	s.sort()
	s="".join(s)
	C[s]+=1
ans=0

for i in C.values():
	ans+=i*(i-1)/2

print ans
### BUGGY CODE ###

N = int(input())
S = list(map(str, input()))
f=0
i_c = j_c = k_c =1
for i in range(N):
    for j in range(N):
        for k in range(N):
            if(k_c>j_c and j_c>i_c):
                if(j_c-i_c!=k_c-j_c):
                    if(
                        S[i]!=S[j] and 
                        S[i]!=S[k] and
                        S[j]!=S[k]):
                        # print("!!",i,j,k)
                        f+=1
                        # print(i_c,j_c,k_c)
            k_c+=1
        j_c+=1
        k_c = 1
    i_c+=1
    j_c = 1

print(f)

### FIXED CODE ###

n=int(input())
s=input()
r=g=b=0
for i in s:
  if i=="R":r+=1
  elif i=="G":g+=1
  else:b+=1

ans=r*g*b
for i in range(n):
  for j in range(i+1,n):
    k_ = j+(j-i)
    if(k_ >=n):
      break
    ans -= int(s[i]!= s[j] and s[i] != s[k_] and s[j] != s[k_])

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

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

if 1 not in A:
    print(-1)
    exit()


for i in range(N-1):
    if A[i] in l:
        continue
    for j in range(i+1,N):
        if A[i]>A[j]:
            if A[j] not in l:
                continue
        else:
            if l[c]+1==A[i]:
                l.append(A[i])
                c+=1
if l[-1]+1 == A[-1]:
    l.append(A[-1])

print(N+1-len(l))


### FIXED CODE ###

N=int(input())
A=[int(x) for x in input().split()]
ne=1
c=0

if 1 not in A:
    print(-1)
    exit()


for i in range(N-1):
    if A[i]==ne:
        c+=1
        ne+=1
if A[-1]==ne:
    c+=1
print(N-c)
### BUGGY CODE ###

N = int(input())
A = map(int, input().split())
re = 1
for i in A:
    re *= i
if re > 10**18:
    print(-1)
else:
    print(re)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
result = 1
if 0 in A:
    print(0)
else:
    for i in range(N):
        result *= A[i]
        if result > 10**18:
            print(-1)
            quit()
    print(result)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.buffer.readline
n, q = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = [int(i) - 1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)

p = [0] * n
for _ in range(q):
    pp, x = [int(i) for i in input().split()]
    p[pp - 1] += x


def dfs(i=0, r=-1):
    if r!=-1:
        p[i] += p[r]
    for j in e[i]:
        if j != r:
            dfs(j, i)
dfs()

print(" ".join(map(str,p)))


### FIXED CODE ###

import sys

sys.setrecursionlimit(1000000)


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


n, q = [int(i) for i in input().split()]
ab = [[] for _ in range(n)]
for _ in range(n - 1):
    i, j = [int(i)-1 for i in input().split()]
    ab[i].append(j)
    ab[j].append(i)
p = [0]*n
for _ in range(q):
    i, j = [int(i) for i in input().split()]
    p[i-1] += j

al = [False]*n
pp = [0]*n


def a(i=0, j=0):
    al[i] = True
    j += p[i]
    pp[i] = str(j)
    for k in ab[i]:
        if not al[k]:
            a(k, j)


a()
print(" ".join(pp))
### BUGGY CODE ###

S = list(input())

a = ''
count = 0
i = 0
while(i < len(S)):
    for j in range(i,len(S)):
        a += S[j]
        if(int(a) % 2019 == 0):
            count += 1
    i += 1
    a = ''
print(count)

### FIXED CODE ###

S = input()
P =2019
ans = 0
 
count = [0] * P
count[0] = 1
u = 0
for i, s in enumerate(reversed(S)):
    u = (int(s) * pow(10, i, P) + u) % P
    ans += count[u]
    count[u] += 1
print(ans)
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(2,N+1):
  ans += (i-1)%i
print(ans)

### FIXED CODE ###

N = int(input())

print((N-1)*N//2)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
m = max(A)
for n in range(N):
    if A[n] < m:
        print(m)
        continue
    elif n == 0:
        print(max(A[n + 1:]))
    elif n == N - 1:
        print(max(A[:n]))
    else:
        print(max(max(A[:n]), max(A[n + 1:])))

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
m = max(A)
ans = list(map(str, [m for _ in range(N)]))
if A.count(m) > 1:
    print('\n'.join(ans))
    exit()
AA = A[:]
AA.remove(m)
mm = max(AA)
for n in range(N):
    if A[n] == m:
        ans[n] = str(mm)
        break
print('\n'.join(ans))
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
l=[]
for i in range(q):
  l.append(tuple(map(int,input().split())))
for j in range(q):
  x,y=l[j]
  a=s[x-1:y]
  num=a.count('AC')
  print(num)

### FIXED CODE ###

import bisect
n,q=map(int,input().split())
s=input()
slst=[]
cnt=[]
for i in range(n-1):
  slst.append(s[i:i+2])
for a,b in enumerate(slst):
  if b=='AC':
    cnt.append(a)
l=[]
for i in range(q):
  x,y=map(int,input().split())
  M=bisect.bisect_left(cnt,x-1)
  N=bisect.bisect_right(cnt,y-2)
  print(N-M)