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

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

if p == 1:
    print(1)
else:
    g = 1
    r = 1
    while g**n <= p:
        if p%(g**n) == 0:
            r = g
        g += 1
    print(r)

### FIXED CODE ###

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

if p == 1:
    print(1)
elif n == 1:
    print(p)
else:
    for i in range(round(p**(1/n)), 0, -1):
        if p % i**n == 0:
            print(i)
            break
### BUGGY CODE ###

n = int(input())
s = input()

def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j] and j < i:
        	j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A
ans = 0
for i in range(n-1):
	tmp = z_algo(s[i:])
	res = max(tmp[1:])
	if ans < res:
		ans = res

print(ans)


### FIXED CODE ###

n = int(input())
s = input()

def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
        	j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A
ans = 0
for i in range(n-1):
	tmp = z_algo(s[i:])
	for j,zj in enumerate(tmp):
		if j+1 > zj:
			ans = max(ans,zj)

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

N = int(input())
D = {}
for i in range(N):
    s = input()
    if s in D:
        D[s] += 1
    else:
        D[s] = 0
E = sorted(D.items())
G = [j[0] for j in E if j[1] == max(D.values())]
print(*G, sep="\n")

### FIXED CODE ###

import collections
N = int(input())
D = collections.Counter(input() for i in range(N))
maximum = max(D.values())
sort = sorted(key for key,value in D.items() if value == maximum)
for s in sort:
    print(s)
### BUGGY CODE ###

class Segtree:
    def __init__(self, original, func, element):
        self.n = len(original)
        self.element = element
        self.func = func
        self.N0 = 1 << (self.n-1).bit_length()
        self.seg = [element]*(self.N0 << 1)
        for i, j in enumerate(original, self.N0):
            self.seg[i] = j
        for i in range(self.N0-1, 0, -1):
            self.seg[i] = func(self.seg[2*i], self.seg[2*i+1])

    def get(self, i):
        return self.seg[i+self.N0]
        
    def update(self, i, x):
        i += self.N0
        self.seg[i] = x
        while i > 1:
            y = self.seg[i ^ 1]
            i >>= 1
            x = self.func(x, y)
            self.seg[i] = x
                
    def add(self, i, d):
        self.update(i, self.get(i)+d)
        
    def query(self, l, r):
        l += self.N0
        r += self.N0
        nl = self.element
        nr = self.element
        while l < r:
            if l & 1:
                nl = self.func(nl, self.seg[l])
                l += 1
            if r & 1:
                nr = self.func(nr, self.seg[r-1])
            l >>= 1
            r >>= 1
     
        return self.func(nl, nr)

n, m = map(int, input().split())
L = Segtree([0]*(m+2), lambda x, y:x+y, 0)
LR = [list(map(int, input().split())) for _ in range(n)]
for l, r in LR:
  L.add(l, 1)
  L.add(r+1, -1)
S = sorted([(r-l+1, l, r) for l, r in LR])
cnt = 0
A = []
for i in range(m, 0, -1):
  while S and S[-1][0] == i:
    c, l, r = S.pop()
    cnt += 1
    L.add(l, -1)
    L.add(r+1, 1)
  res = cnt
  for j in range(0, m+1, i):
    res += L.query(0, j+1)
  A.append(res)
print(*A[::-1], sep="\n")

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
  n, m = map(int, input().split())
  LR = [list(map(int, input().split())) for _ in range(n)]
  
  BIT = [0]*(m+2)
  def add(i, a):
    while i <= m+1:
      BIT[i] += a
      i += i&(-i)
  def bit_sum(i):
    res = 0
    while i > 0:
      res += BIT[i]
      i -= i&(-i)
    return res
  
  for l, r in LR:
    add(l, 1)
    add(r+1, -1)
  
  S = sorted([(r-l+1, l, r) for l, r in LR])
  cnt = 0
  L = []
  for i in range(m, 0, -1):
    while S and S[-1][0] == i:
      c, l, r = S.pop()
      cnt += 1
      add(l, -1)
      add(r+1, 1)
    res = cnt
    for j in range(0, m+1, i):
      res += bit_sum(j)
    L.append(res)
  print(*L[::-1], sep="\n")

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

