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

n=int(input())
a=list(map(int,input().split()))
tf=[1]*n
n=n-1
notdiv=True
firstyn=0
for i in range(n,-1,-1):
  notdiv=True
  if tf[i] ==0:
    continue
  for j in range(i):
    if a[i]%a[j] == 0:
      tf[i]=0
    if a[j]%a[i] == 0:
      tf[j]=0
print(sum(tf))

### FIXED CODE ###

def main():
  n=int(input())
  a=sorted(map(int,input().split()))
  maxa=a[-1]+1
  tf=[False]*maxa
  r=0
  n-=1
  for i in range(n):
    a_i=a[i]
    if tf[a_i] ==False:
      for j in range(a_i,maxa,a_i):
        tf[j]=True
      if a_i < a[i+1]:
        #print(a_i)
        r+=1
  if tf[-1] ==False:
    r+=1
  print(r)
main()
### BUGGY CODE ###

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

b = []
for i in range(m):
  c = a[i][0]
  d = a[i][1]
  for e in range(c,d+1):
    b.append(e)
  if i >= 1:
    c = [t for t in set(b) if b.count(t) == 2]
    b = c
  
print(len(b))

### FIXED CODE ###

n,m = map(int, input().split())
a = []
b = []
c = []
for i in range(m):
  a.append(list(map(int, input().split())))
for i in range(m):
  b.append(a[i][0])
  c.append(a[i][1])
  
b_max = max(b)
c_min = min(c)

ans = max(0, min(c) - max(b) + 1)

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

N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7

