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

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

for i in range(Q):
    B,C = (int(x) for x in input().split())

    for j in range(N):

        try:
            idx = A.index(B)
            if(idx>-1):
                #if A[j]==B:
                #    A[j]=C
                A[idx]=C
        except ValueError:
            break
    
    print(sum(A))


### FIXED CODE ###

# 371 ms, 27032 KB
n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = []
c = []
 
bc = [map(int, input().split()) for _ in range(q)]
b, c = [list(i) for i in zip(*bc)]
 
dic = {}
for aa in a:
    dic[aa] = dic.get(aa, 0) + 1
 
s = sum(a)
for i in range(q):
    if b[i] not in dic:
        print (str(s))
        continue
    s += (c[i]-b[i]) * dic[b[i]]
    dic[c[i]] = dic.get(c[i], 0) + dic[b[i]]
    del dic[b[i]]
    print(s)
### BUGGY CODE ###

n=int(input())
L=[sorted(list(input()))for i in range(n)]
x=0
while L!=[]:
    a=L.count(L[0])
    if a!=1:
        x+=a*(a-1)//2
    L=[l for l in L if l!=L[0]]
print(x)

### FIXED CODE ###

import collections
n=int(input())
L=["".join(sorted(input()))for _ in range(n)]
C=collections.Counter(L)
a=0
for i in set(L):
    n=C[i]
    a+=n*(n-1)//2
print(a)
### BUGGY CODE ###

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

ans = 0
for i in A:
    if ans != 0:
        ans = ans * i
    else:
        ans = i

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

### FIXED CODE ###

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

A.sort()
ans = 0

if A[0] == 0:
    print(ans)
    exit()

for i in A:
    if ans != 0:
        ans = ans * i
    else:
        ans = i
    if ans > 1000000000000000000:
        print("-1")
        exit()

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

n=int(input())
A=list(map(int,input().split()))
s=[0]
for i in range(n):
    s.append(s[-1]+A[i])
cnt=[]
S=set(s)
for i in S:
    cnt.append(s.count(i))
ans=0
for i in cnt:
    if 1<i:
        ans+=i*(i-1)//2
print(ans)


### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
s=[0]
for i in range(n):
    s.append(s[-1]+A[i])
s.sort()
ans=0
cnt=1
for i in range(1,n+1):
    if s[i-1]==s[i]:
        cnt+=1
    else:
        if 2<=cnt:
            ans+=(cnt*(cnt-1))//2
            cnt=1
        else:
            cnt=1
if 2<=cnt:
    ans+=(cnt*(cnt-1))//2
print(ans)
### BUGGY CODE ###

import sys

input = sys.stdin.readline


def dot(a, b):
    c = [[0] * n for _ in range(n)]
    for i, ai in enumerate(a):
        for j, bj in enumerate(zip(*b)):
            ck = 0
            for ak, bk in zip(ai, bj):
                ck += ak * bk
                c[i][j] = ck % md
    return c


def pwr(a, k):
    c = None
    while c == None:
        if k & 1:
            c = a
        a = dot(a, a)
        k >>= 1

    while k > 0:
        if k & 1:
            c = dot(a, c)
        a = dot(a, a)
        k >>= 1
    return c


md = 10 ** 9 + 7
n, k = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
print(sum([sum(pk) % md for pk in pwr(a, k)]) % md)


### FIXED CODE ###

import sys

input = sys.stdin.readline


def dot(a, b):
    c = [[0] * n for _ in range(n)]
    for i, ai in enumerate(a):
        for j, bj in enumerate(zip(*b)):
            c[i][j] = sum(ak * bk for ak, bk in zip(ai, bj)) % md
    return c


def pwr(a, k):
    c = None
    while c == None:
        if k & 1:
            c = a
        a = dot(a, a)
        k >>= 1

    while k > 0:
        if k & 1:
            c = dot(a, c)
        a = dot(a, a)
        k >>= 1
    return c


md = 10 ** 9 + 7
n, k = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
print(sum([sum(pk) % md for pk in pwr(a, k)]) % md)
### BUGGY CODE ###

