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

# E.py#
H, W, A, B = map(int,input().split())
P = 10**9+7
# H, W, A, B = map(int,"2 3 1 1".split())

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def fact(i):
	t = 1
	while i > 0:
		t = (t * i) % P
		i -= 1
	return t

def comb(i,j):
	return (fact(i+j) * modinv(fact(i),P) * modinv(fact(j),P)) % P

s = 0
i = 0
while H-A-i > 0 and B+i+1 <= W and A+i <= H and W-B-i >= 0:
#	print((H-A-i,B+i+1))
	s = (s + comb(H-A-i-1,B+i+1-1) * comb(A+i,W-B-i-1)) % P
	i += 1	
print(s)



### FIXED CODE ###

H, W, A, B = map(int,input().split())
P = 10**9+7
# H, W, A, B = map(int,"2 3 1 1".split())

M = H+W-1
factlist = [1] * (H+W)
factinvlist = [1] * (H+W)
t = 1
for i in range(M):
	t = (t * (i+1)) % P
	factlist[i+1] = t
t = pow(factlist[M],P-2,P)
factinvlist[M] = t
for i in range(M):
	t = (t * (M-i)) % P
	factinvlist[M-i-1] = t

def comb(i,j):
	return (factlist[i+j] * factinvlist[i] * factinvlist[j]) % P

s = 0
i = 0
while H-A-i-1 >= 0 and B+i <= W and A+i <= H and W-B-i-1 >= 0:
#	print((H-A-i,B+i+1))
	s = (s + comb(H-A-i-1,B+i) * comb(A+i,W-B-i-1)) % P
	i += 1	
print(s)
### BUGGY CODE ###

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

hats = A[:]

from collections import defaultdict
d = defaultdict(lambda: {})

for i, h1 in enumerate(hats):
    hats2 = hats[i+1:]
    for j, h2 in enumerate(hats2):
        h3 = h1^h2
        d[h1][h3] = h2
        d[h3][h1] = h2

#print(d)
        
def dfs(top, now1, now2, count):
    if now2 == top:
        #print(count)
        if count == N:
            return True
        else:
            return False

    now1, now2 = now2, now2 ^ d[now1][now2]

    return dfs(top, now1, now2, count+1)
    
ans = False
h1 = hats[0]
for h2 in d[h1]:
    if dfs(h1, h1, h2, 2):
        ans = True
        
if ans:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

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

hats = A[:]
import copy
from collections import defaultdict
d = defaultdict(lambda: 0)

for h in hats:
    d[h] += 1

def f():
    if len(d) == 3:
        xor = 0
        for key in d:
            xor ^= key
        if xor == 0:
            lsit_d = list(d.keys())
            if d[lsit_d [0]] == d[lsit_d [1]] and d[lsit_d [0]] == d[lsit_d [2]]:
                return 'Yes'
            else:
                return 'No'
        else:
            return 'No'

    if len(d) == 1:
        lsit_d = list(d.keys())
        if lsit_d [0] == 0:
            return 'Yes'
        
    if len(d) == 2:
        if d[0] * 2 == N - d[0]:
            return 'Yes'
    
    return 'No'
    
print(f())
### BUGGY CODE ###

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

from itertools import accumulate

for _ in range(k):
    imos=[0]*(n+1)
    for i in range(n):
        l=max(0,i-a[i])
        r=min(n,i+a[i]+1)
        imos[l]+=1
        imos[r]-=1
    a=list(accumulate(imos[:n]))
    if a.count(n)==n:
        break
print(*a)


### FIXED CODE ###

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

from itertools import accumulate

for _ in range(k):
    imos=[0]*(n+1)
    for i in range(n):
        l=max(0,i-a[i])
        r=min(n,i+a[i]+1)
        imos[l]+=1
        imos[r]-=1
    a=list(accumulate(imos[:n]))
    if a.count(n)==n:
        break
print(*a)
### BUGGY CODE ###

ai = lambda: list(map(int, input().split()))

n,x = ai()
a = ai()


def m(k):
    z = []
    for i in range(n):
        z.append(min(a[i-j] for j in range(k+1)))
    return sum(z)


print(min(m(k) + x*k for k in range(n)))


### FIXED CODE ###

ai = lambda: list(map(int, input().split()))

n,x = ai()
a = ai()