fac=[]
finv=[]
inv=[]
def combi_init():
    fac.append(1)
    fac.append(1)
    finv.append(1)
    finv.append(1)
    inv.append(1)
    inv.append(1)

    for i in range(2,N+1):
        fac.append(fac[i-1]*i%mod)
        inv.append(mod-mod//i*inv[mod%i]%mod)
        finv.append(finv[i-1]*inv[i]%mod)

def combi_mod(n,k):
    combi_init()
    ret=fac[n]*finv[n-k]*finv[k]%mod
    return ret

A.sort()

ans=0

for i in range(N-1,K-2,-1):
    ans+=(A[i]-A[(N-1)-i])*combi_mod(i,K-1)


ans%=mod

print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7

fac=[]
finv=[]
inv=[]
def combi_init():
    fac.append(1)
    fac.append(1)
    finv.append(1)
    finv.append(1)
    inv.append(1)
    inv.append(1)

    for i in range(2,N+1):
        fac.append(fac[i-1]*i%mod)
        inv.append(mod-mod//i*inv[mod%i]%mod)
        finv.append(finv[i-1]*inv[i]%mod)

def combi_mod(n,k):

    ret=fac[n]*finv[n-k]*finv[k]%mod
    return ret

A.sort()

ans=0
combi_init()
for i in range(N-1,K-2,-1):
    ans+=(A[i]-A[(N-1)-i])*combi_mod(i,K-1)


ans%=mod

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

import sys

import numpy as np
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import dijkstra

sys.setrecursionlimit(10000)
INF = float('inf')

N, M, S, T = list(map(int, input().split()))
U = []
V = []
A = []
B = []
for _ in range(M):
    u, v, a, b = list(map(int, input().split()))
    U.append(u)
    V.append(v)
    A.append(a)
    B.append(b)

graph_yen = coo_matrix((A, (U, V)), shape=(N + 1, N + 1))
graph_snuke = coo_matrix((B, (U, V)), shape=(N + 1, N + 1))

# yen_mins[i]: S から i まで行くときの最小金額
yen_mins = dijkstra(graph_yen, indices=S, directed=False, unweighted=False)
# snuke_mins[i]: T から i まで行くときの最小金額
snuke_mins = dijkstra(graph_snuke, indices=T, directed=False, unweighted=False)

# total_mins[i]: i で両替して S から T まで行くときの最小金額
total_mins = 10 ** 15 - (yen_mins + snuke_mins)[1:]

# 後ろから累積最大値とる
for a in np.maximum.accumulate(total_mins[::-1])[::-1]:
    print(int(a))


### FIXED CODE ###

import heapq
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')


def dijkstra(graph, start):
    """
    :param list of (list of (int, int)) graph:
    :param int start:
    :return:
    """
    dist = [INF for _ in range(len(graph))]
    dist[start] = 0
    heap = []
    heapq.heappush(heap, (0, start))

    while len(heap) > 0:
        w, v = heapq.heappop(heap)
        if w > dist[v]:
            continue
        for u, dw in graph[v]:
            if w + dw < dist[u]:
                dist[u] = w + dw
                heapq.heappush(heap, (w + dw, u))
    return dist


N, M, S, T = list(map(int, input().split()))
graph_yen = [[] for _ in range(N + 1)]
graph_snuuk = [[] for _ in range(N + 1)]
for _ in range(M):
    u, v, a, b = list(map(int, input().split()))
    graph_yen[u].append((v, a))
    graph_yen[v].append((u, a))
    graph_snuuk[u].append((v, b))
    graph_snuuk[v].append((u, b))

# yen_mins[i]: S から i まで行くときの最小金額
yen_mins = np.array(dijkstra(graph_yen, start=S))
# snuke_mins[i]: T から i まで行くときの最小金額
snuke_mins = np.array(dijkstra(graph_snuuk, start=T))

# totals[i]: i で両替して S から T まで行くときの最大金額
totals = 10 ** 15 - (yen_mins + snuke_mins)[1:]
# 後ろから累積最大値とる
for a in np.maximum.accumulate(totals[::-1])[::-1]:
    print(int(a))
### BUGGY CODE ###


def resolve():
    INF = 1<<60
    H, N = map(int, input().split())
    A, B = [], []
    for i in range(N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)

    dp = [INF]*(H+1)
    dp[0] = 0

    for h in range(H):
        for i in range(N):
            to = min(H, A[i]+h)
            dp[to] = min(dp[to], dp[h]+B[i])

    print(dp[H])


if __name__ == "__main__":
    resolve()


### FIXED CODE ###


def resolve():
    INF = 1<<60
    H, N = map(int, input().split())
    A, B = [], []
    for i in range(N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)

    dp = [[INF]*(H+1) for _ in range(N+1)]
    dp[0][0] = 0

    for i in range(N):
        for j in range(H+1):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            dp[i+1][min( j + A[ i ], H)] = min(dp[i+1][min( j + A[ i ], H)], dp[i+1][j] + B[i])
    print(dp[N][H])


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

import sys
from itertools import islice, repeat


def _resolve(costs, k):
    sum_ = sum(costs)
    v = 0
    if k >= len(costs):
        if sum_ > 0:
            x = k // len(costs) - 1
            v = x * sum_
            k -= x * len(costs)
        else:
            k = len(costs)

    points = [v] * (len(costs) * (k + 1))
    for i in range(k):
        for n in range(len(costs)):
            points[(i + 1) * len(costs) + n] = points[i * len(costs) + n] + costs[(i + n) % len(costs)]
    
    ans = max(points)
    if ans == 0:
        y = max(costs)
        if y < 0:
            ans = y
    return ans


def resolve(in_):
    N, K = map(int, next(in_).split())
    P = [0] + list(map(int, next(in_).split()))
    C = [0] + list(map(int, next(in_).split()))

    graphs = []
    p = set(P[1:])
    while p:
        index = p.pop()
        graph = [C[index]]
        index = P[index]
        while index in p:
            graph.append(C[index])
            p.remove(index)
            index = P[index]
        graphs.append(graph)

    ans = max(map(_resolve, graphs, repeat(K)))
    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from itertools import islice, repeat


def _resolve(costs, k):
    sum_ = sum(costs)
    v = 0
    if k >= len(costs):
        if sum_ > 0:
            x = k // len(costs) - 1
            v = x * sum_
            k -= x * len(costs)
        else:
            k = len(costs)

    points = [v] * (len(costs) * (k + 1))
    for i in range(k):
        for n in range(len(costs)):
            points[(i + 1) * len(costs) + n] = points[i * len(costs) + n] + costs[(i + n) % len(costs)]
    
    ans = max(points)
    if ans == 0:
        y = max(costs)
        if y < 0:
            ans = y
    return ans


def resolve(in_):
    N, K = map(int, next(in_).split())
    P = [0] + list(map(int, next(in_).split()))
    C = [0] + list(map(int, next(in_).split()))

    graphs = []
    p = set(P[1:])
    while p:
        index = p.pop()
        graph = [C[index]]
        index = P[index]
        while index in p:
            graph.append(C[index])
            p.remove(index)
            index = P[index]
        graphs.append(graph)

    ans = max(map(_resolve, graphs, repeat(K)))
    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


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

N, K = map(int, input().split())
mod = 998244353

LR = [tuple(map(int, input().split())) for _ in range(K)]
LR.sort()

dp = [0] * (N + 1)
dp[1] = 1
for i in range(1, N):
    if dp[i] <= 0:
        continue
    for L, R in LR:
        for d in range(L, R + 1):
            if i + d < N + 1:
                dp[i + d] += dp[i]
                dp[i + d] %= mod

print(dp[N])


### FIXED CODE ###

N, K = map(int, input().split())
mod = 998244353

LR = [tuple(map(int, input().split())) for _ in range(K)]
LR.sort()

dpsum = [0] * (N + 1)
dpsum[1] = 1
dp = [0] * (N + 1)
dp[1] = 1

for i in range(2, N + 1):
    for L, R in LR:
        l = i - R
        r = i - L
        
        if r < 0:
            continue
        l = max(l, 0)
        
        dp[i] += dpsum[r] - dpsum[l - 1]
        dp[i] %= mod
    dpsum[i] = dpsum[i - 1] + dp[i]

print(dp[N])
### BUGGY CODE ###

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    time = [[[INF] * 4 for __ in range(W)] for _ in range(H)]
    dr = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = collections.deque()
    for i in range(4):
        q.append((0, x1, y1, i))
        time[x1][y1][i] = 0
    while q:
        t, i, j, d = q.pop()
        timeij = time[i][j]
        if timeij[d] != t: continue
        nt = (t + K - 1) // K * K
        for nd in range(4):
            if nd == d: continue
            if timeij[nd] > nt:
                q.appendleft((nt, i, j, nd))
                timeij[nd] = nt
        ni, nj = i + dr[d][0], j + dr[d][1]
        if not (0 <= ni < H and 0 <= nj < W): continue
        if C[ni][nj] == '@': continue
        timeninj = time[ni][nj]
        if timeninj[d] > t + 1:
            q.append((t + 1, ni, nj, d))
            timeninj[d] = t + 1
    ans = min(time[x2][y2][i] for i in range(4))
    if ans == INF:
        print(-1)
    else:
        print((ans + K - 1) // K)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)


### FIXED CODE ###

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[INF] * W for _ in range(H)]
    q = collections.deque([(x1, y1)])
    dist[x1][y1] = 0
    while q:
        i, j = q.popleft()
        d = dist[i][j]
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] == d + 1: continue
                if dist[ni][nj] < d + 1: break
                dist[ni][nj] = d + 1
                q.append((ni, nj))
    ans = dist[x2][y2]
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
select_num = [0 for i in range(N+1)]
select_num2 = [0 for i in range(N+1)]
maxim = max(A)
count_num = [0 for i in range(maxim+1)]
for i in range(1,maxim+1):
  count_num[i] = A.count(i)
  select_num[i] = (count_num[i] - 0)*(count_num[i] - 1)//2
  select_num2[i] = count_num[i] - 1
sumS = sum(select_num)
for i in range(N):
  s = select_num2[A[i]] 
  print(sumS -s)

### FIXED CODE ###

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

select_num = 0
count_num = [0]*(N+1)
for i in A:
  count_num[i] += 1
for i in range(1,N+1):
  select_num += (count_num[i])*(count_num[i] - 1)//2
for i in A:
  print(select_num -count_num[i] + 1)
### BUGGY CODE ###

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

res = []
for i in range(n):
  count = 0
  flag = True
  for j in range(i,n-1):
    if h[j] >= h[j+1]:
      if flag:
      	count += 1
    else:
      flag = False
      break
  res.append(count)
      
print(max(res))

### FIXED CODE ###

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

res = []
count = 0
for i in range(n-1):
  if h[i] >= h[i+1]:
    count += 1
    if i == (n-2):
      res.append(count)
  else:
    if count != 0: 
      res.append(count)
    count = 0

if len(res) == 0:
  print(0)
else:
  print(max(res))
### BUGGY CODE ###

N,A=map(int,input().split())
x=[int(i) for i in input().split()]
NX=N*max([max(x),A])
dp=[[[0 for s in range(NX+1)] for k in range(N+1)] for j in range(N+1)]
dp[0][0][0]=1
for j in range(N+1):
    for k in range(N+1):
        for s in range(NX+1):
            if j==0 and k==0 and s==0:
                dp[j][k][s]=1
            elif j>=1 and s<x[j-1]:
                dp[j][k][s]=dp[j-1][k][s]
            elif j>=1 and k>=1 and s>=x[j-1]:
                dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-x[j-1]]
            else:
                dp[j][k][s]=0
