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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N,M = list(map(int,input().split()))
uf = UnionFind(N)
p = list(map(int,input().split()))
L = []
for i in range(M):
    x,y = map(int,input().split())
    uf.union(x - 1,y - 1)
cnt = 0
for x in uf.all_group_members().values():
    tmp = set()
    for y in x:
        tmp.add(p[y]-1)
    for y in x:
        if y in tmp:
            cnt+=1
print(cnt)



### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return {i for i in range(self.n) if self.find(i) == root}

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N,M = list(map(int,input().split()))
uf = UnionFind(N)
p = list(map(int,input().split()))
L = []
for i in range(M):
    x,y = map(int,input().split())
    uf.union(x - 1,y - 1)
cnt = 0
for i in range(N):
    if uf.same(i,p[i]-1):
        cnt+=1
print(cnt)
### BUGGY CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    S = readline().strip()
    N = len(S)

    A = list(range(N))
    for _ in range(10):
        for i, a in enumerate(A):
            if S[a] == 'L':
                A[i] -= 1
            else:
                A[i] += 1

    B = A
    for _ in range(99):
        A, B = B, list(range(N))
        for _ in range(10):
            for i, b in enumerate(B):
                B[i] = A[b]

    ans = [0] * N
    for b in B:
        ans[b] += 1

    print(*ans)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    S = readline().strip()
    N = len(S)

    A = list(range(N))
    for _ in range(10):
        for i, a in enumerate(A):
            if S[a] == 'L':
                A[i] -= 1
            else:
                A[i] += 1

    B = A
    for _ in range(99):
        A, B = B, list(range(N))
        for _ in range(10):
            for i, b in enumerate(B):
                B[i] = A[b]

    ans = [0] * N
    for b in B:
        ans[b] += 1

    print(*ans)
    return


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

N = int(input())
k = []
for i in range(N):
  A = input()
  if A in k:
    k.remove(A)
  else:
    k.append(A)
print(len(k))

### FIXED CODE ###

import collections
N = int(input())
ans = 0
now = 0
k = []
for i in range(N):
  A = int(input())
  k.append(A)
p = collections.Counter(k)
for i in p:
  if p[i]%2 == 1:
    ans += 1
print(ans)
### BUGGY CODE ###

N = int(input())
s = input()

for bit in range(4):
    animal = [-1] * N
    animal[0] = bit % 2
    animal[1] = bit // 2
    for i in range(1, N-1):
        if (animal[i] == 0) ^ (s[i] == 'o'):
            animal[i+1] = 1 - animal[i-1]
        else:
            animal[i+1] = animal[i-1]
    ok = True
    if animal[-1] == 0:
        if (s[-1] == 'o') ^ (animal[-2] == animal[0]):
            ok = False
    if animal[-1] == 1:
        if (s[-1] == 'o') ^ (animal[-2] != animal[0]):
            ok = False
    if animal[0] == 0:
        if (s[0] == 'o') ^ (animal[-1] == animal[1]):
            ok = False
    if animal[0] == 1:
        if (s[0] == 'o') ^ (animal[-1] != animal[1]):
            ok = False
    if ok:
        ans = ''
        for i in range(N):
            ans += 'S' if animal[i] == 0 else 'W'
        print(ans)
        exit()
print(-1)


### FIXED CODE ###

N = int(input())
s = input()

for bit in range(4):
    animal = [-1] * N
    animal[0] = bit % 2
    animal[1] = bit // 2
    for i in range(1, N-1):
        if (animal[i] == 0) ^ (s[i] == 'o'):
            animal[i+1] = 1 - animal[i-1]
        else:
            animal[i+1] = animal[i-1]
    ok = True
    if animal[-1] == 0:
        if (s[-1] == 'o') ^ (animal[-2] == animal[0]):
            ok = False
    if animal[-1] == 1:
        if (s[-1] == 'o') ^ (animal[-2] != animal[0]):
            ok = False
    if animal[0] == 0:
        if (s[0] == 'o') ^ (animal[-1] == animal[1]):
            ok = False
    if animal[0] == 1:
        if (s[0] == 'o') ^ (animal[-1] != animal[1]):
            ok = False
    if ok:
        ans = ''
        for i in range(N):
            ans += 'S' if animal[i] == 0 else 'W'
        print(ans)
        exit()