ma = [[] for _ in range(n)]
for i in range(n):
    ma[i].append(a[i])
    for j in range(1,n):
        if ma[i][-1] > a[i-j]:
            ma[i].append(a[i-j])
        else:
            ma[i].append(ma[i][-1])


def m(k):
    return sum(ma[i][k] for i in range(n))


print(min(m(k) + x*k for k in range(n)))
### BUGGY CODE ###

import sys
#from numba import jit

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def cc(v, pp,dame):
	if v == pp[-1]:
		return False, -1
	if dame and dame[-1] == v:
		return False, 0
	
	for p in pp:
		if v % p == 0:
			return False, 0
		if v < 2*p:
			return True, 0
	return True, 0
			
def main():
	n = int(input())
	#b , c = tin()
	#s = input()
	al = lin()
	al.sort()
	pp=[al[0]]
	dame=[]
	n_same=0
	n_same_set=set()
	for v in al[1:]:
		tf, vv = cc(v, pp, dame)
		if tf:
			pp.append(v)
		elif dame and v != dame[-1]:
			dame.append(v)
		if vv == -1 and pp[-1] not in n_same_set:
			n_same_set.add(pp[-1])
			n_same += vv
	print(len(pp) + n_same)
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

### FIXED CODE ###

import sys
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	n = int(input())
	#b , c = tin()
	al = lin()
	al.sort()
	
	unique_al = list(set(al))
	unique_al.sort()
	
	al_counter = collections.Counter(al)
	ok=[v for v in al_counter.keys() if al_counter[v] == 1]
	d = {v:i for i,v in enumerate(ok)}
	max_v = 10**6+1
	for check in unique_al:
		for v in range(2*check, max_v, check):
			if v in d:
				ok[d[v]]=0
				
	return sum([v > 0 for v in ok ])
		
	
	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
### BUGGY CODE ###

k = int(input())
a=7
i=1
if k%5==0 or k%2==0:
  print(-1)
  exit()
while True:
  if a%k ==0:
    print(i)
    break
  i+=1
  a = a + 7*10**(i-1)


### FIXED CODE ###

k = int(input())
if k % 2 == 0 or k%5==0:
    print(-1)
    exit()
a = 7
ans = 1
while True:
    if a % k == 0:
        print(ans)
        exit()
    a = (a*10+7) % k
    ans += 1
### BUGGY CODE ###

R, C, k = map(int, input().split())
xs = [[0] * C for _ in range(R)]
for _ in range(k):
    r, c, v = map(int, input().split())
    xs[r - 1][c - 1] = v

dp = [[[0] * 4 for _ in range(C + 1)] for _ in range(R + 1)]
for i in range(R):
    for j in range(C):
        for k in range(2, -1, -1):
            dp[i][j][k + 1] = max(dp[i][j][k + 1], dp[i][j][k] + xs[i][j])
        for k in range(4):
            dp[i][j + 1][k] = max(dp[i][j + 1][k], dp[i][j][k])
        dp[i + 1][j][0] = max(dp[i + 1][j][0], *dp[i][j])
print(max(dp[R - 1][C - 1]))


### FIXED CODE ###

R, C, k = map(int, input().split())
xs = [[0] * C for _ in range(R)]
for _ in range(k):
    r, c, v = map(int, input().split())
    xs[r - 1][c - 1] = v

dp = [[[0] * (C + 1) for _ in range(R + 1)] for _ in range(4)]
for i in range(R):
    for j in range(C):
        for k in range(2, -1, -1):
            dp[k + 1][i][j] = max(dp[k + 1][i][j], dp[k][i][j] + xs[i][j])
        for k in range(4):
            dp[k][i][j + 1] = max(dp[k][i][j + 1], dp[k][i][j])
            dp[0][i + 1][j] = max(dp[0][i + 1][j], dp[k][i][j])
ans = 0
for k in range(4):
    ans = max(ans, dp[k][R - 1][C - 1])
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
a = input("").split(" ")
a = [int(i) for i in a]

for i in range(1,n - k+1):
    score = 1
    p_score = 1
    for j in range(i,i+k):
        score *= a[j]
        p_score *= a[j-1]
    if score > p_score:
        print("Yes")
    else:
        print("No")



### FIXED CODE ###

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