#(dp)
ans=0
for k in range(1,N+1):
    ans+=dp[N][k][k*A]
print(ans)


### FIXED CODE ###

N,A=map(int,input().split())
x=[int(i) for i in input().split()]
NX=N*max([max(x),A])
dp=[[[0 for s in range(NX+1)] for k in range(N+1)] for j in range(N+1)]
dp[0][0][0]=1
for j in range(N+1):
    for k in range(N+1):
        for s in range(NX+1):
            if j==0 and k==0 and s==0:
                dp[j][k][s]=1
            elif j>=1 and s<x[j-1]:
                dp[j][k][s]=dp[j-1][k][s]
            elif j>=1 and k>=1 and s>=x[j-1]:
                dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-x[j-1]]
            else:
                dp[j][k][s]=0
#(dp)
ans=0
for k in range(1,N+1):
    ans+=dp[N][k][k*A]
print(ans)
### BUGGY CODE ###

import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')


def solve():
    n, q = nm()
    c = nl()
    m = 500010
    sq = 600
    g = [0]*q
    for i in range(q):
        l, r = nm()
        gr = l // sq
        g[i] = (gr << 60) + ((r-1) << 40) + ((l-1) << 20) + i
    mask = (1 << 20) - 1
    g.sort()
    ans = [0] * q
    d = [0]*(n+1)
    cl = 0; cr = -1
    cur = 0
    for x in g:
        i = x & mask
        x >>= 20
        l = x & mask
        x >>= 20
        r = x & mask
        while r > cr:
            cr += 1
            if d[c[cr]] == 0:
                cur += 1
            d[c[cr]] += 1
        while l < cl:
            cl -= 1
            if d[c[cl]] == 0:
                cur += 1
            d[c[cl]] += 1
        while cr > r:
            if d[c[cr]] == 1:
                cur -= 1
            d[c[cr]] -= 1
            cr -= 1
        while l > cl:
            if d[c[cl]] == 1:
                cur -= 1
            d[c[cl]] -= 1
            cl += 1
        ans[i] = cur
    prn(ans)
    return