print(-1)
### BUGGY CODE ###

from collections import deque

n,q = map(int, input().split())
tree = [[int(i) for i in input().split()] for i in range(n-1)] 
px = [[int(i) for i in input().split()] for i in range(q)] 
A = [set() for i in range(n)]
B = [set() for i in range(n)]
C = [set() for i in range(n)]
flag = [False] * n

for i,a in enumerate(tree):
  A[a[1]-1].add(tree[i][0])
  B[a[0]-1].add(tree[i][1])

for i in range(n):
  C[i] = A[i] | B[i]

ans = [0] * n

for i in px:

  ans[i[0]-1] += i[1]
  
cr = deque()
cr.append(1)
flag[0] = True

while cr:
  c = cr.popleft()
  flag[c-1] = True
  for i in C[c-1]:
    if flag[i-1]:
      continue
    else:
      cr.append(i)
      ans[i-1] += ans[c-1]
print(*ans)

### FIXED CODE ###

from collections import deque
import sys
def input():
   return sys.stdin.readline()[:-1]
  
n,q = map(int, input().split())
tree = [[int(i) for i in input().split()] for i in range(n-1)] 
px = [[int(i) for i in input().split()] for i in range(q)] 
A = [set() for i in range(n)]
B = [set() for i in range(n)]
C = [set() for i in range(n)]
flag = [False] * n

for i,a in enumerate(tree):
  A[a[1]-1].add(tree[i][0])
  B[a[0]-1].add(tree[i][1])

for i in range(n):
  C[i] = A[i] | B[i]

ans = [0] * n

for i in px:

  ans[i[0]-1] += i[1]
  
cr = deque()
cr.append(1)
flag[0] = True

while cr:
  c = cr.popleft()
  flag[c-1] = True
  for i in C[c-1]:
    if flag[i-1]:
      continue
    else:
      cr.append(i)
      ans[i-1] += ans[c-1]
print(*ans)
### BUGGY CODE ###

X,Y,Z,K=map(int,input().split())
x=list(map(int,input().split()))
y=list(map(int,input().split()))
z=list(map(int,input().split()))

L=[]
for xx in x:
  for yy in y:
    L.append(yy+xx)
L=sorted(L,reverse=True)

if K > X*Y:
  LL=[]
  for l in L:
    for zz in z:
      LL.append(l+zz)
  [print(i) for i in sorted(LL,reverse=True)]   
else:
  LL=[]
  for l in L[:K]:
    for zz in z:
      LL.append(l+zz)
  LL=sorted(LL,reverse=True)
  for k,ll in zip(range(K),LL):
    print(ll)
    

### FIXED CODE ###

X,Y,Z,K=map(int,input().split())
x=list(map(int,input().split()))
y=list(map(int,input().split()))
z=list(map(int,input().split()))

L=[xx+yy for xx in x for yy in y ]
L=sorted(L,reverse=True)

if K > X*Y:
  LL=[l+zz for l in L for zz in z]
  [print(i) for i in sorted(LL,reverse=True)]   
else:
  LL=[l+zz for l in L[:K] for zz in z]
  LL=sorted(LL,reverse=True)
  [print(ll) for k,ll in zip(range(K),LL)]
### BUGGY CODE ###

from bisect import bisect
n=int(input())
p=list(map(int,input().split()))
data=[0]*(n+1)
for i in range(n):
    data[p[i]]=i+1
lst=[data[n]]
ans=0
if data[n-1]>data[n]:
    lst.append(data[n-1])
    ans+=(lst[0]*(n-lst[1]+1))*(n-1)
else:
    lst=[data[n-1]]+lst
    ans+=(lst[0]*(n-lst[1]+1))*(n-1)
lst.append(n+1)
lst=[0]+lst
for i in range(2,n):
    h=data[n-i]
    y=bisect(lst,h)
    if y==1:
        ans+=(h*(lst[2]-lst[1]))*(n-i)
        lst=[lst[0]]+[h]+lst[1:]
    elif y==len(lst)-1:
        ans+=((n-h+1)*(lst[-2]-lst[-3]))*(n-i)
        lst=lst[:(len(lst)-1)]+[h]+[lst[-1]]
    else:
        ans+=((lst[y+1]-lst[y])*(h-lst[y-1])+(lst[y]-h)*(lst[y-1]-lst[y-2]))*(n-i)
        lst=lst[:y]+[h]+lst[y:]