s=input()
n=len(s)
l=[0]*2019
l[0]=1
k=0
mod=2019
for i in range(n-1,-1,-1):
  k=(k+int(s[i])*10**(n-1-i))%mod
  l[k]+=1
ans=0
for i in l:
  ans+=i*(i-1)//2
print(ans)

### FIXED CODE ###

s=input()
n=len(s)
l=[0]*2019
l[0]=1
k=0
mod=2019
r=1
for i in range(n-1,-1,-1):
  k+=int(s[i])*r
  k%=mod
  r*=10
  r%=mod
  l[k]+=1
ans=0
for i in l:
  ans+=i*(i-1)//2
print(ans)
### BUGGY CODE ###

from collections import deque
from enum import Enum, auto
import sys
sys.setrecursionlimit(100000)

class Color(Enum):
    WHITE = auto()
    GRAY = auto()
    BLACK = auto()

n, m = list(map(int, input().split(' ')))
adj_list = [[] for i in range(n)]
for i in range(m):
    u, v = list(map(int, input().split(' ')))
    adj_list[u].append(v)
    adj_list[v].append(u)

# 幅優先
def adj_bfs(s, e):
    queue = deque([])
    colors = [Color.WHITE for i in range(n)]

    queue.append(s)
    colors[s] = Color.GRAY

    while len(queue) > 0:
        u = queue.popleft()
        for v in adj_list[u]:
            if colors[v] == Color.WHITE:
                colors[v] = Color.GRAY
                queue.append(v)
                if v == e: return True
        colors[u] = Color.BLACK
    return False

# 深さ優先
colors = [Color.WHITE for i in range(n)]

def adj_dfs(u, e):
    colors[u] = Color.GRAY

    for v in adj_list[u]:
        if colors[v] == Color.WHITE:
            if v == e: return True
            if adj_dfs(v, e):
                return True

    colors[u] = Color.BLACK
    return False

q = int(input())
for i in range(q):
    s, e = list(map(int, input().split(' ')))
    colors = [Color.WHITE for i in range(n)]
    if adj_dfs(s, e):
        print('yes')
    else:
        print('no')



### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(100000)

n, m = list(map(int, input().split(' ')))
adj_list = [[] for i in range(n)]
for i in range(m):
    u, v = list(map(int, input().split(' ')))
    adj_list[u].append(v)
    adj_list[v].append(u)

# 深さ優先
# 全ての点をたどって連結しているもの同士を同じ色に設定する
colors = []

def adj_dfs(r, c):
    global colors
    stack = deque([])
    stack.append(r)
    colors[r] = c
    while len(stack) != 0:
        u = stack.pop()
        for v in adj_list[u]:
            if colors[v] == None:
                colors[v] = c
                stack.append(v)

def assign_color():
    global colors
    id = 1
    colors = [None for i in range(n)]
    for u in range(n):
        if colors[u] == None:
            id += 1
            adj_dfs(u, id)

assign_color()

q = int(input())
for i in range(q):
    s, e = list(map(int, input().split(' ')))
    if colors[s] == colors[e]:
        print('yes')
    else:
        print('no')
### BUGGY CODE ###

from collections import defaultdict
N = int(input())
a = list(map(int, input().split()))

d = defaultdict(int)

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

f = 1

for ai in a:
    # g = gcd(g, ai)
    for n, cnt in factorization(ai):
        if n in d:
            f = 0
        if n != 1:
            d[n] += 1



if f:
    print('pairwise coprime')
else:
    f2 = 1
    for key in d:
        if d[key] == N:
            f2 = 0
            break
    if f2:
        print('setwise coprime')
    else:
        print('not coprime ') 



### FIXED CODE ###

from math import gcd

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

am = max(a)

memo = [1] * (am+1)
memo[0] = 0
memo[1] = 0

d = set([])

