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

n,w = map(int,input().split())
items = [[0,0] for i in range(n+1)]
dp =[[0 for i in range(w+1)] for i in range(n+1)]

for i in range(1, n+1):
  items[i][0],items[i][1] = map(int,input().split())

for i in range(1,n+1):
  for j in range(1,w+1):
    if items[i][0] <= j:
      dp[i][j] = max(dp[i-1][j],dp[i-1][j-items[i][0]]+items[i][1])
    else:
      dp[i][j] = dp[i-1][j]

print(dp[n][w])

### FIXED CODE ###

from collections import defaultdict
n, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(n)]

dp = defaultdict(int)
dp[0] = 0
for w, v in wv:
    dp_cur = list(dp.items())
    for w_cur, v_cur in dp_cur:
        if w_cur+w <= W:
            dp[w_cur+w] = max(dp[w_cur+w], v_cur+v)
print(max(dp.values()))
### BUGGY CODE ###

import collections
N,K = map(int, input().split())
A = list(map(int, input().split()))
List = {}
for i in A:
    if List.get(i,None)==None:
        List[i]=1
    else:
        List[i]+=1
#c = collections.Counter(List)
#print(min((v, k) for k, v in List.items()))
tmp=0
while(True):
    c = collections.Counter(List)
    if(len(c)<=K):break
    Str=min((v, k) for k, v in List.items())
    tmp+=int(Str[0])
    del List[int(Str[1])]

print(tmp)


### FIXED CODE ###

import heapq

N,K=map(int,input().split())
A=list(map(int,input().split()))
l=[0]*max(A)
ans=0
for item in A:
    l[item-1]+=1
    
heapq.heapify(l)

while len(l)>K:
    ans+=heapq.heappop(l)
    
print(ans)
### BUGGY CODE ###

N=int(input())

min_=100000

for i in range(1, N):
    for j in range(1, N):
        sum_i=0
        sum_j=0
        if i + j == N:
            tmp_i=i
            tmp_j=j
            while tmp_i > 0:
                sum_i += tmp_i % 10
                tmp_i = tmp_i // 10
            while tmp_j > 0:
                sum_j += tmp_j % 10
                tmp_j = tmp_j // 10
            min_=min(min_, sum_i+sum_j)



print(min_)

### FIXED CODE ###

N=int(input())

min_=100000

