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

import sys

n, *inp = map(int, sys.stdin.buffer.read().split())
vvv = [0] + inp[0:n * 2:2]
www = [0] + inp[1:n * 2:2]

weight_limit = 10 ** 5
precalc_limit = min(1 << 9, n + 1)
precalc = [[0] * (weight_limit + 1)]

for u in range(1, precalc_limit):
    v = vvv[u]
    w = www[u]
    dp = precalc[u >> 1][:]
    for x in range(weight_limit, w - 1, -1):
        nv = dp[x - w] + v
        if dp[x] < nv:
            dp[x] = nv
    precalc.append(dp)

buf = []
mp = iter(inp[n * 2 + 1:])
for u, l in zip(mp, mp):
    if u < precalc_limit:
        buf.append(precalc[u][l])
        continue
    dp_w = [0]
    dp_v = [0]
    while u >= precalc_limit:
        v = vvv[u]
        w = www[u]
        for i in range(len(dp_w)):
            nw = dp_w[i] + w
            if nw > l:
                continue
            nv = dp_v[i] + v
            dp_w.append(nw)
            dp_v.append(nv)
        u >>= 1
    ans = 0
    for w, v in zip(dp_w, dp_v):
        nv = v + precalc[u][l - w]
        if ans < nv:
            ans = nv
    buf.append(ans)

print('\n'.join(map(str, buf)))


### FIXED CODE ###

import sys

n, *inp = map(int, sys.stdin.buffer.read().split())
vvv = [0] + inp[0:n * 2:2]
www = [0] + inp[1:n * 2:2]

weight_limit = 10 ** 5
precalc_limit = min(1 << 10, n + 1)
precalc = [[0] * (weight_limit + 1)]

for u in range(1, precalc_limit):
    v = vvv[u]
    w = www[u]
    dp = precalc[u >> 1][:]
    for x in range(weight_limit, w - 1, -1):
        nv = dp[x - w] + v
        if dp[x] < nv:
            dp[x] = nv
    precalc.append(dp)

buf = []
mp = iter(inp[n * 2 + 1:])
for u, l in zip(mp, mp):
    if u < precalc_limit:
        buf.append(precalc[u][l])
        continue
    dp_w = [0]
    dp_v = [0]
    while u >= precalc_limit:
        v = vvv[u]
        w = www[u]
        for i in range(len(dp_w)):
            nw = dp_w[i] + w
            if nw > l:
                continue
            nv = dp_v[i] + v
            dp_w.append(nw)
            dp_v.append(nv)
        u >>= 1
    ans = 0
    for w, v in zip(dp_w, dp_v):
        nv = v + precalc[u][l - w]
        if ans < nv:
            ans = nv
    buf.append(ans)

print('\n'.join(map(str, buf)))
### BUGGY CODE ###

import math
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

def main():
    def dijkstra(graph: list, node: int, start: int) -> list:
        # graph[node] = [(cost, to)]
        inf = 3 * 10 ** 9
        dist = [inf] * node

        dist[start] = 0
        heap = [(0, start)]
        while heap:
            cost, thisNode = heappop(heap)
            for NextCost, NextNode in graph[thisNode]:
                dist_cand = dist[thisNode] + NextCost
                if dist_cand < dist[NextNode]:
                    dist[NextNode] = dist_cand
                    heappush(heap,(dist[NextNode], NextNode))
        return dist
        # dist = [costs to nodes]

    xs, ys, xt, yt = map(int, input().split())
    n = int(input())
    circles = [(xs, ys, 0), (xt, yt, 0)] + [tuple(map(int, input().split())) for i in range(n)]
    n += 2

    edges = [[] for i in range(n)]
    for i in range(n):
        for j in range(i+1, n):
            dist = math.sqrt((circles[i][0] - circles[j][0]) ** 2 + (circles[i][1] - circles[j][1]) ** 2)
            cost = max(0, dist - circles[i][2] - circles[j][2])
            edges[i].append((cost, j))
            edges[j].append((cost, i))


    dist = dijkstra(edges, n, 0)

    print(dist[1])


