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

h,w,d=map(int,input().split())
num=[0]*(h*w)
for i in range(h):
    a=list(map(int,input().split()))
    for j in range(w):
        num[a[j]-1]=(i,j)

q=int(input())
ans=[0]*q
for i in range(q):
    l,r=map(int,input().split())
    for j in range((r-l)//d):
        ans[i]+=abs(num[l+(j+1)*d-1][0]-num[l+j*d-1][0])+abs(num[l+(j+1)*d-1][1]-num[l+j*d-1][1])

print(*ans,sep='\n')

### FIXED CODE ###

h,w,d=map(int,input().split())
num=[0]*(h*w)
for i in range(h):
    a=list(map(int,input().split()))
    for j in range(w):
        num[a[j]-1]=(i,j)

cost=[0]*(h*w)
for i in range(d,h*w):
    cost[i]=cost[i-d]+abs(num[i][0]-num[i-d][0])+abs(num[i][1]-num[i-d][1])

q=int(input())
ans=[0]*q
for i in range(q):
    l,r=map(int,input().split())
    ans[i]=cost[r-1]-cost[l-1]

print(*ans,sep='\n')
### BUGGY CODE ###

H,N=map(int, input().split())
AB=[list(map(int, input().split())) for _ in range(N)]

INF=10**9

dp=[INF for _ in range(H+1)]
dp[H]=0
for h in range(H,0,-1):
    for n in range(N):
        A,B=AB[n]
        newH=max(0,h-A)
        dp[newH]=min(dp[newH], dp[h]+B)

print(dp[0])

### FIXED CODE ###

H,N=map(int, input().split())
AB=[list(map(int, input().split())) for _ in range(N)]

INF=10**9

dp=[INF for _ in range(H+1)]
dp[H]=0
for h in range(H,0,-1):
    for n in range(N):
        A,B=AB[n]
        newH=max(0,h-A)
        dp[newH]=min(dp[newH], dp[h]+B)

print(dp[0])
### BUGGY CODE ###

N,Y=[int(s) for s in input().split()]
##N枚でY円
flag=0
i10=0
while i10*10000<=Y and i10<=N:
  i5=0
  while i10*10000+i5*5000<=Y and i10+i5<=N :
    i1=0
    while i10*10000+i5*5000+i1*1000<=Y and i10+i5+i1<=N :
      if i10*10000+i5*5000+i1*1000==Y and i10+i5+i1==N:
        print(*[i10,i5,i1])
        flag=1
        break
      i1+=1
    if flag==1 : break
    i5+=1
  if flag==1 : break
  i10+=1
else:
  print(*[-1,-1,-1])


### FIXED CODE ###

N,Y=[int(s) for s in input().split()]
##N枚でY円
flag=0
i10=0
while i10*10000<=Y and i10<=N:
  i5=0
  while i10*10000+i5*5000<=Y and i10+i5<=N :
    i1=N-i10-i5
    if i10*10000+i5*5000+i1*1000==Y:
      print(*[i10,i5,i1])
      flag=1
      break
    i5+=1
  if flag==1 : break
  i10+=1
else:
  print(*[-1,-1,-1])
### BUGGY CODE ###

M = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

max_vs = [0] * 10001
n, m = [int(v) for v in input().split()]
a = [int(v) for v in input().split()]
for i in range(1, n + 1):
        for v in a:
                if M[v] > i:
                        continue
                elif M[v] == i:
                        max_vs[i] = max(max_vs[i], v)
                else:
                        if max_vs[i - M[v]] > 0:
                                max_vs[i] = max(max_vs[i], int(str(v) + str(max_vs[i - M[v]])))
print(max_vs[n])

### FIXED CODE ###

M = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

max_vs = [''] * 10001
n, m = [int(v) for v in input().split()]
a = [int(v) for v in input().split()]
for i in range(1, n + 1):
        for v in a:
                if M[v] > i:
                        continue
                elif M[v] == i:
                        if max_vs[i] == '' or int(max_vs[i]) < v:
                                max_vs[i] = str(v)
                else:
                        if max_vs[i - M[v]] != '':
                                if (max_vs[i] == '') or (len(max_vs[i]) < len(str(v) + max_vs[i - M[v]])) or (len(max_vs[i]) == len(str(v) + max_vs[i - M[v]]) and max_vs[i] < str(v) + max_vs[i - M[v]]):
                                        max_vs[i] = str(v) + max_vs[i - M[v]]
print(max_vs[n])
### BUGGY CODE ###

N = int(input())
S = input()
S = [0 if si == "#" else 1 for si in S]
Bsum = [0] #境界より左にある黒の数
Wsum = [0] #境界より右にある白の数
for i in range(N):
    Bsum = Bsum + [Bsum[-1]+(1 if S[i]==0 else 0) ]
    Wsum = [Wsum[0]+(1 if S[N-i-1]==1 else 0)] + Wsum
print(min([Bsum[i]+Wsum[i] for i in range(N+1)]))

### FIXED CODE ###

N = int(input())
S = input()
Bsum = [0] #境界より左にある黒の数
Wsum = [0] #境界より右にある白の数
for i in range(N):
    Bsum += [Bsum[-1]+(1 if S[i]=="#" else 0) ]
    Wsum += [Wsum[-1]+(1 if S[N-i-1]=="." else 0)]
print(min([Bsum[i]+Wsum[N-i] for i in range(N+1)]))
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(1,n):
    ans += i%(i+1)

print(ans)

### FIXED CODE ###

n = int(input())
ans = (n-1)*n // 2
print(ans)
### BUGGY CODE ###

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

sum = [[0 for j in range(n)] for i in range(n)]
xor = [[0 for j in range(n)] for i in range(n)]
ans = n

for i in range(n):
    sum[i][i] = a_list[i]
    xor[i][i] = a_list[i]
for r in range(n):
    for l in range(r+1, n):
        sum[r][l] = sum[r][l-1] + a_list[l]
        xor[r][l] = xor[r][l - 1] ^ a_list[l]
        if sum[r][l] == xor[r][l]:
            ans += 1

print(ans)


### FIXED CODE ###

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

ans = 0
r = -1
xor_n = 0
sum_n = 0
for l in range(n):
    while True:
        r += 1

        if r < n:
            nr = a[r]
            xor_n ^= nr
            sum_n += nr
            ok = xor_n == sum_n
        if r >= n or not ok:
            ans += (r - 1) - l + 1
            sum_n -= nr
            sum_n -= a[l]
            xor_n ^= nr
            xor_n ^= a[l]
            r -= 1
            break
print(ans)
### BUGGY CODE ###

N = int(input())
sum = 0
for i in range(1, N):
    sum += i
print(sum)

### FIXED CODE ###

N = int(input())
print((N-1)*N//2)
### BUGGY CODE ###

N, M = map(int, input().split())
if N == 1:
    print(1)
else:
    A = [int(input()) for _ in range(M)]

    S =[0]*(N + 1)
    S[0] = 1
    if 1 in A:
        S[1] = 0
    else:
        S[1] = 1

    for i in range(2, N+1):
        if i in A:
            S[i] = 0
        else:
            S[i] = (S[i-1] + S[i-2]) % 1000000007
    print(S[N])


### FIXED CODE ###

N, M = map(int, input().split())
A = set()
for _ in range(M):
    A.add(int(input()))
p = 10 ** 9 + 7
DP = [0 for _ in range(N + 1)]
DP[0] = 1
if 1 in A:
    DP[1] = 0
else: DP[1] = 1
for i in range(2, N+1):
    if i in A:
        DP[i] = 0
    else:
        DP[i] = (DP[i-1] + DP[i-2])%p
print(DP[N])
### BUGGY CODE ###

from bisect import bisect_left
from decimal import Decimal

N, *A = map(Decimal, open(0).read().split())
N = int(N)
A.sort()

c = {}
intc = 0
ints = []
decs = []
for d in A:
    if d in c:
        c[d] += 1
        if d == int(d):
            intc += 1
    else:
        c[d] = 1
        if d == int(d):
            intc += 1
            ints.append(d)
        else:
            decs.append(d)

result = intc * (intc - 1) // 2
for i in range(len(decs)):
    a = decs[i]
    if a < 1:
        t = bisect_left(decs, 1 / a)
    else:
        t = i + 1
    for j in range(t, len(decs)):
        b = decs[j]
        t = a * b
        if t == int(t):
            #print(a, b)
            result += c[a] * c[b]

    f = a - int(a)
    t = bisect_left(ints, 1 / f)
    for j in range(t, len(ints)):
        b = ints[j]
        t = a * b
        if t == int(t):
            #print(a, b)
            result += c[a] * c[b]

print(result)


### FIXED CODE ###

def conv(s):
    if s.find('.') == -1:
        s += '.'
    s = s.rstrip('0')
    t = len(s) - s.find('.') - 1
    a = int(s.replace('.', ''))
    if a == 0:
        return (0, 0)
    x, y = -t, -t
    while a % 5 == 0:
        x += 1
        a //= 5
    while a % 2 == 0:
        y += 1
        a //= 2
    return (x, y)


N, *A = open(0).read().split()
N = int(N)

d = {}
for a in A:
    t = conv(a)
    d.setdefault(t, 0)
    d[t] += 1

result = 0
xs = list(d.keys())
for i in range(len(xs)):
    x, y = xs[i]
    t = d[xs[i]]
    if x >= 0 and y >= 0:
        result += t * (t - 1) // 2
    for j in range(i + 1, len(xs)):
        m, n = xs[j]
        if x + m >= 0 and y + n >= 0:
            result += t * d[xs[j]]
print(result)
### BUGGY CODE ###

h,w,k=map(int,input().split())
ans=10**9
choco=[list(input()) for i in range(h)]
sumL=[[0 for i in range(w+1)] for j in range(h+1)]
for i in range(h):
    for j in range(w):
        sumL[i][j]=sumL[i-1][j]+sumL[i][j-1]-sumL[i-1][j-1]+int(choco[i][j])
for stat in range(2**(h-1)):
    cnt=0;previous=-1
    flg=0
    cut=format(stat,"b").zfill(h-1)
    cutl=[]
    for hi in range(h-1):
        if cut[hi]=="1":
            cutl.append(hi)
            cnt+=1
    cutl.append(h-1)
    cutl.append(-1)
    for yoko in range(w):
        for seg in range(len(cutl)):
            if sumL[cutl[seg]][yoko]-sumL[cutl[seg]][previous]-sumL[cutl[seg-1]][yoko]+sumL[cutl[seg-1]][previous]>k and yoko-previous<=1:flg=1
            elif sumL[cutl[seg]][yoko]-sumL[cutl[seg]][previous]-sumL[cutl[seg-1]][yoko]+sumL[cutl[seg-1]][previous]>k:previous=yoko-1;cnt+=1
            
    if not flg and cnt < ans:ans=cnt
    
print(ans)

### FIXED CODE ###

h,w,k=map(int,input().split())
ans=10**9
choco=[list(input()) for i in range(h)]
sumL=[[0 for i in range(w+1)] for j in range(h+1)]
for i in range(h):
    for j in range(w):
        sumL[i][j]=sumL[i-1][j]+sumL[i][j-1]-sumL[i-1][j-1]+int(choco[i][j])
for stat in range(2**(h-1)):
    cnt=0;previous=-1
    flg=0
    cut=format(stat,"b").zfill(h-1)
    cutl=[]
    for hi in range(h-1):
        if cut[hi]=="1":
            cutl.append(hi)
            cnt+=1
    cutl.append(h-1)
    cutl.append(-1)
    for yoko in range(w):
        for seg in range(len(cutl)):
            if sumL[cutl[seg]][yoko]-sumL[cutl[seg]][previous]-sumL[cutl[seg-1]][yoko]+sumL[cutl[seg-1]][previous]>k and yoko-previous<=1:flg=1
            elif sumL[cutl[seg]][yoko]-sumL[cutl[seg]][previous]-sumL[cutl[seg-1]][yoko]+sumL[cutl[seg-1]][previous]>k:previous=yoko-1;cnt+=1
            
    if not flg and cnt < ans:ans=cnt
    
print(ans)
### BUGGY CODE ###

import math
N=int(input())
for i in range(1,N+1):
    tmp=0
    tgt=int(math.sqrt(i/2)+1)
    for j in range(1,tgt):
        for k in range(j,tgt):
            for h in range(k,tgt):
                if h**2+j**2+k**2+h*j+j*k+k*h==i:
                    if j==k==h:
                        tmp+=1
                    elif j==k or k ==h:
                        tmp+=3
                    else:
                        tmp+=6
    print(tmp)

### FIXED CODE ###

N=int(input())
a=[0]*10**4
for j in range(1,101):
    for k in range(1,101):
        for h in range(1,101):
            tmp=h**2+j**2+k**2+h*j+j*k+k*h
            if tmp<=10000:
                a[tmp-1]+=1
for i in range(N):
    print(a[i])
### BUGGY CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n = int(input())
A = []
ans = 0
nodes = set()
adjacent_list = defaultdict(list)
for i in range(n):
    tmp = list(map(int, input().split()))
    pre = tmp[0] - 1
    nodes.add(min(i, pre) * n + max(i, pre))
    for j in tmp[1:]:
        l, g = min(i, j - 1), max(i, j - 1)
        pre_l, pre_g = min(i, pre), max(i, pre) 
        adjacent_list[pre_l * n + pre_g].append(l * n + g)
        pre = j - 1
nodes = list(nodes)
#まず、閉路検
seen = defaultdict(lambda: False)
visited = defaultdict(lambda: False)
def check(node):
    if visited[node]:
        return
    seen[node] = True
    for i in adjacent_list[node]:
        if seen[i] and (not visited[i]):
            print(-1)
            exit()
        check(i)
    visited[node] = True
def dfs_path(node):
    if not adjacent_list[node]:
        return 1
    if node in finish:
        return finish[node]
    tmp = 0
    for i in adjacent_list[node]:
        tmp = max(tmp, dfs_path(i) + 1)
    finish[node] = tmp
    return finish[node]
finished = set()

for i in nodes:
    check(i)
finish = defaultdict(int)
for i in nodes:
    dfs_path(i)
print(max(max(finish.values()), 1))

### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n = int(input())
A = []
M = [[-1 for _ in range(n)] for _ in range(n)]
cnt = 0
for i in range(n):
    for j in range(i+1,n):
        M[i][j] = cnt
        M[j][i] = cnt
        cnt += 1
ans = 0
nodes = []
adjacent_list = [[] for i in range(n*(n-1)//2)]
for i in range(n):
    tmp = list(map(int, input().split()))
    pre = tmp[0] - 1
    for j in tmp[1:]:
        adjacent_list[M[i][pre]].append(M[i][j-1])
        pre = j - 1
#まず、閉路検
seen = defaultdict(lambda: False)
visited = defaultdict(lambda: False)
def check(node):
    if visited[node]:
        return
    seen[node] = True
    for i in adjacent_list[node]:
        if seen[i] and (not visited[i]):
            print(-1)
            exit()
        check(i)
    visited[node] = True
def dfs_path(node):
    if not adjacent_list[node]:
        return 1
    if finish[node]:
        return finish[node]
    tmp = 0
    for i in adjacent_list[node]:
        tmp = max(tmp, dfs_path(i) + 1)
    finish[node] = tmp
    return finish[node]
finished = set()
finish = [0 for i in range(n*(n-1)//2)]
for i in range(n*(n-1)//2):
    check(i)
    dfs_path(i)
print(max(max(finish), 1))
### BUGGY CODE ###

def query(i):
    '''
    a[0] + a[1] + … + a[i-1] を求める
    O(logN)
    '''
    res = 0
    while i > 0:
        res += BIT[i]
        i -= i & -i
    
    return res


def update(i, x):
    '''
    a[i-1]にxを加算
    O(logN)
    '''
    while i <= n:
        BIT[i] += x
        i += i & -i


n, q = map(int, input().split())
c = list(map(int, input().split()))
query_ = [list(map(int, input().split())) + [i] for i in range(q)]

query_.sort(key=lambda x: x[1])

res = [0] * q
pos = [-1] * n
BIT = [0] * (n+1)
p = 0
for l, r, idx in query_:
    for i in range(p, r):
        if pos[c[i]-1] != -1:
            update(pos[c[i]-1]+1, -1)
        update(i+1, 1)
        pos[c[i]-1] = i
    
    res[idx] = query(r) - query(l-1)
    p = r

for v in res:
    print(v)

### FIXED CODE ###

import sys

input = sys.stdin.readline

def query(i):
    '''
    a[0] + a[1] + … + a[i-1] を求める
    O(logN)
    '''
    res = 0
    while i > 0:
        res += BIT[i]
        i -= i & -i
    
    return res


def update(i, x):
    '''
    a[i-1]にxを加算
    O(logN)
    '''
    while i <= n:
        BIT[i] += x
        i += i & -i


n, q = map(int, input().split())
c = list(map(int, input().split()))
query_ = [list(map(int, input().split())) + [i] for i in range(q)]

query_.sort(key=lambda x: x[1])

res = [0] * q
pos = [-1] * n
BIT = [0] * (n+1)
p = 0
for l, r, idx in query_:
    for i in range(p, r):
        if pos[c[i]-1] != -1:
            update(pos[c[i]-1]+1, -1)
        update(i+1, 1)
        pos[c[i]-1] = i
    
    res[idx] = query(r) - query(l-1)
    p = r

for v in res:
    print(v)
### BUGGY CODE ###

import numpy as np
import copy
N=int(input())
l=list(map(int, input().split()))  #リスト入力
cp = copy.copy(l)

#even_c=0
#odd_c=0
c=0

if l[0]!=0:
  #l[0]=-1
  #even_c=even_c+1
  for k in range(1,N):
    #print(sum(l[:k]),sum(l[:k+1]))
    s=sum(l[:k])
    if s*sum(l[:k+1])>0:
      #print(k)
      c=c+abs(-np.sign(s)-s-l[k])
      l[k]=-np.sign(s)-s
  #print(l)
  if sum(l)==0:
    print(c+1)
    #print(1+sum([abs(l[n]-cp[n]) for n in range(N)]))
  else:
    print(c)
    #print(sum([abs(l[n]-cp[n]) for n in range(N)]))

  
else:
  #1
  sei_l=copy.copy(l)
  sei_l[0]=1
  for k in range(1,N):
    #print(sum(l[:k]),sum(l[:k+1]))
    if sum(sei_l[:k])*sum(sei_l[:k+1])>0:
      #print(k)
      sei_l[k]=-np.sign(sum(sei_l[:k]))-sum(sei_l[:k])
  #print(l)
  if sum(sei_l)==0:
    c1=1+sum([abs(sei_l[n]-cp[n]) for n in range(N)])
  else:
    c1=sum([abs(sei_l[n]-cp[n]) for n in range(N)])  
  #-1
  fu_l=copy.copy(l)
  sei_l[0]=-1
  for k in range(1,N):
    #print(sum(l[:k]),sum(l[:k+1]))
    if sum(fu_l[:k])*sum(fu_l[:k+1])>0:
      #print(k)
      fu_l[k]=-np.sign(sum(fu_l[:k]))-sum(fu_l[:k])
  #print(l)
  if sum(fu_l)==0:
    c2=1+sum([abs(fu_l[n]-cp[n]) for n in range(N)])
  else:
    c2=sum([abs(fu_l[n]-cp[n]) for n in range(N)])  
  
  print(max(c1,c2))

### FIXED CODE ###

from copy import copy
n = int(input())
a = [int(x) for x in input().split()]
ans1=[(-1)**i for i in range(n)]

b=copy(a)
res_b=0
sb=0
c=copy(a)
res_c=0
sc=0
for i in range(n):
  sb+=a[i]
  if ans1[i]*sb>0:
    pass
  else:
    b[i]=ans1[i]-(sb-b[i])
    sb=sb-a[i]+b[i]
    res_b+=abs(b[i]-a[i])

  sc+=a[i]
  if -1*ans1[i]*sc>0:
    pass
  else:
    c[i]=-1*ans1[i]-(sc-c[i])
    sc=sc-a[i]+c[i]
    res_c+=abs(c[i]-a[i])
  
print(min(res_b,res_c))
### BUGGY CODE ###

n,k=map(int,input().split())
m=abs(n-k)
while m<n:
    n=m
    m=abs(n-k)
print(n)

### FIXED CODE ###

n,k=map(int,input().split())
m=n%k
if m>abs(m-k):
    m=abs(m-k)
print(m)
### BUGGY CODE ###

from collections import deque
n,m,k = map(int,input().split()) 
g = [[] for _ in range(n)]
bl = [[] for _ in range(n)]

for _ in range(m):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    g[a].append(b)
    g[b].append(a)

for _ in range(k):
    c,d = map(int,input().split())
    c,d = c-1,d-1
    bl[c].append(d)
    bl[d].append(c)


def bfs(u):
    q = deque([u])
    d = [None]*n
    d[u] = 0
    while q:
        v = q.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                q.append(i)
    return d


for i in range(n):
    ans = 0
    d = bfs(i)
    for j in range(len(d)):
        if j != i and d[j] != None and j not in g[i]:
            if j not in bl[i]:
                ans += 1
    print(ans,end = " ")

### FIXED CODE ###

n,m,k = map(int,input().split())
par = [-1]*(n+1)
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    else:
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
def size(x):
    return -par[find(x)]
g = [[] for _ in range(n+1)]
b = [[] for _ in range(n+1)]
for _ in range(m):
    s,t = map(int,input().split())
    unite(s,t)
    g[s].append(t)
    g[t].append(s)
for _ in range(k):
    s,t = map(int,input().split())
    b[s].append(t)
    b[t].append(s)
for i in range(1,n+1):
    ans = size(i)-1-len(g[i])
    for e in b[i]:
        if same(i,e):
            ans -= 1
    print(ans,end=" ")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(200000+10)

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

#xの木の根を求める
def root(x,li): 
    if li[x] == x:
        return x
    else:
        li[x] = root(li[x],li)
        return li[x]

#xとyが同じ集合に属するかの判定
def find(x,y,li):
    return root(x,li) == root(y,li)

#xとｙを併合
def union(x,y,li):
    x = root(x,li)
    y = root(y,li)
    if x==y:
        return
    else:
        li[x] = y

li = [i for i in range(N+20)]

for i in range(len(AB)):
    AB[i][0] -= 1
    AB[i][1] -= 1
    union(AB[i][0], AB[i][1], li)

for i in range(N):
    root(i, li)

cnt = [0 for i in range(N+20)]
for i in range(N):
    cnt[li[i]] += 1
print(max(cnt))

### FIXED CODE ###

import sys
sys.setrecursionlimit(200000+10)

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

class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    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):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        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
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
            # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

UF = UnionFind(N)
li = [i for i in range(N+20)]

for i in range(len(AB)):
    AB[i][0] -= 1
    AB[i][1] -= 1
    UF.Unite(AB[i][0], AB[i][1])

cnt = [UF.Count(i) for i in range(N)]
print(max(cnt))
### BUGGY CODE ###

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

sum_K = [sum(nums[i:i+K]) \
        for i in range(len(nums)-K+1)]
        
print((max(sum_K)+K)/2)

### FIXED CODE ###

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

sum_K = [0]*(N-K+1)
sum_K[0] = sum(nums[:K])
for pos in range(1,N-K+1):
    sum_K[pos] = sum_K[pos-1] -   \
        nums[pos-1] + nums[pos+K-1]

print((max(sum_K)+K)/2)
### BUGGY CODE ###

MOD = 10**9+7
N, M = [int(x) for x in input().split()]
a_list = []
if (M != 0):
    a_list = [int(input()) for _ in range(M)]
dp = [0] * (N+1)
dp[0] = 1
dp[1] = int(not (1 in a_list))
for i in range(2, N+1):
    if (i not in a_list):
        dp[i] = (dp[i-1] + dp[i-2]) % MOD
print(dp[N])


### FIXED CODE ###

from sys import setrecursionlimit
setrecursionlimit(10**7)
lst = dict({0: 1, 1: 1, 2: 2})
def calc(n):
    if (n in lst):
        return lst[n]
    else:
        lst[n] = calc(n-1) + calc(n-2)
        return lst[n]

N, M = [int(x) for x in input().split()]
if (M != 0):
    a_list = [int(input()) for _ in range(M)]
    span_list = [a_list[0]-1]
    for i, a in enumerate(a_list[:-1]):
        if (a_list[i+1] - a) == 1:
            print(0)
            exit()
        else:
            span_list.append(a_list[i+1] - 2 - a)
    span_list.append(N - a_list[-1] -1)
else:
    span_list = [N]
max_span = max(span_list)
for i in range(max_span+1):
    calc(i)
ans = 1
for span in span_list:
    ans = (ans * lst[span]) % (10**9+7)
print(ans)
### BUGGY CODE ###

n=int(input())
ans=0
mod=1000000007
list1=list(map(int ,input().split()))
for i in range(n):
  ans=ans+list1[i]*sum(list1[i+1:n])
    
print(ans%mod)

### FIXED CODE ###

n=int(input())
ans=0
mod=10**9+7
list1=list(map(int ,input().split()))
sums=sum(list1)

for i in list1:
  sums -=i
  ans +=sums*i%mod
  
print(ans%mod)
### BUGGY CODE ###

h, w = map(int, input().split())
maze = [input() for i in range(h)]
graph = {}

for i, s_i in enumerate(maze):
  for j, s_ij in enumerate(s_i):
    if s_ij == ".":
      graph[i * w + j] = []
      if i > 0 and maze[i - 1][j] == ".":
        graph[i * w + j].append((i - 1) * w + j)
      if j > 0 and maze[i][j - 1] == ".":
        graph[i * w + j].append(i * w + j - 1)
      if j < w - 1 and maze[i][j + 1] == ".":
        graph[i * w + j].append(i * w + j + 1)
      if i < h - 1 and maze[i + 1][j] == ".":
        graph[i * w + j].append((i + 1) * w + j)

ans = 0
for start in graph.keys():
  dist = {}
  c = 0
  dist[start] = c
  hoge = {start}
  for _ in graph.keys():
    c += 1
    fuga = set()
    for h in hoge:
      fuga |= set(graph[h])
    fuga -= set(dist.keys())
    for f in fuga:
      dist[f] = c  
    hoge = fuga
  ans = max(ans, max(dist.values()))
  
print(ans)



### FIXED CODE ###

h, w = map(int, input().split())
maze = [input() for i in range(h)]
graph = {}

for i, s_i in enumerate(maze):
  for j, s_ij in enumerate(s_i):
    if s_ij == ".":
      graph[i * w + j] = []
      if i > 0 and maze[i - 1][j] == ".":
        graph[i * w + j].append((i - 1) * w + j)
      if j > 0 and maze[i][j - 1] == ".":
        graph[i * w + j].append(i * w + j - 1)
      if j < w - 1 and maze[i][j + 1] == ".":
        graph[i * w + j].append(i * w + j + 1)
      if i < h - 1 and maze[i + 1][j] == ".":
        graph[i * w + j].append((i + 1) * w + j)

ans = 0
for start in graph.keys():
  dist = {}
  c = 0
  dist[start] = c
  hoge = {start}
  for _ in graph.keys():
    c += 1
    fuga = set()
    for h in hoge:
      fuga |= set(graph[h])
    fuga -= set(dist.keys())
    for f in fuga:
      dist[f] = c
    hoge = fuga
    if len(dist) == len(graph):
      break
  ans = max(ans, max(dist.values()))
  
print(ans)