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

import sys
from heapq import *

H,W=map(int,input().split())
si,sj=[int(x)-1 for x in input().split()]
ti,tj=[int(x)-1 for x in input().split()]
A=list(sys.stdin)

ans=-1
hp=[(0,si,sj)]
dirs=[-2,-1,0,1,2]
dist=[[float('inf')]*W for _ in range(H)]
dist[si][sj]=0
while hp:
    k,i,j=heappop(hp)
    if i==ti and j==tj:
        ans=k
        break
    if k>dist[i][j]:
        continue
    dist[i][j]=k
    for di in dirs:
        for dj in dirs:
            if di==dj==0:
                continue
            ni,nj=i+di,j+dj
            if not (0<=ni<H and 0<=nj<W):
                continue
            if A[ni][nj]=='#':
                continue
            if abs(di)+abs(dj)==1:
                nk=k
            else:
                nk=k+1
            heappush(hp,(nk,ni,nj))

print(ans)


### FIXED CODE ###

import sys
from heapq import *

H,W=map(int,input().split())
si,sj=[int(x)-1 for x in input().split()]
ti,tj=[int(x)-1 for x in input().split()]
A=list(sys.stdin)

ans=-1
hp=[(0,si,sj)]
dirs=[-2,-1,0,1,2]
dist=[[float('inf')]*W for _ in range(H)]
dist[si][sj]=0
while hp:
    k,i,j=heappop(hp)
    if i==ti and j==tj:
        ans=k
        break
    if k>dist[i][j]:
        continue
    for di in dirs:
        for dj in dirs:
            if di==dj==0:
                continue
            ni,nj=i+di,j+dj
            if not (0<=ni<H and 0<=nj<W):
                continue
            if A[ni][nj]=='#':
                continue
            if abs(di)+abs(dj)==1:
                nk=k
            else:
                nk=k+1
            if nk>=dist[ni][nj]:
                continue
            dist[ni][nj]=nk
            heappush(hp,(nk,ni,nj))

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

N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
a = 0
b = 0
ans = 0
t = sum(A)
temp = 0
if t <= K:
    ans = N
for i in range(0,N+1):
    if i != 0:
        t -= A[-i]
    temp = t
    j = 0
    ans2 = 0
    while temp < K and j < len(B):
        if temp + B[j] <= K:
            ans2 += 1
            temp += B[j]
            j += 1
        else:
            break
    if temp <= K:
        ans = max(ans,len(A)-i+ans2)
print(ans)


### FIXED CODE ###

N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
a = 0
b = 0
ans = 0
t = sum(A)
temp = 0
if t <= K:
    ans = N
j = 0
ans2 = 0
for i in range(0,N+1):
    if i != 0:
        t -= A[-i]
    while t < K and j < len(B):
        if t + B[j] <= K:
            ans2 += 1
            t += B[j]
            j += 1
        else:
            break
    if t <= K:
        ans = max(ans,len(A)-i+ans2)
print(ans)
### BUGGY CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
s = list(set(a))

cnt=0
for i in s:
  if a.count(i)%2==1:
    cnt+=1
print(cnt)

### FIXED CODE ###

import collections
n=int(input())
a=[int(input()) for i in range(n)]
s=list(collections.Counter(a).values())
cnt=0
for i in s:
  if i%2!=0:
    cnt+=1
print(cnt)
### BUGGY CODE ###

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

xh=[list(map(int, input().split())) for _ in range(n)]
xh.sort()

cnt=0