for ai in range(2, am+1):
    for j in range(2, am // ai + 1):
        memo[ai * j] = 0

cs = set([])
for i, memoi in enumerate(memo):
    if memoi:
        cs.add(i)

# print(cs)


f1 = 1
f2 = 1

for ai in a:
    lim = int(ai**0.5)+1
    f0 = 0
    if ai in cs:
        if ai in d:
            f0 = 1
            f1 = 0
        else:
            d.add(ai)
    else:  
        for i in cs:
            if i >= lim:
                break
            if ai % i == 0:
                if i in d or ai//i in d:
                    f1 = 0
                    f0 = 1
                    break
                else:
                    d.add(i)
                    d.add(ai//i)
    if f0:
        break


if f1:
    print('pairwise coprime')
else:
    g = a[0]
    for ai in a:
        g = gcd(ai, g)
    if g == 1:
        print('setwise coprime')
    else:
        print('not coprime')
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=0
for i in range(n-2):
  for j in range(i+1,n-1):
    b=a[i]+a[j]
    k=j+1
    while a[k]<b:
      k+=1
      if k>=n:
        break
    ans+=k-j-1
print(ans)

### FIXED CODE ###

import bisect
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=0
for i in range(n-2):
  for j in range(i+1,n-1):
    ans+=bisect.bisect_left(a,a[i]+a[j])-j-1
print(ans)
### BUGGY CODE ###

n = int(input())

ans = 1
for i in range(1,n+1):
    ans *= i

print(ans %(10**9+7))

### FIXED CODE ###

mod = 10**9 + 7
 
N = int(input())
 
ans = 1
 
for i in range(N):
    ans = ans*(i+1) % mod

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

n, p = map(int,input().split())
s = str(input())
ans = 0

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i])%p == 0:
            ans += i+1
    print(ans)
    exit()

tmp = [0] * p
tmp[0] = 1
mod = 0
for i in range(1,n+1):
    mod += (int(s[-i]) * 10**i) % p
    mod %= p
    ans += tmp[mod]
    tmp[mod] += 1

print(ans)

### FIXED CODE ###

n, p = map(int,input().split())
s = str(input())
ans = 0

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i])%p == 0:
            ans += i+1
    print(ans)
    exit()

tmp = [0] * p
tmp[0] = 1
mod = 0
r = 1
for i in range(1,n+1):
    mod += (int(s[-i]) * r) % p
    mod %= p
    tmp[mod] += 1
    r *= 10
    r %= p

for i in tmp:
    ans += i*(i-1)//2

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

K=int(input())
if K % 2 == 0:
    print(-1)
    exit()

x = 7
ans = 1
while x > 0:
    if x < K:
        x = x*10 + 7
        ans += 1
        continue
    x = x % K

print(ans)


### FIXED CODE ###

K=int(input())
if K % 2 == 0:
    print(-1)
    exit()

m = set()
x = 7
ans = 1
while x > 0:
    if x < K:
        x = x*10 + 7
        ans += 1
    x = x % K
    if x in m:
        print(-1)
        exit(0)
    else:
        m.add(x)

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

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

Benefit = 0

for b in range(2**N):
	Binary = []
	binary = b
	for n in range(N):
		Binary.append(binary % 2)
		binary = binary //(2)
#	print("Binary = " + str(Binary))
	B = 0
	for n in range(N):
		if Binary[n] == 1:
			B += V[n] - C[n]
	Benefit = max(Benefit, B)
#print("Benefit = " + str(Benefit) )

print(Benefit)


### FIXED CODE ###

N = int(input())
V = list(map(int , input().split()))
C = list(map(int , input().split()))
B = 0

for n in range(N):
	if V[n] - C[n] > 0:
		B += V[n] - C[n]

print(B)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
S = []
for i in range(1,N+1):
    S.append(A.index(i)+1)
print(*S)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=[]
kari=[]
for i in range(N):
    ans.append([A[i],i+1])
ans.sort()
#print(ans)
for j in range(N):
    kari.append(ans[j][1])
print(*kari)
### BUGGY CODE ###

N = int(input())
a = list(input().split())

b = []
for i in range(N):
  if i % 2 == 0:
    b.append(a[i])
  else:
    b.insert(0, a[i])
if N % 2 == 1:
  b = b[::-1]
print (" ".join(b))

### FIXED CODE ###

N = int(input())
a = list(input().split())

print (" ".join(a[-1::-2] + a[N%2::2]))
### BUGGY CODE ###

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

S = input()
Q = int(input())

# Queries = []
# for _ in range(Q):
#     Queries.append(list(input().split()))
    
