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

def pr(data,next,head,tail):
    i = head
    while(1):
        if i == -1:
            print("")
            break
        print(data[i],end = "")
        i = next[i]
        if i != -1 :
            print(" ",end = "")

def ins_f(data,next,prev,x,head,tail):
    size = len(data)
    if head != -1 :
        data.append(x)
        size += 1
        next.append(head)
        prev.append(-1)
        prev[head] = size -1
        head = size -1
    else :
        data.append(x)
        size += 1
        next.append(-1)
        prev.append(-1)
        tail = size-1
        head = size-1
    return head,tail

def dl(data,next,prev,x,head,tail):
    i = head
    while(1):
        if data[i] == x:
            if i == head:
                head,tail = dl_f(next,prev,head,tail)
                break
            elif i == tail:
                head,tail = dl_l(next,prev,head,tail)
                break
            else :
                prev[next[i]] = prev[i]
                next[prev[i]] = next[i]
                break
        elif i == tail:
            break
        i = next[i]
    return head,tail

def dl_f(next,prev,head,tail):
    if head == -1:
        return head
    elif next[head] == -1:
        head = -1
        tail = -1
    else:
        prev[next[head]] = -1
        head = next[head]
    return head,tail

def dl_l(next,prev,head,tail):
    if tail == -1:
        pass
    elif prev[tail] == -1:
        head = -1
        tail = -1
    else:
        next[prev[tail]] = -1
        tail = prev[tail]
    return head,tail

n = int(input())
data = []
next = []
prev = []
head = -1
tail = -1
size = len(data)

for i in range(n):
    x = input().split()
    if x[0] == "insert":
        head,tail = ins_f(data,next,prev,x[1],head,tail)
    elif x[0] == "delete":
        head,tail = dl(data,next,prev,x[1],head,tail)
    elif x[0] == "deleteFirst":
        head,tail = dl_f(next,prev,head,tail)
    elif x[0] == "deleteLast":
        head,tail = dl_l(next,prev,head,tail)
pr(data,next,head,tail)



### FIXED CODE ###

from collections import deque

def pr(a):
    for i in range(len(a)):
        if i == len(a)-1:
            print(a[i])
        else:
            print(a[i],end = " ")

n = int(input())
q = deque()
for i in range(n):
    x = input()
    l = len(x)
    if x[0] == "i":
        q.insert(0,x[7:])
    elif x[6] == " ":
        try:
            q.remove(x[7:])
        except:
            pass
    elif l > 10:
        q.popleft()
    elif l > 6:
        q.pop()

print(*q)
### BUGGY CODE ###

n = int(input())
s = list(input() for _ in range(n))

l = list(set(s))

if len(l) == len(s):
    s.sort()
    for i in s:
        print(i)
    exit()

count = [0] * len(l)
for i, v in enumerate(l):
    count[i] = s.count(v)

m = max(count)
indexes = [i for i, x in enumerate(count) if x == m]

ans = []
for i in indexes:
    ans.append(l[i])

ans.sort()

for i in ans:
    print(i)

### FIXED CODE ###

import collections

n = int(input())
s = list(input() for _ in range(n))

c = dict(collections.Counter(s))
m = max(c.values())
ans = [k for k, v in c.items() if v == m]

ans.sort()
for i in ans:
    print(i)
### BUGGY CODE ###

a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
if a[1]>=a[0]:
    print(0)
else:
    c=[]
    if a[0]<=a[1]*2:
        for i in range(a[0]-a[1]):
            c.append(min(b))
            b.remove(min(b))
        print(sum(c))
    else:
        for i in range(a[1]):
            b.remove(max(b))
        print(sum(b))

### FIXED CODE ###

a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
if a[1]>=a[0]:
    print(0)
else:
    print(sum(sorted(b)[:a[0]-a[1]]))
### BUGGY CODE ###

n = int(input())

total = 0
for i in range(1, n):
    for j in range(1, n):
        if i * j < n:
            total += 1
print(total)



### FIXED CODE ###

n = int(input())

total = 0
for i in range(1, n + 1):
    j = n // i
    if n % i == 0:
        j -= 1
    total += j

print(total)
### BUGGY CODE ###

import sys
H, W = map(int, input().split())
G = [sys.stdin.readline() for _ in range(H)]