solve()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

class BIT:
    '''
    0-indexed
    '''
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.depth = N.bit_length()

    def _bitsum(self, i):
        ret = 0
        while i:
            ret += self.tree[i]
            i ^= i & -i
        return ret

    def bitsum(self, l, r=None): # [l, r)
        if r is None:
            return self._bitsum(l)
        else:
            return self._bitsum(r) - self._bitsum(l)

    def bitadd(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        return

    def lower_bound(self, x):
        sum_ = 0
        pos = 0
        v = 1 << self.depth
        for i in range(self.depth, -1, -1):
            k = pos + v
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += v
            v >>= 1
        return pos + 1, sum_


def solve():
    n, q = nm()
    c = nl()
    m = 500010
    m2 = m * m
    g = [0]*q
    for i in range(q):
        l, r = nm()
        g[i] = ((r-1) << 40) + ((l-1) << 20) + i
    mask = (1 << 20) - 1
    g.sort()
    ans = [0] * q
    b = BIT(m)
    last = [n + 5]*(n+1)
    cr = -1
    for r in g:
        i = r & mask
        r >>= 20
        l = r & mask
        r >>= 20
        while cr < r:
            cr += 1
            b.bitadd(last[c[cr]], -1)
            last[c[cr]] = cr
            b.bitadd(cr, 1)
        ans[i] = b.bitsum(l, r+1)
    prn(ans)
    return

solve()
### BUGGY CODE ###

#abc128
N,Q=map(int,input().split())
stop_list=[list(map(int,input().split())) for _ in range(N)]
D_list=[int(input()) for _ in range(Q)]

N_line=dict()

for i in stop_list:
    N_line[i[2]]=[]

for i in stop_list:
    N_line[i[2]].append([i[0]-0.5,i[1]-0.5])

N_line=sorted(N_line.items(), key=lambda x:x[0])
D_achieve=[]


for d in D_list:
    judge=False
    for N in N_line:
        c_number=N[0]
        #N[0]は座標、N[1]は時間のリスト
        for time in N[1]:
            if time[0]<c_number+d<time[1]:
                D_achieve.append(c_number)
                judge=True
            if judge:
                break
        if judge:
            break
    if judge==False:
        D_achieve.append(-1)

        
        
for i in D_achieve:
    print(i)

### FIXED CODE ###

from heapq import heappop,heappush

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


event=[]
q=[]
for _ in range(N):
    S,T,X=map(int,input().split())
    event.append([S-X,1,X])
    event.append([T-X,-1,X])

for i in range(Q):
    event.append([int(input()),2,i])

stop_set=set()
event.sort()
q=[]

for pos,m,x in event:
    if m==-1:
        stop_set.remove(x)
        
    elif m==1:
        #heappushする時点でqはソートされている
        heappush(q,x)
        stop_set.add(x)
    
    else:
        #この時点でのstop_setは、i番目の人が遭遇する通行止めの座標
        #この時点でのqは今までstopになった座標
        while q:
            #qはソート済なので、q[0]は最小値　それがstop_setから外れている場合、heappopでそれを排除する
            if q[0] not in stop_set:
                heappop(q)
            #q[0]がstop_setから外れてない場合、それ以降のqも外れていないのでbreak    
            else:
                break

        if q:
            print(q[0])
        else:
            print(-1)
### BUGGY CODE ###

s = input()
t = input()

slist = list(s)
tlist = list(t)
# 番兵設定

scounter = 0
slength=len(slist)

for tchar in tlist:
    Slist=[]
    for schar in slist[scounter%slength:]:
        Slist.append(schar)
    for schar in slist[:scounter%slength]:
        Slist.append(schar)
    Slist.append("aa")
    for schar in Slist:
        # print(schar,tchar,scounter)
        if schar == "aa":
            scounter = -1
            tcharcheckflag=True
            break
        if tchar == schar:
            scounter += 1
            tcharcheckflag=True
            break
        scounter+=1
    if scounter == -1:
        break

print(scounter)

### FIXED CODE ###

slist = input()
tlist = input()
scounter = 0
slength=len(slist)
slist=slist+slist
preposition=-1
for tchar in tlist:
    preposition=slist.find(tchar, preposition+1)
    if preposition==-1:
        scounter=-1
        break
    elif preposition>=slength:
        scounter+=slength
        preposition-=slength
    # print(tchar, scounter, preposition)
if (scounter==-1):
    print(scounter)
else:
    print(scounter+preposition+1)
### BUGGY CODE ###

N,Q = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*(N-1)]
PX = [list(map(int,input().split())) for _ in [0]*Q]