print(ans)

### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
f=[0]*(n+1)
for i in range(n):
    f[p[i]]=i+1
l=[0]+[i for i in range(n+1)]
r=[i+1 for i in range(n+1)]+[n+1]
ans=0
for i in range(1,n+1):
    x=f[i]
    l1,r1=l[x],r[x]
    l2,r2=l[l1],r[r1]
    ans+=i*((l1-l2)*(r1-x)+(x-l1)*(r2-r1))
    l[r1],r[l1]=l1,r1
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int,input().split()))
q = [(x+1)/2 for x in p]
arr = []

for i in range(n-k+1):
  arr.append(sum(q[i:i+k]))
  
print(max(arr))

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int,input().split()))
q = [(x+1)/2 for x in p]
q1 = sum(q[:k])
ans = q1

for i in range(n-k):
  x = q1-q[i] +q[i+k]
  q1 = x
  if ans < x:
    ans = x
  
print(ans)
### BUGGY CODE ###

from bisect import bisect_left,bisect_right
import string 

dic = {c:[] for c in string.ascii_lowercase}

n = int(input())
s = list(input())
q = int(input())

for i,c in enumerate(s,start=1):
  dic[c].append(i)
  
for i in range(q):
  p,l,r = map(str,input().split())
  if p =='1':
    j = int(l)
    c = s[j-1]
    dic[c].pop(bisect_left(dic[c],j))
    dic[r].insert(bisect_left(dic[r],j),j)
    s[j-1] = r
  else:
    ans = 0
    l = int(l)
    r = int(r)
    for c in dic.keys():
      pl = bisect_left(dic[c],l)
      if pl < len(dic[c]):
        if dic[c][pl] <= r:
          ans += 1
    print(ans)

### FIXED CODE ###

from bisect import bisect_left,bisect_right
import string 

dic = {c:[] for c in string.ascii_lowercase}

n = int(input())
s = list(input())
q = int(input())

for i,c in enumerate(s,start=1):
  dic[c].append(i)
  
for i in range(q):
  p,l,r = map(str,input().split())
  if p =='1':
    j = int(l)
    if r == s[j-1]:
      continue
    c = s[j-1]    
    dic[c].pop(bisect_left(dic[c],j))
    dic[r].insert(bisect_left(dic[r],j),j)
    s[j-1] = r
  else:
    ans = 0
    l = int(l)
    r = int(r)
    for c in string.ascii_lowercase:
      pl = bisect_left(dic[c],l)
      if pl < len(dic[c]):
        if dic[c][pl] <= r:
          ans += 1
    print(ans)
### BUGGY CODE ###

N = input()
a = 0
n = len(N)
NN = int(N)
for i in range(n):
    a += NN%10
    NN = NN//10
if a%9 == 0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

N = list(input())
for i in range(len(N)):
    N[i] = int(N[i])
if sum(N)%9 == 0:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

x=int(input())
for i in range(-1000,1000):
    for j in range(-1000,1000):
        if i**5-j**5==x:
            print("{} {}".format(i,j))
            break

### FIXED CODE ###

x=int(input())
for i in range(0,1000):
    for j in range(-1000,1000):
        if i**5-j**5==x:
            print("{} {}".format(i,j))
            exit(0)
### BUGGY CODE ###

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

