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

from sys import stdin
from collections import deque

H, W = [int(x) for x in stdin.readline().rstrip().split()]
maze = [stdin.readline().rstrip().split()[0] for _ in range(H)]

ans = 0

for h in range(H):
    for w in range(W):
        if maze[h][w] == '#':
            continue
        else:
            q = deque([(h, w, 0)])
            temp_h = h
            temp_w = w
            visited = [[0] * W for _ in range(H)]
            while len(q) > 0:
                temp = q.popleft()
                temp_h = temp[0]
                temp_w = temp[1]
                temp_d = temp[2]
                ans = max(ans, temp_d)
                visited[temp_h][temp_w] = 1
                if temp_h + 1 < H and maze[temp_h + 1][temp_w] == '.' and visited[temp_h + 1][temp_w] == 0:
                    q.append((temp_h + 1, temp_w, temp_d + 1))
                if temp_h - 1 >= 0 and maze[temp_h - 1][temp_w] == '.' and visited[temp_h - 1][temp_w] == 0:
                    q.append((temp_h - 1, temp_w, temp_d + 1))
                if temp_w + 1 < W and maze[temp_h][temp_w + 1] == '.' and visited[temp_h][temp_w + 1] == 0:
                    q.append((temp_h, temp_w + 1, temp_d + 1))
                if temp_w - 1 >= 0 and maze[temp_h][temp_w - 1] == '.' and visited[temp_h][temp_w - 1] == 0:
                    q.append((temp_h, temp_w - 1, temp_d + 1))

print(ans)

### FIXED CODE ###

from sys import stdin
import queue

H, W = [int(x) for x in stdin.readline().rstrip().split()]
maze = [stdin.readline().rstrip().split()[0] for _ in range(H)]

ans = 0

for h in range(H):
    for w in range(W):
        if maze[h][w] == '#':
            continue
        else:
            q = queue.Queue()
            q.put((h, w))
            visited = [[-1] * W for _ in range(H)]
            visited[h][w] = 0
            while q.qsize() > 0:
                temp = q.get()
                temp_h = temp[0]
                temp_w = temp[1]
                ans = max(ans, visited[temp_h][temp_w])
                if temp_h + 1 < H and maze[temp_h + 1][temp_w] == '.' and visited[temp_h + 1][temp_w] < 0:
                    visited[temp_h + 1][temp_w] = visited[temp_h][temp_w] + 1
                    q.put((temp_h + 1, temp_w))
                if temp_h - 1 >= 0 and maze[temp_h - 1][temp_w] == '.' and visited[temp_h - 1][temp_w] < 0:
                    visited[temp_h - 1][temp_w] = visited[temp_h][temp_w] + 1
                    q.put((temp_h - 1, temp_w))
                if temp_w + 1 < W and maze[temp_h][temp_w + 1] == '.' and visited[temp_h][temp_w + 1] < 0:
                    visited[temp_h][temp_w + 1] = visited[temp_h][temp_w] + 1
                    q.put((temp_h, temp_w + 1))
                if temp_w - 1 >= 0 and maze[temp_h][temp_w - 1] == '.' and visited[temp_h][temp_w - 1] < 0:
                    visited[temp_h][temp_w - 1] = visited[temp_h][temp_w] + 1
                    q.put((temp_h, temp_w - 1))

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

n, m = map(int, input().split())

p = m // n
while m % p != 0:
    p -= 1

print(p)


### FIXED CODE ###

n, m = map(int, input().split())

p = m // n
while m % p != 0:
    p -= 1

print(p)
### BUGGY CODE ###

n=int(input())
a=[int(i) for i in input().split()]
for i in range(n):
  x=0
  for j in set(a):
    c=a[0:i].count(j)+a[i+1:n].count(j)
    x+=int(c*(c-1)/2)
  print(x)

### FIXED CODE ###

n=int(input())
a=[int(i) for i in input().split()]
m=max(a)
l=[0]*(m+1)
c=[0]*(m+1)
for i in a:
  l[i]+=1