main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def dijkstra(edge_adj: list, node: int, start: int) -> list:
    # graph[node] = [(cost, to)]
    inf = 3 * 10 ** 9
    dist = [inf] * node
    used = [False] * node

    dist[start] = 0
    while True:
        v = -1
        for i in range(node):
            if not used[i] and (v == -1 or dist[v] > dist[i]):
                v = i

        if v == -1:
            break

        used[v] = True
        for i in range(node):
            if dist[i] > dist[v] + edge_adj[v][i]:
                dist[i] = dist[v] + edge_adj[v][i]

    return dist
    # dist = [costs to nodes]

xs, ys, xt, yt = map(int, input().split())
n = int(input())
circles = [(xs, ys, 0), (xt, yt, 0)]
for i in range(n):
    circles.append(tuple(map(int, input().split())))
n += 2

edges = [[0] * n for i in range(n)]
for i in range(n):
    for j in range(i+1, n):
        dist = ((circles[i][0] - circles[j][0]) ** 2 + (circles[i][1] - circles[j][1]) ** 2) ** 0.5
        cost = max(0, dist - circles[i][2] - circles[j][2])
        edges[i][j] = cost
        edges[j][i] = cost


dist = dijkstra(edges, n, 0)

print(dist[1])
### BUGGY CODE ###

import sys
import math
import itertools

N=int(input())
if(N%4==0):
    x=3*N//4
    print(x,x,x)
    exit()
for x in range(3501):
    if(4*x-2*N>0 and (N*x)%(4*x-2*N)==0):
        h=(N*x)//(4*x-2*N)
        print(h,x,x)
        exit()
