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

import sys
input = sys.stdin.readline
from heapq import *
N, Q = map(int, input().split())
X = []
for _ in range(N):
    s, t, x = map(int, input().split())
    X.append((s-x,t-x,x))

X = sorted(X, key = lambda x: x[0])
i = 0
A, B, C = [], [], []
for _ in range(Q):
    d = int(input())
    while i < len(X) and d >= X[i][0]:
        a, b, x = X[i]
        heappush(A, (x, b))
        heappush(B, (b, x))
        i += 1
    while len(B) and B[0][0] <= d:
        b, x = heappop(B)
        heappush(C, (x, b))
    while len(C) and len(A) and C[0][0] == A[0][0]:
        heappop(A)
        heappop(C)
    print(A[0][0] if A else -1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
from bisect import bisect_left as bl
class segtree:
    def __init__(self, nn):
        self.NN = nn
        self.XX = [0] * (2**(nn+1)-1)
    def getmax(self, i):
        j = 2**self.NN + i - 1
        ma = -1
        while j >= 0:
            ma = max(ma, self.XX[j])
            j = (j-1) // 2
        return -1 if ma <= 0 else INF - ma
    def updaterange(self, a, b, x):
        l = a + (1<<self.NN)
        r = b + (1<<self.NN)
        s = 0
        while l < r:
            if l%2:
                self.XX[l-1] = max(self.XX[l-1], x)
                l += 1
            if r%2:
                r -= 1
                self.XX[r-1] = max(self.XX[r-1], x)
            l >>= 1
            r >>= 1

N, Q = map(int, input().split())
st = segtree(18)
INF = 1<<50
X = []
D = []
for _ in range(N):
    s, t, x = map(int, input().split())
    X.append((s, t, x))
for _ in range(Q):
    D.append(int(input()))

for s, t, x in X:
    st.updaterange(bl(D, s-x), bl(D, t-x), INF-x)
for i in range(Q):
    print(st.getmax(i))
### BUGGY CODE ###

import sys

N, M = map(int, input().split())
S = input()
T = input()

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

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

L = lcm(N, M)
X = [0 for i in range(L)]

for i in range(N):
    index = i * (L // N)
    X[index] = S[i]

for i in range(M):
    index = i * (L // M) 
    if X[index] != 0 and X[index] != T[i]:
        print(-1)
        sys.exit()
    
print(L)

### FIXED CODE ###

N, M = map(int, input().split())
S = input()
T = input()

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

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

L = lcm(N, M)
s = L // M
t = L // N

if S[::s] != T[::t]:
    L = -1
print(L)
### BUGGY CODE ###

from math import gcd
inpl = lambda: list(map(int,input().split()))
def primes(N):
    P = []
    for i in range(2,N):
        sieve = 1
        for p in P:
            if p*p > i:
                break
            elif i % p == 0:
                sieve = 0
                break
        if sieve == 0:
            continue
        else:
            P.append(i)
    return P

N = int(input())
A = inpl()

g = A[0]
for a in A:
    g = gcd(g,a)
if g > 1:
    print('not coprime')
    exit()

P = primes(1000)
for p in P:
    n = 0
    for i in range(N):
        if A[i] % p == 0:
            n += 1
            while A[i] % p == 0:
                A[i] //= p
            if n > 1:
                print('setwise coprime')
                exit()
s = set()
for a in A:
    if a == 1:
        continue
    elif a in s:
        print('setwise coprime')
        exit()
    else:
        s.add(a)
print('pairwise coprime')


### FIXED CODE ###

from math import gcd
inpl = lambda: list(map(int,input().split()))
def primes(N):
    P = []
    firstfactor = [1]*N
    for i in range(2,N):
        sieve = 1
        for p in P:
            if p*p > i:
                break
            elif i % p == 0:
                sieve = 0
                firstfactor[i] = p
                break
        if sieve == 0:
            continue
        else:
            firstfactor[i] = i
            P.append(i)
    return P, firstfactor

N = int(input())
A = inpl()

g = A[0]
for a in A:
    g = gcd(g,a)
if g > 1:
    print('not coprime')
    exit()

ff = primes(max(A)+1)[1]
st = set()
for a in A:
    prev = 0
    while a > 1:
        p = ff[a]
        a //= p
        if p == prev:
            continue
        elif p in st:
            print('setwise coprime')
            exit()
        else:
            prev = p
            st.add(p)
print('pairwise coprime')
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

def solve(G, p, ans, st, fst):
    cnt_1 = 0
    for nxt in G[p]:
        if nxt in st:
            cnt_1 += 1
    cnt_2 = 0
    for v in st:
        if p in G[v]:
            cnt_2 += 1
    if cnt_1 > 1 or cnt_2 > 1:
        return False
    elif cnt_1 == 1 and cnt_2 == 1:
        if fst in G[p]:
            for v in st:
                ans.append(v)
            return True
        else:
            return False
    for nxt in G[p]:
        st.add(nxt)
        if solve(G, nxt, ans, st, fst):
            return True
        st.remove(nxt)
    return False

def main():
    n, m = map(int, input().split())
    G = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        G[a].append(b)
    ans = []
    f = False
    st = set()
    for i in range(1, n+1):
        st.add(i)
        if solve(G, i, ans, st, i):
            f = True
            break
        st.remove(i)
    if f:
        print(len(ans))
        ans.sort()
        for v in ans:
            print(v)
    else:
        print(-1)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

def solve(G, p, ans, st, fst, arr, x):
    arr[p] = x
    cnt_1 = 0
    z = -1
    for nxt in G[p]:
        if nxt in st:
            cnt_1 += 1
            z = nxt
    cnt_2 = 0
    for v in st:
        if p in G[v]:
            cnt_2 += 1
    if cnt_1 > 1 or cnt_2 > 1:
        return False
    elif cnt_1 == 1 and cnt_2 == 1:
        if fst in G[p]:
            for v in st:
                ans.append(v)
            return True
        else:
            k = arr[z]
            for v in st:
                if arr[v] >= k:
                    ans.append(v)
            return True
    for nxt in G[p]:
        st.add(nxt)
        if solve(G, nxt, ans, st, fst, arr, x+1):
            return True
        st.remove(nxt)
    arr[p] = 0
    return False

def main():
    n, m = map(int, input().split())
    G = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        G[a].append(b)
    ans = []
    f = False
    st = set()
    arr = [0]*(n+1)
    for i in range(1, n+1):
        st.add(i)
        if solve(G, i, ans, st, i, arr, 1):
            f = True
            break
        st.remove(i)
    if f:
        print(len(ans))
        ans.sort()
        for v in ans:
            print(v)
    else:
        print(-1)

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

N, K = map(int, input().split())
A = [int(x) for x in input().split()]

A_past = 1
for Ai in A[:K]:
  A_past *= Ai

for i in range(N-K):
  A_now = 1
  for Ai in A[i+1:i+K+1]:
    A_now *= Ai
  if A_now > A_past:
    print("Yes")
  else:
    print("No")
  A_past = A_now



### FIXED CODE ###

N, K = map(int, input().split())
A = [int(x) for x in input().split()]

for i in range(N-K):
  t = A[i+K]/A[i]
  if t > 1:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

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

a.sort()

import collections
c = collections.Counter(a)

d=[]
for ck,cv in c.items():
    if cv>=2:
       d.append(ck) 
dset=set(d)
    
#aa=[]
aaset=set()
#icnt=0
while True:
    aaset.add(a[0])
#    aa.append(a[0])
    a2=[]
#    for i in range(1,len(a)):
    for i,ai in enumerate(a,1):
        if ai%a[0]!=0:
            a2.append(ai)
    a=a2.copy()
#    print(aa,a)     
    if len(a2)==0:
        break
#    icnt+=1
#    if icnt>10:break

#aaset=set(aa)
aaset=aaset-dset    
print(len(aaset))

### FIXED CODE ###

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

a.sort()
amax=max(a)
dp=[True]*(amax+1)

import collections
c = collections.Counter(a)

d=[]
for ck,cv in c.items():
    if cv>=2:
       d.append(ck) 
dset=set(d)
    
aa=set()
for ai in a:
    if dp[ai]:
        aa.add(ai)
        for aj in range(ai*2,amax+1,ai):
            dp[aj]=False

aa=aa-dset    
print(len(aa))
### BUGGY CODE ###

import copy
n, k = input().split()
m = list(map(int, input().split()))
ans = 0
kazu =[]
kai = []
kitai2 = 0
for x in range(int(n) - (int(k)-1)):
    kazu = []
    kazu = m[x:x+int(k)]
    if ans < sum(kazu):
        ans = sum(kazu)
        kai = copy.deepcopy(kazu)

for j in range(int(k)):
    kitai = 0
    for g in range(kai[j]):
        kitai += g+1
    kitai2 += kitai / kai[j]
print(kitai2)

### FIXED CODE ###

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

m = [(e + 1) / 2 for e in p]

t = sum(m[0:K])
result = t
for i in range(N - K):
    t -= m[i]
    t += m[i + K]
    if t > result:
        result = t
print(result)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from itertools import accumulate
N,K = list(map(int,input().split()))
p = list(map(int,input().split()))
E = [0]*N

for i in range(N):
  E[i] = (p[i]+1)/2
  
#acc = list(accumulate(E))
#print(E,acc)

for i in range(N-K+1):
  if i == 0:
    ans = sum(E[i:i+K])
  else:
    ans = max(ans,sum(E[i:i+K]))
print(ans)




### FIXED CODE ###

import itertools 
N,K =list(map(int,input().split()))
p =list(map(int,input().split()))
E = [0] * N

for i in range(N):
  E[i]=(p[i]+1)/2
acc = [0]
acc += list(itertools.accumulate(E))

ans = 0
for i in range(N-K+1):
  ans = max(acc[i+K] - acc[i], ans)

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

# C - Lamps

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

b = [0] * n
for kk in range(k):
    l = [i - a[i] for i in range(n)]
    r = [i + a[i] for i in range(n)]
    l.sort()
    r.sort()
    ln = 0
    rn = 0
    for i in range(n):
        while ln < n and l[ln] <= i:
            ln += 1
        while rn < n and r[rn] <  i:
            rn += 1
        b[i] = ln - rn
    a, b = b, a
    if all(v >= n for v in a):
        break

print(' '.join(map(str, a)))


### FIXED CODE ###

# C - Lamps

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

b = [0] * n
for kk in range(k):
    l = [i - a[i] for i in range(n)]
    r = [i + a[i] for i in range(n)]
    l.sort()
    r.sort()
    ln = 0
    rn = 0
    for i in range(n):
        while ln < n and l[ln] <= i:
            ln += 1
        while rn < n and r[rn] <  i:
            rn += 1
        b[i] = ln - rn
    a, b = b, a
    if all(v >= n for v in a):
        break

print(' '.join(map(str, a)))
### BUGGY CODE ###

from collections import Counter

def get_prime(n):
    prime = Counter()
    
    while not n % 2:
        prime[2] += 1
        n //= 2
        
    i = 3
    
    while i <= n**0.5:
        while not n % i:
            prime[i] += 1
            n //= i
        i += 2
        
    if n > 1: prime[n] += 1
        
    return prime
    
    
MOD = 10**9+7
    
N = int(input())
A = list(map(int, input().split()))

prime = Counter()

for a in A:
    p = get_prime(a
                  )
    for x, n in p.items():
        prime[x] = max(prime[x], n)
        
X = 1
for x, n in prime.items():
    X = X * pow(x, n, MOD)
    
print(sum([X//a for a in A]) % MOD)


### FIXED CODE ###

import sys
input = sys.stdin.readline

MOD = 10**9+7
def pow(a, b):
    res = 1
    while b:
        if b & 1: res = res * a % MOD
        a = a**2 % MOD
        b >>= 1
    return res

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = set(A)
    
    m = max(B)+1    
    prime = {i:i for i in range(m)}
    is_prime = [False] * m
    
    for i in range(2, int(m**0.5)+1):
        if is_prime[i]: continue
        is_prime[i] = True
        
        for j in range(2*i, m, i):
            if not is_prime[j]: prime[j] = i
            is_prime[j] = True
            
    from collections import Counter
    
    count = Counter()
            
    for a in A:
        c = Counter()
        while a > 1:
            n = prime[a]
            c[n] += 1
            a //= n
        for k, v in c.items(): count[k] = max(count[k], v)
            
    x = 1
    for k, v in count.items(): x = x * k**v % MOD
    
    ans = 0
    for a in A: ans += x * pow(a, MOD-2) % MOD
    
    print(ans%MOD)

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

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

A_list_min = sorted(A_list)
F_list_max = sorted(F_list, reverse=True)

first_OK = 10**12

def is_ok(arg):
    check_cnt = 0
    return_flag = 0
    for i in range(N):
        a_temp = A_list_min[i]
        while a_temp*F_list_max[i] > arg:
            check_cnt += 1
            a_temp -= 1
    if check_cnt <= K:
        return_flag = 1
    else:
        return_flag = 0
    return return_flag

def bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

print(bisect(-1, first_OK))

### FIXED CODE ###

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

A_list_min = sorted(A_list)
F_list_max = sorted(F_list, reverse=True)

first_OK = 10**12

def is_ok(arg):
    check_cnt = 0
    return_flag = 0
    for i in range(N):
        temp = A_list_min[i] - arg//F_list_max[i]
        if temp > 0:
            check_cnt += A_list_min[i] - arg//F_list_max[i]
    if check_cnt <= K:
        return_flag = 1
    else:
        return_flag = 0
    return return_flag

def bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

print(bisect(-1, first_OK))
### BUGGY CODE ###

import numpy as np

a=int(input())
b=list(map(int,input().split()))
b=np.array(b)

c=[[0 for s in range(a)] for _ in range(a)]
aa=0
for i in c:
    if aa==a-1:
        i[0]=1/2
        i[aa]=1/2
    else:
        i[aa+1]=1/2
        i[aa]=1/2
    aa+=1
c=np.array(c)

x=np.linalg.solve(c,b)
x=list(x)
for j in range(len(x)):
    x[j]=int(x[j])
print(" ".join(repr(e) for e in x))


### FIXED CODE ###

a=int(input())
b=list(map(int,input().split()))
c=sum(b[::2])-sum(b[1::2])
d=[c]
for i in b:
    d.append(2*i-c)
    c=2*i-c

d.pop()
print(*d)
### BUGGY CODE ###

S = input()
Q = int(input())

add_to_last = []
add_to_beginning = []

mode = 1
for i in range(Q):
  query = input()
  if query=='1':
    mode *= -1
  else:
    _, F, C = query.split()
    if F=='1':
      if mode==1:
        add_to_beginning.insert(0,C)
      else:
        add_to_last.append(C)
    else:
      if mode==1:
        add_to_last.append(C)
      else:
        add_to_beginning.insert(0,C)

if mode==1:
  print("".join(add_to_beginning), end="")
  print(S, end="")
  print("".join(add_to_last))
else:
  print("".join(add_to_last[::-1]), end="")
  print(S[::-1], end="")
  print("".join(add_to_beginning[::-1]))


### FIXED CODE ###

S = input()
Q = int(input())

add_to_last = []
add_to_beginning = []

queries = [input() for _ in range(Q)]

mode = 1
for i in range(Q):
  query = queries[i]
  if query=='1':
    mode *= -1
  else:
    _, F, C = query.split()
    if F=='1':
      if mode==1:
        add_to_beginning.append(C)
      else:
        add_to_last.append(C)
    else:
      if mode==1:
        add_to_last.append(C)
      else:
        add_to_beginning.append(C)   

if mode==1:
  add_to_beginning.reverse()
  print("".join(add_to_beginning), end="")
  print(S, end="")
  print("".join(add_to_last))
else:
  add_to_last.reverse()
  print("".join(add_to_last), end="")
  print(S[::-1], end="")
  print("".join(add_to_beginning))
### BUGGY CODE ###

s=list(input())
k1=int(input())
l1=set()
for i in range(len(s)):
    l1.add(s[i])
a1=[]
for i in range(len(l1)):
    a1.append(l1.pop())
a1.sort()
for i in range(len(a1)):
    str=a1[i]
    l2=set()
    for j in range(len(s)):
        if s[j]==str:
            l2.add(s[j])
            str2=s[j]
            for k in range(j+1,len(s)):
                str2+=s[k]
                l2.add(str2)
    if len(l2)>=k1:
        l3=sorted(l2)
        ans=l3[k1-1]
        break
    else:
        k1-=len(l2)
print(ans)


### FIXED CODE ###

s=list(input())
k1=int(input())
l1=set()
for i in range(len(s)):
    l1.add(s[i])
a1=[]
for i in range(len(l1)):
    a1.append(l1.pop())
a1.sort()
for i in range(len(a1)):
    str=a1[i]
    l2=set()
    for j in range(len(s)):
        if s[j]==str:
            l2.add(s[j])
            str2=s[j]
            for k in range(j+1,min(len(s),j+7)):
                str2+=s[k]
                l2.add(str2)
    if len(l2)>=k1:
        l3=sorted(l2)
        ans=l3[k1-1]
        break
    else:
        k1-=len(l2)
print(ans)
### BUGGY CODE ###

N = int(input()) - 1

LARGE = 10**9+7

def ex_euclid(x, y):
    c0, c1 = x, y
    a0, a1 = 1, 0
    b0, b1 = 0, 1
 
    while c1 != 0:
        m = c0 % c1
        q = c0 // c1
 
        c0, c1 = c1, m
        a0, a1 = a1, (a0 - q * a1)
        b0, b1 = b1, (b0 - q * b1)
 
    return c0, a0, b0
# precompute
fac_list = [1]*(N+1)
fac = 1
for i in range(1, N+1):
    fac = (fac * i) % LARGE
    fac_list[i] = fac
    
fac_inv_list = [1]*(N+1)
for i in range(N+1):
    c,a,b = ex_euclid(fac_list[i], LARGE)
    fac_inv_list[i] = a % LARGE
    
def nCr(n, r):
    return (((fac_list[n] * fac_inv_list[r]) % LARGE) * fac_inv_list[n-r]) % LARGE

def pat(n, r):
    return (((fac_list[n] * fac_inv_list[r]) % LARGE) * fac_inv_list[n-r]) % LARGE


pat = 0
score = 0

for k in range(N+1):
    if k-1 >= N-k:
        res = (((nCr(k-1, N-k)*fac_list[k]) % LARGE) * fac_list[N-k]) % LARGE
        score = (score + (res - pat) * k) % LARGE
        # print(k, pat, res)
        pat = res
print(score)

### FIXED CODE ###

N = int(input()) - 1

LARGE = 10**9+7

def ex_euclid(x, y):
    c0, c1 = x, y
    a0, a1 = 1, 0
    b0, b1 = 0, 1
 
    while c1 != 0:
        m = c0 % c1
        q = c0 // c1
 
        c0, c1 = c1, m
        a0, a1 = a1, (a0 - q * a1)
        b0, b1 = b1, (b0 - q * b1)
 
    return c0, a0, b0
# precompute
fac_list = [1]*(N+1)
fac = 1
for i in range(1, N+1):
    fac = (fac * i) % LARGE
    fac_list[i] = fac
    
fac_inv_list = [1]*(N+1)
for i in range(N+1):
    fac_inv_list[i] =  pow(fac_list[i], LARGE-2, LARGE)
    
def nCr(n, r):
    return (((fac_list[n] * fac_inv_list[r]) % LARGE) * fac_inv_list[n-r]) % LARGE

def pat(n, r):
    return (((fac_list[n] * fac_inv_list[r]) % LARGE) * fac_inv_list[n-r]) % LARGE


pat = 0
score = 0

for k in range(N+1):
    if k-1 >= N-k:
        res = (((fac_list[k-1]*fac_list[k]) % LARGE) * fac_inv_list[k-1-N+k]) % LARGE
        score = (score + (res - pat) * k) % LARGE
        # print(k, pat, res)
        pat = res
print(score)
### BUGGY CODE ###

import numpy as np

n = int(input())
l = []
r = []
ind = []
for i in range(n):
    li, ri = map(int, input().split())
    l.append(li)
    r.append(ri+1)
    ind.append(i)

arglmax = l.index(max(l))
argrmin = r.index(min(r))
num = 0
for i in range(n):
    num = max(r[i] - l[i], num)
ans1 = num + max(0, r[argrmin]-l[arglmax])

lst = [l, r, ind]
lst = list(np.array(lst).T)
lst = sorted(lst, key=lambda x: (x[0]), reverse=True)
lst = sorted(lst, key=lambda x: (x[1]))
lst = list(np.array(lst).T)
sorted_l = list(lst[0])
sorted_r = list(lst[1])
sorted_ind = list(lst[2])

ans2 = 0
for i in range(n-1):
    ai = max(0, min(np.array(sorted_r[i+1:])-l[arglmax]))
    bi = max(0, min(r[argrmin]-np.array(sorted_l[:i+1])))
    ans2 = max(ans2, ai+bi)

print(max(ans1, ans2))

### FIXED CODE ###

import numpy as np

n = int(input())
l = []
r = []
for i in range(n):
    li, ri = map(int, input().split())
    l.append(li)
    r.append(ri+1)

arglmax = l.index(max(l))
argrmin = r.index(min(r))
num = 0
for i in range(n):
    num = max(r[i] - l[i], num)
ans1 = num + max(0, r[argrmin]-l[arglmax])

lst = [l, r]
lst = list(np.array(lst).T)
lst = sorted(lst, key=lambda x: (x[0]), reverse=True)
lst = sorted(lst, key=lambda x: (x[1]))
lst = list(np.array(lst).T)
sorted_l = list(lst[0])
sorted_r = list(lst[1])

sorted_r_minus_lmax = list(np.array(sorted_r)-l[arglmax])
mini = sorted_r_minus_lmax[n-1]
for i in range(1, n):
    mini = min(mini, sorted_r_minus_lmax[n-1-i])
    sorted_r_minus_lmax[n-1-i] = mini
rmin_minus_sorted_l = list(r[argrmin]-np.array(sorted_l))
mini = rmin_minus_sorted_l[0]
for i in range(1, n):
    mini = min(mini, rmin_minus_sorted_l[i])
    rmin_minus_sorted_l[i] = mini

ans2 = 0
for i in range(n-1):
    ai = max(0, sorted_r_minus_lmax[i+1])
    bi = max(0, rmin_minus_sorted_l[i])
    ans2 = max(ans2, ai+bi)

print(max(ans1, ans2))
### BUGGY CODE ###

n = int(input())
a = [0] * n
for i in range(n):
  a[i] = int(input())

for i in range(n):
  b = [0] * n
  for j in range(n):
    if j == i:
      continue
    else:
      b[j] = a[j]
  print(max(b))

### FIXED CODE ###

n = int(input())
a = [0] * n
for i in range(n):
  a[i] = int(input())

asort = sorted(a,reverse=True)
for i in range(n):
  if a[i] == asort[0]:
    print(asort[1])
  else:
    print(asort[0])
### BUGGY CODE ###

#conding utf-8
N,Q=map(int,input().split())
S=input()
lr=[[int(i) for i in input().split()] for i in range(Q)]

AC=[0 for i in range(N)]

for i in range(N-1):
  if S[i:i+2]=="AC":
    AC[i]=1

for i in range(Q):
  print(sum(AC[lr[i][0]-1:lr[i][1]-1]))

### FIXED CODE ###

#conding utf-8
N,Q=map(int,input().split())
S=input()
lr=[[int(i) for i in input().split()] for i in range(Q)]

AC=[0]
tmp=0
for i in range(N-1):
  if S[i:i+2]=="AC":
    tmp=tmp+1
  AC.append(tmp)

for i in range(Q):
  print(AC[lr[i][1]-1]-AC[lr[i][0]-1])
### BUGGY CODE ###

array = [2,4,8,16,32,64]

num = int(input())
while num not in array:
     num -= 1
print(num)

### FIXED CODE ###

array = [2,4,8,16,32,64]

num = int(input())
while num not in array:
    if num == 1:
        break
    else:
        num -= 1
print(num)
### BUGGY CODE ###

N = int(input())
S = input()
answer = float('inf')
for i in range(N):
    count = 0
    left = list(S[:i])
    right = list(S[i+1:])
    for j in range(len(left)):
        if 'W' in left[j]:
            count += 1
    for j in range(len(right)):
        if 'E' in right[j]:
            count += 1
    if answer >= count:
        answer = count

    # print(left, right)

print(answer)

### FIXED CODE ###

N = int(input())
s = input()
numE = s.count('E')
numW = 0
answer = numE
for i in range(N):
    if s[i] == 'W':
        answer = min(answer, numE + numW)
        numW += 1
    else:
        numE -= 1
        answer= min(answer, numE + numW)
 
print(answer)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readlines = sys.stdin.buffer.readlines
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)


def main():
    OFS = 100005
    N = int(input())
    G = [[] for _ in [0]*OFS*2]
    for line in readlines():
        x, y = map(int, line.split())
        y += OFS
        G[x].append(y)
        G[y].append(x)

    def dfs(v):
        if v < OFS:
            counter[0] += 1
        else:
            counter[1] += 1

        for u in G[v]:
            if visited[u]:
                continue
            visited[u] = 1
            dfs(u)

    visited = [0]*OFS*2
    ans = 0
    for i in range(OFS):
        if visited[i]:
            continue
        counter = [0]*2
        visited[i] = 1
        dfs(i)
        ans += counter[0] * counter[1]

    print(ans - N)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readlines = sys.stdin.buffer.readlines
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)


def main():
    OFS = 100005
    N = int(input())
    G = [[] for _ in [0]*OFS*2]
    for line in readlines():
        x, y = map(int, line.split())
        y += OFS
        G[x].append(y)
        G[y].append(x)

    def dfs(v):
        if v < OFS:
            counter[0] += 1
        else:
            counter[1] += 1

        for u in G[v]:
            if visited[u]:
                continue
            visited[u] = 1
            dfs(u)

    visited = [0]*OFS*2
    ans = 0
    for i in range(OFS):
        if visited[i]:
            continue
        counter = [0]*2
        visited[i] = 1
        dfs(i)
        ans += counter[0] * counter[1]

    print(ans - N)


if __name__ == '__main__':
    main()