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

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

es = []
for _ in range(N):
    s, t, x = map(int, input().split())
    es.append((s - x, 1, x))
    es.append((t - x, 0, x))

for _ in range(Q):
    d = int(input())
    es.append((d, 2, -1))

es.sort(key=lambda x: (x[0], x[1]))
st = set()
cur_min_stop = -1
check_needed = True
for i, (time, typ, pos) in enumerate(es):
    # print(es)
    # print(st)
    # print(i, (time, typ, pos))
    if typ == 1:
        st.add(pos)
        if cur_min_stop == -1 or pos < cur_min_stop:
            cur_min_stop = pos
    elif typ == 0:
        st.remove(pos)
        if pos == cur_min_stop:
            check_needed = True
    else:
        if check_needed:
            if st:
                cur_min_stop = min(st)
            else:
                cur_min_stop = -1
            check_needed = False
        print(cur_min_stop)


### FIXED CODE ###

# 理解する時間がなかったので、とりあえず写経
from bisect import bisect_left
from operator import itemgetter

N, Q = [int(i) for i in input().split()]
Construction = [tuple(int(i) for i in input().split()) for j in range(N)]
D = [int(input()) for _ in range(Q)]

ans = [-1] * Q
skip = [-1] * Q

Construction.sort(key=itemgetter(2))

for s, t, x in Construction:
    l = bisect_left(D, s - x)
    r = bisect_left(D, t - x)
    t = l
    while t < r:
        if skip[t] == -1:
            ans[t] = x  # lからr-1の時刻に出発した人は座標xの工事に引っかかる
            skip[t] = r  # lからr-1の時刻に出発した人はもう調べないようにする
            t += 1
        else:
            t = skip[t]  # tが指定する人はもう調べ終わっているので飛ばす
print(*ans, sep='\n')
### BUGGY CODE ###

def check(x, dist, H):

	for i, j in dist:
		if x == i:
			if H[x - 1] <= H[j - 1]:
				return 0
		elif x == j:
			if H[x - 1] <= H[i - 1]:
				return 0
	return 1



n, m = map(int, input().split())
H = list(map(int, input().split()))
dist = []
count = 0
for _ in range(m):
	a, b, = map(int, input().split())
	dist.append((a,b))

for x in range(1, n + 1):
	if check(x, dist, H) == 1:
		count += 1

print(count)


### FIXED CODE ###

def check(a, b, H, L):


	if H[a - 1] <= H[b - 1]:
			L[a - 1] = 0
	if H[b - 1] <= H[a - 1]:
			L[b - 1] = 0
	
n, m = map(int, input().split())
H = list(map(int, input().split()))
L = [i for i in range(1, n + 1)]
count = 0
for _ in range(m):
	a, b = map(int, input().split())
	check(a, b, H, L)

for i in L:
	if i != 0:
		count += 1
print(count)
### BUGGY CODE ###

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

R = [v for v,i in enumerate(S) if i == 'R']
G = [v for v,i in enumerate(S) if i == 'G']
B = [v for v,i in enumerate(S) if i == 'B']
t = len(B)
c = 0
for i in R:
    for j in G:
        a = max(i,j)
        b = min(i,j)
        d = [2* b -a,2 * a - b,(a+b)/2]
        for s in d:
            if s in B:
                c -= 1
        c += t

print(c)

### FIXED CODE ###

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

R = set([v for v,i in enumerate(S) if i == 'R'])
G = set([v for v,i in enumerate(S) if i == 'G'])
B = set([v for v,i in enumerate(S) if i == 'B'])
t = len(B)
c = 0
for i in R:
    for j in G:
        d = [2* i -j,2 * j - i,(i+j)/2]
        for a,s in enumerate(d):
            if s in B:
                c -= 1
        c += t

print(c)
### BUGGY CODE ###

from math import factorial as f
N, M, K = map(int, input().split())
mod = 10 ** 9 + 7

def combi(n, r):
  return f(n) // f(n - r) // f(r) % mod