counts = [[[-1] * 4 for _ in range(W + 1)] for _ in range(H + 1)]
for h in range(H):
    for w in range(W):
        if G[h][w] == ".":
            counts[h][w][0] = counts[h][w-1][0] + 1
            counts[h][w][1] = counts[h-1][w][1] + 1
        dih = H - h - 1
        diw = W - w - 1
        if G[dih][diw] == ".":
            counts[dih][diw][2] = counts[dih][diw+1][2] + 1
            counts[dih][diw][3] = counts[dih+1][diw][3] + 1
ans = 0
for h in range(H):
    for w in range(W):
        if G[h][w] == ".":
            ans = max(ans, sum(counts[h][w]) + 1)
print(ans)

### FIXED CODE ###

import sys
H, W = map(int, input().split())
G = [sys.stdin.readline() for _ in range(H)]

counts = [[[-1] * 4 for _ in range(W + 1)] for _ in range(H + 1)]
for h in range(H):
    for w in range(W):
        if G[h][w] == ".":
            counts[h][w][0] = counts[h][w-1][0] + 1
            counts[h][w][1] = counts[h-1][w][1] + 1
        dih = H - h - 1
        diw = W - w - 1
        if G[dih][diw] == ".":
            counts[dih][diw][2] = counts[dih][diw+1][2] + 1
            counts[dih][diw][3] = counts[dih+1][diw][3] + 1
ans = 0
for h in range(H):
    for w in range(W):
        if G[h][w] == ".":
            ans = max(ans, sum(counts[h][w]) + 1)
print(ans)
### BUGGY CODE ###

base = input().split()
n = int(base[0])
k = int(base[1])
ans = []
def fnk(a):
  if a>=0:
    return a
  else:
    return a*(-1)
if n%k==0:
  print(0)
elif n%k==1:
  print(1)
else:
  while fnk(n-k) not in ans:
    ans.append(fnk(n-k))
    n = fnk(n-k)
  print(min(ans))


### FIXED CODE ###

base = input().split()
n = int(base[0])
k = int(base[1])
s = n%k
t = k-s
if s>t:
  print(t)
else:
  print(s)
### BUGGY CODE ###

from operator import mul
from functools import reduce

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

result = reduce(mul, a)
if result <= 10 ** 18:
    print(result)
else:
    print(-1)


### FIXED CODE ###

import sys

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

if 0 in a:
    print(0)
    sys.exit()

hg = 10 ** 18
ans = 1
for i in a:
    ans *= i
    if ans > hg:
        print(-1)
        sys.exit()

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

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n, m = MAP()
a = LIST()
for i in range(m):
    aa = max(a)
    idx = a.index(aa)
    a[idx] //= 2