#input
N, M = map(int, input().split())
x, y = [0]*M, [0]*M
for i in range(M):
    x[i], y[i] = map(int, input().split())

#output
#便宜的にすべての点を-1しておく。
#dp[i]を頂点iから始まるpathで最長の長さとする。
#dp[i] = max(dp[v]+1)(vは頂点iから到達できる任意の頂点)
z = [[]] * N
for xitem in x:
    z[xitem-1] = [yitem-1 for i, yitem in enumerate(y) if x[i] == xitem]

visited = [False] * N
memo = [0] * N
dp = [0] * N

def dp(v):
    if visited[v]:
        return memo[v]
    else:
        res = 0
        for u in z[v]:
            res = max(res, dp(u)+1)
        memo[v] = res
        visited[v] = True
        return res
for i in range(N):
    dp(i)

print(max(memo))

### FIXED CODE ###

#input
import sys
sys.setrecursionlimit(10**7)
N, M = map(int, input().split())
z = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    z[x-1].append(y-1)

#output
#便宜的にすべての点を-1しておく。
#dp[i]を頂点iから始まるpathで最長の長さとする。
#dp[i] = max(dp[v]+1)(vは頂点iから到達できる任意の頂点)

visited = [False] * N
memo = [0] * N

def dp(v):
    if visited[v]:
        return memo[v]
    else:
        res = 0
        for u in z[v]:
            res = max(res, dp(u)+1)
        memo[v] = res
        visited[v] = True
        return res
for i in range(N):
    dp(i)

print(max(memo))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a2 = [0]
cnt = 0
for i in a:
    a2.append(a2[-1] + i)

info = list(set(a2))
chm = []
for k in info:
    chm.append(a2.count(k))

for j in chm:
    if j == 2:
        cnt += 1
    elif j == 1:
        continue
    else:
        cnt += j * (j - 1) // 2
print(cnt)

### FIXED CODE ###


n = int(input())
a = list(map(int, input().split()))
a2 = [0]
cnt = 0
tmp = 0
for i in a:
    a2.append(a2[-1] + i)

a2.sort()
for j in range(n):
    if a2[j] == a2[j+1]:
        tmp += 1
    else:
        if tmp >= 2:
            cnt += tmp*(tmp+1)//2
            tmp = 0
        else:
            cnt += tmp
            tmp = 0
if tmp != 0:
    if tmp >= 2:
        cnt += tmp*(tmp+1)//2
        tmp = 0
    else:
        cnt += tmp
        tmp = 0
print(cnt)
### BUGGY CODE ###

import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
    
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


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

#if gcd(*A) % 2 != 0:
    #print(0)
    #exit(0)

#sisu_2 = factorization(A[0])[0][1] 
sisu_2 = min([factorization(A[i])[0][1] for i in range(N)])

#lcm_a = lcm(*A)
#lcm_a_half = lcm_a // 2
lcm_a = lcm(*A) // 2
'''
l = []
sisu_a0 = 0
for i in range(N):
    sisu = 0
    while A[i]%2==0:
        A[i] //= 2
        sisu += 1
    
    if sisu_a0==0:
        sisu_a0 = sisu
    else:
        if sisu_a0!=sisu:
            print(0)
            exit()
'''
if (lcm_a % (2**sisu_2) == 0) or lcm_a > M:
#factorization(lcm_a)[0][1] != sisu_2 or lcm_a_half > M:
#if lcm_a > M:
    print(0)
    exit(0)
