Harryxun/stf_run huggingface dataset:
n = int(input())
a = list(map(int, input().split()))

a.sort()
if a[0] > 0:
    m = sum(a[1:]) - a[0]
    print(m)
    tmp = a[0]
    for i in range(1, n-1):
        print(tmp, a[i])
        tmp -= a[i]
    print(a[n-1], tmp)
elif a[-1] < 0:
    m = -sum(a[:-1]) + a[-1]
    print(m)
    tmp = a[n-1]
    for i in range(0, n-1, -1):
        print(tmp, a[i])
        tmp -= a[i]
else:
    m = 0
    pos = []
    neg = []
    for ai in a:
        m += abs(ai)
        if ai >= 0:
            pos.append(ai)
        else:
            neg.append(ai)
    print(m)
    tmp = 0
    ni = 0
    pi = 0

    if len(pos) > 1:
        print(neg[ni], pos[pi])  # pos > 1
        tmp = neg[ni] - pos[pi]
        ni += 1
        pi += 1

        while pi < len(pos) - 1:
            print(tmp, pos[pi])
            tmp = tmp - pos[pi]
            pi += 1
        print(pos[pi], tmp)
        tmp = pos[pi] - tmp
        while ni < len(neg):
            print(tmp, neg[ni])
            tmp -= neg
            ni += 1
    else:
        print(pos[pi] - neg[ni])
        tmp = pos[pi] - neg[ni]
        ni += 1
        while ni < len(neg):
            print(tmp, neg[ni])
            tmp -= neg
            ni += 1





### FIXED CODE ###

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

a.sort()
if a[0] >= 0:
    m = sum(a[1:]) - a[0]
    print(m)
    tmp = a[0]
    for i in range(1, n-1):
        print(tmp, a[i])
        tmp -= a[i]
    print(a[n-1], tmp)
elif a[-1] <= 0:
    m = -sum(a[:-1]) + a[-1]
    print(m)
    tmp = a[n-1]
    for i in range(n-1):
        print(tmp, a[i])
        tmp -= a[i]
else:
    m = 0
    pos = []
    neg = []
    for ai in a:
        m += abs(ai)
        if ai >= 0:
            pos.append(ai)
        else:
            neg.append(ai)
    print(m)
    tmp = 0
    ni = 0
    pi = 0

    if len(pos) > 1:
        print(neg[ni], pos[pi])
        tmp = neg[ni] - pos[pi]
        ni += 1
        pi += 1

        while pi < len(pos) - 1:
            print(tmp, pos[pi])
            tmp = tmp - pos[pi]
            pi += 1
        print(pos[pi], tmp)
        tmp = pos[pi] - tmp
        while ni < len(neg):
            print(tmp, neg[ni])
            tmp -= neg[ni]
            ni += 1
    else:
        print(pos[pi], neg[ni])
        tmp = pos[pi] - neg[ni]
        ni += 1
        while ni < len(neg):
            print(tmp, neg[ni])
            tmp -= neg[ni]
            ni += 1
# ABC-129-B
N = int(input())
W = list(map(int, input().split()))
ans = 10**9

for i in range(1, n):
    S1 = sum(W[:i])
    S2 = sum(W[i:])
    sa = abs(S1-S2)
    ans = min(ans, sa)
print(ans)

### FIXED CODE ###

N = int(input())
W = list(map(int, input().split()))
ans = 10**9

for i in range(1, N):
    S1 = sum(W[:i])
    S2 = sum(W[i:])
    sa = abs(S1-S2)
    ans = min(ans, sa)
print(ans)
import heapq
N,M = map(int,input().split())
AB = [[] for i in range(M+1)]
for i in range(N):
    a,b = list(map(int,input().split()))
    AB[a].append(-b)
work = 0
AB2 = []
for i in range(1,M+1):
    AB2 += AB[i]
    heapq.heapify(AB2)
    if not AB2:
        continue
    b = heapq.heappop(AB2)
    work += -b
print(work)

### FIXED CODE ###