E = [[] for _ in [0]*N]
for a,b in AB:
    a-=1
    b-=1
    E[a].append(b)
    E[b].append(a)

P = [-1]*N
P[0] = 0
q = [0]
while q:
    i = q.pop()
    for j in E[i]:
        if P[j]!=-1: continue
        P[j] = i
        q.append(j)
P[0] = -1

V = [0]*N
for p,x in PX:
    p-=1
    V[p] += x

q = [0]
while q:
    i = q.pop()
    for j in E[i]:
        if j==P[i] : continue
        V[j] += V[i]
        q.append(j)

print(*V)

### FIXED CODE ###

N,Q = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*(N-1)]
PX = [list(map(int,input().split())) for _ in [0]*Q]

E = [[] for _ in [0]*N]
for a,b in AB:
    a-=1
    b-=1
    E[a].append(b)
    E[b].append(a)

P = [-1]*N
P[0] = 0
q = [0]
while q:
    i = q.pop()
    for j in E[i]:
        if P[j]!=-1: continue
        P[j] = i
        q.append(j)
P[0] = -1

V = [0]*N
for p,x in PX:
    p-=1
    V[p] += x

q = [0]
done = [False]*N
while q:
    i = q.pop()
    done[i] = True
    for j in E[i]:
        if done[j] : continue
        V[j] += V[i]
        q.append(j)