for i in set(a):
  c[i]=l[i]*(l[i]-1)/2
s=sum(c)
for i in range(n):
  print(int(s-c[a[i]]+(l[a[i]]-1)*(l[a[i]]-2)/2))
### BUGGY CODE ###

import math
A,B,N = map(int,input().split())
res = 0

for x in range(1, B+1):
  res = max(res, math.floor(A*x/B)-A*math.floor(x/B))
  if x == N:
    print(res)
    exit()

print(res)

### FIXED CODE ###

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

x = min(N, B-1)
print((A*x//B) - A*(x//B))
### BUGGY CODE ###

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

sum_A = sum(A)
ans = abs(2 * A[0] - sum_A)

for i in range(1, N - 1):
    temp = 0
    for j in range(i):
        temp += A[j]
    temp = abs(2 * temp - sum_A)
    if temp < ans:
        ans = temp

print(ans)



### FIXED CODE ###

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

sum_A = sum(A)
temp = 2 * A[0] - sum_A
ans = abs(temp)

for i in range(1, N - 1):
    temp = temp + 2 * A[i]
    if abs(temp) < ans:
        ans = abs(temp)

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

import sys
n = int(input())
la = list(map(int, input().split()))
ans = 1
for i in la:
  ans *= i

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

### FIXED CODE ###

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default
      
n = int(input())
la = list(map(int, input().split()))
import sys
if my_index(la, 0) > 0:
  print(0)
  sys.exit()

ans = 1
for i in la:
  ans *= i
  if ans > 10**18:
    print(-1)
    sys.exit()
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7
ans = 0
for i in range(60):
    count = sum(1 for j in a if j>>i & 1)
    ans += count * (n-count) * pow(2,i,mod)
print(ans % mod)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7
ans = 0
for i in range(60):
    mask = 1 << i
    count = sum(1 for j in a if mask & j == 0)
    ans += count * (n-count) * pow(2,i,mod)
print(ans % mod)
### BUGGY CODE ###

N,K=map(int,input().split())
H=list(map(int,input().split()))
dp=[0 for i in range(N)]
def calcmin(n,d):#インデックスがnのノードまでいくための最小コスト（最大移動距離はd）
  p=dp[n-d]+abs(H[n-d]-H[n])
  for q in range(d):
    if p>dp[n-(d-q)]+abs(H[n-(d-q)]-H[n]):
      p=dp[n-(d-q)]+abs(H[n-(d-q)]-H[n])
  return p
for i in range(min(K,N)):
  dp[i]=calcmin(i,i)
for i in range(K,N):
  dp[i]=calcmin(i,K)
print(dp[N-1]) 

### FIXED CODE ###

N,K=map(int,input().split())
H=list(map(int,input().split()))
dp=[0 for i in range(N)]
def calcmin(n,d):#インデックスがnのノードまでいくための最小コスト（最大移動距離はd）
  p=dp[n-d]+abs(H[n-d]-H[n])
  for q in range(d):
    if p>dp[n-(d-q)]+abs(H[n-(d-q)]-H[n]):
      p=dp[n-(d-q)]+abs(H[n-(d-q)]-H[n])
  return p
for i in range(min(K,N)):
  dp[i]=calcmin(i,i)
for i in range(K,N):
  dp[i]=calcmin(i,K)
print(dp[N-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def func(x, nn):
    value = 0
    for i in range(nn - 1):
        for j in range(i + 1, nn):
            value += x[i] ^ x[j]
    ans = value % (10 ** 9 + 7)
    return ans

def main():
    n = int(input())
    li = list(map(int, input().split()))
    print(func(li, n))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import numpy as np
n = int(input())
arr = np.array([int(i) for i in input().split()])
mod = 10 ** 9 + 7
s = 0

for i in range(60):
    t = arr & 1
    c1 = np.count_nonzero((arr & 1))
    s += 2 ** i * c1 * (n - c1)
    arr >>= 1

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

from collections import deque
import copy

H, W = map(int, input().split())
a = [list(input()) for _ in range(H)]
d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
que = deque([(i, j) for i in range(H) for j in range(W) if a[i][j] == '#'])
count = 0

flag_all = False

while True:
	count += 1

	que_next = deque()
	while que:
		i, j = que.popleft()
		for k in range(4):
			dx, dy = d[k][0], d[k][1]
			x = i + dx
			y = j + dy
			if x >= 0 and x < H and y >= 0 and y < W and a[x][y] != '#':
				a[x][y] = '#'
				que_next.append((x, y))

	que = copy.copy(que_next)

	if not que:
		break
print(count-1)


### FIXED CODE ###

from collections import deque
import copy

H, W = map(int, input().split())
a = [list(input()) for _ in range(H)]
d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
que = deque([(i, j) for i in range(H) for j in range(W) if a[i][j] == '#'])
count = 0

flag_all = False

while True:
	count += 1

	que_next = deque()
	while que:
		i, j = que.popleft()
		for k in range(4):
			dx, dy = d[k][0], d[k][1]
			x = i + dx
			y = j + dy
			if x >= 0 and x < H and y >= 0 and y < W and a[x][y] != '#':
				a[x][y] = '#'
				que_next.append((x, y))

	que = copy.copy(que_next)

	if que:
		que = copy.copy(que_next)
	else:
		break
print(count-1)
### BUGGY CODE ###

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from itertools import accumulate

def resolve():
    it = map(int, sys.stdin.read().split())
    N, K = next(it), next(it)
    A = [next(it) for i in range(N)]

    for k in range(K):
        B = [0]*(N+1)
        for i, di in enumerate(A):
            lhs = max(0, i-di)
            rhs = min(i+di+1, N)

            B[lhs] += 1
            B[rhs] -= 1

        if B[0] == N:
            print(*[N]*N)
            return
        A = accumulate(B)

    print(*list(A)[:-1])

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from itertools import accumulate

def resolve():
    it = map(int, sys.stdin.read().split())
    N, K = next(it), next(it)
    A = [next(it) for i in range(N)]

    for k in range(K):
        B = [0]*(N+1)
        for i, di in enumerate(A):
            lhs = max(0, i-di)
            rhs = min(i+di+1, N)

            B[lhs] += 1
            B[rhs] -= 1

        if B[0] == N:
            print(*[N]*N)
            return
        A = accumulate(B)

    print(*list(A)[:-1])

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

s=list(input())
q=int(input())
for i in range(q):
    data=input().split()
    if(len(data)==1):
       s.reverse()
    elif(data[1]=="1"):
        s.insert(0,data[2])
    else:
        s.append(data[2])
print(''.join(s))


### FIXED CODE ###

s=list(input())
q=int(input())
start=[]
owari=[]
r=1
for i in range(q):
    data=input().split()
    if(len(data)==1):
        r*=-1
    elif(data[1]=="1"):
        if(r==1):
            start.append(data[2])
        else:
            owari.append(data[2])
    else:
        if(r==1):
            owari.append(data[2])
        else:
            start.append(data[2])

if(r==1):
    start.reverse()
    print(''.join(start),end='')
    print(''.join(s),end='')
    print(''.join(owari),end='')
else:
    owari.reverse()
    s.reverse()
    print(''.join(owari),end='')
    print(''.join(s),end='')
    print(''.join(start),end='')
### BUGGY CODE ###

# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate,permutations, combinations,combinations_with_replacement,product

def resolve():
    N,K,Q=map(int,input().split())
    A=[int(input()) for i in range(Q)]

    process=[K]*N
    for i in range(Q):
        for j in range(N):
            if A[i]-1!=j:
                process[j]-=1
    for i in process:
        if i<=0:
            print('No')
        else:
            print('Yes')


resolve()

### FIXED CODE ###

# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate,permutations, combinations,combinations_with_replacement,product

def resolve():
    N,K,Q=map(int,input().split())
    A=[int(input()) for i in range(Q)]

    S=[0]*N
    for i in A:
        S[i-1]+=1

    for i in S:
        if K-(Q-i)<=0:
            print('No')
        else:
            print('Yes')


resolve()
### BUGGY CODE ###

import sys
input = sys.stdin.readline


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1] * (n + 1)
        self.rnk = [0] * (n + 1)

    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def size(self, x):
        return -self.root[self.find_root(x)]


# adj: [[weight, u, v] * num_edge], V: number of vertices
def kruskal(adj, V):
    adj.sort()
    uf = UnionFind(V)
    ans = 0
    for edge in adj:
        weight, u, v = edge
        if not uf.isSameGroup(u, v):
            ans += weight
            uf.unite(u, v)
    return ans


N = int(input())
x_list = []
y_list = []
x_app = x_list.append
y_app = y_list.append
for i in range(N):
    x, y = map(int, input().split())
    x_app([x, i])
    y_app([y, i])

x_list.sort()
y_list.sort()
adj = []
adj_app = adj.append
for i in range(N-1):
    adj_app([x_list[i + 1][0] - x_list[i][0], x_list[i + 1][1], x_list[i][1]])
    adj_app([y_list[i + 1][0] - y_list[i][0], y_list[i + 1][1], y_list[i][1]])

print(kruskal(adj, N))


### FIXED CODE ###

# 6199094

import array
import sys
input = sys.stdin.readline

class UnionFind():
    def __init__(self,n):
        self.parent = [-1 for _ in range(n)]

    def size(self,x):
        return -self.parent[self.find(x)]

    def find(self,x):
        if(self.parent[x]<0):
            return x
        else:
            self.parent[x]=self.find(self.parent[x])
            return self.parent[x]

    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return False
        if(self.size(x)<self.size(y)):
            self.parent[y]+=self.parent[x]
            self.parent[x]=y
        else:
            self.parent[x]+=self.parent[y]
            self.parent[y]=x
        return True

    def same(self,x,y):
        return self.find(x)==self.find(y)

def main():
    N = int(input())
    xli = []
    yli = []
    x_app = xli.append
    y_app = yli.append


    for i in range(N):
        x,y = (int(x) for x in input().split())
        x_app([x-1,i])
        y_app([y-1,i])
    xli.sort()
    yli.sort()

    edges = []
    edges_app = edges.append
    for i in range(N-1):
        edges_app((xli[i][1],xli[i+1][1],xli[i+1][0]-xli[i][0]))
        edges_app((yli[i][1],yli[i+1][1],yli[i+1][0]-yli[i][0]))


    edges.sort(key=lambda edge: edge[2])
    uf = UnionFind(N)
    weight = 0

    for edge in edges:
        if not uf.same(edge[0], edge[1]):
            uf.unite(edge[0], edge[1])
            weight+=edge[2]
    print(weight)

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

def main():
    N = int(input())
    G = [[] for _ in range(N+1)]
    st = 0
    st_w = 0
    for i in range(N-1):
        u, v, w = (int(i) for i in input().split())
        G[u].append((v, w))
        G[v].append((u, w))
        if i == 0:
            st = u
            st_w = w
    color = [-1] * (N+1)  # 1: 0: white, black, -1: undefined

    def coloring(v, w):
        todo = []
        cur = 0
        color[v] = cur
        todo.append((v, w))
        while todo:
            u, w = todo[-1]
            for next_v, d in G[u]:
                if color[next_v] != -1:
                    continue
                if d % 2 != 0:
                    cur = (cur + 1) % 2
                color[next_v] = cur
                todo.append((next_v, d))
                break
            else:
                _, dist = todo.pop()
                if dist % 2 != 0:
                    cur = (cur + 1) % 2

    coloring(st, st_w)
    for c in color[1:]:
        print(c)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    G = [[] for _ in range(N+1)]
    st = 0
    st_w = 0
    for i in range(N-1):
        u, v, w = (int(i) for i in input().split())
        G[u].append((v, w))
        G[v].append((u, w))
        if i == 0:
            st = u
            st_w = w
    color = [-1] * (N+1)  # 0: white, 1: black, -1: undefined
    from collections import deque

    def coloring(v, w):
        """
        breadth-first search
        a simplified version
        """
        que = deque()
        color[v] = 0
        que.append((v, w))
        while que:
            u, w = que.popleft()
            for v, d in G[u]:
                if color[v] != -1:
                    continue
                if d % 2 != 0:
                    n_col = (color[u] + 1) % 2
                else:
                    n_col = color[u]
                color[v] = n_col
                que.append((v, d))

    coloring(st, st_w)
    for c in color[1:]:
        print(c)


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

L,R = map(int,input().split())
if L-R>0:
  print(0)
else:
  c = 2018
  for i in range(L,R):
    for j in range(i+1,R+1):
      a = i%2019
      b = j%2019
      t = (a*b)%2019
      if c > t:
        c = t
      else:
        continue
     
  print(c)

### FIXED CODE ###

L,R = map(int,input().split())
if R-L > 673 or (L%2019) > (R%2019):
  print(0)
else:
  l = L%2019
  r = R%2019
  c = 2018
  w = set()
  for i in range(l,r):
    for j in range(i+1,r+1):
      t = (i*j)%2019
      if c > t:
        c = t
  print(c)
### BUGGY CODE ###

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

for i in range(5*10**8):
  k = abs(A - i )
  l = abs(B - i)
  if k == l:
    print(k)
  else:
    print('IMPOSSIBLE')

### FIXED CODE ###

A, B = map(int, input().split())
 
if (A + B)%2 == 0:
  k = (A + B)/2
  print(round(k))
else:
  print('IMPOSSIBLE')
### BUGGY CODE ###

N = int(input())
A = input().split(" ")
B = input().split(" ")
C = input().split(" ")
m = 0

for n in range(N):
    A[n] = int(A[n])
    B[n] = int(B[n])
    C[n] = int(C[n])

A.sort()
B.sort()
C.sort()

for i in range(N):
    for j in range(N):
        if A[i] >= B[j]:
            continue
        for k in range(N):
            if B[j] < C[k]:
                m =  m + N - k
                break

print(m)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
 
A.sort()
B.sort()
C.sort()
C.reverse()
 
ans = 0
ai = 0
ci = N-1
for b in B:
    while ai < N and A[ai] < b:
        ai += 1
    while ci >= 0 and C[ci] <= b:
        ci -= 1
    ans += ai * (ci+1)
 
print(ans)
### BUGGY CODE ###

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

pairs = []
ratios = []
a_list = []
inputs = []
for i in range(n):
    a, b = map(int, input().split(" "))
    a_list.append(a)
    #ratio = a/b
    #ratios.append(ratio)
    #pairs.append([a, b, ratio])
    inputs.append([a, b])

#pairs = sorted(pairs, key=lambda x: -x[2])
#print(pairs)

max_a = max(a_list)

min_val = -1-max_a
costs = {}
for i in range(min_val, h+1):
    costs[i] = None
costs[h] = 0
#costs = [None for i in range(h)] + [0]

for val in range(h, min_val-1, -1):
    for a, b in inputs:
        if val+a > h:
            continue
        if costs[val+a] is None:
            continue

        if costs[val] is not None:
            costs[val] = min(costs[val+a]+b, costs[val])
        else:
            costs[val] = costs[val+a]+b

out = min([costs[val] for val in range(min_val, 1) if costs[val] is not None])
#print(costs)
print(out)

### FIXED CODE ###

input = raw_input
range = xrange
h, n = map(int, input().split(" "))

pairs = []
ratios = []
a_list = []
inputs = []
for i in range(n):
    a, b = map(int, input().split(" "))
    a_list.append(a)
    #ratio = a/b
    #ratios.append(ratio)
    #pairs.append([a, b, ratio])
    inputs.append([a, b])

#pairs = sorted(pairs, key=lambda x: -x[2])
#print(pairs)

max_a = max(a_list)

min_val = -1-max_a
costs = {}
for i in range(min_val, h+1):
    costs[i] = None
costs[h] = 0
#costs = [None for i in range(h)] + [0]

for val in range(h, min_val-1, -1):
    for a, b in inputs:
        if val+a > h:
            continue
        if costs[val+a] is None:
            continue

        if costs[val] is not None:
            costs[val] = min(costs[val+a]+b, costs[val])
        else:
            costs[val] = costs[val+a]+b

out = min([costs[val] for val in range(min_val, 1) if costs[val] is not None])
#print(costs)
print(out)
### BUGGY CODE ###

n,k=map(int,input().split())
p=tuple(map(int,input().split()))
idx = 0
s=0
e=0

for i in range(n-k+1):
    s1 = sum(p[i:i+k])
    if s1 > s:
        idx = i
        s = s1

for i in range(idx,idx+k):
    p1 = p[i]
    e1 = (1 + p1)*(p1//2 + 0.5*(p1%2))/p1
    e += e1

print(e)

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
l=[sum(p[:k])]

for i in range(n-k):
    l1=l[i] - p[i] + p[i+k]
    l.append(l1)

print((max(l)+k)/2)
### BUGGY CODE ###

import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N=int(input())
strings=[list(input()) for a in range(N)]
[thing.sort() for thing in strings]
sorteds=["".join(thing) for thing in strings]
sums=0
for st in list(set(sorteds)):
    n=sorteds.count(st)
    if n!=1:
       sums=sums+combinations_count(n,2)

print(sums)



### FIXED CODE ###

import math
import collections
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N=int(input())
strings=[str(sorted(input())) for a in range(N)]
c=collections.Counter(strings)
tp=c.most_common()
sums=0
for thing in tp:
    if thing[1]!=1:
        sums=sums+combinations_count(thing[1],2)
    else:break

print(sums)
### BUGGY CODE ###

N,X=map(int,input().split())
inputcities=list(map(int, input().split()))
cities=list(set([abs(inputcities[i]-X) for i in range(N)]))
N=len(cities)
count=0
flag=0
minimum=min(cities)
for j in range(minimum+1)[::-1]:
  for i in range(N):
    if cities[i]%j==0:
      count+=1
    else:
      count=0
      break
    if count==N:
      print(j)
      flag=1
      break
  if flag==1:
    break

### FIXED CODE ###

def gcd(a,b):
    if a < b:
        a,b = b,a
    if a % b == 0:
        return b
    else:
        return gcd(b,(a % b))
 
N,X=map(int,input().split())
inputcities=list(map(int, input().split()))
cities=[abs(inputcities[i]-X) for i in range(N)]
cities.sort()
D=cities[0]
for i in range(N):
  D=gcd(D,cities[i])
print(D)
### BUGGY CODE ###

from fractions import gcd
from functools import reduce
N = int(input())
A = list(map(int, input().split()))

def solve(A, i):
    ans = A[0]
    if i == 0:
        ans = A[1]
    for j in range(len(A)):
        if j == i:
            continue
        ans = gcd(ans, A[j])
    return ans

# print(N, A)
B = []
for i in range(len(A)):
    B.append(solve(A, i))

print(max(B))


### FIXED CODE ###

from fractions import gcd
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
# print(N, A)

L = [0]*(N - 1)
R = [0]*(N - 1)
L[0] = A[0]
R[0] = A[-1]

for i in range(1, N - 1):
    L[i] = gcd(L[i - 1], A[i])
    R[i] = gcd(R[i - 1], A[-1 - i])

# print(L)
# print(R)

B = [R[-1]]
for i in range(N - 2):
    l = L[i]
    r = R[N - 3 - i]
    # print(l, r)
    B.append(gcd(l, r))
B.append(L[-1])

# print(B)
ans = max(B)
print(ans)
### BUGGY CODE ###

import re

rexp = re.compile("AC")

N, Q = map(int, input().split())
S = input()
ruiseki_S = [""]
for i in range(N):
    ruiseki_S.append(ruiseki_S[i] + S[i])
for i in range(Q):
    l, r = map(int, input().split())
    a = ruiseki_S[r].replace(ruiseki_S[l - 1], "", 1)
    print(len(rexp.findall(a)))


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