for h,n in itertools.product(range(1,3501)[::-1],range(1,3501)[::-1]):
    x=N*h*n
    y=4*n*h-N*n-N*h
    if(y>0 and x%y==0):
        print(h,n,x//y)
        break
"""
4/N=1/h+1/n+1/w
4/N=(nw+hw+hn)/nhw
4nhw/N=nw+hw+hn
4nhw=Nnw+Nhw+Nhn
(4nh-Nn-Nh)w=Nhn
w=Nhn/(4nh-Nn-Nh)

4/N=3/x
4x/N=3
4x=3N
h,n,w=3N/4  (N%4==0)

4/N=1/h+2/x
4/N-2/x=1/h
(4x-2N)/Nx=1/h
h=Nx/(4x-2N)
"""


### FIXED CODE ###

import sys
import math
import itertools

N=int(input())
if(N%4==0):
    x=3*N//4
    print(x,x,x)
    exit()
for x in range(3501):
    if(4*x-2*N>0 and (N*x)%(4*x-2*N)==0):
        h=(N*x)//(4*x-2*N)
        print(h,x,x)
        exit()
if(N>2000):st=-1
else:st=1
for h,n in itertools.product(range(1,3501)[::st],range(1,3501)[::st]):
    x=N*h*n
    y=4*n*h-N*n-N*h
    if(y>0 and x%y==0):
        print(h,n,x//y)
        break
"""
4/N=1/h+1/n+1/w
4/N=(nw+hw+hn)/nhw
4nhw/N=nw+hw+hn
4nhw=Nnw+Nhw+Nhn
(4nh-Nn-Nh)w=Nhn
w=Nhn/(4nh-Nn-Nh)

4/N=3/x
4x/N=3
4x=3N
h,n,w=3N/4  (N%4==0)

4/N=1/h+2/x
4/N-2/x=1/h
(4x-2N)/Nx=1/h
h=Nx/(4x-2N)
"""
### BUGGY CODE ###

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

result = [0] * n
for x in range(0,n):
    if n - x < max(result):
        break
    for i in range(x, n-1):
        if h[i] < h[i+1]:
            break
        else:
            result[x] += 1
print(max(result))

### FIXED CODE ###

n = int(input())
h = list(map(int,input().split()))
result = []
count = 0
for x in range(0,n-1):
    if h[x] >= h[x+1]:
        count += 1
    else:
        result.append(count)
        count = 0
result.append(count)
print(max(result))
### BUGGY CODE ###

import bisect

N, M, Q = map(int, input().split())
trains = [list(map(int, input().split())) for i in range(M)]
queries = [list(map(int, input().split())) for i in range(Q)]
trains.sort(key = lambda x: x[1])

A  =[[0] * N for _ in range(N)] #A[i][j] = (i + 1) -> (j+1)なる列車の本数
for train in trains:
    li, ri = train
    A[li - 1][ri - 1] += 1
dp = [[0 for _ in range(N)] for __ in range(N)]

def ans(left, right):
    if dp[left][right] > 0:
        return dp[left][right]
    elif left > right:
        return 0
    elif left == right:
        dp[left][right] = A[left][right]
        return dp[left][right]
    else:
        dp[left][right] = ans(left, right-1) + ans(left + 1, right) + A[left][right] - ans(left + 1, right - 1)
        return dp[left][right]

for q in range(Q):
    pi, qi = queries[q]
    print(ans(pi - 1, qi - 1))


### FIXED CODE ###

N, M, Q = map(int, input().split())
trains = [list(map(int, input().split())) for i in range(M)]
queries = [list(map(int, input().split())) for i in range(Q)]

A  =[[0] * N for _ in range(N)] #A[i][j] = (i + 1) -> (j+1)なる列車の本数
for train in trains:
    li, ri = train
    A[li - 1][ri - 1] += 1

dp = [[0] * N for __ in range(N)]
for i in range(N - 1, -1, -1):
    for j in range(i, N):
        if i == j:
            dp[i][j] = A[i][j]
        else:
            dp[i][j] = dp[i][j - 1] + dp[i + 1][j] + A[i][j] - dp[i + 1][j - 1]
for q in range(Q):
    pi, qi = queries[q]
    print(dp[pi - 1][ qi - 1])
### BUGGY CODE ###

n = int(input())
d = list(map(int,input().split()))
arc = []
abc = []
cnt = 0
if n % 2 == 1:
    print(0)
    exit()
d.sort()
right = n // 2
left = right - 1
for i in range(d[left],d[right]+1):
    k = i
    abc = []
    arc = []
    for j in d:
        if j >= k:
            arc.append(j)
        elif j < k:
            abc.append(j)
    if len(arc) == len(abc):
        cnt += 1
print(cnt)


### FIXED CODE ###

import math
N = int(input())
d = list(map(int,input().split()))
ABC = []
ARC = []
d.sort()
pivot = (len(d)-1) / 2
left = math.floor(pivot)
right = math.ceil(pivot)
if d[left] == d[right]:
    K = d[left]

elif d[left] !=  d[right]:
    lists = list(range(d[left]+1,d[right]+1))
    K = lists[0]
for i in range(len(d)):
    if K <= d[i]:
        ARC.append(d[i])
    elif K > d[i]:
        ABC.append(d[i])
if len(ABC) == len(ARC):
    print(len(lists))
else:
    print("0")
### BUGGY CODE ###

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

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

def lcm(x, y):
	return (x * y) // gcd(x, y)

num = a[0]
for i in range(1, n):
	num = lcm(num, a[i])

ans = 0
for i in range(n):
	ans += (num//a[i]) % 1000000007
	if ans > 1000000007:
		ans = ans%1000000007

print(ans)

### FIXED CODE ###

import fractions
 
n = int(input())
a = list(map(int, input().split()))
 
l = 1
for i in range(n):
	l = l // fractions.gcd(l, a[i])*a[i]
 
ans = 0
for i in range(n):
	ans += l//a[i]
print(ans%(10**9+7))
### BUGGY CODE ###

#dj 16D8101012J ito jun
n = int(input())
for _ in range(n):
    a = input()
    b = input()
    na=len(a)
    nb=len(b)
    array = [[0]*(nb+1) for _ in range(na+1)]
    for i,x in enumerate(a,1):
        prerow=array[i-1]
        row=array[i]
        for j,y in enumerate(b,1):
            if x == y:
                row[j]=prerow[j-1]+1
            elif prerow[j] < row[j-1]+1:
                row[j] = row[j-1]
            else:
                row[j] = prerow[j]
    print(array[na][nb])



### FIXED CODE ###

#dj 16D8101012J ito jun
import sys
def search(a,b):
    na=len(a)
    nb=len(b)
    array = [[0]*(nb+1) for _ in range(na+1)]
    for i,x in enumerate(a,1):
        prerow=array[i-1]
        row=array[i]
        for j,y in enumerate(b,1):
            if x == y:
                row[j]=prerow[j-1]+1
            elif prerow[j] < row[j-1]:
                row[j] = row[j-1]
            else:
                row[j] = prerow[j]
    return array[-1][-1]

n = int(input())
strs = [list(i) for i in sys.stdin.read().splitlines()]
result = [search(strs[i*2], strs[i*2+1]) for i in range(n)]
print(*result, sep="\n")
### BUGGY CODE ###

#!/usr/bin/env python3
# 方針は分かったのでヨシ！ (dist[nx][ny] > dist[x][y] を忘れてた　後コードきたねえ)
INF = float("inf")
import sys
input = sys.stdin.readline
from collections import*

def bfs():
    q = deque([(sx, sy)])
    dist = [[INF]*W for _ in range(H)]
    dist[sx][sy] = 0
    
    while q:
        x, y = q.popleft()
        for nx, ny in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:
            if 0<=nx<H and 0<=ny<W and dist[nx][ny] > dist[x][y]:
                if c[nx][ny] == ".":
                    dist[nx][ny] = dist[x][y]
                    q.appendleft((nx, ny))
        for nx, ny in [(x-1, y-1), (x-1, y+1), (x+1, y+1), (x+1, y-1)]:
            if 0<=nx<H and 0<=ny<W and dist[nx][ny] > dist[x][y]:
                if c[nx][ny] == ".":
                    dist[nx][ny] = dist[x][y] + 1
                    q.append((nx, ny))
        for nx in range(x-2, x+3):
            for ny in [y+2, y-2]:
                if 0<=nx<H and 0<=ny<W and dist[nx][ny] > dist[x][y]:
                    if c[nx][ny] == ".":
                        dist[nx][ny] = dist[x][y] + 1
                        q.append((nx, ny))
        for nx in [x+2, x-2]:
            for ny in range(y-1, y+2):
                if 0<=nx<H and 0<=ny<W and dist[nx][ny] > dist[x][y]:
                    if c[nx][ny] == ".":
                        dist[nx][ny] = dist[x][y] + 1
                        q.append((nx, ny))            
    return dist[gx][gy]

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

cx, cy = map(int, input().split()); sx, sy = cx - 1, cy - 1
dx, dy = map(int, input().split()); gx, gy = dx - 1, dy - 1
c = [input()[:-1] for _ in range(H)]
ans = bfs()
print(ans if ans != INF else -1)

### FIXED CODE ###

#!/usr/bin/env python3
INF = 10**7
import sys
input = sys.stdin.readline
from collections import*

def bfs():
    q = deque([(sx, sy)])
    dist = [[INF] * W for _ in range(H)]
    dist[sx][sy] = 0
    
    while q:
        x, y = q.popleft()
        b = dist[x][y]
        if (x, y) == (gx, gy):
            return b
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W and dist[nx][ny] > b and c[nx][ny] == ".":
                dist[nx][ny] = b
                q.appendleft((nx, ny))
        B = b + 1
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W and dist[nx][ny] > B and c[nx][ny] == ".":
                    dist[nx][ny] = B
                    q.append((nx, ny)) 
    return -1

H, W = map(int, input().split())
cx, cy = map(int, input().split())
dx, dy = map(int, input().split())
sx, sy, gx, gy = cx - 1, cy - 1, dx - 1, dy - 1
c = [input()[:-1] for _ in range(H)]
ans = bfs()
print(ans if ans != INF else -1)
### BUGGY CODE ###

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

ans=-1
for i in range(n):
  tmp=0
  for j in range(i+1,n):
    if H[j-1]>=H[j]:
      tmp+=1
    else:
      break
  ans=max(ans,tmp)
print(ans)


### FIXED CODE ###

import itertools
n=int(input())
H=list(map(int,input().split()))

ans=[]
for i in range(1,n):
  if H[i-1]>=H[i]:
    ans.append(1)
  else:
    ans.append(0)

out=0
tmp=0
for a in ans:
  if a==1:
    tmp+=1
  else:
    out=max(out,tmp)
    tmp=0
print(max(out,tmp))
### BUGGY CODE ###

N = int(input())
T0 = list(map(int, input().split()))
V = list(map(int, input().split()))

INF = 1000

Tmax = 0
T = [0]
for t in T0:
    Tmax += t
    T.append(Tmax)

preh = 0
ans = 0
for t0 in range(2*Tmax+1):
    t = t0/2
    height = INF
    for n in range(-1, N+1):
        if n == -1:
            t1, t2, v = -1, 0, 0
        elif n == N:
            t1, t2, v = Tmax, Tmax+1, 0
        else:
            t1, t2, v = T[n], T[n+1], V[n]
        
        if t < t1:
            y = v + t1 - t
        elif t1 <= t <= t2:
            y = v
        else:
            y = v + t - t2
        height = min(height, y)
    
    ans += (preh + height)*0.5/2

    preh = height
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
T0 = list(map(int, input().split()))
V = list(map(int, input().split()))

INF = 1000
def main():
    Tmax = 0
    T = [0]
    for t in T0:
        Tmax += t
        T.append(Tmax)

    preh = 0
    ans = 0
    for t0 in range(2*Tmax+1):
        t = t0/2
        height = INF
        for n in range(-1, N+1):
            if n == -1:
                t1, t2, v = -1, 0, 0
            elif n == N:
                t1, t2, v = Tmax, Tmax+1, 0
            else:
                t1, t2, v = T[n], T[n+1], V[n]
            
            if t < t1:
                y = v + t1 - t
            elif t1 <= t <= t2:
                y = v
            else:
                y = v + t - t2
            height = min(height, y)
        
        ans += (preh + height)*0.5/2
        preh = height
    print(ans)

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

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

ans = 0
for i in range(0,N):
  
  for j in range(0,i):
    
    ans = ans + A[i] * A[j]
    ans = ans%(10**9+7)

print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
 
ans = 0
sum = 0
for i in range(1,N):
  
  sum = sum + A[i-1]
  ans = (ans + sum*A[i])%(10**9+7)
  
print(ans)
### BUGGY CODE ###

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

    mnozenje = 1
    for i in a:
        mnozenje *= i

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


if __name__ == '__main__':
    main()


### FIXED CODE ###

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

    if 0 in a:
        print(0)
        return

    maks = 10**18
    mnozenje = 1
    for i in a:
        mnozenje *= i

        if mnozenje > maks:
            print(-1)
            return

    print(mnozenje)


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

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

b = []
for i in range(n):
    b.append(arr[i])
    b.reverse()

for i in range(n-1):
    print(b[i], end = ' ')
print(b[-1])


### FIXED CODE ###

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

b = [0] * n
center = n // 2
for i in range(n):
    if i % 2 == 0:
        b[center + (i//2)] = arr[i]
    else:
        b[center - ((i+1)//2)] = arr[i]

if n % 2 == 0:
    pass
else:
    b.reverse()

for i in range(n-1):
    print(b[i], end = ' ')
print(b[-1])
### BUGGY CODE ###

from collections import deque
n,m = map(int, input().split())
ab=deque()
for _ in range(m):
    ab.append(list(map(int, input().split())))

ans=deque([0]+[1]+[0]*(n-1))
tmp=deque()

tansakuheya=deque([1])

for _ in range(100009):

	for heya in tansakuheya:

		for gyou in range(m):
			if ab[gyou][0]==heya:
				if ans[ab[gyou][1]]==0:
					ans[ab[gyou][1]]=ab[gyou][0]
					tmp.append(ab[gyou][1])

			if ab[gyou][1]==heya:
				if ans[ab[gyou][0]]==0:
					ans[ab[gyou][0]]=ab[gyou][1]
					tmp.append(ab[gyou][0])
	
	if len(tmp)==0:
		break

	tansakuheya=tmp
	tmp=deque()

print("Yes")
for i in range(2,n+1):
	print(ans[i])

### FIXED CODE ###

from collections import deque
n,m = map(int, input().split())
ikisaki=[[] for _ in range(n+1)]

for _ in range(m):
    a,b = map(int, input().split())
    ikisaki[a].append(b)
    ikisaki[b].append(a)
ans=[0]+[1]+[0]*(n-1)
tansakuheya=deque([1])
tmp=deque()

for _ in range(1000009):

    for bangou in tansakuheya:

        for heya in ikisaki[bangou]:
            if ans[heya]==0:
                ans[heya]=bangou
                tmp.append(heya)

    tansakuheya=tmp.copy()
    tmp=deque()


    if not tansakuheya:
        break

print("Yes")
for i in range(2,n+1):
	print(ans[i])
### BUGGY CODE ###

import math

q= int(input())
lrs = [list(map(int,input().split())) for l in range(q)]

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

primes = [0]
for i in range(1,10**5+3):
    if is_prime(i):
        primes.append(1)
    else:
        primes.append(0)

like20 = [0]
for i in range(1,10**5+3):
    if primes[i] == 1 and primes[(i+1) // 2] == 1:
        like20.append(1)
    else:
        like20.append(0)

for lr in lrs:
    l = lr[0]
    r = lr[1]
    print(like20[l:r+1].count(1))
    

### FIXED CODE ###

import math

q= int(input())
lrs = [list(map(int,input().split())) for l in range(q)]

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

primes = [0]
for i in range(1,10**5+3):
    if is_prime(i):
        primes.append(1)
    else:
        primes.append(0)

like20 = [0]
for i in range(1,10**5+3):
    if primes[i] == 1 and primes[(i+1) // 2] == 1:
        like20.append(like20[i-1]+1)
    else:
        like20.append(like20[i-1])

for lr in lrs:
    print(like20[lr[1]] - like20[lr[0]-1])
### BUGGY CODE ###

N, M = map(int, input().split())
A = list([int(input()) for i in range(M)])

stairs = [1] * (N+1)
for i in reversed(range(N+1)):
    if i in A:
        stairs[i] = 0
        continue

    prev_step, two_prev_step = 1, 0
    if (N + 1) > i+1:
        prev_step = stairs[i+1]
    if (N + 1) > i+2:
        two_prev_step = stairs[i+2]

    stairs[i] = prev_step + two_prev_step
print(stairs[0] % 1000000007)

### FIXED CODE ###

import sys
max_num = 1000000007
input = sys.stdin.readline
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]

stairs = [1] * (N+1)
for i in A:
    stairs[i] = 0

for i in range(1, N):
    if stairs[i+1] != 0:
        stairs[i+1] = stairs[i] + stairs[i-1]
print(stairs[N] % max_num)
### BUGGY CODE ###

from collections import deque

def bfs(maze, visited, sy, sx, gy, gx):
  queue = deque([[sy, sx]])
  visited[sy][sx] = 0
  while queue:
    y, x = queue.popleft()
    if [y, x] == [gy, gx]:
      return visited[y][x]
    for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
      new_y, new_x = y+j, x+k
      if new_y >= H or new_y < 0 or new_x >= W or new_x < 0:
        continue
      elif maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
        visited[new_y][new_x] = visited[y][x] + 1
        queue.append([new_y, new_x])

H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]
ans = 0
for sy in range(H):
  for sx in range(W):
    for gy in range(H):
      for gx in range(W):
        visited = [[-1]*W for j in range(H)]
        res = bfs(maze, visited, sy, sx, gy, gx)
        if res != None:
          ans = max(ans, res)
print(ans)

### FIXED CODE ###

from scipy.sparse.csgraph import dijkstra, csgraph_from_dense
import numpy as np

H, W = map(int, input().split())
S = [input() for _ in range(H)]

v_id_dict = {}
dista = np.ones((400, 400)) * np.inf

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            v_id_dict[i, j] = len(v_id_dict)

            if (i > 0) and (S[i - 1][j] == "."):
                dista[v_id_dict[(i, j)], v_id_dict[(i - 1, j)]] = 1

            if (j > 0) and (S[i][j - 1] == "."):
                dista[v_id_dict[(i, j)], v_id_dict[(i, j - 1)]] = 1

dist_mat = dijkstra(
    csgraph_from_dense(dista[: len(v_id_dict), : len(v_id_dict)]),
    directed=False,
    unweighted=False,
)

print(int(dist_mat.max()))
### BUGGY CODE ###

def main():
    N, M, Q = map(int, input().split())
    LR = [[0 for _ in range(N + 1)] for _ in range((N + 1))]
    for _ in range(M):
        L, R = map(int, input().split())
        LR[L][R] += 1
    ans = []
    for _ in range(Q):
        p, q = map(int, input().split())
        c = 0
        for R in LR[p:]:
            c += sum(R[:q + 1])
        ans.append(c)
    for a in ans:
        print(a)


main()


### FIXED CODE ###

def main():
    N, M, Q = map(int, input().split())
    cs = [[0 for _ in range(N + 1)] for _ in range((N + 1))]
    for _ in range(M):
        L, R = map(int, input().split())
        cs[L][R] += 1
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            cs[i][j] += cs[i - 1][j]
            cs[i][j] += cs[i][j - 1]
            cs[i][j] -= cs[i - 1][j - 1]
    ans = []
    for _ in range(Q):
        p, q = map(int, input().split())
        ans.append(cs[q][q] - cs[q][p - 1] - cs[p - 1][q] + cs[p - 1][p - 1])
    for a in ans:
        print(a)


main()