else:
    print(int((M-lcm_a) // (lcm_a*2) + 1))

### FIXED CODE ###

import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
    
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


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

#if gcd(*A) % 2 != 0:
    #print(0)
    #exit(0)

#sisu_2 = factorization(A[0])[0][1] 

#lcm_a = lcm(*A)
#lcm_a_half = lcm_a // 2
lcm_a = lcm(*A) // 2

l = []
sisu_a0 = 0
for i in range(N):
    sisu = 0
    while A[i]%2==0:
        A[i] //= 2
        sisu += 1
    
    if sisu_a0==0:
        sisu_a0 = sisu
    else:
        if sisu_a0!=sisu:
            print(0)
            exit()
#if (lcm_a % (2**sisu_2) == 0) or lcm_a > M:
#if factorization(lcm_a)[0][1] != sisu_2 or lcm_a_half > M:
if lcm_a > M:
    print(0)
    exit(0)
else:
    print(int((M-lcm_a) // (lcm_a*2) + 1))
### BUGGY CODE ###

# スペース区切りの整数入力
N,M = map(int, input().split())
#指定数分の３つの整数を順番に受けてリストに入力
move = []
for i in range(M):
    move.append(list(map(int, input().split())))

dp = [0] * (N+1)
done_n = -1

def findpath(now_x):
    if now_x <= done_n:
        return dp[now_x]
    for x,y in move:
        if now_x == x:
            dp[now_x] = max(dp[now_x],findpath(y) + 1)
    return dp[now_x]

maxpath = 0
for do_n in range(1,N+1):
    done_n = do_n - 1
    maxpath = max(maxpath,findpath(do_n))

print(maxpath)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)

# スペース区切りの整数入力
N,M = map(int, input().split())
#指定数分の３つの整数を順番に受けてリストに入力
move = {}
for i in range(M):
    x,y = map(int, input().split())
    move.setdefault(x,[]).append(y)

dp = [-1] * (N+10)

def findpath(now_x):
    if dp[now_x] > -1:
        return dp[now_x]
    maxpath = 0
    if now_x in move.keys():
        for y in move[now_x]:
            maxpath = max(maxpath,findpath(y) + 1)
    dp[now_x] = maxpath
    return maxpath

Ans = 0
for do_x in range(1,N+1):
    Ans = max(Ans,findpath(do_x))

print(Ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():

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

    # bit全探索
    # https://qiita.com/gogotealove/items/11f9e83218926211083a#%E4%BE%8B%E9%A1%8C-1
    ans=0
    for i in range(2 ** N):
        cnt = 0
        for j in range(N):  # このループが一番のポイント
            if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
                cnt+=A[j]
        if cnt%2==P:
            ans+=1
    print(ans)



resolve()

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    N, P = map(int, input().split())
    A = list(map(int, input().split()))
    even=0
    odd=0
    for i in range(N):
        if A[i] % 2==0:
            even+=1
    odd=N-even

    if odd==0:
        print(2**N if P==0 else 0)
    else:
        print(2**(N-1))

resolve()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
s = input()
len_s = len(s)
k = int(input())
substring_list = []
sappend = substring_list.append
for i in range(len_s):
    for j in range(i,len_s):
        sappend(s[i:j+1])
substring_set = set(substring_list)
print(sorted(substring_set)[k-1])

### FIXED CODE ###

# -*- coding: utf-8 -*-
s = input()
len_s = len(s)
k = int(input())
substring_list = []
sappend = substring_list.append
for i in range(len_s):
    for j in range(5):
        sappend(s[i:min(i+1+j,len_s)])
substring_set = set(substring_list)
print(sorted(substring_set)[k-1])
### BUGGY CODE ###

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

ans = 0
for i in range(n):
  j = 0
  sum = 0
  xorsum = 0
  while i + j < n:
    sum = sum + li[i+j]
    xorsum = xorsum ^ li[i+j]
    if sum == xorsum:
      ans = ans + 1
    j = j + 1

print(ans)

### FIXED CODE ###

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

ans = 0
w_xor,w_sum = A[0],A[0]
l,r = 0,0

while l < N and r < N:
  #print(l,r,w_xor, w_sum)

  if w_xor == w_sum:
    if r < N-1:
    #print(l,r)
      r += 1
      w_xor = w_xor ^ A[r]
      w_sum = w_sum + A[r]
      continue
    else:
      ans += 1+r-l
  else:
    # l,r-1、までがマッチしてたということなので1小さい
    ans += r-l
  w_xor = w_xor ^ A[l] 
  w_sum = w_sum - A[l]
  l += 1
  
print(ans)
### BUGGY CODE ###

from fractions import gcd

MOD = 10**9 + 7
N = int(input())
A = list(map(int, input().split()))

l = A[0]
for a in A:
  l = l * a // gcd(l, a)

ans = 0
for a in A:
  ans += (l//a) % MOD
  ans %= MOD

print(ans)

### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def power(n, r, mod=10**9+7):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod


MOD = 10**9 + 7
N = int(input())
A = list(map(int, input().split()))

l = A[0]
for a in A:
  t = l%a
  if t != 0:
    l = lcm(l, a)

l %= MOD
ans = 0
for a in A:
  ans += (l * power(a, MOD-2)) % MOD
  ans %= MOD

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

h,n = map(int,input().split())
li2=[input() for i in range(n)]
ab = []
for i in range(n):
    ab.append( [int(x.strip()) for x in li2[i].split()])
w = (int(h/ab[0][0])+1) * ab[0][1]
dp = [[0] * (w+1) for i in range(n+1)]

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

ans = 0
for i in range(w+1):
    if dp[n][i] >= h:
        print(i)
        exit()

### FIXED CODE ###

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

x = []
for i in range(a[1]):
    x1, y1 = [int(i) for i in input().split()]
    x.append((x1, y1))

max_tup = max(x, key=lambda x: x[0])
max_a = max_tup[0]
dp = [0] * (HP + max_a)

for i in range(1, len(dp)):
    dp[i] = min(dp[i - a] + b for a, b in x)

print(dp[HP])
### BUGGY CODE ###

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

index=0
while index < n:
    a = listA[index]
    if index%2==0:
        listC=[a]
        listC.extend(listB)
        listB=listC
    else:
        listB.append(a)
    index+=1
if n%2==0:
    listB.reverse()

print(" ".join(list(map(str, listB))))

### FIXED CODE ###

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

stA=""
if n%2 == 0:
    index = len(listA)-1
    while index > 0:
        if index== len(listA)-1:
            stA +=str(listA[index])
        else:
            stA+=" "+str(listA[index])
        index-=2
    index = 0
    while index < len(listA)-1:
        stA+=" "+str(listA[index])
        index+=2
else:
    index = len(listA)-1
    while index > -1:
        if index == len(listA)-1:
            stA += str(listA[index])
        else:
            stA += " "+str(listA[index])
        index -= 2
    index = 1
    while index < len(listA)-1:
        stA += " "+str(listA[index])
        index += 2
        
print(stA)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
Max = 2000
def l():
    return list(map(int,input().split()))
def m():
    return map(int,input().split())

h,w = m()

aa = [[] for i in range(h)]
aaa = []
ma = 0
for i in range(h):
    k = list(input())
    for j in range(w):
        if k[j] == "#":
            aa[i].append(0)
            aaa.append([i,j])
        else:
            aa[i].append(Max)
kk = []
while True:
    if len(aaa) == 0:
        break
    for i in range(len(aaa)):
        c,v = aaa.pop(-1)
        if not c == 0:
            if aa[c-1][v] > aa[c][v]+1:
                aa[c-1][v] = aa[c][v]+1
                kk.append([c-1,v])
                ma = max(ma,aa[c-1][v])
        if not c == h-1:
            if aa[c+1][v] > aa[c][v]+1:
                aa[c+1][v] = aa[c][v]+1
                kk.append([c+1,v])
                ma = max(ma,aa[c+1][v])
        if not v == 0:
            if aa[c][v-1] > aa[c][v]+1:
                aa[c][v-1] = aa[c][v]+1
                kk.append([c,v-1])
                ma = max(ma,aa[c][v-1])
        if not v == w-1:
            if aa[c][v+1] > aa[c][v]+1:
                aa[c][v+1] = aa[c][v]+1
                kk.append([c,v+1])
                ma = max(ma,aa[c][v+1])
    aaa = kk
    kk = []
print(ma)
        


### FIXED CODE ###

import sys
input = sys.stdin.readline
Max = 2000
def l():
    return list(map(int,input().split()))
def m():
    return map(int,input().split())

h,w = m()

aa = [[] for i in range(h)]
aaa = []
ma = 0
for i in range(h):
    k = list(input())
    for j in range(w):
        if k[j] == "#":
            aa[i].append(0)
            aaa.append([i,j])
        else:
            aa[i].append(Max)
kk = []
while True:
    if len(aaa) == 0:
        break
    for i in range(len(aaa)):
        c,v = aaa[i]
        if not c == 0:
            if aa[c-1][v] > aa[c][v]+1:
                aa[c-1][v] = aa[c][v]+1
                kk.append([c-1,v])
                ma = max(ma,aa[c-1][v])
        if not c == h-1:
            if aa[c+1][v] > aa[c][v]+1:
                aa[c+1][v] = aa[c][v]+1
                kk.append([c+1,v])
                ma = max(ma,aa[c+1][v])
        if not v == 0:
            if aa[c][v-1] > aa[c][v]+1:
                aa[c][v-1] = aa[c][v]+1
                kk.append([c,v-1])
                ma = max(ma,aa[c][v-1])
        if not v == w-1:
            if aa[c][v+1] > aa[c][v]+1:
                aa[c][v+1] = aa[c][v]+1
                kk.append([c,v+1])
                ma = max(ma,aa[c][v+1])
    aaa = kk
    kk = []
print(ma)
### BUGGY CODE ###

from queue import Queue as queue

def main():
    h, w = map(int, input().split())
    s = [input() for i in range(h)]

    inf = h * w
    dp = [[inf for j in range(w)] for i in range(h)]

    q = queue()
    for i, si in enumerate(s):
        for j, sij in enumerate(si):
            if sij == '#':
                q.put((i, j))
                dp[i][j] = 0

    dijs = list(zip([-1, 0, 1, 0], [0, -1, 0, 1]))
    while not q.empty():
        i, j = q.get()
        for di, dj in dijs:
            ni = i + di
            nj = j + dj
            if not (0 <= ni < h and 0 <= nj < w): continue
            if dp[ni][nj] <= dp[i][j] + 1: continue
            q.put((ni, nj))
            dp[ni][nj] = dp[i][j] + 1

    print(max(max(dpi) for dpi in dp))

main()

### FIXED CODE ###

from collections import deque

def main():
    h, w = map(int, input().split())
    s = [input() for i in range(h)]

    inf = h * w
    dp = [[inf for j in range(w)] for i in range(h)]

    q = deque()
    for i, si in enumerate(s):
        for j, sij in enumerate(si):
            if sij == '#':
                q.append((i, j))
                dp[i][j] = 0

    dijs = list(zip([-1, 0, 1, 0], [0, -1, 0, 1]))
    while q:
        i, j = q.popleft()
        for di, dj in dijs:
            ni = i + di
            nj = j + dj
            if not (0 <= ni < h and 0 <= nj < w): continue
            if dp[ni][nj] <= dp[i][j] + 1: continue
            q.append((ni, nj))
            dp[ni][nj] = dp[i][j] + 1

    print(max(max(dpi) for dpi in dp))

main()
### BUGGY CODE ###

import numpy as np
from collections import deque
H,W = map(int, input().split())
CH,CW = map(lambda x: int(x) - 1, input().split())
DH,DW = map(lambda x: int(x) - 1, input().split())
S = [input() for i in range(H)]
INF = 10 ** 9
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]
h = CH
w = CW
Distance = [[INF] * W for _ in range(H)]
Distance[h][w] = 0
q = deque(())
q.append((h,w))
while q:
  h,w = q.popleft()
  if [h,w] == [DH,DW]:
    break
  for i,j in walk:
    hwalk = h + i
    wwalk = w + j
    if 0 <= hwalk < H and 0 <= wwalk < W and S[hwalk][wwalk] == '.' and Distance[h][w] < Distance[hwalk][wwalk]:
      Distance[hwalk][wwalk] = Distance[h][w]
      q.appendleft((hwalk,wwalk))
  for i,j in warp:
    hwalk = h + i
    wwalk = w + j
    if 0 <= hwalk < H and 0 <= wwalk < W and S[hwalk][wwalk] == '.' and Distance[h][w] + 1 < Distance[hwalk][wwalk]:
      Distance[hwalk][wwalk] = Distance[h][w] + 1
      q.append((hwalk,wwalk))
print(int(Distance[DH][DW]) if Distance[DH][DW] != INF else -1)

### FIXED CODE ###

from collections import deque
H,W = map(int, input().split())
CH,CW = map(lambda x: int(x) - 1, input().split())
DH,DW = map(lambda x: int(x) - 1, input().split())
S = [input() for i in range(H)]
INF = 10 ** 9
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]
h = CH
w = CW
Distance = [[INF] * W for _ in range(H)]
Distance[h][w] = 0
q = deque(())
q.append((h,w))
while q:
  h,w = q.popleft()
  if [h,w] == [DH,DW]:
    break
  for i,j in walk:
    hwalk = h + i
    wwalk = w + j
    if 0 <= hwalk < H and 0 <= wwalk < W and S[hwalk][wwalk] == '.' and Distance[h][w] < Distance[hwalk][wwalk]:
      Distance[hwalk][wwalk] = Distance[h][w]
      q.appendleft((hwalk,wwalk))
  for i,j in warp:
    hwalk = h + i
    wwalk = w + j
    if 0 <= hwalk < H and 0 <= wwalk < W and S[hwalk][wwalk] == '.' and Distance[h][w] + 1 < Distance[hwalk][wwalk]:
      Distance[hwalk][wwalk] = Distance[h][w] + 1
      q.append((hwalk,wwalk))
print(int(Distance[DH][DW]) if Distance[DH][DW] != INF else -1)
### BUGGY CODE ###

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

for i in range(n):
    if a[i] in d:
        d[a[i]] += 1
    else:
        d[a[i]] = 1


d_c = {}
d_2_c = {}
for i in d:
    d_c[i] = d[i] * (d[i] - 1) // 2
    d_2_c[i] = (d[i] - 1) * (d[i] - 2) // 2


for i in range(n):
    b = a[i]
    count = 0
    for j in d:
        if j != b:
            count += d_c[j]
        else:
            count += d_2_c[j]
    print(count)


### FIXED CODE ###

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

for i in range(n):
    if a[i] in d:
        d[a[i]] += 1
    else:
        d[a[i]] = 1

count = 0
for i in d:
    count += d[i] * (d[i] - 1) // 2


for i in range(n):
    b = d[a[i]]
    print(count-b+1)
### BUGGY CODE ###

n, x, y = map(int, input().split())
ans = []

for i in range(1, n):
    for j in range(i + 1, n + 1):
        diff1 = j - i
        diff2 = x + y - i - j + 1
        if i <= x and j >= y:
            diff2 = x - y - i + j + 1
        elif x <= i <= y and x <= j <= y:
            diff2 = -x + y + i - j + 1
        elif x < i < y and j > y:
            diff2 = -x - y + i + j +1
        if diff2 < 1:
            diff2 = diff1
        diff = min(diff1, diff2)
        ans.append(diff)

for i in range(1, n):
    print(ans.count(i))

### FIXED CODE ###

n, x, y = map(int, input().split())
ans = [0]*n

for i in range(1, n):
    for j in range(i + 1, n + 1):
        diff1 = j - i
        diff2 = x + y - i - j + 1
        if i <= x and j >= y:
            diff2 = x - y - i + j + 1
        elif x <= i <= y and x <= j <= y:
            diff2 = -x + y + i - j + 1
        elif x < i < y and j > y:
            diff2 = -x - y + i + j + 1
        if diff2 < 1:
            diff2 = diff1
        diff = min(diff1, diff2)
        ans[diff] = ans[diff] + 1

for i in range(1, n):
    print(ans[i])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

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

s_k = 1
for j in range(k):
    s_k *= scores[j]

for i in range(k + 1, n + 1):
    _s_k = s_k
    remove = scores[i - k - 1]
    add    = scores[i - 1]

    if remove < add:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

# -*- coding: utf-8 -*-

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

for i in range(k + 1, n + 1):
    remove = scores[i - k - 1]
    add    = scores[i - 1]

    if remove < add:
        print('Yes')
    else:
        print('No')