for i in range(1, N//2+1):
    j=N-i
    sum_i=0
    sum_j=0
    tmp_i=i
    tmp_j=j
    while tmp_i  > 0:
        sum_i += tmp_i % 10
        tmp_i = tmp_i // 10
    while tmp_j > 0:
        sum_j += tmp_j % 10
        tmp_j = tmp_j // 10
    min_=min(min_, sum_i+sum_j)

print(min_)
### BUGGY CODE ###

import itertools

H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
ans = 1e4
for t in itertools.product([0, 1], repeat=H-1):
    cnt = t.count(1)
    SW = []
    tmp = [int(s) for s in S[0]]
    for i, c in enumerate(t):
        if c:
            SW.append(tmp)
            tmp = [int(s) for s in S[i+1]]
        else:
            tmp = [tmp[j] + int(S[i+1][j]) for j in range(W)]
    SW.append(tmp)
    H_ = len(SW)
    sums = [0] * H_
    for w in range(W):
        sumtmp = [sums[i] + SW[i][w] for i in range(H_)]
        if max(sumtmp) > K:
            cnt += 1
            sums = [SW[i][w] for i in range(H_)]
        else:
            sums = sumtmp
    ans = min(ans, cnt)
print(ans)        

### FIXED CODE ###

import itertools

H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
ans = 1e4
for t in itertools.product([0, 1], repeat=H-1):
    cnt = t.count(1)
    SW = []
    tmp = [int(s) for s in S[0]]
    for i, c in enumerate(t):
        if c:
            SW.append(tmp)
            tmp = [int(s) for s in S[i+1]]
        else:
            tmp = [tmp[j] + int(S[i+1][j]) for j in range(W)]
    SW.append(tmp)
    H_ = len(SW)
    sums = [0] * H_
    if max(itertools.chain.from_iterable(SW)) > K:
        continue
    for w in range(W):
        sumtmp = [sums[i] + SW[i][w] for i in range(H_)]
        if max(sumtmp) > K:
            cnt += 1
            sums = [SW[i][w] for i in range(H_)]
        else:
            sums = sumtmp
    ans = min(ans, cnt)
print(ans)
### BUGGY CODE ###

from functools import  reduce
n,k=map(int,input().split())
l=list(map(int,input().split()))
x=reduce(lambda x,y: x*y,l[:k])
temp=[x]
for i in range(k,len(l)):
	x*=l[i]
	x//=l[i-k]
	temp.append(x)
for i in range(1,len(temp)):
	if temp[i]>temp[i-1]:
		print('Yes')
	else:
		print('No')

### FIXED CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
for i in range(k,len(l)):
	if l[i]<=l[i-k]:
		print('No')
	else:
		print('Yes')
### BUGGY CODE ###

n, k = list(map(int, input().split()))
p = list(map(int, input().split()))
exp = [sum([(pi + 1) / 2 for pi in p[i:i+k]]) for i in range(n-k+1)]
print(max(exp))

### FIXED CODE ###

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

rsum = [(p[0] + 1) / 2]
for i in range(1, n):
  rsum.append((p[i] + 1) / 2 + rsum[i-1])
  
result = 0
if (n == k):
  result = rsum[-1]

else:
  for i in range(n-k):
    if result < rsum[i+k] - rsum[i]:
      result = rsum[i+k] - rsum[i]

print(result)
### BUGGY CODE ###

A, B, C = map(int, raw_input().split())
memo = [[A, B, C]]
queue = [[0, [A, B, C]]]
while queue != []:
	now = queue.pop(0)
	if now[1][0] == now[1][1] and now[1][0] == now[1][2]:
		print now[0]
		break
	next = []
	for i in range(0, 3):
		lst1 = [now[1][0], now[1][1], now[1][2]]
		lst2 = [now[1][0]+1, now[1][1]+1, now[1][2]+1]
		lst1[i] += 2
		lst2[i] -= 1
		next.append(lst1)
		next.append(lst2)
	for i in range(0, 6):
		if next[i] not in memo:
			memo.append(next[i])
			queue.append([now[0]+1, next[i]])


### FIXED CODE ###

inpt = map(int, raw_input().split())
inpt.sort()
A = inpt[0]
B = inpt[1]
C = inpt[2]
tmp1 = (C-A)/2
tmp2 = (C-B)/2
A += tmp1*2
B += tmp2*2
memo = []
queue = [[tmp1+tmp2, [A, B, C]]]
while queue != []:
	now = queue.pop(0)
	if now[1][0] == now[1][1] and now[1][0] == now[1][2]:
		print now[0]
		break
	next = []
	for i in range(0, 3):
		lst1 = [now[1][0], now[1][1], now[1][2]]
		lst2 = [now[1][0]+1, now[1][1]+1, now[1][2]+1]
		lst1[i] += 2
		lst2[i] -= 1
		next.append(lst1)
		next.append(lst2)
	for i in range(0, 6):
		if next[i] not in memo:
			queue.append([now[0]+1, next[i]])
### BUGGY CODE ###

import math
N=int(input())
A=list(map(int,input().split()))
ans1 = A[0]
ans2 = 0
f = True
for i in range(1, N):
    ans1 = math.gcd(ans1, A[i])
    for j in range(i+1, N):
        ans2 = math.gcd(A[i-1],A[j-1])
        if (ans2 > 1):
            f = False

if f:
    print('pairwise coprime')
else:
    if ans1==1:
        print('setwise coprime')
    else:
        print('not coprime')


### FIXED CODE ###

from math import gcd

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

# setwise validation
tmp = 0
for a in A:
    tmp = gcd(tmp, a)
isSetwise = (tmp == 1)

# pairwise validation
M = 10 ** 6
sieve = [0] * (M + 1)
for a in A:
    sieve[a] += 1

cnt = 0
isPairwise = True
for i in range(2, M + 1):
    isPairwise &= (sum(sieve[j] for j in range(i, M + 1, i)) <= 1)

# check
if isPairwise:
    ans = 'pairwise coprime'
elif isSetwise:
    ans = 'setwise coprime'
else:
    ans = 'not coprime'
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

for i in range(M):
  max_index = A.index(max(A))
  A[max_index] = A[max_index]//2

print(sum(A))

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = [-i for i in map(int, input().split())]
heapq.heapify(A)
for i in range(M):
  tmp = -((-heapq.heappop(A))//2)
  heapq.heappush(A, tmp)

print(-sum(A))
### BUGGY CODE ###

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

if 0 in list:
    ans=0
else:
    ans=1
    for i in range(n):
        ans=ans*list[i]

    if ans>10**18:
        ans=-1

print(ans)

### FIXED CODE ###

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

if 0 in list:
    ans=0
else:
    ans=1
    for i in range(n):
        ans=ans*list[i]
        if ans>10**18:
            ans=-1
            break

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

import heapq
from collections import defaultdict


class Dijkstra(object):

    """ 使用例
    dik = Dijkstra()
    edge = defaultdict(list)
    edge[(1, 1)].append([1, (1, 2)])
    edge[(1, 2)].append([1, (1, 1)])
    edge[(1, 2)].append([2, (2, 1)])
    edge[(2, 1)].append([2, (1, 2)])
    edge[(2, 1)].append([5, (2, 2)])
    edge[(2, 2)].append([5, (2, 1)])
    edge[(2, 2)].append([3, (1, 2)])
    edge[(1, 2)].append([3, (2, 2)])

    s0 = (1, 1)
    ans = dik(s0, edge)

    """

    def __init(self):
        pass

    def __call__(self, s0, edge):

        # s0:始点 (,,,)
        # edge[(,,,)] = [コスト、(,,,)], [コスト、(,,,)]

        d = defaultdict(lambda: float('inf'))
        used = defaultdict(lambda: True)

        edgelist = edge[s0]
        heapq.heapify(edgelist)

        d[s0] = 0
        used[s0] = False

        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            if not used[minedge[1]]:
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = False

            for e in edge[v]:
                if used[e[1]]:
                    heapq.heappush(edgelist, [e[0] + d[v], e[1]])

        return d


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

s_max = 3000
S = min(S, s_max)

dik = Dijkstra()
edge = defaultdict(list)
s0 = (1, S)


for m in range(1, M + 1):
    U, V, A, B = map(int, input().split())
    for s in range(A, s_max + 1):
        edge[(U, s)].append([B, (V, s - A)])
        edge[(V, s)].append([B, (U, s - A)])

for n in range(1, N + 1):
    C, D = map(int, input().split())
    for s in range(s_max + 1):
        s1 = min(s + C, s_max)
        edge[(n, s)].append([D, (n, s1)])

d = dik(s0, edge)

for n in range(2, N + 1):
    ans = []
    for s in range(s_max + 1):
        ans.append(d[(n, s)])
    print(min(ans))


### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline
 
INF = 10 ** 18
 
class Edge():
    def __init__(self, end, cost, time):
        self.end = end
        self.cost = cost
        self.time = time
 
dp = []
h = []
 
def push(t, v, x):
    if x < 0:
        return
    if dp[v][x] <= t:
        return
    dp[v][x] = t
    heapq.heappush(h, (t, v, x))
 
def dijkstra(n, G, cd, start, s, max_s):
    global dp
    dp = [[INF for j in range(max_s+1)] for i in range(n)] 
    push(0, start, s)
 
    while h:
        # 使っていない頂点のうち、現時点で最も到達短時間が短いものを選びvとする
        t, v, x = heapq.heappop(h)
        if dp[v][x] < t:
            continue
        # 両替
        if x < max_s:
            push(t+cd[v][1], v, min(x+cd[v][0], max_s))
        # vから到達可能な頂点について、到達時間が短くなれば更新
        for e in G[v]:
            push(t+e.time, e.end, x-e.cost)
 
 
n, m, s = map(int, input().split())
uvab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(n)]
 
es = [[] for i in range(n)]
max_s = 50 * (n-1)
 
for u, v, a, b in uvab:
    es[u-1].append(Edge(v-1,a,b))
    es[v-1].append(Edge(u-1,a,b))
 
dijkstra(n, es, cd, 0, min(max_s,s), max_s)
 
for i in range(1, n):
    print(min(dp[i]))
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
n, k = map(int, input().split())
x = list(map(int, input().split()))
count = 1
machi = 0
machi_list = [0]
next_machi = x[machi] - 1
while True:
    if next_machi in machi_list:
        break
    count += 1
    machi_list.append(next_machi)
    machi = next_machi
    next_machi = x[machi] - 1

z = 0
for i in range(0, count):
    if machi_list[i] == next_machi:
        z = i
        break
loop_machi_list = machi_list[z:]
if k < z:
    machi = machi_list[k] + 1
    print(machi)
else:
    k = k - z
    machi = loop_machi_list[k % len(loop_machi_list)] + 1
    print(machi)

### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
n, k = map(int, input().split())
x = list(map(int, input().split()))
count = 1
machi = 0
machi_list = [0]
next_machi = x[machi] - 1
machi_dict = {}
while True:
    if next_machi in machi_dict:
        break
    count += 1
    machi_dict[next_machi] = 1
    machi_list.append(next_machi)
    machi = next_machi
    next_machi = x[machi] - 1

z = 0
for i in range(0, count):
    if machi_list[i] == next_machi:
        z = i
        break
loop_machi_list = machi_list[z:]
if k < z:
    machi = machi_list[k] + 1
    print(machi)
else:
    k = k - z
    machi = loop_machi_list[k % len(loop_machi_list)] + 1
    print(machi)
### BUGGY CODE ###

# input
S = input()
N = len(S)

# check
cnt = 0
del_ind = []
append = del_ind.append

while N > 1:
    for i in range(1, N):
        if S[i - 1:i + 1] in ["01", "10"]:
            cnt += 2
            N -= 2
            S = S[:i - 1] + S[i + 1:]
            break
print(cnt)

### FIXED CODE ###

# input
S = input()
N = len(S)

# check
print(min(S.count("0"), S.count("1")) * 2)
### BUGGY CODE ###

n=m=int(input())
i=2
while i<=n and m!=1:
    if m%i==0:
        n=n*(i-1)//i
        while m%i==0: m//=i
    i+=1
print(n)

### FIXED CODE ###

n=m=int(input())
i=2
while i*i<=n:
    if n%i==0:
        m=m//i*(i-1)
        while n%i==0: n//=i
    i+=1
if n!=1:m=m//n*(n-1)
print(m)
### BUGGY CODE ###

K,S = map(int,input().split())
count = 0
for i in range(K+1):
    if i == S:
        count += 1
        break
    for j in range(K+1):
        if i + j == S:
            count += 1
            break
        for k in range(K+1):
            if i+j+k == S:
                count += 1
print(count)

### FIXED CODE ###

K,S = map(int,input().split())
count = 0
for x in range(K+1):
    for y in range(K+1):
        z = S - x - y
        if 0 <= z <= K:
            count += 1
print(count)
### BUGGY CODE ###

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

y=1
for i in range(n):
   y*=a[i]
   
if(y>10**18):
       print(-1)
else :
       print(y)

### FIXED CODE ###

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


if 0 in a :
    print(0)
    exit() ##インタラクティブシェルを終了させる関数

y=1
for i in range(n):
   y*=a[i]
   if(y>10**18):
       print(-1)
       exit()
print(y)
### BUGGY CODE ###

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

rgb = {'R', 'G', 'B'}

res = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        if S[i] != S[j]:
            tmp = rgb
            tmp = tmp - {S[i], S[j]}
            ok = True
            k = j
            while ok:
                k = S.find(list(tmp)[0], k + 1)
                if k == -1:
                    ok = False
                elif k - j != j - i:
                    res += 1
                else:
                    pass
print(res)


### FIXED CODE ###

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

R = S.count('R')
G = S.count('G')
B = S.count('B')

res = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        k = j + j - i
        if k >= N:
            break
        if S[i] != S[j] and S[j] != S[k] and S[i] != S[k]:
            res += 1

res = R * G * B - res
print(res)
### BUGGY CODE ###

n=int(input())
strl=[list(input()) for i in range(n)]
"""
def anagram(sa,sb) :
  flag=True
  sal=list(sa)
  sbl=list(sb)
  sal.sort()
  sbl.sort()
  if sal==sbl:
    return True
  else :
    return False
  
  for i in range(10) :
    if sal[i] in sbl :
      sbl.remove(sal[i])
    else :
      flag=False
      break

  """
  #return flag
   
#print(anagram("peanutbomb","constraint"))    
count=0
for i in range(n) :
  jl=list(range(i+1,n))
  for j in jl :
    flag=True
    sal=strl[i]
    sbl=strl[j]
    sal.sort()
    sbl.sort()
    if sal==sbl:
      count+=1
    """
    flag=True
    sal=list(strl[i])
    sbl=list(strl[j])
    for k in range(10):
      tmp=sal[k]
      if tmp in sbl :
        sbl.remove(tmp)
      else :
        flag=False
        break
     
    if flag :
      count+=1
    """
print(count)

### FIXED CODE ###

#import numpy as np
n=int(input())
strl=[list(input()) for i in range(n)]

count=0
pt={}
#il=np.arange(n)
for i in range(n) :
  sal=strl[i]
  sal.sort()
  temp="".join(sal)
  if temp in pt.keys() :
    #ptがある
    tempc=pt[temp]
    count+=tempc
    pt[temp]=tempc+1
  else :
    pt[temp]=1
print(count)
#print(count)
### BUGGY CODE ###

n,k,*a=map(int,open(0).read().split())
for _ in range(k):
  b=[0]*n
  for i,q in enumerate(a):
    b[max(0,i-q)]+=1
    if i+q+1<n:
      b[i+q+1]-=1
  for i in range(1,n):
    b[i]+=b[i-1]
  if a==b:
    break
  a=b[:]
print(*a)

### FIXED CODE ###

# coding: utf-8
# Your code here!
import time
t1=time.time()
def LI():return list(map(int,input().split()))
n,k=LI()
a=LI()

for _ in range(k):
    tab=[0]*(n)
    for i in range(n):
        q=a[i]
        if 0<=i-q:
            tab[i-q]+=1
        else:
            tab[0]+=1
        if i+q+1<=n-1:
            tab[i+q+1]-=1
        else:
            pass
    b=[tab[0]]
    for i in range(n-1):
        b.append(tab[i+1]+b[-1])
    a=b[:]
    if time.time()-t1>1.5:
        print(*a)
        exit()
print(*a)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict


def solve():
  ## input
  N = int(input())
  An = [[i-1 for i in list(map(int, input().split()))] for _ in range(N)]  

  ## solve
  ret = 0
  Pn = [0 for _ in range(N)]
  rev = 0
  while rev < N-1:
    dct = defaultdict(lambda:set([]))
    game = 0
    rev = N
    for i in range(N):
      if Pn[i] >= N-1:
        continue
      else:
        j = An[i][Pn[i]]
        if i in dct[j]:
          dct[j].remove(i)
          game,Pn[i],Pn[j] = [game+1,Pn[i]+1,Pn[j]+1]
          rev = min(rev,Pn[i],Pn[j])
        else:
          dct[i].add(j)
    if game > 0:
      ret += 1
    else:
      return -1
  return ret

print(solve())


### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import deque,defaultdict
from sys import stdin



def solve():
  ## input
  N = int(input())
  An = [deque([i-1 for i in list(map(int, stdin.readline().rstrip().split()))]) for _ in range(N)]

  ## solve
  Pn = set([i for i in range(N)])
  count = 0
  while len(Pn) > 0:
    Qn = set([])
    dct = defaultdict(lambda:set([]))
    for i in Pn:
      j = An[i][0]
      if i in dct[j]:
        An[i].popleft()
        if len(An[i]) > 0:
          Qn.add(i)
          Qn.add(An[i][0])
        An[j].popleft()
        if len(An[j]) > 0:
          Qn.add(j)
          Qn.add(An[j][0])
      else:
        dct[i].add(j)
    Pn = Qn
    count += 1
  for i in range(N):
    if len(An[i]) > 0:
      return -1
  return count



print(solve())
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 998244353
 
n, s = map(int, input().split())
a = [int(item) for item in input().split()]
# dp[i-th item][j val] : tuple(cnt, used cnt)
dp = [[dict() for _ in range(s+1)] for _ in range(n + 1)]
dp[0][0][0] = 1
 
for i, item in enumerate(a):
    for j in range(s):
        for uc, c in dp[i][j].items():
            if uc not in dp[i+1][j]:
                dp[i+1][j][uc] = c
            else:
                dp[i+1][j][uc] += c
            if j + item > s:
                continue
            if uc + 1 not in dp[i+1][j + item]:
                dp[i+1][j + item][uc + 1] = c
            else:
                dp[i+1][j + item][uc + 1] += c
 
ans = 0
for dics in dp:
    for key, val in dics[-1].items():
        ans += pow(2, n - key, MOD) * val
        ans %= MOD
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 998244353

n, s = map(int, input().split())
a = [int(item) for item in input().split()]

dp = [[0] * (s + 1) for _ in range(n+1)]
dp[0][0] = 1

for i, item in enumerate(a):
    for j in range(s, -1, -1):
        if dp[i][j] == 0:
            continue
        if j + item <= s:
            dp[i+1][j+item] += dp[i][j] 
        dp[i+1][j] += dp[i][j] * 2
        dp[i+1][j] %= MOD

print(dp[-1][-1] % MOD)
### BUGGY CODE ###

# abc177_c.py
N = int(input())
A = list(map(int,input().split()))
ans = 0
mod = 10**9+7
for i in range(N-1):
    for j in range(i+1,N):
        if i != j:
            ans+=A[i]*A[j]
            ans%=mod
print(ans%mod)


### FIXED CODE ###

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    square = []
    for i in A:
        square.append(i**2)
    return (sum(A)**2 - sum(square))//2 % (10**9+7)


print(solve())
### BUGGY CODE ###

def resolve():
    '''
    code here
    '''
    import collections

    H, W = [int(item) for item in input().split()]
    Ch, Cw = [int(item)-1 for item in input().split()]
    Dh, Dw = [int(item)-1 for item in input().split()]
    grid = [[item for item in input()] for _ in range(H)]

    fp = [[10**6 for _ in range(W)] for _ in range(H)]

    que = collections.deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0
    next_y_x = [[0, 1], [1, 0], [-1, 0], [0, -1]]
    w_goto = []
    for i in range(5):
        for j in range(5):
            if [i, j] in next_y_x:
                pass
            else:
                w_goto.append([-2 + i, -2 + j])
    w_goto.remove([0,0])

    while que:
        temp = que.popleft()
        w_num = temp[2]

        for dy, dx in next_y_x:
            ny = temp[0] + dy
            nx = temp[1] + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1:
                if grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                    que.append([ny, nx, temp[2]])
                    fp[ny][nx] = w_num
        
        cnt = 0
        for dy, dx in w_goto:
            nwy = temp[0] + dy
            nwx = temp[1] + dx
            nw = w_num +1

            if 0 <= nwy <= H-1 and 0 <= nwx <= W-1 and cnt <= 10:
                if grid[nwy][nwx] == '.' and fp[nwy][nwx] > w_num:
                    que.append([nwy, nwx, nw])
                    fp[nwy][nwx] = nw
                    cnt += 1

    if fp[Dh][Dw] != 10**6:
        print(fp[Dh][Dw])
    else:
        print(-1)

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    '''
    code here
    '''
    from collections import deque

    H, W = [int(item) for item in input().split()]
    Ch, Cw = [int(item)-1 for item in input().split()]
    Dh, Dw = [int(item)-1 for item in input().split()]
    grid = [input() for _ in range(H)]
    max_num = 10**6
    fp = [[max_num] * W for _ in range(H)]

    que = deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while que:
        y, x, w_num = que.popleft()

        for dy, dx in walk:
            ny = y + dy
            nx = x + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                que.appendleft([ny, nx, w_num])
                fp[ny][nx] = w_num

        for dy, dx in warp:
            ny = y + dy
            nx = x + dx
            nw = w_num +1

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > nw:
                que.append([ny, nx, nw])
                fp[ny][nx] = nw

    if fp[Dh][Dw] != max_num:
        print(fp[Dh][Dw])
    else:
        print(-1)

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

def main():
    inf = 10 ** 9 + 5
    n = int(input())
    n2 = 2 ** n
    s = list(map(int, input().split()))
    s.sort(reverse=True)
    # print(s)
    pp = [s[0]]
    s[0] = inf
    for _ in range(n):
        np = pp[:]
        while pp:
            p = pp.pop()
            i = 1
            while 1:
                if s[i] < p:
                    np.append(s[i])
                    s[i] = inf
                    break
                else:
                    i += 1
                if i == n2:
                    print("No")
                    exit()
        pp = np
    print("Yes")

main()


### FIXED CODE ###

def main():
    inf = 10 ** 9 + 5
    n = int(input())
    n2 = 2 ** n
    s = list(map(int, input().split()))
    s.sort(reverse=True)
    # print(s)
    pp = [s[0]]
    s[0] = inf
    for _ in range(n):
        pp.sort()
        i = 1
        np = pp[:]
        while pp:
            p = pp.pop()
            while 1:
                if s[i] < p:
                    np.append(s[i])
                    s[i] = inf
                    break
                else:
                    i += 1
                if i == n2:
                    print("No")
                    exit()
        pp = np
    print("Yes")

main()