# for Query in Queries:
#     T = int(Query[0])
#     if T == 1:
#         S = S[::-1]
#     else:
#         F = int(Query[1])
#         C = Query[2]
#         if F == 1:
#             S = C + S
#         else:
#             S = S + C
# print(S)

swap = 1
head = ""
tail = ""
for _ in range(Q):
    Query = list(input().split())

    if Query[0] == "1":
        swap *= -1
    
    else:
        F, C = Query[1], Query[2]
        if F == "1":
            if swap == 1:
                head = C + head
            else:
                tail = tail + C
        else:
            if swap == -1:
                head = C + head
            else:
                tail = tail + C            

print((head + S + tail)[::swap])



### FIXED CODE ###

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
from collections import deque

S = input()
Q = int(input())

# Queries = []
# for _ in range(Q):
#     Queries.append(list(input().split()))
    
# for Query in Queries:
#     T = int(Query[0])
#     if T == 1:
#         S = S[::-1]
#     else:
#         F = int(Query[1])
#         C = Query[2]
#         if F == 1:
#             S = C + S
#         else:
#             S = S + C
# print(S)

swap = 1
head = deque()
tail = deque()
for _ in range(Q):
    Query = list(input().split())

    if Query[0] == "1":
        swap *= -1
    
    else:
        F, C = Query[1], Query[2]
        if F == "1":
            if swap == 1:
                head.appendleft(C)
            else:
                tail.append(C)
        else:
            if swap == -1:
                head.appendleft(C)
            else:
                tail.append(C)         


print(("".join(head) + S + "".join(tail))[::swap])
### BUGGY CODE ###

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