import heapq
from collections import defaultdict
N,M = map(int,input().split())
AB = defaultdict(list)
for i in range(N):
    a,b = list(map(int,input().split()))
    if a not in AB:
        AB[a] = [-b]
    else:
        AB[a] += [-b]
work = 0
AB2 = []
heapq.heapify(AB2)
for i in range(1,M+1):
    for j in AB[i]:
        heapq.heappush(AB2,j)
    if not AB2:
        continue
    b = heapq.heappop(AB2)
    work += -b
print(work)
if 500*K < X :
	print("Yes")
else :
  print("No")

### FIXED CODE ###

K,X = map(int,input().split())
if 500*K<X:
  print("No")
else:
  print("Yes")
import math
x1,y1,x2,y2=map(int,input().split())
dx=abs(x1-x2)
dy=abs(y1-y2)
print(math.sqrt(dx*dx+dy*dy))

### FIXED CODE ###

import math
x1,y1,x2,y2=map(float,input().split())
dx=abs(x1-x2)
dy=abs(y1-y2)
print(math.sqrt(dx*dx+dy*dy))
A, B, K = map(int, input().split())
 
cand = []
for i in range(100,0,-1):
    if A%i == 0 and B%i == 0:
        cand += [i]        
print(cand[K-1]

### FIXED CODE ###

A, B, K = map(int, input().split())
 
cand = []
for i in range(100,0,-1):
  if A%i == 0 and B%i == 0:
    cand += [i]
    
    
print(cand[K-1])
s = input().strip()
s_new = input().strip()
if s == s_new[0:len(s)]:
  if len(s) + 1 = len(s_new):
    print("Yes")
  else:
    print('No')
else:
  print("No")

### FIXED CODE ###

s = input().strip()
s_new = input().strip()
if s == s_new[0:len(s)]:
  if len(s) + 1 == len(s_new):
    print("Yes")
  else:
    print('No')
else:
  print("No")
ciar = list(int, input().split())
W,H,x,y,r = [ciar[0],ciar[1],ciar[2],ciar[3],ciar[4]]
if (x + r) < W and (y + r) < H :
    print("Yes")
else :
    print("No")

### FIXED CODE ###

ciar = input().split()
W = int(ciar[0])
H = int(ciar[1])
x = int(ciar[2])
y = int(ciar[3])
r = int(ciar[4])
if (x + r) <= W and (x - r) >= 0 :
    if (y + r) <= H and (y - r) >= 0 :
        print("Yes")
    else :
        print("No")
else :
    print("No")
n = input()
flag = [0 for i in xrange(n)]
a = []
b = []
for i in xrange(n):
	x,y = map(int, raw_input().split())
	a.append((x,y,i))
	b.append((y,x,i))
a.sort(reverse = True)
b.sort(reverse = True)
ptr1 = 0
ptr2 = 0
turn = 0
ans1 = 0
ans2 = 0
while ptr1 < n and ptr2 < n:
	if turn == 0:
		while flag[a[ptr1][2]] == 1:
			ptr1 += 1
		if ptr1 < n:
			ans1 += a[ptr1][0]
			flag[a[ptr1][2]] = 1
			ptr1 += 1
		turn = 1
	else:
		while flag[b[ptr2][2]] == 1:
			ptr2 += 1
		if ptr2 < n:
			ans2 += b[ptr2][0]
			flag[b[ptr2][2]] = 1
			ptr2 += 1
		turn = 0
print ans1-ans2


### FIXED CODE ###

n = input()
ans = 0
l = []
for i in xrange(n):
	a,b = map(int, raw_input().split())
	ans -= b
	l.append(a+b)
l.sort(reverse = True)
for i in xrange(0,n,2):
	ans += l[i]
print ans
read=input;
A,B=map(int,read()).spilt()
if A>=0 and A<=5:
  print(0);
elif A>5 and A<=12:
  print(B/2);
else:
  print(B);

### FIXED CODE ###

read=input();
A,B=read.split(' ')
A=int(A)
B=int(B)
if A>12:
  print(B);
elif A>5:
  print(int(B/2));
else:
  print(0);
n = int(input())
A = list(map(int, input().split()))
count = 0
while True:
    for i in range(n):
        if (A[i] % 2 == 1) or (A[i] == 0):
            break
        elif:
            A[i] = A[i] // 2
            s += 1
            continue
print(count)


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
s = 0

def count(A, n):
    for i in range(n):
        if (A[i] % 2 == 1) or (A[i] == 0):
            return False
        A[i] = A[i] // 2
    return True

while True:
    if count(A, n):
        s += 1
    else:
        break
    
print(s)
from sys import stdin
li = list(map(int,stdin.readline().rstrip.split()))
if li[1] > li[2]:
    print(li[0]*li[1])
else:
    print(li[0]*li[2])

### FIXED CODE ###

from sys import stdin
li = list(map(int,stdin.readline().rstrip().split()))
if li[1]*li[0] > li[2]:
    print(li[2])
else:
    print(li[0]*li[1])
W,H,x,y = map(int,input().split())
if x==0 or x==W or y==0 or y==H:
  s = H*W/2
  print('{:.10f}'.format(s))
else:
  a = min(x*H,(W-x)*H)
  b = min(y*W,(H-y)*W)
  s = max(a,b)
  print('{:.10f}'.format(s))
if x==0 and y==0:
  print(0)
elif x==W and y==0:
  print(0)
elif x==0 and y==H:
  print(0)
elif x==W and y==H:
  print(0)
elif y == H*x/W or y == (-1)*H*x/W:
  print(1)
else:
  print(0)

### FIXED CODE ###

X,A = map(int,input().split())
if X<A:
  print(0)
if X>=A:
  print(10)
def main():

    S = input().split()
    Q = int(input())

    # for _ in range(Q):
    #     q = input().split()
    #     if q[0] == '1':
    #         S.reverse()
    #     elif q[0] == '2':
    #         if q[1] == '1':
    #             tmp = [q[2]]
    #             tmp.extend(S)
    #             S = tmp
    #         elif q[1] == '2':
    #             S.append(q[2])
    # print("".join(S))
    q_list = []
    for _ in range(Q):
        q_list.append(input().split())

    for q in q_list:
        if q[0] == '1':
            S.reverse()
        elif q[0] == '2':
            if q[1] == '1':
                tmp = [q[2]]
                tmp.extend(S)
                S = tmp
            elif q[1] == '2':
                S.append(q[2])
    print("".join(S))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    S = list(input())
    s = set(S)
    if len(s) == 1:
        print('No')
    else:
        print('Yes')


if __name__ == '__main__':
    main()
a,b = map(int,input().split())
b -= 1
if a%b == 0:
    print(a//b)
else:
    print(a//b+1)

### FIXED CODE ###

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

b -= 1
if b%(a-1) == 0:
    print(b//(a-1))
else:
    print(b//(a-1)+1)
N,M=map(int,input().split())
P,S=[],[]
ans,pen=0,0
task=[0]*N
for _ in range(M):
    A,B=map(str,input().split())
    P.append(int(A))
    S.append(B)

for j in range(M):
    if task[A[M]-1]!=-1 and S[j]=="WA":
        pen+=1
    elif task[A[M]-1]!=-1 and S[j]=="AC":
        ans+=1
        task[A[M]]=-1
        break
print(ans,pen)

### FIXED CODE ###

N,M=map(int,input().split())
P,S=[],[]
ans,pen=0,0
task=[0]*N
for _ in range(M):
    A,B=map(str,input().split())
    P.append(int(A))
    S.append(B)

for j in range(M):
    if task[P[j]-1]!=-1 and S[j]=="WA":
        task[P[j]-1]+=1
    elif task[P[j]-1]!=-1 and S[j]=="AC":
        ans+=1
        pen+=task[P[j]-1]
        task[P[j]-1]=-1
print(ans,pen)
N = int(input())
sum=0
for i in range(N):
    x, u = input().split()
    if x == "JPY":
        sum+=int(x)
    else:
        sum+=int(x)*380000
print(sum)

### FIXED CODE ###

N = int(input())
sum=0
for i in range(N):
    x, u = list(map(str, input().split()))
    if u == "JPY":
        sum+=int(x)
    else:
        sum+=float(x)*380000
print(sum)
n, k = map(int, input().split())
s = str(input())

x = str(s[k-1])
y = x.lower()
s[k-1] = y

print(s)

### FIXED CODE ###

n, k = map(int, input().split())
s = str(input())

if s[k-1] == 'A':
    print(s[:k-1] + 'a' + s[k:])

elif s[k-1] == 'B':
    print(s[:k-1] + 'b' + s[k:])

else:
    print(s[:k-1] + 'c' + s[k:])
# -*- coding: utf-8 -*-

import math
import sys
import heapq
from operator import itemgetter
import itertools
input = sys.stdin.readline

# a = int(input().rstrip())
# a, b = map(int, input().rstrip().split())
# D = list(map(int, input().rstrip().split()))
# H = [int(input().rstrip()) for _ in range(L)]
# DD = [[0 for j in range(100)] for i in range(200)]
# dict = {} ## dictionary

# a = sorted(a, key=lambda x: x[1]))
# if __name__ == '__main__':


def divisors(p, q):
	ans = []
	if q == 1:
		ans = [1]
	else:
		for i in range(2, q // p + 1):
			if q % i == 0:
				ans.append(i)
	return(ans)

N, M = map(int, input().rstrip().split())
print(divisors(N, M)[-1])

### FIXED CODE ###

# -*- coding: utf-8 -*-

import math
import sys
import heapq
from operator import itemgetter
import itertools
input = sys.stdin.readline

# a = int(input().rstrip())
# a, b = map(int, input().rstrip().split())
# D = list(map(int, input().rstrip().split()))
# H = [int(input().rstrip()) for _ in range(L)]
# DD = [[0 for j in range(100)] for i in range(200)]
# dict = {} ## dictionary

# a = sorted(a, key=lambda x: x[1]))
# if __name__ == '__main__':


def divisors(n, m):
	for i in range(m//n, 0, -1):
		if m % i == 0:
			return(i)


N, M = map(int, input().rstrip().split())
print(divisors(N, M))
A, B, N = map(int, input().split())
behavior = input()

for b in behavior:
  if b == 'S':
    if A > 0:
      A -= 1
  elif b == 'C':
    if B > 0:
      B -= 1
  elif b == 'E':
    if not ((A == 0) and (B == 0)):
      if A >= B:
        A -= 1
      else:
        B -= 1
print(A)
print(B)

### FIXED CODE ###

sx, sy, tx, ty = map(int, input().split())
path = ''
for _ in range(tx - sx):
  path += 'R'
for _ in range(ty - sy):
  path += 'U'
for _ in range(tx - sx):
  path += 'L'
for _ in range(ty - sy):
  path += 'D'

  
path += 'D'
for _ in range(tx - sx + 1):
  path += 'R'
for _ in range(ty - sy + 1):
  path += 'U'
path += 'L'
path += 'U'
for _ in range(tx - sx + 1):
  path += 'L'
for _ in range(ty - sy + 1):
  path += 'D'
path += 'R'

print(path)
n = int(input())

alis = list(map(int, input().split()))

ans = 1

for a in alis:
  ans *= a
  if ans > 10**18:
	ans = -1
	break

print(ans)


### FIXED CODE ###

n = int(input())

alis = list(map(int, input().split()))

ans = 1

if 0 in alis:
  print(0)
  exit()

for a in alis:
	ans *= a
	if ans > 10**18:
		ans = -1
		break

print(ans)
a,b = map(int,input().split())
if (a*b)%2 = 1:
  print(odd)
else:
  print(even)

### FIXED CODE ###

a,b = map(int,input().split())
if (a*b)%2 == 1:
  print('Odd')
else:
  print('Even')
import sys
input = sys.stdin.readline
def main():
  n = int(input())
  l = list(map(int, input().split()))
  n = 2000
  l = []
  l.sort()
  l.append(99999999)
  c = 0
  for i in range(n - 2):
      t = i + 2
      for j in range(i + 1, n - 1):
          for k in range(t, n + 1):
              if l[i] + l[j] <= l[k]:
                  t = k
                  break
          if t > j: c += t - j - 1
          if j + 1 == t: t += 1
  print(c)
if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
  n = int(input())
  l = list(map(int, input().split()))
  l.sort()
  l.append(99999999)
  c = 0
  for i in range(n - 2):
      t = i + 2
      for j in range(i + 1, n - 1):
          for k in range(t, n + 1):
              if l[i] + l[j] <= l[k]:
                  t = k
                  break
          if t > j: c += t - j - 1
          if j + 1 == t: t += 1
  print(c)
if __name__ == "__main__":
  main()
n=input()
z=0
for i in range(n):
  a,b=intput().split()
  z+=a*380000 if b=="BTC" else a
print(z)
  


### FIXED CODE ###

n=int(input())
z=0
for i in range(n):
  a,b=input().split()
  if b=="BTC":
    z += float(a)*380000
  else:
    z += int(a)
print(z)
str_list = list(input().split()
i = len(str_list)

a=0
b=0
c=0                
d=0                
                
for num in range(1, i)
    if str_list[num] == 'AC':
                a += 1
    elif str_list[num] == 'WA':
                b += 1
    elif str_list[num] == 'TLE':
                c +=1
    elif str_list[num] == 'RE':
                d +=1
    	continue;

print('AC x'+ a)
print('WA x'+ b)
print('TLE x'+ c)
print('RE x'+ d)


### FIXED CODE ###

n = int(input())
str_list = [input() for _ in range(n)]


a=0
b=0
c=0                
d=0                
                
for i in range(n):
    if str_list[i] == 'AC':
    	a += 1
    elif str_list[i] == 'WA':
    	b += 1
    elif str_list[i] == 'TLE':
    	c +=1
    else :
    	d +=1

print('AC x '+ str(a))
print('WA x '+ str(b))
print('TLE x '+ str(c))
print('RE x '+ str(d))
N,K,X,Y=map(int, input().split())

result = 0
if N > K:
  result = K * X + (N - K) * Y
else:
  result = N * X

print(result)


### FIXED CODE ###

N = int(input())
K = int(input())
X = int(input())
Y = int(input())
if(N<=K):
  print(X*N)
else:
  print(X*K+(N-K)*Y)
l1 = list(map(int, input().split()))
l2 = list(map(int, input().split()))

H = int(l1[0])
N = int(l1[1])
A = int(sum(l2))
break
result = H - A
if result <= 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

l = list(map(int, input().split()))

def attack(l):
    H = l[0]
    A = l[1]
    cnt = 0
    while H > 0:
        H -= A
        cnt += 1
    return cnt

print(attack(l))
H,W = int(input()),int(input())
h,w = int(input()),int(input())

ans = (H - h) * (W - w)
print(ans)


### FIXED CODE ###

H,W = map(int,input().split())
h,w = map(int,input().split())
ans = (H-h)*(W-w)
print(ans)
n = int(input())
s = list(input())
lis = []
rtmp = 0
ltmp = 0
tmp = 0
l,r = 0,0

for i in range(n-1):
    if (s[i] != s[i+1]):
        #clis+= 1
        #print(i)
        rtmp = i+1
        ltmp = i
        for j in range(ltmp):
            if s[j] == '#':
                tmp += 1
        for j in range(rtmp,n):
            if s[j] == '.':
                tmp += 1
        lis.append(tmp)
        #print(lis)
    tmp = 0
    l,r = 0,0

if len(lis) == 0: 
    print(0)
else:
    print(min(lis))


### FIXED CODE ###

a,b,c = map(int, input().split())
if (a <= c and c <= b) or (a >= c and c >= b):
    print('Yes')
else:
    print('No')
import numpy as np

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

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

for i in range(M):
    max_value = max(goods)
    max_index = np.where(goods == max_value)[0]
    goods[max_index] = goods[max_index]//2
    
sum_value = sum(goods)

print(sum_value)


### FIXED CODE ###

S = input()

l = ['Sunny', 'Cloudy', 'Rainy']

i = l.index(S)

if i == 0:
  print('Cloudy')
elif i == 1:
  print('Rainy')
elif i == 2:
  print('Sunny')
# coding: utf-8
# Your code here!
N,K=map(int,input().split())
X=list(map(int,input().split()))

def journey(main,sub):
    main=main[:]
    sub=list(map(lambda x:x*2,sub))
    
    ans=0
    for _ in range(K):
        if len(main)==0:
            ans+=sub.pop(-1)
        elif len(sub)==0:
            ans+=main.pop(-1)
        elif main[-1]<=sub[-1]:
            ans+=main.pop(-1)
        else:
            ans+=sub.pop(-1)
    
    return ans
    
i=0
while X[i]<0:
    i+=1

neg=[0]
pos=[0]
neg=neg+list(map(lambda x:x*(-1),X[:i][::-1]))
pos=pos+X[i:]
d_pos=[pos[i+1]-pos[i] for i in range(len(pos)-1)][::-1]#popしたいのでひっくり返す
d_neg=[neg[i+1]-neg[i] for i in range(len(neg)-1)][::-1]

a=(journey(d_pos,d_neg))
b=(journey(d_neg,d_pos))

print(min(a,b))



### FIXED CODE ###

# coding: utf-8
# Your code here!
import bisect

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

zero=bisect.bisect_left(X,0)

ans=10**18
start=max(0,zero-K)
for i in range(start,start+N-K+1):
    #print(i)
    m=min(0,X[i])
    M=max(0,X[i+K-1])
    ans=min((abs(m)+abs(M)*2),(abs(m)*2+abs(M)),ans)
    if i+K==N:
        break
    
print(ans)
n=list(input())
for i in range(3):
  if n[i]=="1":
    n[i]=9
  else:
    n[i]=1
s=""
for i in range(3):
  s+="n[i]"
print(int(s))

### FIXED CODE ###

n=input()
ans=""
for i in range(3):
  if n[i]=="1":
    ans+="9"
  else:
    ans+="1"
print(ans)
n = input()
c = 0
for i in range(1,n):
  c += i
print(c)

### FIXED CODE ###

n = int(input())
c = 0
for i in range(1,n+1):
  c += i
print(c)
from collections import deque
def main():
    S = input()
    S = deque([c for c in S])
    Q = int(input())
    rvCt = 0

    head, tail = deque([]), deque([])
    for _ in range(Q):
        query = input().split()
        if query[0] == '1':
            rvCt += 1
        else:
            if rvCt % 2 == 1:
                S = head + S + tail
                S.reverse()
                head, tail = deque([]), deque([])
            rvCt = 0
            if query[1] == '1':
                head.appendleft(query[2])
            else:
                tail.append(query[2])

    if rvCt % 2 == 1:
        S = head + S + tail
        S.reverse()
    else:
        S = head + S + tail
    
    print(''.join(S))

main()

### FIXED CODE ###

from collections import deque
def main():
    S = input()
    S = deque([c for c in S])
    Q = int(input())
    rvCt = 0

    for _ in range(Q):
        query = input().split()
        if query[0] == '1':
            rvCt += 1
        else:
            doReverse = False
            if rvCt % 2 == 1:
                doReverse = True

            if query[1] == '1':
                if doReverse:
                    S.append(query[2])
                else:
                    S.appendleft(query[2])
            else:
                if doReverse:
                    S.appendleft(query[2])
                else:
                    S.append(query[2])

    if rvCt % 2 == 1:
        S.reverse()
    
    print(''.join(S))

main()
N = input()
a = sorted(list(map(int, input().split())))
b = (a[0] + a[1]) / 2
if N > 2:
  for c in a[2:]:
    b = (b + c) / 2
print(b)

### FIXED CODE ###

N = int(input())
a = sorted(list(map(int, input().split())))
b = (a[0] + a[1]) / 2
if N > 2:
  for c in a[2:]:
    b = (b + c) / 2
print(b)
from collections import deque
H, W = list(map(int, input().split()))
S =[list(input()) for _ in range(H)]

mv = {(1, 0), (-1, 0), (0, 1), (0, -1)}


def BFS(St):
    stk = deque([[St[0],St[1],0]])
    seen = [[False]*W for _ in range(H)]
    while len(stk) > 0:
        l = stk.pop()
        i = l[0]
        j = l[1]
        ct = l[2]
        seen[i][j] = True
        for k in mv:
            x = i+k[0]
            y = j+k[1]
            if 0 <= x < H and 0 <= y < W:
                if S[x][y] == '.' and seen[x][y] == False:
                    stk.appendleft([x, y, ct+1])
    return(ct)

ans = 0
# 各スタート地点に対して最大距離を出力すればいいですねって話

for i in range(H):
    for j in range(W):
        
            continue
        ans=max(ans,BFS([i,j]))
print(ans)


### FIXED CODE ###

H, W = list(map(int, input().split()))
S =[list(input()) for _ in range(H)]
N=H*W
INF=float('inf')
L=[[INF]*N for _ in range(N)]
for i in range(N):
    h=i//W
    w=i%W
    # print(i,h,w)
    if S[h][w]=='.':
        L[i][i]=0
    if w>0 and S[h][w-1]=='.':
        L[i][i-1]=1
    if w<W-1 and S[h][w+1]=='.':
        L[i][i+1]=1
    if h>0 and S[h-1][w]=='.':
        L[i][i-W]=1
    if h<H-1 and S[h+1][w]=='.':
        L[i][i+W]=1
# print(L)

for i in range(N):
    via=L[i]
    if via[i]==INF:
        continue
    for j in range(N):
        st=L[j]
        if st[j]==INF:
            continue
        for k in range(N):
            L[j][k]=min(st[i]+via[k], st[k])
# print(L)
ans=0
for i in range(N):
    for j in range(N):
        if L[i][j]!=INF:
            ans=max(ans,L[i][j])
print(ans)
N, Q = map(int, input().split())
S = input()
t = [0] * N
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])


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations
    #from itertools import accumulate, product, permutations
    from math import floor, ceil

    #mod = 1000000007

    n,q = map(int, input().split())
    s = input()
    l = [0]*(n+1)
    for i in range(n):
        if s[i:i+2]=='AC':
            l[i+1]=l[i] + 1
        else:
            l[i+1]=l[i]

    for _ in range(q):
        a, b = map(int, input().split())
        print(l[b-1]-l[a-1])


if __name__ == '__main__':
    main()
def sieve(n):
    p = [1] * (n + 1)
    p[0] = p[1] = 0
    
    for i in range(int(n ** 0.5) + 1):
        if p[i]:
            for j in range(2 * i, len(p), i):
                p[j] = 0
    return p

def get_quad(n, p):
    for ni in range(n,0,-1):
        if p[ni] and p[ni - 2] and p[ni - 6] and p[ni - 8]:
            return ni

import sys
f = sys.stdin


n = [int(line) for line in f][:-1]
prime = sieve(max(n))
for ni in n:
    print(get_quad(ni, prime))

### FIXED CODE ###

def get_quad(n, p):
    if n < 19:
        return 13
    n = (n + 1) // 10 * 10 - 1
    for ni in range(n,0,-10):
        if p[ni] and p[ni - 2] and p[ni - 6] and p[ni - 8]:
            return ni
        
def sieve():
    n = 10000001
    p = [1] * n
    p[0] = p[1] = 0
    
    for i in range(int(n ** 0.5)):
        if p[i]:
            for j in range(2 * i, len(p), i):
                p[j] = 0
    return p

import sys
f = sys.stdin

prime = sieve()
while True:
    n = f.readline().strip()
    if not n.isdigit():
        continue
    n = int(n)
    if n == 0:
        break
    print(get_quad(n, prime))