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

#H=4
#W=6
#
#S[0]=["#",".",".","#",".","."]
#S[1]=[".",".",".",".",".","#"]
#S[2]=[".",".",".",".","#","."]
#S[3]=["#",".","#",".",".","."]

H,W=map(int,input().split())
S=[0]*H
for i in range(H):
    S[i]=list(input())


MAP=[[[0,0,0,0] for i in range(W)]for i in range(H)]
#MAP[H][W]

#ue
for i in range(W):
    c=0
    d=0
    for j in range(H):
        if(S[j][i]=="."):
            c+=1
            MAP[j][i][0]+=c
        else:
            c=0
        if(S[H-j-1][W-i-1]=="."):
            d+=1
            MAP[H-j-1][W-i-1][0]+=d
        else:
            d=0

#hidari
for j in range(H):
    c=0
    d=0
    for i in range(W):
        if(S[j][i]=="."):
            c+=1
            MAP[j][i][0]+=c
        else:
            c=0
        if(S[H-j-1][W-i-1]=="."):
            d+=1
            MAP[H-j-1][W-i-1][0]+=d
        else:
            d=0

#migi
MAX=0
for j in range(H):
    for i in range(W-1,-1,-1):
        MAX=max(MAX,MAP[j][i][0]-3)

print(MAX)

### FIXED CODE ###

#H=4
#W=6
#
#S[0]=["#",".",".","#",".","."]
#S[1]=[".",".",".",".",".","#"]
#S[2]=[".",".",".",".","#","."]
#S[3]=["#",".","#",".",".","."]

H,W = map(int,input().split())

S = [[0]*W for i in range(H)]

for i in range(H):
    T=list(input())
    for j in range(W):
        if T[j] == "#":
            S[i][j] = 0
        else:
            S[i][j] = 1
MAP=[[0]*(W+2) for i in range(H+2)]
MAPH=[[0]*(W+2) for i in range(H+2)]
MAPU=[[0]*(W+2) for i in range(H+2)]
MAPL=[[0]*(W+2) for i in range(H+2)]
MAPR=[[0]*(W+2) for i in range(H+2)]

MAX=0

for i in range(1,W+1):
    for j in range(1,H+1):
            MAPH[j][i]=(MAPH[j-1][i]+1)*S[j-1][i-1]
            MAP[j][i]+=MAPH[j][i]
            MAPU[H-j+1][W-i+1]=(MAPU[H-j+2][W-i+1]+1)*S[H-j][W-i]
            MAP[H-j+1][W-i+1]+=MAPU[H-j+1][W-i+1]
for j in range(1,H+1):
    for i in range(1,W+1):
            MAPL[j][i]=(MAPL[j][i-1]+1)*S[j-1][i-1]
            MAP[j][i]+=MAPL[j][i]
            MAPR[H-j+1][W-i+1]=(MAPR[H-j+1][W-i+2]+1)*S[H-j][W-i]
            MAP[H-j+1][W-i+1]+=MAPR[H-j+1][W-i+1]
            MAX=max(MAX,MAP[j][i]-3,MAP[H-j+1][W-i+1]-3)
print(MAX)
### BUGGY CODE ###

N=int(input())
P = list(map(int,input().split()))
ans=0


for i in range(N):
    an=0
    for j in range(0, i):
        if P[j]>=P[i]:
            an+=1
        else:
            an+=0
    if an==i:
        ans+=1
    else:
        ans+=0
print(ans)

### FIXED CODE ###

N=int(input())
P = list(map(int,input().split()))
ans=0
m=P[0]
 
for i in range(N):
    if m >= P[i]:
        ans += 1
        m = P[i]

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

NK = input().split(' ')
N = int(NK[0])
K = int(NK[1])
 
while True:
  d = abs(N-K)
  if d<N:
    N = d
  else:
    break

print(N)

### FIXED CODE ###

NK = input().split(' ')
N = int(NK[0])
K = int(NK[1])

while N>K:
  N = N%K
  
print(min([N,K-N]))
### BUGGY CODE ###

import collections
n = int(input())