for i in range(n - k):
    if a[k+i] > a[i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import sys
N = int(input())
A = list(map(int, input().split()))
 
ans = 1
 
for i in A:
    ans = ans*i
    if ans > int(10**18) and A.count(0) == 0:
        print(-1)
        sys.exit()
 
if ans > int(10**18):
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import sys
N = int(input())
A = list(map(int, input().split()))
 
ans = 1

if A.count(0) != 0:
    print(0)
    sys.exit()

for i in A:

    ans = ans*i
    if ans > int(10**18):
        print(-1)
        sys.exit()
 
if ans > int(10**18):
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import sys
from itertools import accumulate
input=sys.stdin.buffer.readline
def main():
    n, k = map(int, input().strip().split())
    A = [*map(int, input().strip().split())]
    
    # for _ in range(min(k,int(math.log(n,2)))):
    
    for _ in "_"*k:
        b=[0]*(n+1)
        
        for i,v in enumerate(A):
            b[max(0,i-v)]+=1
            b[min(n,i+v+1)]-=1
        
        # update ans
        # cnt=0
        # for i in range(1,n):
        #     b[i]+=b[i-1]
        A=[*accumulate(b)][:-1]
        
        if min(A)==n:
            break
    print(" ".join(map(str,A)))

if '__main__' == __name__:
    main()

### FIXED CODE ###

import sys
from itertools import accumulate
input=sys.stdin.buffer.readline

def main():
    n, k = map(int, input().split())
    A = [*map(int, input().split())]
    
    # for _ in range(min(k,int(math.log(n,2)))):
    
    for _ in "_"*k:
        b=[0]*(n)
        
        for i,v in enumerate(A):
            if i>v:
            # b[max(0,i-v)]+=1
                b[i-v]+=1
            else:
                b[0]+=1
            j=i-~v
            # if i+v+1<n:
            #     b[i+v+1]-=1
            if j<n:
                b[j]-=1
        
        # update ans
        # cnt=0
        # for i in range(1,n):
        #     b[i]+=b[i-1]
        A=[*accumulate(b)]
        
        if min(A)==n:
            break
    print(" ".join(map(str,A)))

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

# -*- coding: utf-8 -*-
"""
Created on Tue Dec 19 10:03:26 2017

@author: kotania
"""
N = int(input())

AList = []

count = 0
        
for n in range(0,N):
    An = input()
    
    if An in AList:
        AList.remove(An)
        count -= 1
    else:
        AList.append(An)
        count += 1

print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue Dec 19 10:03:26 2017

@author: kotania
"""
from collections import Counter

N = int(input())
 
AList = []
 
count = 0
        
for n in range(0,N):
    AList.append(input())
    
countDict = Counter(AList)
countDictValues = countDict.values()

count = 0

for c in countDictValues:
    if c % 2 == 1 :
        count += 1

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

import sys
sys.setrecursionlimit(10**6)

mod=10**9+7
N,K=map(int,input().split())

tree=[]
for i in range(N+1):
  tree.append([])

for i in range(N-1):
  a,b=map(int,input().split())
  tree[a].append(b)
  tree[b].append(a)
#print(tree)

answer=1
visited=[False]*(N+1)
def dfs(node,depth,cind):
  #print(node,depth,cind)
  global answer
  visited[node]=True
  
  if depth==0:
    answer*=K
    answer%=mod
  elif depth==1:
    answer*=K-1-cind
    answer%=mod
  else:
    answer*=K-2-cind
    answer%=mod
  
  next_nodes=tree[node]
  i=0
  for nn in next_nodes:
    if not visited[nn]:
      dfs(nn,depth+1,i)
      i+=1

node=N-1
dfs(node,0,0)
print(answer)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

mod=10**9+7
N,K=map(int,input().split())

tree=[]
for i in range(N+1):
  tree.append([])

for i in range(N-1):
  a,b=map(int,input().split())
  tree[a].append(b)
  tree[b].append(a)
#print(tree)

answer=1
visited=[False]*(N+1)
def dfs(node,depth,cind):
  #print(node,depth,cind)
  global answer
  visited[node]=True
  
  if depth==0:
    answer*=K
    answer%=mod
  elif depth==1:
    answer*=K-1-cind
    answer%=mod
  else:
    answer*=K-2-cind
    answer%=mod
  
  next_nodes=tree[node]
  i=0
  for nn in next_nodes:
    if not visited[nn]:
      dfs(nn,depth+1,i)
      i+=1

node=N//2
dfs(node,0,0)
print(answer)
### BUGGY CODE ###

from collections import defaultdict

N = int(input())
S = input()

strList = defaultdict(list)

for leng in range(N):
    for left in range(N - leng + 1):
        sub = S[left: left + leng]
        strList[sub].append(left)

ans = 0
for sub, leftList in strList.items():
    leng = len(sub)
    if leftList[0] + leng <= leftList[-1]:
        ans = max(ans, leng)

print(ans)


### FIXED CODE ###

from collections import deque

N = int(input())
S = input()

def isOk(leng):
    hashList = set()
    que = deque([])
    for left in range(N - leng + 1):
        hs = hash(S[left: left + leng])
        if hs in hashList:
            return True
        que.append(hs)
        if len(que) >= leng:
            hashList.add(que.popleft())
    return False

ok = 0
ng = N

while ng - ok > 1:
    mid = (ng + ok) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ok)
### BUGGY CODE ###

n = int(input())
nn = (n + 1) / 2
s = [0]*n
print(0)
s[0] = input()
if s[0] == "Vacant":
    exit()
print(n-1)
s[n-1] = input()
if s[n-1] == "Vacant":
    exit()
ll = 0
hh = nn-1
while hh - ll > 1:
    l = ll*2
    h = hh*2
    ii = (ll + hh) / 2
    i = ii*2
    print(i)
    s[i] = input()
    if s[i] == "Vacant":
        exit()
    elif s[i] != s[l]:
        ll = ii
    else:
        hh = ii
print(ll+hh)
exit()

### FIXED CODE ###

n = int(input())
nn = (n + 1) // 2
s = [0]*n
print(0)
s[0] = input()
if s[0] == "Vacant":
    exit()
print(n-1)
s[n-1] = input()
if s[n-1] == "Vacant":
    exit()
ll = 0
hh = nn-1
while hh - ll > 1:
    l = ll*2
    h = hh*2
    ii = (ll + hh) // 2
    i = ii*2
    print(i)
    s[i] = input()
    if s[i] == "Vacant":
        exit()
    elif s[i] != s[l]:
        hh = ii
    else:
        ll = ii
print(ll+hh)
### BUGGY CODE ###

def v_max(x):#x(sec)における最大速度
    res = x
    
    for i in range(n + 1):
        t_l = t2[i]
        t_r = t2[i + 1]
        
        if 0 <= x < t_l:
            vi = v[i] + (t_l - x)
        elif t_l <= x <= t_r:
            vi = v[i]
        else:
            vi = v[i] + (x - t_r)
            
        res = min(res, vi)
        
    return res

n = int(input())
t = list(map(int, input().split()))
t2 = [0]#累積和
for i in range(n):
    t2.append(t2[i] + t[i])#0, t1, t1 + t2, t1 + t2 + t3, ...のように増えていく
finish_t = t2[-1]#終了時刻
t2.append(finish_t)
v = list(map(int, input().split())) + [0]#v1, v2, ..., 0

#print(t)
#print(t2)
#print(v)

now = 0
v_l = 0
ans = 0
while now < finish_t:
    now += 0.5
    v_r =  v_max(now)
    ans += 0.25 * (v_l + v_r)

    v_l = v_r
    
print(ans)

### FIXED CODE ###

'''
38分あたり
https://www.youtube.com/watch?v=T1zXzsoK268
'''
def input_num_list(): return list(map(int, input().split()))

n = int(input())
t = input_num_list()
T = sum(t)
v = input_num_list()
maxv = [100 for _ in range(2 * T + 1)]
maxv[0] = 0
maxv[2 * T] = 0

t_l, t_r = 0, 0
for i in range(n):
    t_l = t_r
    t_r += t[i]
    vv = v[i]
    for j in range(2 * t_l, 2 * t_r + 1):
        maxv[j] = min(maxv[j], vv)

#print(maxv)
i = 1
while i <= 2 * T:
    maxv[i] = min(maxv[i], maxv[i - 1] + 0.5)
    i += 1
#print(maxv)
i = 2 * T - 1
while i >= 0:
    maxv[i] = min(maxv[i], maxv[i + 1] + 0.5)
    i -= 1
#print(maxv)
ans = 0
i = 0
while i <= 2 * T - 1:
    ans += 0.25 * (maxv[i] + maxv[i + 1])
    i += 1
    
print(ans)
#print(maxv)
### BUGGY CODE ###

def f(k, a_s):
    md = 10 ** 9 + 7
    dp = [[0] * (k + 1) for _ in range(n)]
    dp[0][0] = 1
    for i, a in enumerate(a_s[:-1]):
        dpi1 = dp[i + 1]
        dpi = dp[i]
        dpi1[0] = s = dp[i][0] % md
        for j in range(1, a + 1):
            dpi1[j] = s = (s + dpi[j]) % md
        for j in range(a + 1, k + 1):
            dpi1[j] = s = (s + dpi[j] - dpi[j - a - 1]) % md
    return sum(dp[-1][k - a_s[-1]:]) % md


n, k = map(int, input().split())
a_s = list(map(int, input().split()))
print(f(k, a_s))


### FIXED CODE ###

def f(n, k, a_s):
    md = 10 ** 9 + 7
    dp = [0] * (k + 1)
    dp[0] = 1
    for a in a_s[:-1]:
        ndp = [0] * (k + 1)
        ndp[0] = s = dp[0] % md
        for j in range(1, a + 1):
            ndp[j] = s = (s + dp[j]) % md
        for j in range(a + 1, k + 1):
            ndp[j] = s = (s + dp[j] - dp[j - a - 1]) % md
        dp = ndp
    return sum(dp[k - a_s[-1]:]) % md


n, k = map(int, input().split())
a_s = list(map(int, input().split()))
print(f(n, k, a_s))
### BUGGY CODE ###

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

direction = 1

for i in range(Q):
    q = list(map(str, input().split())) 
    if q[0] == "1":
        direction *= (-1)
        #S = S[::-1]
    elif q[0] == "2":
        if direction > 0:
            if q[1] == "1":
                S = q[2] + S
            elif q[1] == "2":
                S = S + q[2]
        elif direction < 0:
            if q[1] == "1":
                S = S + q[2]
            elif q[1] == "2":
                S = q[2] + S 

if direction < 0:
    S = S[::-1]           

print(S)

### FIXED CODE ###

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

head = ''
back = ''
direction = 1

for i in range(Q):
    q = list(map(str, input().split())) 
    if q[0] == "1":
        direction *= (-1)
        #S = S[::-1]
    else:
        if q[1] == "1":
            if direction == 1:
                head = head + q[2]
            else:
                back = back + q[2]
        else:
            if direction == 1:
                back = back + q[2]
            else:
                head = head + q[2]

if direction == 1:
    print(head[::-1]+S+back)
else:
    print(back[::-1]+S[::-1]+head)
### BUGGY CODE ###

import operator as op
from functools import reduce
 
def npr(n, r):
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    return numer


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

# edge_mat[i][j] = 1 iff vertex_i and vertex_j are connected
edge_mat = [[0 for j in range(N)] for i in range(N)]
for k in range(N - 1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    edge_mat[a][b] = 1
    edge_mat[b][a] = 1

# ナンバリングは０オリジン
# 頂点０をrootとする

# depth1 = 階層１の頂点を列挙
num = 0
for j in range(1, N):
    if edge_mat[0][j] == 1:
        num += 1

# 各頂点から出る子の個数を列挙
child_num = [0 for i in range(N)]
child_num[0] = num
for j in range(1, N):
    child_num[j] = sum(edge_mat[j]) - 1

# calculate
min_child = min(child_num)
if K < min_child:
    print(0)
else:
    ans = (K * npr(K - 1, child_num[0])) % q
    for i in range(1, N):
        val = npr(K - 2, child_num[i]) % q
        ans = (ans * val) % q
    print(ans)

### FIXED CODE ###

import operator as op
from functools import reduce
 
def npr(n, r):
    numer = 1
    for k in range(r):
        numer = numer * (n - k)
        numer %= q
    return numer


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

child_num = [0 for i in range(N)]
for k in range(N - 1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    child_num[a] += 1
    child_num[b] += 1

for i in range(1, N):
    child_num[i] -= 1

# calculate
min_child = min(child_num)
if K < min_child:
    print(0)
else:
    ans = (K * npr(K - 1, child_num[0])) % q
    for i in range(1, N):
        val = npr(K - 2, child_num[i]) % q
        ans = (ans * val) % q
    print(ans)
### BUGGY CODE ###

from collections import deque
h, w = map(int, input().split())
que = deque()

blck = [1] * (w + 2)
data = [blck]
for ln in range(1, h+1):
    line = list(input().rstrip())
    lineN = [0] * (w+2)
    lineN[0] = 1
    lineN[-1] = 1
    for r, letter in zip(range(1, w+1), line):
        if letter == '#':
            lineN[r] = 1
            que.append((ln, r))
    data.append(lineN)
data.append(blck)


count = 0
next = deque()
while len(que) > 0:
    count += 1
    while len(que) > 0:
        row, col = que.popleft()
        for r, c in ((row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)):
            if data[r][c] == 0:
                next.append((r, c))
                data[r][c] = 1
    que, next = next, que

print(count - 1)

### FIXED CODE ###

from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = [None] * (H*W)
matS = matE = 0
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "#":
            mat[matE] = (h, w, 0)
            matE+=1
    dp[h] = s

def search(dp, mat, nH, nW, cnt):
    global matE
    if dp[nH][nW] == ".":
        mat[matE] = (nH, nW, cnt+1)
        matE+=1
        dp[nH][nW] = "#"

while matS < matE:
    h, w, cnt = mat[matS]
    matS += 1

    if h > 0:
        search(dp, mat, h - 1, w, cnt)
    if h < H-1:
        search(dp, mat, h + 1, w, cnt)
    if w > 0:
        search(dp, mat, h , w - 1, cnt)
    if w < W-1:
        search(dp, mat, h , w + 1, cnt)

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

N = int(input())

A = []
numbers = {}
for i in range(N):
    num = int(input())
    if num not in A:
        A.append(num)
        
    if num in numbers.keys():
        numbers[num] = (numbers[num] + 1)%2 
    else:
        numbers[num] = 1

##print(numbers)

count = 0
for i in range(len(A)):
    val = numbers[A[i]]
    if val == 1:
        count += 1

print(count)     

### FIXED CODE ###

N = int(input())

A = []
for i in range(N):
    A.append(int(input()))

A.sort()


tmpcount = 1
count = 0
A.append(-1)

for i in range(1,N+1):
    if A[i] == A[i-1]:
        tmpcount += 1
    else:
        if tmpcount % 2 == 1:
            count += 1
        tmpcount = 1

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

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
BC= [list(map(int, input().split()))]
for i in range(1,Q):
    BC.append(list(map(int, input().split())))
    
print
for q in range(Q):
    for i in range(N):
        if A[i] == BC[q][0]:
            A[i] = BC[q][1]
    print(sum(A))
    

### FIXED CODE ###

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

num = [0]*10**5

#Aの要素の数を管理するリストnumを作成
for k in range(len(A)):
    num[A[k]-1] += 1

counter = 0 #Biと一致した要素の数
s = sum(A) #合計を初期化

for q in range(Q):
    counter = num[BC[q][0]-1]
    num[BC[q][1]-1] += counter #Ciの数に加える
    num[BC[q][0]-1]=0 #Biと等しい値を0個に
    s += (BC[q][1]- BC[q][0])*counter
    print(s)
### BUGGY CODE ###

#13:12
n,q = map(int,input().split())
import heapq
event = []
for _ in range(n):
  s,t,x = map(int,input().split())
  heapq.heappush(event,(s-x,t-x,x))
t = 0
now = []
for _ in range(q):
  d = int(input())
  if event:
    while event[0][0] <= d:
      tmp = heapq.heappop(event)
      heapq.heappush(now,(tmp[2],tmp[1]))
      if not event:
        break
  if now:
    while now[0][1] <= d:
      heapq.heappop(now)
      if not now:
        print(-1)
        break
    else:
      print(now[0][0])
  else:
    print(-1)

### FIXED CODE ###

#13:12
n,q = map(int,input().split())
import heapq
import sys
input = sys.stdin.readline
event = []
for _ in range(n):
  s,t,x = map(int,input().split())
  heapq.heappush(event,(s-x,t-x,x))
t = 0
now = []
for _ in range(q):
  d = int(input())
  if event:
    while event[0][0] <= d:
      tmp = heapq.heappop(event)
      heapq.heappush(now,(tmp[2],tmp[1]))
      if not event:
        break
  if now:
    while now[0][1] <= d:
      heapq.heappop(now)
      if not now:
        print(-1)
        break
    else:
      print(now[0][0])
  else:
    print(-1)