res = 0
c = combi(N * M - 2, K - 2)
for i in range(1, N):
  res += ((N - i + 1) * (N - i) // 2) * c * M * M % mod
  res %= mod

for i in range(1, M):
  res += ((M - i + 1) * (M - i) // 2) * c * N * N % mod
  res %= mod

print(res % mod)

### FIXED CODE ###

from math import factorial as f
N, M, K = map(int, input().split())
mod = 10 ** 9 + 7

def combi(n, r):
  return f(n) // (f(n - r) * f(r)) % mod

res = 0
c = combi(N * M - 2, K - 2)
for i in range(1, N):
  res += ((N - i + 1) * (N - i) // 2) * c * M * M % mod
  res %= mod

for i in range(1, M):
  res += ((M - i + 1) * (M - i) // 2) * c * N * N % mod
  res %= mod

print(res % mod)
### BUGGY CODE ###

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

x = 1

for i in range(N):
  x = x * X[i]

if x > 10 ** 18: print("-1")
else: print(x)

### FIXED CODE ###

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

x = 1

if min(X) == 0:
  print(0)
  x = -1
else:
  for i in range(N):
    x = x * X[i]
    if x > 10 ** 18:
      print(-1)
      x = -1
      break
    
if x > 0: print(x)
### BUGGY CODE ###

N = int(input())
A,B = [],[]
for _ in range(N-1):
    array = list(map(int,input().split()))
    A.append(array[0])
    B.append(array[1])
from collections import defaultdict as ddict
children = ddict(list)
for a,b in zip(A,B):
    children[a].append(b)
ans = ddict(int)
col = 0
for child in sorted(children.keys()):
    used = set({0,ans[child]})
    for j in sorted(children[child]):
        temp = min(set(range(max(used)+2))-used)
        ans[j] = temp
        col = max(col,temp)
        used.add(temp)
print(col)
print("\n".join(str(ans[b]) for b in B))

### FIXED CODE ###

N = int(input())
AB = [[]]*(N-1)
for i in range(N-1):
    AB[i] = list(map(int,input().split()))
from collections import defaultdict as ddict
from collections import deque
tree = ddict(list)
B = [0]*(N-1)
for i,ab in enumerate(AB):
    tree[ab[0]].append(ab[1])
    B[i] = ab[1]
# 各エッジの色を格納する変数の初期化
# C[0]は使わない
C = [0]*N
# 幅優先探索用のcue
Q = deque([1])
while Q:
    q = Q.popleft()
    c = 0
    for w in tree[q]:
        # 色をインクリメントした際に親の色とかぶったら更に1を加算する
        # 他は単純なインクリメント
        c += 1 + int(C[q-1] == c+1)
        # エッジの色を格納
        C[w-1] = c
        # 子供をcueに追加
        Q.append(w)
print(max(C))
for b in B:
    print(C[b-1])
### BUGGY CODE ###

import sys
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
#from bisect import bisect_left as bl
input = sys.stdin.readline

n,Q=map(int,input().split())
xs = []
ts = set()
qs = []
for _ in range(n):
    s,t,x=map(int,input().split())
    xs += [(s-x-0.4,True,x), (t-x-0.5,False,x)]
    ts.add(x)
for _ in range(Q):
    xs.append((int(input()), 2, 0))
xs.sort(key=lambda x:x[0])

mx,XN = 10**9,len(ts)
x2i = {x:i for i,x in enumerate(ts)}
st = SegTree([mx]*XN, XN, mx, min)
for t,r,x in xs:
    if r == 2:
        c = st.query(0,XN)
        print(c if c!= mx else -1)
    else:
        st.update(x2i[x], x if r else mx)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n,Q=map(int,input().split())
b_num = 2**(n-1).bit_length()
mx = 10**9
segl=[mx]*2*b_num 

def update( k, x):
    k += b_num-1
    segl[k] = x
    while k+1:
        k = (k-1)//2
        segl[k] = min(segl[k*2+1],segl[k*2+2])
    
if __name__ == '__main__':
    xs = []
    for i in range(n):
        s,t,x=map(int,input().split())
        xs += [(s-x-0.4,True,x,i), (t-x-0.5,False,x,i)]
    for _ in range(Q):
        xs.append((int(input()),2))
    xs.sort(key=lambda x:x[0])
    for x in xs:
        if x[1]==2:
            print(segl[0] if segl[0]!= mx else -1)
            continue
        update(x[3], x[2] if x[1] else mx)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

def dfs(v,p=-1):
  for u in graph[v]:
    if u == p: continue
    ans[u] += ans[v]
    dfs(u,v)

N,Q = map(int,input().split())
graph = {i:[] for i in range(1,N+1)}
ans = [0 for i in range(N+1)]
for _ in range(N-1):
  a,b = map(int,input().split())
  graph[a].append(b)
  graph[b].append(a)

for _ in range(Q):
  p, x = map(int,input().split())
  ans[p] += x

dfs(1)
print(*ans[1:])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
input=lambda :sys.stdin.readline()

def sol():

  N,Q = map(int,input().split())
  graph = [[] for i in range(N)]
  ans = [0 for i in range(N)]
  for _ in range(N-1):
    a,b = map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

  for _ in range(Q):
    p, x = map(int,input().split())
    ans[p-1] += x 
 
  def dfs(v,p=-1):
    for u in graph[v]:
      if u == p: continue
      ans[u] += ans[v]
      dfs(u,v)
  dfs(0)
  print(*ans)

sol()
### BUGGY CODE ###

n = int(input())
x = list(map(int, input().split()))
xs = sorted(x)
a = xs[n // 2 - 1]
b = xs[n // 2]
for i in range(n):
    if xs.index(x[i]) < n // 2:
        print(b)
    else:
        print(a)

### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
xs = sorted(x)
a = xs[n // 2 - 1]
b = xs[n // 2]
for i in x:
    if i <= a:
        print(b)
    else:
        print(a)
### BUGGY CODE ###

def main():
  s = ''.join(reversed(input()))
  multiplier = 1
  divisor = 10 ** 9 + 7
  list10 = list(range(10))
  list13 = list(range(13))
  p = [0 for i in list13]
  np = [0 for i in list13]
  if s[0] != '?':
    p[int(s[0])] = 1
  else:
    for j in list10:
      p[j] = 1
  for i in range(1, len(s)):
    multiplier = (10 * multiplier) % 13
    if s[i] != '?':
      r = int(s[i]) * multiplier
      for j in list13:
        np[(j + r) % 13] = p[j]
    else:
      r = 0
      for j in list10:
        for k in list13:
          np[(k + r) % 13] += p[k]
        r += multiplier
    for j in list13:
      p[j] = np[j] % divisor
      np[j] = 0
  print(p[5] % divisor)
main()

### FIXED CODE ###

s = ''.join(reversed(input()))
multiplier = 1
divisor = 10 ** 9 + 7
p = [0 for i in range(13)]
if s[0] != '?':
  p[int(s[0])] = 1
else:
  for j in range(10):
    p[j] = 1
for i in range(1, len(s)):
  multiplier = (10 * multiplier) % 13
  np = [0 for j in range(13)]
  if s[i] != '?':
    r = int(s[i]) * multiplier
    for j in range(13):
      np[(j + r) % 13] = p[j]
  else:
    for j in range(10):
      r = j * multiplier
      for k in range(13):
        np[(k + r) % 13] += p[k]
  for j in range(13):
    p[j] = np[j] % divisor
print(p[5] % divisor)
### BUGGY CODE ###

#import time
#t1=time.time()

n=int(input())
a=list(map(int,input().split()))
count=0
flag=1
a.reverse()
l=a

for i in range(n):
  if a[-i-1]==flag:
    flag+=1
  else:
    l=l[:-1]
    count+=1

if count==n:
  print(-1)
else:
  print(count)

#t2=time.time()
#print(t2-t1)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
count=0
flag=1

l=a
left=0
for i in range(n):
  if l[i]==flag:
    flag+=1
  else:
    count+=1
    
if count==n:
  print(-1)
else:
  print(count)
### BUGGY CODE ###

n, k = map(int, input().split())
h = [int(input()) for _ in range(n)]
h.sort()
ans = h[-1]
for i in range(n-k+1):
    trees = h[i:i+k]
    ans = min(
        ans,
        trees[-1] - trees[0]
    )
print(ans)


### FIXED CODE ###

import numpy as np
n, k = map(int, input().split())
h = [int(input()) for _ in range(n)]
h.sort()
h_max = np.array(h[k-1:])
h_min = np.array(h[:-k+1])
print(min(h_max - h_min))
### BUGGY CODE ###

import sys
def inpl(): return list(map(int, sys.stdin.readline().split()))
N, K = map(int, sys.stdin.readline().split())
A = inpl()
dic = {}
for i in range(N):
    dic[i+1] = A[i]
i = 1
visit = []
visit_set = set()
while i not in visit:
    visit.append(i)
    i = dic[i]
find = visit.index(i)
if K < find:
    print(visit[K])
else:
    root = visit[find:]
    length = len(root)
    K = (K-find) % length
    print(root[K])


### FIXED CODE ###

N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
i = 0
visit = []
visit_set = set()
while i not in visit_set:
    visit.append(i)
    visit_set.add(i)
    i = A[i] - 1
find = visit.index(i)
if K < find:
    print(visit[K] + 1)
else:
    root = visit[find:]
    K = (K-find) % len(root)
    print(root[K] + 1)
### BUGGY CODE ###

import sys
from functools import lru_cache

sys.setrecursionlimit(100000)


@lru_cache(maxsize=None)
def dfs(v):
    lv = links[v]
    return max(dfs(u) for u in lv) + 1 if lv else 0


n, m = map(int, input().split())
sss = set(range(n))
links = [set() for _ in range(n)]
for line in sys.stdin.readlines():
    x, y = map(int, line.split())
    x -= 1
    y -= 1
    sss.discard(y)
    links[x].add(y)

print(max(dfs(v) for v in sss))


### FIXED CODE ###

import sys
from functools import lru_cache

sys.setrecursionlimit(1000000)


@lru_cache(maxsize=None)
def dfs(v):
    lv = links[v]
    return max(map(dfs, lv)) + 1 if lv else 0


n, m = map(int, input().split())
sss = set(range(n))
links = [set() for _ in range(n)]
for line in sys.stdin.readlines():
    x, y = map(int, line.split())
    x -= 1
    y -= 1
    sss.discard(y)
    links[x].add(y)

print(max(map(dfs, sss)))
### BUGGY CODE ###

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

a.sort()
bc.sort(key=lambda x:x[1],reverse=True)
d = []
for i in bc:
    for j in range(i[0]):
        d.append(i[1])
#print(d)

if len(d) < n:
    for i in range(n-len(d)):
        d.append(0)

ans = 0
for i in range(n):
    if a[i] < d[i]:
        ans += d[i]
    else:
        ans += a[i]
print(ans)

### FIXED CODE ###

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

for i in a:
    bc.append([1,i])
bc.sort(key=lambda x:x[1],reverse=True)
#print(bc)
ans = 0
for i in bc:
    d = min(i[0],n)
 #   print(d)
    ans += i[1] * d
    n -= d
print(ans)
### BUGGY CODE ###

K = int(input())
S = input()

mod = 10**9 + 7

class Combination:
    def __init__(self, n):
        self.facts = [1 for i in range(n+1)]
        self.invs = [1 for i in range(n+1)]

        for i in range(1, n+1):
            self.facts[i] = self.facts[i-1] * i % mod
        self.invs[n] = pow(self.facts[n], mod-2, mod)
        for i in range(1, n+1):
            self.invs[n-i] = self.invs[n-i+1] * (n-i+1) % mod

    def ncr(self, n, r):
        if n < r:
            return 0
        if n < 0 or r < 0:
            return 0
        else:
            return self.facts[n] * self.invs[r] * self.invs[n-r] % mod

    def nhr(self, n, r):
        if n < r:
            return 0
        if n < 0 or r < 0:
            return 0
        else:
            return self.ncr(n+r-1, n-1)

N = K+len(S)
pow25 = [1] * (N+1)
pow26 = [1] * (N+1)
for i in range(1, N+1):
    pow25[i] = (pow25[i-1] * 25) % mod
    pow26[i] = (pow26[i-1] * 26) % mod

comb = Combination(K+len(S))

ans = 0
for i in range(K+1):
    ans = (ans + comb.ncr(N-i-1, len(S)-1) * pow25[N-i-len(S)] * pow26[i]) % mod

print(ans)

### FIXED CODE ###

K = int(input())
S = input()

mod = 10**9 + 7

class Combination:
    def __init__(self, n):
        self.facts = [1 for i in range(n+1)]
        self.invs = [1 for i in range(n+1)]
        
        for i in range(1, n+1):
            self.facts[i] = self.facts[i-1] * i % mod
            self.invs[i] = pow(self.facts[i], mod-2, mod)

    def ncr(self, n, r):
        if n < r:
            return 0
        if n < 0 or r < 0:
            return 0
        else:
            return self.facts[n] * self.invs[r] * self.invs[n-r] % mod

    def nhr(self, n, r):
        if n < r:
            return 0
        if n < 0 or r < 0:
            return 0
        else:
            return self.ncr(n+r-1, n-1)

N = K+len(S)
comb = Combination(K+len(S))

ans = 0
for i in range(K+1):
    ans = (ans + comb.ncr(N-i-1, len(S)-1) * pow(25, N-i-len(S), mod) * pow(26, i, mod)) % mod

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

left, right = map(int, input().split())

min = 2019
for i in range(left, right+1):
    for j in range(i+1, right+1):
        tmp = (i * j) % 2019
        if tmp < min:
            min = tmp

print(min)


### FIXED CODE ###

left, right = map(int, input().split())

min = 2019
for i in range(left, right+1):
    for j in range(i+1, right+1):
        tmp = (i * j) % 2019
        if tmp < min:
            min = tmp
        if min == 0:
            print(min)
            exit()

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

N = int(input())
import sys
input = sys.stdin.readline
a = []
for i in range(1,N+1):
    a.append(int(input()))
ans = 1
check = a[0]
pre_index = 1
while True:
    if check == 2:
        print(ans)
        exit()
    if pre_index == a[check-1]:
        print(-1)
        exit()
    pre_index = check
    check = a[check-1]
    ans += 1

### FIXED CODE ###

N = int(input())
import sys
input = sys.stdin.readline
a = []
for i in range(1,N+1):
    a.append(int(input()))
ans = 1
check = a[0]
pre_index = 1
while True:
    if 10**5 < ans:
        print(-1)
        exit()
    if check == 2:
        print(ans)
        exit()
    if pre_index == a[check-1]:
        print(-1)
        exit()
    pre_index = check
    check = a[check-1]
    ans += 1
### BUGGY CODE ###

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

scores = []
s = 1
for j in range(K):
    s *= A[j]

for i in range(N-K+1):
    scores.append(s)
    if i == N-K:
        break
    s = s // A[i]
    s *= A[K+i]

for i in range(len(scores)-1):
    if scores[i+1] > scores[i]:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

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

for i in range(N-K):
    if A[K+i] > A[i]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

from collections import deque
import numpy as np
n,m,k=map(int,input().split())
link=[[] for _ in range(n)]
block=[[]  for _ in range(n)]
ans=[]
s=[]
for i in range(m):
    a,b=map(int,input().split())
    link[a-1].append(b-1)
    link[b-1].append(a-1)
for i in range(k):
  a,b=map(int,input().split())
  block[a-1].append(b-1)
  block[b-1].append(a-1)
for i in range(n):#スタートの選び方
    visited=[]
    q=deque([i])
    while len(q)>0:
        x=q.pop()
        visited.append(x)
        for j in link[x]:
            if j in visited:
              continue
            elif j in q:
              continue
            else:q.append(j)
    ans.append(len(visited))
    s.append(visited)
res=[]
for i in range(n):
  l=len((set(link[i]+block[i])&set(s[i])))+1
  res.append(l)
print(*(np.array(ans)-np.array(res)))

### FIXED CODE ###

class UnionFind():
    def __init__(self,n):
      self.n=n
      self.root=[-1]*(n+1)
      self.rank=[0]*(n+1)
      
    def find(self,x):
      if self.root[x]<0:
        return x
      else:
        self.root[x]=self.find(self.root[x])
        return self.root[x]
    
    def unite(self,x,y):
      x=self.find(x)
      y=self.find(y)
      if x==y:
        return 0
      elif self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      else:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
          
    def Same(self,x,y):
      return self.find(x)==self.find(y)
    
    def size(self,x):
      return -self.root[self.find(x)]
import sys
input=sys.stdin.buffer.readline
n,m,k=map(int,input().split())
link=UnionFind(n)
f=[0]*n
block=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    link.unite(a,b)
    f[a]+=1
    f[b]+=1
for _ in range(k):
    a,b=map(int,input().split())
    block[a-1].append(b-1)
    block[b-1].append(a-1)
ans=[]
for i in range(n):
  ret=link.size(i)-f[i]-1
  for j in block[i]:
    if link.Same(i,j):
      ret-=1
  ans.append(ret)
print(*ans)
### BUGGY CODE ###

import math
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
A.sort()
#A = [i for i in range(2, N+2)]

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

D = []
E = []

for i, x in enumerate(A):
  Flag = True

  if i >= 1 and x == D[-1]:
    E.append(x)
    continue

  if i >= 1000 and D[0] != 1 and is_prime(x):
    D.append(x)
    continue
    
  for j in D:
    if x%j == 0:
      Flag = False
      if x == j:
        E.append(x)
      break
    
  if Flag:
    D.append(x)

print(len(set(D)-set(E)))

### FIXED CODE ###


import math
from collections import defaultdict

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

D = defaultdict(int)

AM = A[-1]
dp = [True]*(AM)

for x in A:
  if dp[x-1]:
    temp = 2 * x
    while temp <= AM:
      dp[temp-1] = False
      temp += x

for x in A:
  if dp[x-1]:
    D[x] += 1

ans = len([i for i in D if D[i] == 1])

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

N=int(input())
S=list(str(input()))
R=[]
G=[]
B=[]
for i in range(N):
	if S[i]=='R':
		R.append(i)
	elif S[i]=='G':
		G.append(i)
	else:
		B.append(i)
ans=0
for r in R:
	for g in G:
		for b in B:
			p=r+g+b
			if p==3*r or p==3*g or p==3*b:
				pass
			else:
				ans+=1
print(ans)

### FIXED CODE ###

N=int(input())
S=list(str(input()))
R=0
G=0
B=0
for i in range(N):
	if S[i]=='R':
		R+=1
	elif S[i]=='G':
		G+=1
	else:
		B+=1
ans=G*B*R
for a in range(N-1):
	for d in range(1,(N-a-1)//2+1):
		if S[a]!=S[a+d] and S[a+d]!=S[a+d*2] and S[a]!=S[a+d*2]:
			ans-=1
print(ans)
### BUGGY CODE ###

s = input()
n = int(input())
c = 0
left_l = ['', '']
right_l = ['', '']
s_l = [s, s[::-1]]
for _ in range(n):
  lst = [i for i in input().split()]
  if lst[0] == '1':
    if c == 1:
      s_l[0], s_l[1] = s_l[1], s_l[0]
      s = s_l[0]
      #print(s)
    else:
      s_l = [left_l[0] + s_l[0] + right_l[0], right_l[1] + s_l[1] + left_l[1]]
      s_l[0], s_l[1] = s_l[1], s_l[0]
      s = s_l[0]
      left_l = ['', '']
      right_l = ['', '']
      c = 1
      #print(s)
  elif lst[0] == '2':
    c = 0
    if lst[1] == '1':
      left_l = [lst[2] + left_l[0], left_l[1] + lst[2]]
    elif lst[1] == '2':
      right_l = [right_l[0] + lst[2], lst[2] + right_l[1]]
s = left_l[0] + s_l[0] + right_l[0]
print(s)

### FIXED CODE ###

s = input()
n = int(input())
c = 0
left_l = ['', '']
right_l = ['', '']
s_l = [s, s[::-1]]
for _ in range(n):
  lst = [i for i in input().split()]
  if lst[0] == '1':
    if c == 1:
      s_l[0], s_l[1] = s_l[1], s_l[0]
      #print(s)
    else:
      s_l = [right_l[1] + s_l[1] + left_l[1], left_l[0] + s_l[0] + right_l[0]]
      left_l[0], left_l[1] = '', ''
      right_l[0], right_l[1] = '', ''
      c = 1
      #print(s)
  elif lst[0] == '2':
    c = 0
    if lst[1] == '1':
      left_l[0] = lst[2] + left_l[0]
      left_l[1] = left_l[1] + lst[2]
    elif lst[1] == '2':
      right_l[0] = right_l[0] + lst[2]
      right_l[1] = lst[2] + right_l[1]
w = left_l[0] + s_l[0] + right_l[0]
print(w)
### BUGGY CODE ###

n, q = [int(i) for i in input().split()]
s = input()
l = [0] * q
r = [0] * q
for i in range(q):
  l[i], r[i] = [int(j) for j in input().split()]
for i in range(q):
  t = s[l[i]-1:r[i]]
  print(t.count("AC"))
  
  

### FIXED CODE ###

n, q = [int(i) for i in input().split()]
s = input()
ans = ""
table = [0] * n
cnt = 0
for i in range(n-1):
  if s[i:i+2] == "AC":
    cnt += 1
  table[i+1] = cnt
for i in range(q):
  l, r = [int(j) for j in input().split()]
  print(table[r-1] - table[l-1])