for i in range(n):
    (x,h)=xh[i]
    if h>0:
        bomb=x+d

        count=((-1*h)//a)*(-1)
        damage=count*a
        cnt+=count
        j=1
        #print("bomb",bomb)
        while i+j<n and xh[i+j][0]<=bomb+d:
            xh[i+j][1]-=damage
            j+=1
            #print("?")

print(cnt)



### FIXED CODE ###

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

xh=[list(map(int, input().split())) for _ in range(n)]
xh.sort()

cnt=0

import heapq  # heapqライブラリのimport
#heapq.heapify(a)  # リストを優先度付きキューへ
#heapq.heappop(a)  # 最小値の取り出し
#heapq.heappush(a, -2)

bomb=0
he=[]
heapq.heapify(he)
dic={}

for i in range(n):
    #print(xh[i],bomb,he)
    (x,h)=xh[i]

    if bomb==0:
        secchi=x+d
        count=((-1*h)//a)*(-1)
        damage=count*a
        cnt+=count
        dic[secchi]=damage
        bomb+=damage
        heapq.heappush(he, secchi)
    else:
        while a:
            tmp=heapq.heappop(he)  
            if tmp+d<x:
                bomb-=dic[tmp]
            else:
                heapq.heappush(he, tmp)
                break
            if bomb==0:
                break

        if bomb<h:
            h-=bomb
            secchi=x+d
            count=((-1*h)//a)*(-1)
            damage=count*a
            cnt+=count
            dic[secchi]=damage
            bomb+=damage
            heapq.heappush(he, secchi)



print(cnt)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
pop = 0
for i in set(a):
    if a.count(i) < i:
        pop += a.count(i)
    elif a.count(i) > i:
        pop += a.count(i) - i
print(pop)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
n = {}
pop = 0
for ai in a:
    n[ai] = n.get(ai, 0) + 1
for ni in n:
    if ni < n[ni]:
        pop += n[ni] - ni
    elif ni > n[ni]:
        pop += n[ni]
print(pop)
### BUGGY CODE ###

n, m = map(int, input().strip().split())
dp = [float('inf')]*(2**n)
dp[0] = 0
for i in range(m):
    a, b = input().strip().split()
    a = int(a)
    b = int(b)
    M = 0
    for i in input().strip().split():
        M += 2**(int(i)-1)

    for j in range(2**n):
        dp[j|M] = min(dp[j]+a, dp[j|M])

print(dp[2**n-1] if dp[2**n-1] < float('inf') else -1)

### FIXED CODE ###

n,m = input().split(' ')
n = int(n)
m = int(m)
dp = [float('inf')]*2**n
dp[0] = 0
for i in range(m):
    a,b = input().split(' ')
    a = int(a)
    b = int(b)
    ngo = 0
    for j in input().split(' '):
        ngo += 2**(int(j)-1)
    for j in range(2**n):
        if dp[j|ngo] > dp[j]+a:
            dp[j|ngo] = dp[j]+a
    
if dp[2**n-1] == float('inf'):
    print(-1)
    exit(0)
print(dp[2**n-1])
### BUGGY CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
b_c = [list(map(int,input().split())) for i in range(m)]
b_c.sort(key=lambda x:x[1])
for i_j in b_c:
     b,c = i_j[0],i_j[1]
     for i in range(len(a)):
          if b == 0 or a[i] > c:
               break
          if a[i] < c:
               a[i] = c
               b -= 1
     a.sort()
print(sum(a))

### FIXED CODE ###

def f(n,m):
     a = list(map(int,input().split()))
     min_a = min(a)
     a = [(1,i) for i in a]
     b_c = [tuple(map(int,input().split())) for i in range(m)]
     a += b_c
     a.sort(key=lambda x:x[1])
     ans = 0
     while True:
          if n>a[-1][0]:
               ans += a[-1][0]*a[-1][1]
               n -= a[-1][0]
               a.pop()
          else:
               ans += a[-1][1]*n
               break
     print(ans)

n,m = map(int,input().split())
f(n,m)
### BUGGY CODE ###

X, K, D = map(int, input().split())


for i in range(K):
    if abs(X + D) < abs(X - D):
        X = X + D
    else:
        X = X - D
    if abs(X - D) > abs(X) and abs(X + D) > abs(X):
        if (K - i - 1) % 2 == 1:
            if abs(X - D) < abs(X + D):
                X = X - D
            else:
                X = X + D
        break



print(abs(X))

### FIXED CODE ###

from sys import setrecursionlimit

setrecursionlimit(10 ** 8)


def main(x, k, d):
    for i in range(k):
        if abs(x + d) < abs(x - d):
            x = x + d
        else:
            x = x - d

        if abs(x - d) > abs(x) and abs(x + d) > abs(x):
            if (k - i - 1) % 2 == 1:
                if abs(x - d) < abs(x + d):
                    x = x - d
                else:
                    x = x + d
            break

    print(abs(x))


def sub(x, k, d):
    print(abs(x) - d * k)


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

if abs(a) - b * c >= 0:
    sub(a, b, c)
else:
    main(a, b, c)
### BUGGY CODE ###

alp = {"a":2, "b":3,"c":5,"d":7,"e":11,"f":13,"g":17,"h":19,"i":23,"j":29,
       "k":31,"l":37,"m":41,"n":43,"o":47,"p":53,"q":59,"r":61,"s":67,"t":71,
       "u":73,"v":79,"w":83,"x":3.3,"y":2.3,"z":1.3}

n = int(input())

s = []

for i in range(n):
    tss= str(input()) # tss; temporary str s
    ts = 1
    for j in range(10):
      ts *= alp[tss[j]] # ts; temporary s
    s.append(ts)

a = 0 # a; pre ans

for i in range(n):
    for j in range(1, n - i):
        if s[i] == s[i + j]:
            a += 1

print(a)  


### FIXED CODE ###

n = int(input())
d = dict()

for _ in range(n):
    s = "".join(sorted([x for x in input()]))
    d[s] = d.get(s, 0) + 1

ans = 0

for v in d.values():
    if v >= 2:
        ans += (v * (v-1)) // 2

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

a,b,c,d,e,f = map(int, input().split())

sugar = []
for i in range(0, f+1):
    for j in range(0, f+1):
        y = i*c + j*d
        if y <= f:
            sugar.append(y)

water = []
for i in range(0, f+1):
    for j in range(0, f+1):
        x = i*a*100 + j*b*100
        if x <= f:
            water.append(x)
max_concentration = 0
for x in water:
    for y in sugar:
        if x == 0 and y == 0:
            continue
        elif e * (x // 100) < y:
            continue
        elif x + y > f:
            continue
        else:
            concentration = 100 * y / (x+y)
            if max_concentration <= concentration and concentration <= 100*(e/100) and x+y <= f:
                max_concentration = concentration
                ans1 = x+y
                ans2 = y
print("{} {}".format(ans1, ans2))


### FIXED CODE ###

a,b,c,d,e,f = map(int, input().split())

sugar = []
for i in range(f):
    for j in range(f):
        y = i*c + j*d
        if y <= f:
            sugar.append(y)

water = []
for i in range(0, f//100+1):
    for j in range(0, f//100+1):
        x = i*a*100 + j*b*100
        if x <= f:
            water.append(x)
max_concentration = 0
ans1, ans2 = 0, 0
for x in water:
    for y in sugar:
        if x == 0 and y == 0:
            continue
        elif e * (x // 100) < y:
            continue
        elif x + y > f:
            continue
        else:
            concentration = (100 * y) / (x+y)
            if max_concentration <= concentration:
                max_concentration = concentration
                ans1 = x+y
                ans2 = y
print("{} {}".format(ans1, ans2))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N = int(input())
G = [[] for i in range(N + 1)]
for i in range(1, N):
    a = int(input())
    G[a - 1].append(i)


def dfs(v):
    D = []
    for w in G[v]:
        D.append(dfs(w))

    D = sorted(D, reverse=True)

    num = 0
    for i in range(len(D)):
        num = max(num, D[i] + i + 1)

    return num


print(dfs(0))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N = int(input())
G = [[] for i in range(N + 1)]
for i in range(1, N):
    a = int(input())
    G[a - 1].append(i)


def dfs(v):
    if len(G[v]) == 0:
        return 0
    D = []
    for w in G[v]:
        D.append(dfs(w))

    D = sorted(D, reverse=True)

    num = 0
    for i in range(len(D)):
        num = max(num, D[i] + i + 1)

    return num


print(dfs(0))
### BUGGY CODE ###

N,Q=map(int,input().split())
S=str(input())
for i in range(Q):
    l,r=map(int,input().split())
    count=0
    for j in range(l,r):
        if S[j-1]=="A" and S[j]=="C":
            count+=1
        else:
            count=count
    print(count)


### FIXED CODE ###

N, Q = map(int, input().split())
S = str(input())
wa=[0]*N
p=0
for j in range(1,N):
    if S[j-1]=="A" and S[j]=="C":
        p+=1
        wa[j]=p
    else:
        wa[j]=wa[j-1]
for i in range(Q):
    k =input().split()
    l=int(k[0])
    r=int(k[1])
    print(wa[r-1]-wa[l-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def solve():
    N, Q = map(int, input().split())
    adjL = [[] for _ in range(N)]
    for _ in range(N-1):
        A, B = map(int, input().split())
        A, B = A-1, B-1
        adjL[A].append(B)
        adjL[B].append(A)

    anss = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        p = p-1
        anss[p] += x

    useds = [False] * N
    def dfs(vNow, x):
        useds[vNow] = True
        anss[vNow] += x
        for v2 in adjL[vNow]:
            if not useds[v2]:
                dfs(v2, anss[vNow])

    dfs(0, 0)

    print(' '.join(map(str, anss)))

solve()


### FIXED CODE ###

def solve():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline

    N, Q = map(int, input().split())
    adjL = [[] for _ in range(N)]
    for _ in range(N-1):
        A, B = map(int, input().split())
        A, B = A-1, B-1
        adjL[A].append(B)
        adjL[B].append(A)

    anss = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        p = p-1
        anss[p] += x

    useds = [False] * N
    def dfs(vNow, x):
        useds[vNow] = True
        anss[vNow] += x
        ans = anss[vNow]
        for v2 in adjL[vNow]:
            if not useds[v2]:
                dfs(v2, ans)

    dfs(0, 0)

    print(' '.join(map(str, anss)))

solve()
### BUGGY CODE ###

N = int(input())
numbers = [int(input()) for _ in range(N)]

M = 998244353
count_all = (3 ** N - 3 * (2 ** N - 2) - 3) % M

S = sum(numbers)
count3 = [[0 for _ in range(S + 1)] for _ in range(N)]
count3[0][0] = 2
count3[0][numbers[0]] = 1
count2 = [[0 for _ in range(S + 1)] for _ in range(N)]
count2[0][0] = 1
count2[0][numbers[0]] = 1

for i in range(1, N):
  for j in range(S + 1):
    if (count3[i - 1][j] > 0):
      count3[i][j + numbers[i]] += count3[i - 1][j]
      count3[i][j] += 2 * count3[i - 1][j]
      count2[i][j + numbers[i]] += count2[i - 1][j]
      count2[i][j] += count2[i - 1][j]

count_invalid = 0
for i in range(S):
  if (i > S / 2):
    count_invalid += count3[N - 1][i] - 2 * count2[N - 1][i]
if (S % 2 == 0):
  count_invalid += count3[N - 1][S // 2] - 2 * count2[N - 1][S // 2]

print((count_all - 3 * count_invalid) % M)


### FIXED CODE ###

import numpy as np

N = int(input())
numbers = [int(input()) for _ in range(N)]

M = 998244353
count_all = (3 ** N - 3 * (2 ** N - 2) - 3) % M

S = sum(numbers)
count3 = np.zeros((N, S + 1), dtype=np.int64)
count3[0, 0] = 2
count3[0, numbers[0]] = 1
count2 = np.zeros((N, S + 1), dtype=np.int64)
count2[0, 0] = 1
count2[0, numbers[0]] = 1

for i in range(1, N):
    count3[i, numbers[i]:] += count3[i - 1, :-numbers[i]]
    count3[i, :] += 2 * count3[i - 1, :]
    count3[i, :] %= M
    count2[i, numbers[i]:] += count2[i - 1, :-numbers[i]]
    count2[i, :] += count2[i - 1, :]
    count2[i, :] %= M

invalid_from = S // 2 + 1
if (S % 2 == 0):
  invalid_from = S // 2
count_invalid = np.sum(count3[N - 1, invalid_from:-1]) - 2 * np.sum(count2[N - 1, invalid_from:-1])
count_invalid %= M

print((count_all - 3 * count_invalid) % M)
### BUGGY CODE ###

from collections import deque


def main():

    h, w = map(int, input().split())
    a = ["#" * (w + 2)] + ["#" + input() + "#" for _ in range(h)] + ["#" * (w + 2)]

    d = [[-1] * (w + 2) for _ in range(h + 2)]

    def bfs():
        q = deque()
        for i in range(1, h + 1):
            for j in range(1, w + 1):
                if a[i][j] == "#":
                    q.append((j, i))
                    d[i][j] = 0

        dxy = (1, 0), (-1, 0), (0, 1), (0, -1)

        ans = 0
        while q:
            ux, uy = q.popleft()
            for dx, dy in dxy:
                vx = ux + dx
                vy = uy + dy
                if a[vy][vx] == "." and d[vy][vx] == -1:
                    d[vy][vx] = d[uy][ux] + 1
                    ans = max(ans, d[vy][vx])
                    q.append((vx, vy))

        return ans

    ans = bfs()
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from scipy.ndimage import distance_transform_cdt


def main():
    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]

    sq = [[1 if e == "." else 0 for e in row] for row in a]

    cnt = distance_transform_cdt(sq, metric="taxicab")

    print(cnt.max())


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

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

ans=0
while True:
  if n<=0 or m<=2:
    break
  n-=1
  m-=2
  ans+=1
print(ans+m//4)


### FIXED CODE ###

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

if n*2>=m:
  print(m//2)
else:
  print(n+(m-2*n)//4)
### BUGGY CODE ###

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

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

Swap=["" for i in range(M)]

for i in range(M):
    Swap[i]=set(map(int,input().split()))


Y=[set() for i in range(N)]
Unstacked=[1 for i in range(M)]

Y[0]=Y[0]|Swap[0]
Unstacked[0]=0
j=0
k=0

while True:
    while j<M:
        if Unstacked[j]==0:
            j+=1
            continue

        if Y[k] & Swap[j] !=set():

            Y[k]=Y[k]|Swap[j]
            Unstacked[j]=0
            j=0
            #print(Y,j,Unstacked)

        elif j <M-2:
            j+=1

        else: break

    if 1 in Unstacked:
        
        k+=1
        Y[k]=Swap[Unstacked.index(1)]
        j=0

    else:
        break


#print(Y,j,k,Unstacked)

Other=set(range(1,N+1))
for l in range(k+1):
    Other=Other - Y[l]
    #print(l,Y,Other)

#print(Other)

Other=list(Other)

count=0

for i in range(k+1):
    for j in list(Y[i]):
        if P[j-1] in Y[i]:
            #print(i,j,P[j-1],Y[i])
            count+=1
        

for m in Other:
    if P[m-1]==m:
        #print(m)
        count+=1

print(count)
        
        



### FIXED CODE ###

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

Group=[i for i in range(N+1)]


Swap=[None]*M
for i in range(M):
    Swap[i]=sorted(map(int,input().split()))

def find(x):
    while Group[x] != x:
        x=Group[x]
    return x

for i in range(M):
    if find(Swap[i][1]) != find(Swap[i][0]):
        Group[find(Swap[i][1])]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[find(Swap[i][0])]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[Swap[i][1]]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[Swap[i][1]]=min(find(Swap[i][1]),find(Swap[i][0]))

count=0

for i in range(N):
    if find(P[i])==find(i+1):
        count+=1


print(count)
### BUGGY CODE ###

N = int(input())
A_list = [int(elem) for elem in input().split(' ')]
assert N >= 4
assert len(A_list) == N

# cummulative sum
cuml_A_list = [0] * N
cuml_A_list[0] = A_list[0]
for i in range(1, N):
    cuml_A_list[i] = cuml_A_list[i-1] + A_list[i]
 
# initialize
best_diff = max(cuml_A_list[0], cuml_A_list[1]-cuml_A_list[0], cuml_A_list[2]-cuml_A_list[1], cuml_A_list[-1]-cuml_A_list[2])\
        - min(cuml_A_list[0], cuml_A_list[1]-cuml_A_list[0], cuml_A_list[2]-cuml_A_list[1], cuml_A_list[-1]-cuml_A_list[2])

for mid_sep in range(2, N - 1):
    left_sum = cuml_A_list[mid_sep - 1]
    right_sum = cuml_A_list[-1] - cuml_A_list[mid_sep - 1]
    left_sep = 0
    right_sep = mid_sep + 1
    for left_sep_cand in range(0, mid_sep):
        # obtain the best first separation position
        if abs(cuml_A_list[mid_sep] - 2*cuml_A_list[left_sep_cand]) < abs(cuml_A_list[mid_sep] - 2*cuml_A_list[left_sep]):
            left_sep = left_sep_cand
    for right_sep_cand in range(mid_sep, N):
        # obtain the best third separation position
        if abs(cuml_A_list[-1] - cuml_A_list[right_sep_cand] - (cuml_A_list[right_sep_cand] - cuml_A_list[mid_sep]))\
            < abs(cuml_A_list[-1] - cuml_A_list[right_sep] - (cuml_A_list[right_sep] - cuml_A_list[mid_sep])):
            right_sep = right_sep_cand
    diff = max(cuml_A_list[left_sep], cuml_A_list[mid_sep] - cuml_A_list[left_sep], cuml_A_list[right_sep] - cuml_A_list[mid_sep], cuml_A_list[-1] - cuml_A_list[right_sep])\
        - min(cuml_A_list[left_sep], cuml_A_list[mid_sep] - cuml_A_list[left_sep], cuml_A_list[right_sep] - cuml_A_list[mid_sep], cuml_A_list[-1] - cuml_A_list[right_sep])
    best_diff = min(best_diff, diff)
print(best_diff)


### FIXED CODE ###

N = int(input())
A_list = [int(elem) for elem in input().split(' ')]
assert N >= 4
assert len(A_list) == N

# cummulative sum
cuml_A_list = [0] * N
cuml_A_list[0] = A_list[0]
for i in range(1, N):
    cuml_A_list[i] = cuml_A_list[i-1] + A_list[i]

best_diff = max(cuml_A_list[0], cuml_A_list[1]-cuml_A_list[0], cuml_A_list[2]-cuml_A_list[1], cuml_A_list[-1]-cuml_A_list[2])\
        - min(cuml_A_list[0], cuml_A_list[1]-cuml_A_list[0], cuml_A_list[2]-cuml_A_list[1], cuml_A_list[-1]-cuml_A_list[2])

left_sep = 0
right_sep = 2

# time complexity: O(N)
for mid_sep in range(1, N - 2):
    left_sum = cuml_A_list[mid_sep - 1]
    right_sum = cuml_A_list[-1] - cuml_A_list[mid_sep - 1]

    while abs(cuml_A_list[mid_sep] - 2*cuml_A_list[left_sep]) > abs(cuml_A_list[mid_sep] - 2*cuml_A_list[left_sep + 1]):
        left_sep += 1
    while abs(cuml_A_list[-1] - 2*cuml_A_list[right_sep] + cuml_A_list[mid_sep]) > abs(cuml_A_list[-1] - 2*cuml_A_list[right_sep + 1] + cuml_A_list[mid_sep]):
        right_sep += 1
    diff = max(cuml_A_list[left_sep], cuml_A_list[mid_sep] - cuml_A_list[left_sep], cuml_A_list[right_sep] - cuml_A_list[mid_sep], cuml_A_list[-1] - cuml_A_list[right_sep])\
        - min(cuml_A_list[left_sep], cuml_A_list[mid_sep] - cuml_A_list[left_sep], cuml_A_list[right_sep] - cuml_A_list[mid_sep], cuml_A_list[-1] - cuml_A_list[right_sep])
    best_diff = min(best_diff, diff)
print(best_diff)
### BUGGY CODE ###

import numpy as np 

H,W = map(int,input().split())
S = np.array([[[0,1][i == '.'] for i in input()] for _ in range(H)])

funcA = np.frompyfunc(lambda x,y:y and x+y,2,1)
funcB = np.frompyfunc(lambda x,y:[y,x][(y and x and 1)],2,1)
Hor = funcA.accumulate(S,dtype=np.object,axis=1).astype(np.int)[:,::-1]
Hor = funcB.accumulate(Hor,dtype=np.object,axis=1).astype(np.int)[:,::-1]
Ver = funcA.accumulate(S,dtype=np.object,axis=0).astype(np.int)[::-1,:]
Ver = funcB.accumulate(Ver,dtype=np.object,axis=0).astype(np.int)[::-1,:]
print(np.max(Hor+Ver-1))

### FIXED CODE ###

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

def aaa(s):
    i = 0
    l = len(s)
    o = []
    while True:
        if i == l:
            break
        if s[i] == ".":
            n = 0
            while i < l and s[i] == '.':
                i += 1
                n += 1
            o += [n] * n
        else:
            o += [0]
            i += 1
    return o

Hor = [0]*H
y = 0
while y != H:
    Hor[y] = aaa(S[y])
    y += 1

Ver = [0]*W
x = 0
while x != W:
    _ = 0
    s = [0] * H
    while _ != H:
        s[_] = S[_][x]
        _ += 1
    Ver[x] = aaa(s)
    x += 1

ans = 1
x = 0
while x != W:
    y = 0
    while y != H:
        h = Hor[y][x]
        if h:
            v = Ver[x][y]
            ans = max(ans,h+v-1)
        y += 1
    x += 1

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

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
BC = [list(map(int, input().split())) for _ in range(Q)]

for i in range(Q):
    p, n = BC[i][0], BC[i][1]
    A = [x if x != p else n for x in A]
    print(sum(A))

### FIXED CODE ###

import time
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
BC = [list(map(int, input().split())) for _ in range(Q)]

num = [0] * 100010
for i in A:
    num[i] += 1
s = sum(A)

for i in range(Q):
    p, n = BC[i][0], BC[i][1]
    s += (n - p) * num[p]
    num[n] += num[p]
    num[p] = 0
    print(s)
### BUGGY CODE ###

import collections
H,W,M=map(int,input().split())
h=[None]*M
w=[None]*M
for i in range(M):
    h[i],w[i]=map(int,input().split())
c1=collections.Counter(h)
c2=collections.Counter(w)
cnt=0
ans=0
for i in range(min(len(c1),20)):
    for j in range(min(len(c2),20)):
        for x in range(M):
            flag=True
            if h[x]==c1.most_common()[i][0] and w[x]==c2.most_common()[j][0]:
                ans=max(ans,c1.most_common()[i][1]+c2.most_common()[j][1]-1)
                flag=False
                break
        if flag:
            ans=max(ans,c1.most_common()[i][1]+c2.most_common()[j][1])
print(ans)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H, W, M = map(int, readline().split())
bomb = [tuple(map(lambda x: int(x) - 1, s.split())) for s in readlines()]
X = [0] * H 
Y = [0] * W 
for h, w in bomb:
    X[h] += 1
    Y[w] += 1
maxX = max(X)
maxY = max(Y)

R = [h for h, x in enumerate(X) if x == maxX]  
C = [w for w, y in enumerate(Y) if y == maxY] 

bomb = set(bomb)
for r in R:
    for c in C:
        if (r, c) not in bomb:
            print(maxX + maxY)
            exit()
print(maxX + maxY - 1)