print(*V)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
b = [[]*2 for _ in range(q)]
for i in range(q):
    b[i] = list(map(int, input().split()))

for i in range(q):
    count = 0
    start = b[i][0]-1
    end = b[i][1]-1
    for j in range(start, end):
        if s[j:j+2] == "AC":
            count += 1
    print(count)

### FIXED CODE ###

n, q = map(int, input().split())
s = list(input())
b = [[]*2 for _ in range(q)]
for i in range(q):
    b[i] = list(map(int, input().split()))

c = [0 for _ in range(len(s))]
count = 0

for i in range(len(s)):
    if s[i:i+2] == ["A", "C"]:
        count += 1
        c[i:i+2] = [count-1, count]
    else:
        c[i:i+2] = [count, count]

for i in range(q):
    start = b[i][0]-1
    end = b[i][1]-1
    ans = c[end] - c[start]
    print(ans)
### BUGGY CODE ###

n = int(input())
ans = 1
l = list(map(int, input().split()))
for i in range(n):
    x = l[i]
    ans *= x
    # if ans > 10**18:
    #     print(-1)
    #     exit()
print(ans if ans <= 10**18 else -1)

### FIXED CODE ###

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

import sys

def main():
    n, k = [int(_) for _ in input().split()]
    
    m = abs(n - n // k * k)
    while True:
        ans = abs(m - k)
        if m <= ans:
            print(m)
            sys.exit()
main()

### FIXED CODE ###

import sys

def main():
    n, k = [int(_) for _ in input().split()]
    
    m = abs(n - n // k * k)
    while True:
        ans = abs(m - k)
        if m <= ans:
            print(m)
            sys.exit()
        m = abs(m - k)
main()
### BUGGY CODE ###

import sys
a,b,m = map(int,input().split())
al = list(map(int,input().split()))
bl = list(map(int,input().split()))
ans = []
for i in range(m):
  x,y,c = map(int,input().split())
  ans.append(al[x-1] + bl[y-1] - c)
for i in range(a):
  for j in range(b):
    ans.append(al[i] + bl[j])
print(min(ans))

### FIXED CODE ###

a,b,m = map(int,input().split())
al = list(map(int,input().split()))
bl = list(map(int,input().split()))
yasuiyo = min(al) + min(bl)
ans = []
for i in range(m):
  x,y,c = map(int,input().split())
  ans.append(al[x-1] + bl[y-1] - c)

print(min(min(ans),yasuiyo))