stock = []
ans = 0
for i in range(n):
  str = collections.Counter(input().strip())
  ans += stock.count(str)
  stock.append(str)

print(ans)


### FIXED CODE ###

import collections
n = int(input())



stock = collections.Counter()
ans = 0


for i in range(n):
  str = tuple(sorted(collections.Counter(input().strip()).items()))
  ans += stock[str]
  stock[str] += 1

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

r,g,b,n = (int(i) for i in input().split())
ans = 0
for i in range(n//r+1):
    for j in range(n//g+1):
        k = (n-r*i-j*g)//b
        if sum([r*i,j*g,abs(b*k)]) == n:
            ans += 1
print(ans)


### FIXED CODE ###

r,g,b,n = (int(i) for i in input().split())
ans = 0
for i in range(n//r+1):
    for j in range((n-(i*r))//g+1):
        k = (n-r*i-j*g)//b
        if r*i+j*g+abs(k*b) == n:
            ans += 1
print(ans)
### BUGGY CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
from collections import deque
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N, Q = map(int, readline().split())

    path = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, readline().split())
        path[a-1].append(b-1)
        path[b-1].append(a-1)

    child = [[] for _ in range(N)]
    child[0] = path[0]
    used = [False] * N
    used[0] = True
    que = deque(child[0])
    while que:
        x = que.popleft()
        used[x] = True
        for a in path[x]:
            if used[a]:
                continue
            else:
                child[x].append(a)
                que.append(a)

    counter = [0]*N
    for _ in range(Q):
        p, x = map(int, readline().split())
        que.append(p-1)
        counter[p-1] += x
        while que:
            a = que.popleft()
            for b in child[a]:
                counter[b] += x
                que.append(b)
    print(' '.join(map(str, counter)))

if __name__ == '__main__':
    main()



### FIXED CODE ###

from collections import deque
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7


def main():
  N, Q = map(int, readline().split())
  AB = [[int(x) for x in readline().split()] for _ in range(N-1)]
  PX = [[int(x) for x in readline().split()] for _ in range(Q)]
  
  graph = [[] for _ in range(N+1)]
  for ab in AB:
    graph[ab[0]].append(ab[1])
    graph[ab[1]].append(ab[0])
  
  value = [0] * (N+1)
  for px in PX:
    value[px[0]] += px[1]
  
  stack = deque([1])
  parent = [0] * (N+1)
  while stack:
    x = stack.popleft()
    for y in graph[x]:
      if y == parent[x]:
        continue
      parent[y] = x
      stack.append(y)
      value[y] += value[x]
      
  print(' '.join(map(str, value[1:])))
      
if __name__ == '__main__':
  main()
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
a_s = list(map(int, input().split()))
bs = list(map(int, input().split()))
cs = list(map(int, input().split()))
a_s.sort(reverse=True)
bs.sort(reverse=True)
cs.sort(reverse=True)

list = []
i = -1
# flag = True
minlist = 0
for a in a_s:
    if minlist >= (a + bs[0] + cs[0]):
        break
    for b in bs:
        if minlist >= (a + b + cs[0]):
            break
        for c in cs:
            abc = a + b +c
            if i >= k:
            # if flag and i >= k:
                list.sort(reverse=True)
                minlist = list[k]
                # flag = False
            if minlist >= abc:
                break
            list.append(abc)
            i += 1
list.sort(reverse=True)
for i in range(k):
    print(list[i])


### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ab = []
for ai in a:
  for bi in b:
    ab.append(ai + bi)
ab.sort(reverse = True)

abc = []

for abi in ab[:k]:
  for ci in c:
    abc.append(abi + ci)
abc.sort(reverse = True)

for abci in abc[:k]:
  print(abci)
### BUGGY CODE ###

#N, K = map(int, input().split( ))
#L = list(map(int, input().split( )))
N = int(input())
A = list(map(int, input().split( )))
Q = int(input())
Sum = sum(A)
#Q個の整数の組(B,C)が与えられてB \to Cとして合計を計算
#合計は(Ci-Bi)*(A.count(Bi))変化する.
for i in range(Q):
  E= list(map(int, input().split( )))
  b, c = E[0], E[1]
  dis = c - b 
  Num = A.count(b)
  Sum = Sum + dis*Num
  print(Sum)
  A = [c if a == b else a for a in A]

### FIXED CODE ###

from collections import Counter
#N, K = map(int, input().split( ))
#L = list(map(int, input().split( )))
N = int(input())
A = list(map(int, input().split( )))
Q = int(input())
Sum = sum(A)
#Counterなるものがあるらしい
coun = Counter(A)
#Q個の整数の組(B,C)が与えられてB \to Cとして合計を計算
#合計は(Ci-Bi)*(A.count(Bi))変化する.
for _ in range(Q):
  b, c = map(int, input().split( ))
  Sum += (c-b)*coun[b]
  coun[c] += coun[b]
  coun[b] = 0
  print(Sum)
  # replaceするとタイムエラーになるのか…
  #  A = [c if a == b else a for a in A]
### 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 = [0] * len(indexes)
for i, v in enumerate(indexes):
    ans[i] = l[v]

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 ###

import sys
input = sys.stdin.readline


def main():
    s = "".join(input().split())
    q = int(input())
    queries = [list(input().split()) for _ in range(q)]
    flg = True
    for query in queries:
        if query[0] == "1":
            flg = not flg
            continue
        if query[1] == "1":
            if flg:
                s = query[2] + s
            else:
                s = s + query[2]
        else:
            if flg:
                s = s + query[2]
            else:
                s = query[2] + s
    if not flg:
        s = s[::-1]
    print(s)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    s = input().strip()
    q = int(input())
    queries = [input().split() for _ in range(q)]
    pre = []
    post = []
    flg = True
    for query in queries:
        if query[0] == "1":
            flg = not flg
            continue
        if query[1] == "1":
            if flg:
                pre.append(query[2])
            else:
                post.append(query[2])
        else:
            if flg:
                post.append(query[2])
            else:
                pre.append(query[2])
    pre.reverse()
    pre.append(s)
    pre.extend(post)
    s = "".join(pre)
    if not flg:
        s = s[::-1]
    print(s)


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

z=int(input())

def inv_gcd(a, b):
    a = (a + b) % b
    if a == 0:
        return (b, 0)
    s, t = b, a
    m0, m1 = 0, 1
 
    while t:
        u = s // t
        s -= t * u
        m0 -= m1 * u
 
        tmp = s
        s = t
        t = tmp
        tmp = m0
        m0 = m1
        m1 = tmp
    
    if m0 < 0:
        m0 += b // s
    return (s, m0)
 
 
def crt(r, m):
    n = len(r)
    r0, m0 = 0, 1
 
    for i in range(n):
        r1, m1 = (r[i] + m[i]) % m[i], m[i]
 
        if m0 < m1:
            m0, m1 = m1, m0
            r0, r1 = r1, r0
        
        if m0 % m1 == 0:
            if r0 % m1 != r1:
                return (0, 0)
            continue
        
        g, im = inv_gcd(m0, m1)
 
        u1 = m1 // g
        if (r1 - r0) % g:
            return (0, 0)
        
        x = (r1 - r0) // g % u1 * im % u1
 
        r0 += x * m0
        m0 *= u1
        if (r0 < 0):
            r0 += m0
        
    return (r0, m0)



def divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
      if n % i == 0:
          divisors.append(i)
          if i != n // i:
              divisors.append(n//i)
  divisors.sort()
  return divisors

#print(divisors(2*z))

# for n in range(1,10):
#   # (変数) = (条件がTrueのときの値) if (条件) else (条件がFalseのときの値)
#   ans = n-1 if n%2 else 2*n-1
#   print(ans)

#print(chinese_remainder([2, 3, 2], [3, 5, 7]))

ans = z-1 if z%2 else 2*z-1
for i in divisors(2*z):
  y=2*z//i
  if y == 1:
    continue
  a=[0,-1]
  b=[i,y]
  rem, mod = crt(a, b)
  #print(rem)
  #print(mod)
  if rem == mod == 0:
      continue
  ans = min(ans, rem)

print(ans if z-1 else 1)

### FIXED CODE ###

def inv_gcd(a, b):
    a = (a + b) % b
    if a == 0:
        return (b, 0)
    s, t = b, a
    m0, m1 = 0, 1
 
    while t:
        u = s // t
        s -= t * u
        m0 -= m1 * u
 
        tmp = s
        s = t
        t = tmp
        tmp = m0
        m0 = m1
        m1 = tmp
    
    if m0 < 0:
        m0 += b // s
    return (s, m0)
 
 
def crt(r, m):
    n = len(r)
    r0, m0 = 0, 1
 
    for i in range(n):
        r1, m1 = (r[i] + m[i]) % m[i], m[i]
 
        if m0 < m1:
            m0, m1 = m1, m0
            r0, r1 = r1, r0
        
        if m0 % m1 == 0:
            if r0 % m1 != r1:
                return (0, 0)
            continue
        
        g, im = inv_gcd(m0, m1)
 
        u1 = m1 // g
        if (r1 - r0) % g:
            return (0, 0)
        
        x = (r1 - r0) // g % u1 * im % u1
 
        r0 += x * m0
        m0 *= u1
        if (r0 < 0):
            r0 += m0
        
    return (r0, m0)


def divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i:
        divisors.append(n//i)
  divisors.sort()
  return divisors


# print(divisors(z))

z=int(input())


ans = z-1 if z%2 else 2*z-1
for i in divisors(2*z):
  y=2*z//i
  if y == 1:
    continue
  a=[0,-1]
  b=[i,y]
  rem, mod = crt(a, b)
  #print(rem)
  #print(mod)
  if rem == mod == 0:
      continue
  ans = min(ans, rem)

print(ans if z-1 else 1)
### BUGGY CODE ###

N, M = map(int, input().split())
A = []
B = []

a, b = map(int, input().split())

A.append(a)
B.append(b)

if N != 1:
    for n in range(N-1):
        a, b = map(int, input().split())
        swi = 0
        for j in range(len(A)):
            if A[j] > a:
                A.insert(j, a)
                B.insert(j, b)
                swi = 1
                break
        if swi == 0:
            A.append(a)
            B.append(b)

cntSum = 0
moneySum = 0

for n in range(N):
    if cntSum + B[n] > M:
        moneySum += A[n] * (M - cntSum)
        cntSum += M - cntSum
        break
    else:
        cntSum += B[n]
        moneySum += A[n] * B[n]

print(moneySum)


### FIXED CODE ###

n, m = map(int, input().split())
abList = sorted([list(map(int, input().split())) for _ in range(n)])
abSum = 0
abNum = m
for i in range(n):
    ab = abList[i]
    a, b = ab[0], ab[1]
    if b >= abNum:
        abSum += abNum * a
        break
    else:
        abSum += b * a
        abNum -= b
print(abSum)
### BUGGY CODE ###

n = int(input())
s = input()

ans = []
for i in range(n-1):
    w = s[:i].count('W')
    e = s[i+1:].count('E')
    ans.append(w+e)

ans.append(s[:n].count('W'))

print(min(ans))

### FIXED CODE ###

n = int(input())
S = input()

e = S.count('E')
w = 0
ans = e
for s in S:
    if s == 'E':
        e -= 1
    else:
        w += 1
    ans = min(ans,e+w)

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

from collections import defaultdict

n, m = [int(i) for i in input().split()]

A = defaultdict(int)
p = 10 ** 9 + 7

i = 2

def fact(n, p=10**9 + 7):
    f = [1]
    for i in range(1, n+1):
        f.append(f[-1]*i%p)
    return f

def invfact(n, f, p=10**9 + 7):
    inv = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        inv.append(inv[-1]*i%p)
    return inv[::-1]

f = fact(30+10**5)
invf = invfact(30+10**5, f)

while m != 1:
    while m % i == 0:
        m //= i
        A[i] += 1
    i += 1

n -= 1
ans = 1

for v in A.values():
    ans *= f[v+n] * invf[n] * invf[v] % p
    ans %= p

print(ans)

### FIXED CODE ###

import math
from collections import defaultdict

n, m = [int(i) for i in input().split()]

A = defaultdict(int)
p = 10 ** 9 + 7

if m == 1:
    print(1)
    exit()

def fact(n, p=10**9 + 7):
    f = [1]
    for i in range(1, n+1):
        f.append(f[-1]*i%p)
    return f

def invfact(n, f, p=10**9 + 7):
    inv = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        inv.append(inv[-1]*i%p)
    return inv[::-1]

f = fact(30+10**5)
invf = invfact(30+10**5, f)

def comb(a, b):
    return f[a] * invf[b] * invf[a-b] % p

i = 2

while m != 1 and i <= math.sqrt(m) + 1:
    while m % i == 0:
        m //= i
        A[i] += 1
    i += 1

if not A:
    print(n)
    exit()

if m != 1:
    A[m] = 1

n -= 1
ans = 1

for v in A.values():
    ans *= comb(v+n, n)
    ans %= p

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

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]

# A * B  = N - C
N = int(input())
count = 0
for i in range(1, N):
    count += len(make_divisors(i))

print(count)

### FIXED CODE ###

N = int(input())

N_m1 = N - 1
counter = 0
for i in range(1, N_m1 + 1):
    counter += N_m1 // i

print(counter)
### BUGGY CODE ###

N, x = map(int, input().split())
A = list(map(int, input().split()))
lowest_costs = A[:]
ans = float('inf')

for k in range(N):
    cost = 0
    for i in range(N):
        lowest_costs[i] = min(lowest_costs[i], A[(i-k) % N])
        cost += lowest_costs[i]
    ans = min(cost + x * k, ans)

print(ans)

### FIXED CODE ###

N, x = map(int, input().split())
A = list(map(int, input().split()))
lowest_costs = A[:]
ans = float('inf')

for k in range(N):
    lowest_costs = [min(lowest_costs[i], A[i-k]) for i in range(N)]
    ans = min(sum(lowest_costs) + x * k, ans)

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

import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a.reverse()
mod = 7 + 10**9
leng = 61
data = [[0 for i in range(leng+1)] for j in range(n)]
#pre
for i in range(n):
    k = list(bin(a[i]))
    k.reverse()
    ll = len(k)
    for j in range(1, leng+1):
        if j - 1 >= ll:
            data[i][j] = data[i - 1][j]
            continue
        if k[j - 1] == "1":
            data[i][j] = data[i - 1][j] + 1
        else:
            data[i][j] = data[i-1][j]
ans = 0
a.reverse()
data.reverse()
for i in range(n-1):
    k = deque(bin(a[i]))
    k.reverse()
    k.pop()
    k.pop()
    k = deque(map(int, k))
    for s in range(leng - len(k)):
        k.append(0)
    for j in range(leng):
        if k[j] == 1:
            ans += ((n - i - 1) - data[i+1][j+1]) * (2**j)
            ans %= mod
        else:
            ans += data[i+1][j+1] * (2**j)
            ans %= mod
print(ans)


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.reverse()
    mod = 7 + 10**9
    leng = len(format(max(a), 'b'))
    bit_acc = [0 for i in range(leng)]
    for i in range(n):
        #先頭から二進数を0埋めした
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                bit_acc[j] += 1
    ans = 0
    p = [pow(2,leng - 1 - j, mod) for j in range(leng)]
    for i in range(n):
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                ans += (n - bit_acc[j]) * p[j]
            else:
                ans += bit_acc[j] * p[j]
            ans %= mod
    print((ans * 500000004) % mod)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

def main():
  N = int(input())
  li = list(map(int, input().split()))

  num_of_operation = 0
  
  while True:
    for num in li:
      if num % 2 == 1:
        break
    
    for i in range(N):
      li[i] /= 2
    num_of_operation += 1
  
  print(num_of_operation)

if __name__ == '__main__':
  main()


### FIXED CODE ###

def main():
    N = int(input())
    li = list(map(int, input().split()))

    num_of_operation = 0
    is_dividable = True

    while True:
        for num in li:
            if num % 2 != 0:
                is_dividable = False
                break

        if not is_dividable:
            break

        for i in range(N):
            li[i] //= 2
        num_of_operation += 1

    print(num_of_operation)


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

s = [1 if x == "R" else -1 for x in input()]
ans = [0]*len(s)
for i in range(len(s)):
    locate = i
    while s[locate+s[locate]] == s[i]:
        locate += s[locate]
    distance = abs(locate - i) + 1
    ans[i + s[i]*distance -1*s[i]*(distance%2)] += 1
print(*ans)


### FIXED CODE ###

import math
s = [1 if x == "R" else -1 for x in input()]
ans = [0]*len(s)
i = 0
while i < len(s):
    locate = i
    if locate < len(s)-1:
        while s[locate+1] == s[i]:
            locate += 1
            if locate >= len(s)-1:
                break
    count = locate - i + 1
    tmp = math.ceil(count/2)
    if s[i] == 1:
        ans[locate] += tmp
        ans[locate+1] += count - tmp
    else:
        ans[i] += tmp
        ans[i-1] += count - tmp
    i = locate + 1
print(*ans)
### BUGGY CODE ###

def main():
    N = int(input())
    l = [int(i) for i in input().split()]

    l.sort()
    ans = 0
    for i in range(N-2):
        for j in range(i+1,N-1):
            tmp = l[i] + l[j]
            for k in range(j+1,N):
                if l[k] < tmp:
                    ans +=1
                else:
                    break
    
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import bisect
import time

def main():
    N = int(input())
    L = [int(i) for i in input().split()]
    #N = 2000
    #L = [int(i) for i in range(N)]

    L.sort()
    ans = 0
    for i in range(N-2):
        for j in range(i+1,N-1):
            #ans += bisect.bisect_left(L[j+1:], L[i]+L[j])
            index = bisect.bisect_left(L, L[i]+L[j])
            ans += (index - (j+1))

    print(ans)


if __name__ == "__main__":
    #start = time.time()
    main()
    #elapsed_time = time.time() - start
    #print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")
### BUGGY CODE ###

import fractions
from functools import reduce
def gcd(i):
    return reduce(fractions.gcd, i)
N = int(input())
A = list(map(int, input().split()))
tmp = []
for i in range(N):
    if i == 0 :
        tmp.append(gcd(A[1:]))
    elif i == N-1:
        tmp.append(gcd(A[:N-1]))
    else:
        tmp.append(gcd(A[:i]+A[i+1:]))
print(max(tmp))

### FIXED CODE ###

import fractions
from functools import reduce
def gcd(*i):
    return reduce(fractions.gcd, i)
def main():
    N = int(input())
    A = list(map(int, input().split()))
    L=[0]
    R=[0]
    for i in range(N):
        L.append(gcd(L[i],A[i]))
        R.append(gcd(R[i],A[-(i+1)]))
    R=R[::-1]
    ans=[]
    for i in range(N):
        ans.append(gcd(L[i],R[i+1]))
    print(max(ans))
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

for i in range(Q):
    l, r = map(int, input().split())
    S2=S[l-1:r]
    #print(S2)
    S3=S2.split("AC")
    #print(S3)
    print(len(S3)-1)


### FIXED CODE ###

N, Q = map(int, input().split())
S=input()
S1=S.split("AC")
#print(S1)
C=[]
SC=[0]*len(S)
i=0
ac=0
for a in S1:
    #SC[i]=
    #i+=len(a)
    C.append(len(a))

    #SC[i]=ac
    #SC[i+1]=ac+1
    #i+=2
    #ac+=1
    #C.append(2)

for c in C:
    for j in range(i,i+c):
        SC[j]=ac
    i+=c
    try:
        SC[i]=ac
        SC[i+1]=ac+1
    except:
            break
    ac+=1
    i+=2


#print(i,ac)
#print(C)
#print(SC)


for i in range(Q):
    l, r = map(int, input().split())
    x=SC[r-1]-SC[l-1]
    #x=
    print(x)