for i in range(N):
    copy_X = sort_X.copy()
    copy_X.remove(X[i])
    
    print(copy_X[(N-1)//2])

### FIXED CODE ###

N = int(input())
X = list(map(int, input().split()))
sort_X = sorted(X)
a = sort_X[N//2-1]
b = sort_X[N//2]
for i in range(N):
    if X[i] < b:
        print(b)
    else:
        print(a)
### BUGGY CODE ###

import math
import fractions
import copy
import numpy as np
def j(q):
    if q==1: print("YES")
    elif q == 0:print("NO")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def printrow(a):
    for i in a:
        print(i)
"""
#decomment when needed
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
"""
n = ip()
a  = iprow()
ans = sum(a)
b = iprow()
pl = 0
pr = n-1
if n==1:
    print(min(sum(b),sum(a)))
    exit(0)

while sum(b):
    if b[pl] - a[pl]>0:
        b[pl] -= a[pl]
        a[pl] = 0
    else:
        a[pl]-=b[pl]
        b[pl] = 0
    if b[pl]:
        if b[pl] - a[pl+1]>0:
            b[pl] = 0
            a[pl+1] = 0
        else:
            a[pl+1]-=b[pl]
            b[pl] = 0
    if b[pr] - a[pr+1] > 0:
        b[pr] -= a[pr + 1]
        a[pr+1] = 0
    else:
        a[pr+1] -= b[pr]
        b[pr] = 0
    if b[pr]:
        if b[pr] - a[pr] > 0:
            a[pr] = 0
            b[pr] = 0
        else:
            a[pr] -= b[pr]
            b[pr] = 0
    pl+=1
    pr-=1
print(ans-sum(a))

### FIXED CODE ###

import math
import fractions
import copy
import numpy as np
def j(q):
    if q==1: print("YES")
    elif q == 0:print("NO")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def printrow(a):
    for i in a:
        print(i)
"""
#decomment when needed
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
"""
n = ip()
a  = iprow()
ans = sum(a)
b = iprow()
pl = 0
pr = n-1
if n==1:
    print(min(sum(b),sum(a)))
    exit(0)

while pl <= pr:
    if b[pl] - a[pl]>0:
        b[pl] -= a[pl]
        a[pl] = 0
    else:
        a[pl]-=b[pl]
        b[pl] = 0
    if b[pl]:
        if b[pl] - a[pl+1]>0:
            b[pl] = 0
            a[pl+1] = 0
        else:
            a[pl+1]-=b[pl]
            b[pl] = 0
    if b[pr] - a[pr+1] > 0:
        b[pr] -= a[pr + 1]
        a[pr+1] = 0
    else:
        a[pr+1] -= b[pr]
        b[pr] = 0
    if b[pr]:
        if b[pr] - a[pr] > 0:
            a[pr] = 0
            b[pr] = 0
        else:
            a[pr] -= b[pr]
            b[pr] = 0
    pl+=1
    pr-=1
print(ans-sum(a))
### BUGGY CODE ###

N = int(input())
F = [0] * N
for i in range(N):
  F[i] = list(map(int, input().split()))
  
P = [0] * N   
for i in range(N):
  P[i] = list(map(int, input().split()))

if N == 2:
  while True:
    print("yeah")
#print(F, P)
#print(4 >> 1)
ans = - 10 ** 10
#print(ans)
for i in range(1, 2 ** 10):#bit全探索 #0は空いてる時間帯がないのでカット
  open_n = [0] * N
  profit = 0
  for j in range(10):#10240通り
    if ((i >> j) & 1):#jの時間帯に空いてる
      for k in range(N):#100
        if F[k][j] == 1:
          open_n[k] += 1
  for l in range(N):
    profit += P[l][open_n[l]]
  if ans < profit:
    ans = profit
          
print(ans) 


### FIXED CODE ###

N = int(input())
F = [0] * N
for i in range(N):
  F[i] = list(map(int, input().split()))
  
P = [0] * N   
for i in range(N):
  P[i] = list(map(int, input().split()))

#print(F, P)
#print(4 >> 1)
ans = - 10 ** 10
#print(ans)
for i in range(1, 2 ** 10):#bit全探索 #0は空いてる時間帯がないのでカット
  open_n = [0] * N
  profit = 0
  for j in range(10):#10240通り
    if ((i >> j) & 1):#jの時間帯に空いてる
      for k in range(N):#100
        if F[k][j] == 1:
          open_n[k] += 1
  for l in range(N):
    profit += P[l][open_n[l]]
  if ans < profit:
    ans = profit
          
print(ans)
### BUGGY CODE ###

import functools
import operator


def prod(arr):
    return functools.reduce(operator.mul, arr)


def main():
    N, K = (int(x) for x in input().split(" "))
    A = [int(x) for x in input().split(" ")]
    lastest_score = prod(A[0:K])
    for i in range(1, N-K+1):
        current_score = lastest_score - A[i-1] + A[i + K-1]
        if lastest_score < current_score:
            print("Yes")
        else:
            print("No")
        lastest_score = current_score


if __name__ == '__main__':
    main()


### FIXED CODE ###

def prod(arr):
    s = 0
    for x in arr:
        s += x
    return s


def main():
    N, K = (int(x) for x in input().split(" "))
    A = [int(x) for x in input().split(" ")]
    lastest_score = prod(A[0:K])
    result = ["No"] * (N-K+1)
    for i in range(1, N-K+1):
        current_score = lastest_score - A[i-1] + A[i + K-1]
        if lastest_score < current_score:
            result[i] = "Yes"
        lastest_score = current_score
    [print(x) for x in result[1:]]


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

import copy

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

# imos法
# log(N)ぐらいで収束するので、打ち切れば計算量的には問題なし？

for i in range(K):
    B = [0] * (N+1)
    for j in range(N):
        l = max(0, j-A[j])
        r = min(j+A[j]+1, N)
        B[l] += 1
        B[r] -= 1
    # print("B: {}".format(B))
    for j in range(N):
        B[j+1] += B[j]
    del B[N]
    # print("B: {}".format(B))
    if A == B:
        break
    A = copy.deepcopy(B)

print(*A)


### FIXED CODE ###

import copy

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

# imos法
# log(N)ぐらいで収束するので、打ち切れば計算量的には問題なし？

for i in range(K):
    B = [0] * (N+1)
    for j in range(N):
        l = max(0, j-A[j])
        r = min(j+A[j]+1, N)
        B[l] += 1
        B[r] -= 1
    # print("B: {}".format(B))
    for j in range(N):
        B[j+1] += B[j]
    del B[N]
    # print("B: {}".format(B))
    if A == B:
        break
    A = copy.deepcopy(B)

print(*A)
### BUGGY CODE ###

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

r=[0]*n
for ii in range(n):
  r0=0
  for jj in range(n):
    if ii!=jj:
      r0=r0^a[jj]
  r[ii]=r0
"""
for ii in range(n):
  print(bin(a[ii]),bin(r[ii]))
"""
print(*r)

### FIXED CODE ###

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

r1=0
for jj in range(n):
  r1=r1^a[jj]

r=[0]*n
for ii in range(n):
  r[ii]=r1^a[ii]
"""
for ii in range(n):
  print(bin(a[ii]),bin(r[ii]))
"""
print(*r)
### BUGGY CODE ###

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from collections import deque
import sys
def main(H, W, C, D, S):
    INF = 10**6
    dist = [[INF] * W for _ in range(H)]
    dist[D[0]][D[1]] = 0
    q = deque([D])
    while q:
        i, j = q.popleft()
        d = dist[i][j]
        for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
            if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
                if dist[ni][nj] > d:
                    dist[ni][nj] = d
                    q.append((ni, nj))
        for ni in range(i - 2, i + 2 + 1, 1):
            for nj in range(j - 2, j + 2 + 1, 1):
                if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
                    if dist[ni][nj] > d + 1:
                        dist[ni][nj] = d + 1
                        q.append((ni, nj))

    ans = dist[C[0]][C[1]]
    print(ans if ans < INF else -1)


if __name__ == '__main__':
    input = sys.stdin.readline
    H, W = map(int, input().split())
    C = tuple(map(lambda x: int(x) - 1, input().split()))
    D = tuple(map(lambda x: int(x) - 1, input().split()))
    S = [list(input().rstrip()) for _ in range(H)]
    main(H, W, C, D, S)


### FIXED CODE ###

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from collections import deque
import sys
def main(H, W, C, D, S):
    INF = 10**6
    dist = [[INF] * W for _ in range(H)]
    di, dj = D
    dist[di][dj] = 0
    q = deque([(di, dj, 0)])
    while q:
        i, j, d = q.popleft()
        if d > dist[i][j]: continue
        for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
            if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
                if dist[ni][nj] > d:
                    dist[ni][nj] = d
                    q.appendleft((ni, nj, d))
        for ni in range(i - 2, i + 2 + 1, 1):
            if not(0 <= ni < H): continue
            dni = dist[ni]
            sni = S[ni]
            for nj in range(j - 2, j + 2 + 1, 1):
                if 0 <= nj < W and sni[nj] == '.':
                    if dni[nj] > d + 1:
                        dni[nj] = d + 1
                        q.append((ni, nj, d + 1))

    ans = dist[C[0]][C[1]]
    print(ans if ans < INF else -1)


if __name__ == '__main__':
    input = sys.stdin.readline
    H, W = map(int, input().split())
    C = tuple(map(lambda x: int(x) - 1, input().split()))
    D = tuple(map(lambda x: int(x) - 1, input().split()))
    S = [list(input().rstrip()) for _ in range(H)]
    main(H, W, C, D, S)
### BUGGY CODE ###


import sys
input = sys.stdin.readline
def isSafe(position):
    return not position in listM


STEP = 2
N,M = map(int,input().split())
dp = [0] * (N+1)
cnt = 0


listM=[int(input()) for i in range(M)]
dp[0] = 1

for i in range(N):
    if i+1 > N:
        break
    if isSafe(i+1):
        dp[i+1] += dp[i]
    if i+2 > N:
        break
    if isSafe(i+2):
        dp[i+2] += dp[i]
        #dp[j] = 0
    #print(dp)
        
print(dp[N] % 1000000007)

### FIXED CODE ###


import sys
input = sys.stdin.readline
def isSafe(position):
    return not position in listM
 
 
STEP = 2
N,M = map(int,input().split())
dp = [0] * (N+1)
cnt = 0
 
 
listM={int(input()) for i in range(M)}
dp[0] = 1
 
for i in range(N):
    if i+1 > N:
        break
    if isSafe(i+1):
        dp[i+1] += dp[i]
    if i+2 > N:
        break
    if isSafe(i+2):
        dp[i+2] += dp[i]
        #dp[j] = 0
    #print(dp)
        
print(dp[N] % 1000000007)