dp = [(i + M[0][0] - 1) // M[0][0] * M[0][1] for i in range(H + 1)]
for i in range(N):
    Ai, Bi = M[i]
    ndp = [0] * (H + 1)
    if Ai >= H:
        ndp[0:H + 1] = [min(dp[j], Bi) for j in range(H + 1)]
    else:
        ndp[0:Ai + 1] = [min(dp[j], Bi) for j in range(Ai + 1)]
        for j in range(Ai + 1, H + 1):
            ndp[j] = min(dp[j], ndp[j - Ai] + Bi)
    dp = ndp
print(dp[H])


### FIXED CODE ###

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

dp = [(j + M[0][0] - 1) // M[0][0] * M[0][1] for j in range(H + 1)]
for i in range(1, N):
    Ai, Bi = M[i]
    ndp = [0] * (H + 1)
    if Ai >= H:
        ndp[0:H + 1] = [min(dp[j], Bi) for j in range(H + 1)]
    else:
        ndp[0:Ai + 1] = [min(dp[j], Bi) for j in range(Ai + 1)]
        for j in range(Ai + 1, H + 1):
            ndp[j] = min(dp[j], ndp[j - Ai] + Bi)
    dp = ndp
print(dp[H])
### BUGGY CODE ###

n,m = map(int, input().split())
a = [int(_) for _ in input().split()]

for i in range(m):
    a.sort()
    b,c = map(int, input().split())
    a = [c if j < c else j for j in a[:b]] + a[b:]
    
print(sum(a))

### FIXED CODE ###

from heapq import heappop, heappush


n,m = map(int,input().split())
A = list(map(int,input().split()))
pq = []
ans = 0

for a in A:
    heappush(pq, [-a, 1])
    
for _ in range(m):
    b,c = map(int,input().split())
    heappush(pq, [-c, b])

for i in range(n):
    c,b = heappop(pq)
    c = -c
    ans += c
    if b > 1:
        b -= 1
        heappush(pq, [-c, b])
        
print(ans)
### BUGGY CODE ###

n = int(input())
As = list(map(int, input().split()))
q = int(input())
Ds = [0] * (10 ** 5 + 1)
for a in As:
  Ds[a] += 1
for i in range(q):
  b, c = map(int, input().split())
  Ds[c] += Ds[b]
  Ds[b] = 0
  ans = 0
  for x, i in enumerate(Ds):
    ans += x * i
  print(ans)

### FIXED CODE ###

n = int(input())
As = list(map(int, input().split()))
q = int(input())
Ds = [0] * (10 ** 5 + 1)
Es = [i for i in range(10 ** 5 + 1)]
for a in As:
  Ds[a] += 1
ans = sum(As)
for i in range(q):
  b, c = map(int, input().split())
  ans += Ds[b] * (c-b)
  Ds[c] += Ds[b]
  Ds[b] = 0
  print(ans)
### BUGGY CODE ###

import sys
 
sys.setrecursionlimit(10 ** 6)

N,Q = map(int,input().split())
K = [[] for _ in range(N+1)]
nums = [0 for _ in range(N+1)]

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

for _ in range(Q):
    p, x = map(int, input().split())
    nums[p] += x

def dfs(now,parent):
    for i in K[now]:
        if i != parent:
            nums[i] += nums[now]
            dfs(i,now)

dfs(1,0)
print(*nums[1:])

### FIXED CODE ###

import sys
 
sys.setrecursionlimit(10 ** 6)

def input():
    return sys.stdin.readline().strip()
def main():
    N,Q = map(int,input().split())
    K = [[] for _ in range(N+1)]
    nums = [0 for _ in range(N+1)]

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

    for _ in range(Q):
        p, x = map(int, input().split())
        nums[p] += x

    def dfs(now,parent):
        for i in K[now]:
            if i != parent:
                nums[i] += nums[now]
                dfs(i,now)

    dfs(1,0)
    print(*nums[1:])

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

input()
a = list(map(int, input().split()))
c = []
b = [i for i in a if i in c or c.append(i)]
print(len(c) if len(b) % 2 == 0 else len(c)-1)

### FIXED CODE ###

input()
a = list(map(int, input().split()))
c = {}
lb = lc = 0
for i in a:
  try:
    c[i] += 1
    lb += 1
  except:
    c[i] = 1
    lc += 1
print(lc if lb % 2 == 0 else lc-1)
### BUGGY CODE ###

N, M = map(int, input().split())
tmp = input().split(' ')
H = []
for i in range(N):
    H = H + [int(tmp[i])]

A = []
B = []
for i in range(M):
    ta, tb = map(int, input().split())
    A = A + [ta]
    B = B + [tb]

ans = [1]*N
# v: 1ならいい展望台、0なら良くない展望台 
for i in range(M):
    if H[A[i]-1] > H[B[i]-1]:
        ans[B[i]-1] = 0
    elif H[A[i]-1] < H[B[i]-1]:
        ans[A[i]-1] = 0
    elif H[A[i]-1] == H[B[i]-1]:
        ans[A[i]-1] = 0
        ans[B[i]-1] = 0

print(sum(ans))

### FIXED CODE ###

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

A = [0]*M
B = [0]*M
for i in range(M):
    ta, tb = map(int, input().split())
    A[i] = ta - 1
    B[i] = tb - 1

ans = [True]*N
# v: Trueならいい展望台、Falseなら良くない展望台 
for i in range(M):
    ans[A[i]] = H[A[i]] > H[B[i]] and ans[A[i]]
    ans[B[i]] = H[B[i]] > H[A[i]] and ans[B[i]]

print(ans.count(True))
### BUGGY CODE ###

a,b=map(int,input().split())
s=input()
for i in range(b):
    c,d=map(int,input().split())
    print(s[c-1:d].count("AC"))

### FIXED CODE ###

from itertools import*
a,b=map(int,input().split())
s=input()
table=[0]*(a-1)
for i in range(a-1):
    if s[i:i+2]=="AC":
        table[i]=1
x=[0]+list(accumulate(table))
for i in range(b):
    c,d=map(int,input().split())
    print(x[d-1]-x[c-1])
### BUGGY CODE ###

from collections import Counter
n = int(input())
a_input = list(map(int,input().split()))

a_count = Counter(a_input)

score_li = [0]*len(a_count)
exclude_li = [0]*len(a_count)

for i,(k,v) in enumerate(a_count.items()):
    score_li[i]=v*(v-1)//2
    exclude_li[i]=(v-1)*(v-2)//2

score_sum = sum(score_li)

for i in range(n):
    for j,(k,v) in enumerate(a_count.items()):
        if a_input[i]==k:
            print(score_sum-score_li[j]+exclude_li[j])
            break

### FIXED CODE ###

from collections import Counter
n = int(input())
a_input = list(map(int,input().split()))

a_count = Counter(a_input)

score_dic={}
exclude_dic={}

for k,v in a_count.items():
    score_dic[k]=v*(v-1)//2
    exclude_dic[k]=(v-1)*(v-2)//2

score_sum = sum(score_dic.values())

for i in range(n):
    print(score_sum-score_dic[a_input[i]]+exclude_dic[a_input[i]])
### BUGGY CODE ###

import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
sys.setrecursionlimit(10**7)

def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    N = I()
    P = LI()
    ans = 0
    for i in range(N):
        if min(P[:i+1])>=P[i]:
            ans += 1
    print(ans)

main()



### FIXED CODE ###

import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
sys.setrecursionlimit(10**7)

def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    N = I()
    P = LI()
    ans = 0
    min_num = P[0]
    for i in range(N):
        if min_num>=P[i]:
            ans += 1
            min_num = P[i]

    print(ans)

main()
### BUGGY CODE ###

def sum_each_num(n):
    sum = 0
    while n > 0:
        sum += n % 10
        n = n // 10
    return sum

def main():
    n = int(input())
    sum = sum_each_num(n)
    if n % 9 == 0:
        print("Yes")
    else:
        print("No")

if __name__ == '__main__':
    main()


### FIXED CODE ###

n = int(input())
if n % 9 == 0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())

maze = [list(input()) for i in range(h)]
ans = [[-1]*w for i in range(h)]

dx=[0,1,0,-1]
dy=[1,0,-1,0]
count=0
#niko(x,y,ans[y][x]+1)とする。
def niko(x,y,k,ans):
  for i in range(x-2,x+2):
    for j in range(y-2,y+2):
      if 0<=i<w and 0<=j<h:
        if maze[j][i]=="." and (ans[j][i]>k or ans[j][i]==-1):
          ans[j][i]=k
  return ans
ans[ch-1][cw-1]=0
def bfs(ans):
  qu = deque([])
  qu.append([cw-1,ch-1])
  while qu:
    zahyou=qu.popleft()
    x=zahyou[0]
    y=zahyou[1]
    for i in range(4):
      if 0 <= x+dx[i] < w and 0 <= y+dy[i] < h:
        if maze[y+dy[i]][x+dx[i]]=="." and (ans[y+dy[i]][x+dx[i]]>ans[y][x] or ans[y+dy[i]][x+dx[i]]==-1):
          qu.append([x+dx[i],y+dy[i]])
          ans[y+dy[i]][x+dx[i]] = ans[y][x]

    for i in range(x-2,x+3):
      for j in range(y-2,y+3):
        if 0<=i<w and 0<=j<h:
          if maze[j][i]=="." and (ans[j][i]>ans[y][x]+1 or ans[j][i]==-1):
            ans[j][i]=(ans[y][x]+1)
            qu.append([i,j])

bfs(ans)
print(ans[dh-1][dw-1])
#for i in ans:
#  print(*i)
  

### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())

maze = [list(input()) for i in range(h)]
ans = [[-1]*w for i in range(h)]

dx=[0,1,0,-1]
dy=[1,0,-1,0]

ans[ch-1][cw-1]=0
def bfs(ans):
  qu = deque([])
  qu.append([cw-1,ch-1])
  while qu:
    zahyou=qu.popleft()
    x=zahyou[0]
    y=zahyou[1]
    count=0
    for i in range(4):
      if 0 <= x+dx[i] < w and 0 <= y+dy[i] < h:
        if maze[y+dy[i]][x+dx[i]]=="." and (ans[y+dy[i]][x+dx[i]]>ans[y][x] or ans[y+dy[i]][x+dx[i]]==-1):
          qu.appendleft([x+dx[i],y+dy[i]])
          ans[y+dy[i]][x+dx[i]] = ans[y][x]
          count+=1
    if count!=4:
      for i in range(x-2,x+3):
        for j in range(y-2,y+3):
          if 0<=i<w and 0<=j<h:
            if maze[j][i]=="." and (ans[j][i]>ans[y][x]+1 or ans[j][i]==-1):
              ans[j][i]=(ans[y][x]+1)
              qu.append([i,j])

bfs(ans)
print(ans[dh-1][dw-1])
### BUGGY CODE ###

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

M = [0]*N
total = sum(A)
sub = 0
for i in range((N-1)//2):
    sub += A[2*i + 1]
# print(total, sub)
M[0] = total - 2 * sub
for i in range(1, N):
    M[i] = 2 * A[i - 1] - M[i - 1]
# print(M)
ans = ""
for m in M:
    ans += str(m) + " "
print(ans[0:-1])


### FIXED CODE ###

N = int(input())

# A = list(map(int, input().split()))
# print(N, A)
A = []
l = input().split()
total = 0
sub = 0
for i in range(len(l)):
    v = int(l[i])
    A.append(v)
    total += v
    if i % 2 == 1:
        sub += v

M = [0]*N
# total = sum(A)
# sub = 0
# for i in range((N-1)//2):
#     sub += A[2*i + 1]
# print(total, sub)
M[0] = total - 2 * sub
for i in range(1, N):
    m = 2 * A[i - 1] - M[i - 1]
    M[i] = m
# print(M)
ans = " ".join(map(str, M))
print(ans)
### BUGGY CODE ###

def Q3(x):
    N = x[0][0]
    lst = x[1][:]
    absolute = float('inf')
    for k in range(1, N):
        sunuke = sum(lst[:k])
        arai = sum(lst[k:])
        a = abs(sunuke - arai)
        if a < absolute:
            absolute = a
    return absolute

l = [int(i) for i in input().split()]
m = [int(i) for i in input().split()]
n = [l,m]
print(Q3(n))

### FIXED CODE ###

def Q3(x):
    N = x[0][0]
    lst = x[1][:]
    s = lst[0]
    allsum = sum(lst)
    minimum = abs(allsum - s * 2)
    
    for k in range(1, N - 1):
        s += lst[k]
        a = abs(allsum - s * 2)
        minimum = min(minimum, a)
    return minimum

l = [int(i) for i in input().split()]
m = [int(i) for i in input().split()]
n = [l,m]
print(Q3(n))
### BUGGY CODE ###

n,m = map(int,input().split())
job = [list() for _ in range(m)]
total = 0
l = list()
for _ in range(n):
    a,b = map(int,input().split())
    if a <= m :
        job[a-1].append(b)
for i in range(m):
    l += job[i]
    if l != []:
        l.sort(reverse = True)
        total += l.pop(0)
print(total)


### FIXED CODE ###

import heapq
job = list()
salary = list()
n,m = map(int,input().split())

for i in range(n):
    a,b = map(int,input().split())
    job.append((a,b))

job.sort(reverse = True)

for x in job:
    s,t = x
    heapq.heappush(salary,t)
    if s - m > 0:
        heapq.heappop(salary)
    else:
        m -= 1

print(sum(salary))