print(sum(a))

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from heapq import heapify, heappop, heappush
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n, m = MAP()
a = [-i for i in LIST()]
heapify(a)
for i in range(m):
    b = heappop(a)
    b = - (- b // 2)
    heappush(a, b)
print(-sum(a))
### BUGGY CODE ###

import numpy as np

N, K = map(int, input().split())
A = list(map(int, input().split()))
B = [0]*len(A)

for _ in range(K):
  for i in range(N):
    l = max(0, i-A[i])
    r = min(N-1, i+A[i])
    B[l]+=1
    if r+1 < N:
      B[r+1]-=1
  A = np.cumsum(B)
  if min(A) == N:
    break
  B = [0]*len(A)
A = map(str, A)
print(' '.join(A))

### FIXED CODE ###

import numpy as np
from numba import njit

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


@njit
def search(a):
  B = np.zeros_like(a)
  for i in range(N):
    l = max(0, i-a[i])
    r = min(N-1, i+a[i])
    B[l]+=1
    if r+1 < N:
      B[r+1]-=1
  B = np.cumsum(B)
  return B

for _ in range(K):
  A = search(A)
  if min(A) == N:
      break
A = map(str, A)
print(' '.join(A))
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC137 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def Bellman_Ford(edges,num_v, start):
    #start → iの最短距離
    #start:始点, num_v:頂点数, edges:[辺の始点, 辺の終点, 辺のコスト]
    dist = [-float('inf') for _ in range(num_v)]
    #dist[i] := s→iの最短距離
    dist[start] = 0
    flg = 0
    for _ in range(1000):
        update = False
        for i in range(num_v):
            for edge in edges:
                e_from, e_to, e_cost = edge
                if e_from != -float('inf') and dist[e_to] < dist[e_from] + e_cost:
                    dist[e_to] = dist[e_from] + e_cost
                    update = True
        if not update:
            flg = 1
            break
    return dist, flg

n,m,p = LI()
edge = []
for _ in range(m):
    a,b,c = LI()
    edge.append([a-1,b-1,c-p])
d,f = Bellman_Ford(edge,n,0)
if d[-1] < 0:
    print(0)
elif not f:
    print(-1)
else:
    print(d[-1])


### FIXED CODE ###

#!/usr/bin/env python3
#ABC137 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def Bellman_Ford(edges,num_v, start):
    #start → iの最短距離
    #start:始点, num_v:頂点数, edges:[辺の始点, 辺の終点, 辺のコスト]
    dist = [-float('inf') for _ in range(num_v)]
    #dist[i] := s→iの最短距離
    dist[start] = 0
    flg = 0
    for i in range(num_v):
        update = False
        for edge in edges:
            e_from, e_to, e_cost = edge
            if e_from != -float('inf') and visited[e_to] and dist[e_to] < dist[e_from] + e_cost:
                dist[e_to] = dist[e_from] + e_cost
                update = True
        if not update:
            flg = 1
            break
    return dist, flg

n,m,p = LI()
edge = []
f = defaultdict(dict)
for _ in range(m):
    a,b,c = LI()
    edge.append([a-1,b-1,c-p])
    f[b-1][a-1] = 1
visited = [False]*n
def dfs(x):
    visited[x] = True
    for t in f[x].keys():
        if not visited[t]:
            dfs(t)
dfs(n-1)
d,f = Bellman_Ford(edge,n,0)
if not f:
    print(-1)
else:
    print(max(0,d[-1]))
### BUGGY CODE ###

from itertools import combinations
import bisect
N, K = map(int, input().split())
xy = [tuple(map(int, input().split())) for i in range(N)]
xy.sort(key=lambda x: x[0])
X = [x[0] for x in xy]

ans = 40**18
for a, b in combinations(range(N), 2):
    A, B = max(xy[a][0], xy[b][0]), min(xy[a][0], xy[b][0])
    r = bisect.bisect_right(X, A)
    l = bisect.bisect_left(X, B)
    for c, d in combinations(range(N), 2):
        tmp = 0
        C, D = max(xy[c][1], xy[d][1]), min(xy[c][1], xy[d][1])

        for i in range(l, r):
            if xy[i][1] <= C and xy[i][1] >= D:
                tmp += 1
        #     print(xy[i][1], C, D)

        if tmp >= K and ans > (A-B) * (C - D):
            ans = (A-B) * (C - D)

print(ans)


### FIXED CODE ###

from itertools import combinations
N, K = map(int, input().split())
xy = [tuple(map(int, input().split())) for i in range(N)]

ans = float("inf")
for p1, p2 in combinations(xy, 2):
    x1 = p1[0]
    x2 = p2[0]
    if x2 < x1:
        x1, x2 = x2, x1
        #x2 > x1
    for p3, p4 in combinations(xy, 2):
        y1 = p3[1]
        y2 = p4[1]
        if y2 < y1:
            y1, y2 = y2, y1
        # y2 >= y1
        count = 0
        for x, y in xy:
            if x >= x1 and x <= x2 and y >= y1 and y <= y2:
                count += 1

        if count >= K:
            ans = min(ans, (x2-x1)*(y2-y1))


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


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

dp = [[0,0,0]] #bitをset代わりとして用いる [bitset,最後に置いた数字,転倒数]の構成

for loop in range(N): #N枚のカードを置いていく

    ndp = [] #次のループのdp配列
    for ing in dp: #dpの中の各場合について次の場合を調べる

        bit = ing[0]
        lastnum = ing[1]
        revnum = ing[2]

        for i in range(N): #各カードが後ろにおけるかを判定

            if bit & (2**i) > 0: #既に使われてたら飛ばす
                continue

            revnum_add = 0
            for j in range(N): #転倒数がいくつ増えるかの計算
                if j > i and bit&(2**j) > 0:
                    revnum_add += 1

            if i % 2 == loop % 2: #置く位置と初期位置の偶奇が等しければ表
                if A[i] >= lastnum: #置けるなら置く
                    ndp.append([ bit|(2**i) , A[i] ,revnum+revnum_add])

            else:
                if B[i] >= lastnum:
                    ndp.append([ bit|(2**i) , B[i] ,revnum+revnum_add])


    dp = ndp


ans = float("inf") #答えは最小の転倒数
for ing in dp:
    ans = min(ans,ing[2])

if ans == float("inf"):
    ans = -1
print (ans)


### FIXED CODE ###


N = int(input())

A = list(map(int,input().split()))
B = list(map(int,input().split()))
ans = float("inf")

for ii in range(2 ** N):

    s = format(ii,'b').zfill(N)
    on = 0
    
    for j in s:
        if j == "1":
            on += 1

    if on != (N+1)//2:
        continue

    q = []
    q2 = []

    for i in range(N):
        if s[i] == "1":
            if i % 2 == 0:
                q.append([A[i],i])
            else:
                q.append([B[i],i])
        else:
            if i % 2 != 0:
                q2.append([A[i],i])
            else:
                q2.append([B[i],i])           

    q.sort()
    q2.sort()
    q2.append([float("inf"),0])
    #print (q,q2)

    flag = True
    nmax = 0

    for i in range((N+1)//2):


        if nmax > q[i][0]:
            flag = False
        nmax = q[i][0]

        if nmax > q2[i][0]:
            flag = False
        nmax = q2[i][0]

    if flag:
        r = []
        for i in range((N+1)//2):
            r.append(q[i][1])
            r.append(q2[i][1])

        #print (r)

        now = 0
        z = [i for i in range(N)]
        for i in range(N):
            for j in range(len(z)):
                if z[j] == r[i]:
                    now += j
                    del z[j]
                    break
            #print (z,now)
        ans = min(now,ans)

if ans == float("inf"):
    ans = -1
print (ans)
### BUGGY CODE ###

n = int(input())
l = [str(input()) for i in range(n)]

s = set(l)
c = [l.count(i) for i in s]

res = sorted([[c[i],list(s)[i]] for i in range(len(s))],key=lambda x: (-x[0],x[1]))
[print(i[1]) for i in res if i[0] == res[0][0]]


### FIXED CODE ###

import collections

n = int(input())
l = [str(input()) for i in range(n)]

c = collections.Counter(l).most_common()[::1]
res = sorted([i[0] for i in c if i[1] == c[0][1]])
[print(i) for i in res]
### BUGGY CODE ###

def main():
    from collections import deque
    N = int(input())
    G = [[] for _ in range(N)]
    edge = {}
    ans_key = []
    for i in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        edge[(a-1, b-1)] = -1
        ans_key.append((a-1, b-1))
    max_g = max(len(g) for g in G)

    def bfs(s, max_g):
        dist = [-1 for _ in range(N)]
        color = [{i+1 for i in range(max_g)} for _ in range(N)]
        que = deque()
        que.append(s)
        dist[s] = 0
        while que:
            u = que.popleft()
            for v in G[u]:
                if dist[v] != -1:
                    continue
                dist[v] = dist[u] + 1
                que.append(v)
                c = color[u].pop()
                color[v].discard(c)
                if u < v:
                    edge[(u, v)] = c
                else:
                    edge[(v, u)] = c

    bfs(0, max_g)
    print(max_g)
    for k in ans_key:
        print(edge[k])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    G = [[]*N for _ in range(N)]
    edge_color = {}
    key_ = []
    for _ in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        edge_color[(a-1, b-1)] = -1
        key_.append((a-1, b-1))
    from collections import deque
    deg_max = 0
    for g in G:
        deg_max = max(deg_max, len(g))

    G_color = ['WHITE' for _ in range(N)]
    G_distance = [float('inf') for _ in range(N)]
    G_parent = ['NIL' for _ in range(N)]

    def bfs(s):
        G_color[s] = 'GRAY'
        G_distance[s] = 0
        Q = deque()
        Q.append(s)
        while Q:
            u = Q.popleft()
            if G_parent[u] == 'NIL':
                now_color = 1
            else:
                now_color = (edge_color[(G_parent[u], u)] + 1) % deg_max
            for v in G[u]:
                if G_color[v] == 'WHITE':
                    G_color[v] = 'GRAY'
                    G_distance[v] = G_distance[u] + 1
                    G_parent[v] = u
                    Q.append(v)
                    edge_color[(u, v)] = now_color % deg_max
                    now_color += 1
            G_color[u] = 'BLACK'
    bfs(0)
    print(deg_max)
    for k in key_:
        print(edge_color[k]+1)


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

from itertools import combinations
from sys import stdin,setrecursionlimit
setrecursionlimit(10 ** 7)
n = int(stdin.readline().rstrip())
s = list(stdin.readline().rstrip())
li = [i for i in range(n)]
lin = list(combinations(li, 3))
point = 0
for i in lin:
    if s[i[0]] != s[i[1]] and s[i[2]] != s[i[1]] and s[i[0]] != s[i[2]]:
        if i[2]-i[1] != i[1]-i[0]:
            point += 1
print(point) 

### FIXED CODE ###

n = int(input())
s = input()
R = s.count("R")
G = s.count("G")
B = s.count("B")
point = 0
#全ての組み合わせ
for i in range(n-2):
    for j in range(i+1,n-1):
        k = j + j-i
        if k >= n:
            break
        if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            point += 1
print(R*G*B-point)
### BUGGY CODE ###

import copy

N = int(input())
A = [int(i) for i in input().split(' ')]

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


divisors_list = []

for i in A:
  divisors_list.append(make_divisors(i))
  
count = 0
for i in range(N):
  B = copy.copy(A)
  del B[i]
  flag = 0
  for j in divisors_list[i]:
    if(j in B):
      flag = 1
      break
  if(flag == 0):
    count += 1
      
      
print(count)




  
  


### FIXED CODE ###

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

MAX_A = 1000001

dp = [0]*MAX_A

for i in A:
  if dp[i] == 0:
    for j in range(i, MAX_A,i):
      dp[j] += 1
  else:
    dp[i] += 1

c = 0
for i in A:
  if dp[i] == 1:
    c += 1

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

from collections import deque

n, m = map(int, input().split())
g = [set() for _ in range(n)]

while m:
    s, t = map(int, input().split())
    g[s].add(t)
    g[t].add(s)
    m -= 1


def find(s, t):
    global g
    queue = deque()
    queue.append((0, s))
    queue.append((1, t))
    visited = ([0] * n, [0] * n)
    visited[0][s] = 1
    visited[1][t] = 1

    while queue:
        st, i = queue.popleft()
        for f in g[i]:
            if visited[not st][f]:
                g[s].add(t)
                g[t].add(s)
                return True
            if not visited[st][f]:
                visited[st][f] = 1
                queue.append((st, f))
    return False


q = int(input())
while q:
    s, t = map(int, input().split())
    print('yes' if find(s, t) else 'no')
    q -= 1

### FIXED CODE ###

n, m = map(int, input().split())
g = [set() for _ in range(n)]
group_ids = [0] * n

while m:
    s, t = map(int, input().split())
    g[s].add(t)
    g[t].add(s)
    m -= 1


def search(s, gid):
    global g, group_ids
    queue = set(g[s])
    group_ids[s] = gid

    while queue:
        i = queue.pop()
        if not group_ids[i]:
            group_ids[i] = gid
            queue.update(g[i])


gid = 1
for i in range(n):
    if group_ids[i]:
        continue
    search(i, gid)
    gid += 1

q = int(input())
while q:
    s, t = map(int, input().split())
    gs, gt = group_ids[s], group_ids[t]
    print('yes' if gs and gt and gs == gt else 'no')
    q -= 1
### BUGGY CODE ###

from collections import defaultdict,deque
from sys import stdin,setrecursionlimit
import heapq,bisect,math,itertools,string,queue,copy
setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, stdin.readline().split()))


K = int(input())
def main():
    k = 7
    count = 1
    if K %2==0:
        print(-1)
        return
    while True:
        if k % K == 0:
            print(count)
            return
        k = (k+7*(10**count))%K
        count += 1


main()


### FIXED CODE ###

from collections import defaultdict,deque
from sys import stdin,setrecursionlimit
import heapq,bisect,math,itertools,string,queue,copy
setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, stdin.readline().split()))


K = int(input())
def main():
    k = 7
    count = 1
    re = 1
    if K % 2==0:
        print(-1)
        return
    while True:
        if k % K == 0:
            print(count)
            return
        re =  (re*10)%K
        k = (k+7*re)%K
        count += 1
        if count >= 10**7:
            print(-1)
            return


main()
### BUGGY CODE ###

import re

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

ans = [0] * q

for i in range(q):
    l, r = map(int, input().split())
    sl = s[l - 1 : r]
    # sl = sl.replace("AC", "-")
    # ans = sl.count("-")
    # print(ans)

    result = re.findall(r"AC", sl)
    # print(len(result))
    ans[i] = len(result)
print(*ans, sep="\n")


### 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)
# print(t)
for j in range(q):
    l, r = map(int, input().split())
    print(t[r - 1] - t[l - 1])
### BUGGY CODE ###

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

### FIXED CODE ###

N = input()
A = list(map(int, input().split()))
 
if 0 in A:
    print(0)
    exit()
 
A = sorted(A)[::-1]
val = 1
 
for a in A:
    val *= a
    if val > 10 ** 18:
        print(-1)
        exit()
print(val)