Harryxun/stf_run huggingface dataset:
import collections
import math

n, p = [int(i) for i in input().split()]
d = collections.defaultdict(lambda: 0)

def bunkai(q):
	if q == 1:
		return 0
	for i in range(2, math.ceil(math.sqrt(p))):
		if q % i == 0:
			d[i] += 1
			return bunkai(q//i)

if n == 1 or p == 1:
	print(p)
else:
	bunkai(p)
	ans = 1

	for j in d.key
		k = d[j]
		if k // n >= 1:
			ans *= j**(k//n)
	print(ans)


### FIXED CODE ###

import collections
import math

n, p = [int(i) for i in input().split()]
d = collections.defaultdict(lambda: 0)

def bunkai(q):
	if q == 1:
		return 0
	for i in range(2, math.ceil(math.sqrt(p))):
		if q % i == 0:
			d[i] += 1
			return bunkai(q//i)

if n == 1 or p == 1:
	print(p)
else:
	bunkai(p)
	ans = 1

	for j in d.keys():
		k = d[j]
		if k // n >= 1:
			ans *= j**(k//n)
	print(ans)
#include <iostream>
using namespace std;
int main(void){
   int H,W;
   int i,j;
   while(1){
    cin >> H,cin >> W;
    i=0;
    j=0;
    for(i=0;i<H;i++){
        for(j=0;j<W;j++){
            cout << "#";
            }
        cout << endl;
       }
       cout << endl;
       if(H==0 && W==0)
        break;
   }
   return 0;
}



### FIXED CODE ###

lines = []
colums = []

while True:
  H,W = map(int,input().split())
  if H == 0 and W == 0:
    break
  lines.append(H)
  colums.append(W)

for H,W in zip(lines,colums):
  for i in range(H):
    for j in range(W):
      print("#",end="")
    print("\n",end="")
  print("\n",end="")
n = int(input())
dic = {}
for i in range(n):
  s = sorted(list(input()))
  if s not in dic:
    dic[s] = 0
  dic[s] += 1
ans = 0
for i in dic.values():
  ans += i * (i - 1)
print(ans)

### FIXED CODE ###

n = int(input())
dic = {}
for i in range(n):
  s = ''.join(sorted(list(input())))
  if s not in dic:
    dic[s] = 0
  dic[s] += 1
ans = 0
for i in dic.values():
  ans += i * (i - 1) // 2
print(ans)
import bisect
n=int(input())
l=[]
e=[]
for i in range(n//2):
    j=int(input())
    e.append(j)
    l.append(j)
    j=int(input())
    l.append(j)
if n%2==1:
    j=int(input())
    e.append(j)
    l.append(j)
l.sort()
e.sort()
res=0
for i in range(0,n,2):
    if e[bisect.bisect_left(e,l[i])]!=l[i]:
        res+=1
print(res)

### FIXED CODE ###

import bisect
n=int(input())
l=[]
e=[]
for i in range(n//2):
    j=int(input())
    e.append(j)
    l.append(j)
    j=int(input())
    l.append(j)
if n%2==1:
    j=int(input())
    e.append(j)
    l.append(j)
l.sort()
e.sort()
res=0
for i in range(0,n,2):
    if e[min(len(e)-1,bisect.bisect_left(e,l[i]))]!=l[i]:
        res+=1
print(res)
import sys
n = int (input())
words = []
No=" "
for i in range (n) :
    words.append(input())
for x in range(len(words)-1):
    if words.count(words[x]) > 1 or words[x+1][0] != words[x][-1]:
        No="No"
        print (No)
        sys.exit() 
If No != "No":
     print ("Yes")

### FIXED CODE ###

n = int(input())
words = []
won = True
for i in range(n):
    new_word = input()
    if i > 0 and won:
        if new_word in words or new_word[0] != words[i-1][len(words[i-1])-1]:
            won = False
    words.append(new_word)

if won:
    print("Yes")
else:
    print("No")
import sys
from itertools import count, accumulate
from operator import mul
from functools import reduce
lines = sys.stdin.readlines()

positions = [int(i) for i in lines[1].split(' ')]

distances = [ j - i for i, j in zip(positions, positions[1:])]

n = len(distances)
factorials = [1] + list(accumulate(range(1,n + 1), mul))

combinations = dict()
def combination(i, j):
    j = min(j, i - j)
    if (i, j) in combinations:
        return combinations((i, j))
    else:
        return factorials[i] // (factorials [j] * factorials[i - j])

permutations = dict()
def permutation(i, j):
    if (i, j) in permutations:
        return permutations((i, j))
    else:
        return reduce(mul, range(j, i+1))

s = 0
result = 0
for d, i in zip(distances, count(1)):
    lt = i - 1
    gt = n - i
    t = factorials[n] / i
    s += t
    result += d * s

print(int(result % (pow(10,9) + 7)))

### FIXED CODE ###

import sys
from itertools import count, accumulate
from operator import mul
from functools import reduce
lines = sys.stdin.readlines()

positions = [int(i) for i in lines[1].split(' ')]

distances = [ j - i for i, j in zip(positions, positions[1:])]

n = len(distances)
p = pow(10,9) + 7

factorials = [1] + list(accumulate(range(1,n + 1), lambda x, y: (x * y) % p))

combinations = dict()
def combination(i, j):
    j = min(j, i - j)
    if (i, j) in combinations:
        return combinations((i, j))
    else:
        return factorials[i] // (factorials [j] * factorials[i - j])

permutations = dict()
def permutation(i, j):
    if (i, j) in permutations:
        return permutations((i, j))
    else:
        return reduce(mul, range(j, i+1))

def modpow(a, n, mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n = n >> 1
    return res

s = 0
result = 0
for d, i in zip(distances, count(1)):
    lt = i - 1
    gt = n - i
    i_inv = modpow(i, p-2, p)
    t = factorials[n] * i_inv
    s += t
    result += d * s

print(int(result % (pow(10,9) + 7)))
import sys
input = sys.stdin.readline
import numpy as np

H, W = map(int, input().split())
S = np.array([list(input()) for _ in range(H)]) == '.'
ups = np.zeros((H,W), dtype=int)
downs = np.zeros((H,W), dtype=int)
lefts = np.zeros((H,W), dtype=int)
rights = np.zeros((H,W), dtype=int)

for h in range(H):
    ups[h] = (ups[h-1] + 1) * S[h-1]
    downs[H-h-1] = (downs[H-h-1] + 1) * S[H-h-1]
for w in range(W):
    lefts[:, w] = (lefts[:, w-1] + 1) * S[w-1]
    rights[:, W-w-1] = (rights[:, W-w-1] + 1) * S[W-w-1]
print(np.amax((ups+downs+lefts+rights)*S)+1)


### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())
A = deque()
[A.append(int(input())) for _ in range(M)]

dp = [0]*(N+3)
dp[0] = 1

for i in range(N+1):
    if A:
        a = A[0]
    else:
        a = 0
    if len(A) >= 2:
        b = A[1]
    else:
        b = 0

    dp[i] = dp[i] % (10**9 + 7)
    if not i+1 == a:
        dp[i+1] += dp[i]
    else:
        A.popleft()
    if not i+2 == b and not i+2 == a:
        dp[i+2] += dp[i]
print(dp[N])
import numpy as np

n, m = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(m)]

root = np.zeros((n,n), dtype = int)

for ab in AB:
    root[ab[0]-1][ab[1]-1]=1
    root[ab[1]-1][ab[0]-1]=1

sign = [0]*n
sign[0]=-1
list = [0]

while True:
    x = list.pop(0)

    for y, bool in enumerate(root[x]):
        if sign[y]==0 and bool==1:
            sign[y]=x+1
            list.append(y)

    if len(list)==0:
        break

print('Yes')
for p in sign[1:]:
    print(p)

### FIXED CODE ###

import numpy as np

n, m = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(m)]

root = []
for i in range(n):
    root.append(set())

for ab in AB:
    root[ab[0]-1].add(ab[1]-1)
    root[ab[1]-1].add(ab[0]-1)

sign = [0]*n
sign[0]=-1
list = [0]

while True:
    x = list.pop(0)

    for next in root[x]:
        if sign[next]==0:
            sign[next]=x+1
            list.append(next)

    if len(list)==0:
        break

print('Yes')
for p in sign[1:]:
    print(p)
a=int(input())
b=input()
count=0
for i in range(1000):
  flag=False
  for j in range(a):
    if b[j]=='{0:03d}'.format(str(i))[0]:
      x=j
      flag=True
      break
  if flag:
    flag=False
  else:
    continue
  for k in range(x+1,a):
    if b[k]=='{0:03d}'.format(str(i))[1]:
      y=k
      flag=True
      break
  if flag:
    flag=False
  else:
    continue
  for l in range(y+1,a):
    if b[l]=='{0:03d}'.format(str(i))[1]:
      count+=1
      break
print(count)
      
  
    

### FIXED CODE ###

a,b=map(int,input().split())
c,d=map(int,input().split())
if a+1==c:
  print(1)
else:
  print(0)
N = int(input())
if N % 2 == 0:
  print(0.5000000000)
else:
  print((N+1)/2N)

### FIXED CODE ###

N = int(input())
if N % 2 == 0:
  print(0.5000000000)
else:
  print((N+1)/(2*N))
N = int(input())
S = list(input())
T = list(input())
ans = ""
for i in range(N):
    ans += S[i]
    ans += T[i]
print(ans)

### FIXED CODE ###

N = int(input())
S = list(input())
ans = ""
for i in range(N):
    ans += S[i]
    ans += S[N + i + 1]
print(ans)
# https://atcoder.jp/contests/abc064/tasks/abc064_a
a = int("".join(input()))
if a % 4 == 0:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

# https://atcoder.jp/contests/abc064/tasks/abc064_a
a = int(input().replace(' ', ''))
if a % 4 == 0:
    print("YES")
else:
    print("NO")
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

plus = []
minus = []
for i in a:
    if i > 0: plus.append(i)
    if i < 0: minus.append(-i)
plus.sort(reverse=True)
minus.sort(reverse=True)

ans = 1
if k == n:
    for x in a:
        ans = (ans * x) % mod
elif k > len(plus) + len(minus):
    ans = 0
elif n == len(plus):
    for x in plus[:k]:
        ans = (ans * x) % mod
elif n == len(minus):
    if k % 2 == 1:
        ans = -1
        minus.sort()
    for x in minus[:k]:
        ans = (ans * x) % mod
else:
    i, j = 0, 0
    if k % 2 == 1:
        ans = plus[0]
        i += 1
    while i + j < k:
        x_p = plus[i] * plus[i + 1] if i < len(plus) - 1 else 0
        x_m = minus[j] * minus[j + 1] if j < len(minus) - 1 else 0
        if x_p > x_m:
            ans = (ans * x_p) % mod
            i += 2
        else:
            ans = (ans * x_m) % mod
            j += 2
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

plus = []
minus = []
for i in a:
    if i > 0: plus.append(i)
    if i < 0: minus.append(i)

ans = 1
if k > len(plus) + len(minus):
    ans = 0
elif len(minus) == 0:
    plus.sort(reverse=True)
    for i in range(k):
        ans = (ans * plus[i]) % mod
elif len(plus) == 0:
    if k % 2 == 0:
        minus.sort()
        for i in range(k):
            ans = (ans * minus[i]) % mod
    else:
        if n != len(minus):
            ans = 0
        else:
            minus.sort(reverse=True)
            for i in range(k):
                ans = (ans * minus[i]) % mod
elif k == len(plus) + len(minus) and (len(minus) % 2) == 1:
    if n != k:
        ans = 0
    else:
        for x in plus:
            ans = (ans * x) % mod
        for y in minus:
            ans = (ans * y) % mod
else:
    plus.sort(reverse=True)
    minus.sort()
    i, j = 0, 0
    if k % 2 == 1:
        ans = plus[0]
        i = 1
    while i + j < k:
        tmp_p = plus[i] * plus[i + 1] if i <= len(plus) - 2 else 1
        tmp_m = minus[j] * minus[j + 1] if j <= len(minus) - 2 else 1
        if tmp_p >= tmp_m:
            ans = (ans * (tmp_p % mod)) % mod
            i += 2
        else:
            ans = (ans * (tmp_m % mod)) % mod
            j += 2
print(ans)
n,m,k=map(int,input().split())
stock=[[] for i in range(n)]
ter=[0]*n
ans=[0]*n
for i in range(m):
    a,b=map(int,input().split())
    stock[a-1].append(b-1)
    stock[b-1].append(a-1)
    ans[a-1]-=1
    ans[b-1]-=1
def dfs(i,k):
    size[k]+=1
    for next_i in stock[i]:
        if ter[next_i]==0:
            ter[next_i]=k
            dfs(next_i,k)
total=0
size=[0]*(n+1)
for i in range(n):
    if ter[i]==0:
        total+=1
        ter[i]=total
        dfs(i,total)

for i in range(n):
    ans[i]+=size[ter[i]]-1
for i in range(k):
    c,d=map(int,input().split())
    if ter[c-1]==ter[d-1]:
        ans[c-1]-=1
        ans[d-1]-=1
for i in range(n-1):
    print(ans[i],end=" ")
print(ans[n-1])

### FIXED CODE ###

class UnionFind:
    def __init__(self,n):
        self.n=n
        self.parent=[i for i in range(n)]
        self.rank=[1]*n#木の高さ
        self.size=[1]*n#size[i]はiを根とするグループのサイズ

    def find(self,x):#ｘの根（親）を返す
        if self.parent[x]==x:
            return x
        else:
            self.parent[x]=self.find(self.parent[x])#経路圧縮
            return self.parent[x]

    def unite(self,x,y):#ｘ、ｙの集合の統合
        x=self.find(x)
        y=self.find(y)
        if x!=y:
            if self.rank[x]<self.rank[y]:#ランクの比較
                self.parent[x]=y
                self.size[y]+=self.size[x]
            else:
                self.parent[y]=x
                self.size[x]+=self.size[y]
                if self.rank[x]==self.rank[y]:
                    self.rank[x]+=1
    def group_size(self,x):#ｘが属する集合の大きさ
        return self.size[self.find(x)]
    def is_same(self,x,y):#ｘ、ｙが同じ集合に属するかを判定する
        return self.find(x)==self.find(y)

n,m,k=map(int,input().split())

uf=UnionFind(n)
ans = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    uf.unite(a-1,b-1)
    ans[a - 1] -= 1
    ans[b - 1] -= 1
for i in range(k):
    c, d = map(int, input().split())
    if uf.is_same(c-1,d-1):
        ans[c-1]-=1
        ans[d-1]-=1

for i in range(n):
    ans[i]+=uf.group_size(i)-1
    print(ans[i])
N = int(input())
T = int(input())
clist = []
for i in range(0, N):
    c = int(input())
    t = int(input())
    if t <= T:
        clist.append(c)
clist.sort()
if clist == []:
    print("TLE")
else:
    print(clist[0])


### FIXED CODE ###

InStr = input()
InList = InStr.split()
N = int(InList[0])
T = int(InList[1])
ccalist = []
for i in range(N):
    InStr = input()
    InList = InStr.split()
    cc = int(InList[0])
    ct = int(InList[1])
    if ct <= T:
        ccalist.append(cc)
if ccalist == []:
    print("TLE")
else:
    ccalist.sort()
    print(ccalist[0])
N = int(input())
*A, = map(int,input().split())

A.sort()

for i,a in enumerate(A):
    if a>=0:break
B = A[:i]
C = A[i:]

ans = []
if not B:
    x = C[0]
    for a in C[1:-1]:
        ans.append((x,a))
        x -= a
    ans.append((C[-1],x))
    x = C[-1] - x
elif not C:
    x = B[-1]
    for a in B[:-1]:
        ans.append((x,a))
        x -= a
else:
    x = B[0]
    for a in C[1:]:
        ans.append((x,a))
        x -= a
    ans.append((C[0],x))
    x = C[0]-x
    for a in B[1:]:
        ans.append(x,a)
        x -= a

print(x)
for out in ans:
    print(*out)

### FIXED CODE ###

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

A.sort()

for i,a in enumerate(A):
    if a>=0:break
B = A[:i]
C = A[i:]

ans = []
if not B:
    x = C[0]
    for a in C[1:-1]:
        ans.append((x,a))
        x -= a
    ans.append((C[-1],x))
    x = C[-1] - x
elif not C:
    x = B[-1]
    for a in B[:-1]:
        ans.append((x,a))
        x -= a
else:
    x = B[0]
    for a in C[1:]:
        ans.append((x,a))
        x -= a
    ans.append((C[0],x))
    x = C[0]-x
    for a in B[1:]:
        ans.append((x,a))
        x -= a

print(x)
for out in ans:
    print(*out)
a,b=input(),split()

print(a)


### FIXED CODE ###

a,b = input().split()
a = int(a)
b = int(b)
S = a*b
C = 2 * (a+b)

print(str(S) + " " + str(C))
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
X = list(map(int, sys.stdin.readline().split()))
L = int(sys.stdin.readline())
Q = int(sys.stdin.readline())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]

X = np.array(X, dtype=int)
# rdp[d][i]: i番のホテルから(2^d)日で何個右までいけるか
rdp = np.zeros((N.bit_length(), N), dtype=int)
rdp[0] = np.searchsorted(X, X + L, side='right') - np.arange(N) - 1
for d in range(1, N.bit_length()):
    rdp[d] = rdp[d - 1] + rdp[d - 1][np.arange(N) + rdp[d - 1]]

X = -X[::-1]
# ldp[d][i]: i番のホテルから(2^d)日で何個左までいけるか
ldp = np.zeros((N.bit_length(), N), dtype=int)
ldp[0] = np.searchsorted(X, X + L, side='right') - np.arange(N) - 1
for d in range(1, N.bit_length()):
    ldp[d] = ldp[d - 1] + ldp[d - 1][np.arange(N) + ldp[d - 1]]

# print(rdp)
# print(ldp)


def solver(l, r):
    ret = 0
    while l < r:
        d = np.searchsorted(rdp[:, l], r - l)
        if d > 0 and rdp[d, l] > r - l:
            d -= 1
        ret += 2 ** d
        l += rdp[d, l]
    return ret


def solvel(l, r):
    r = N - r - 1
    l = N - l - 1
    ret = 0
    while l < r:
        d = np.searchsorted(ldp[:, l], r - l)
        if d > 0 and ldp[d, l] > r - l:
            d -= 1
        ret += 2 ** d
        l += ldp[d, l]
    return ret


# print(np.searchsorted([1, 2, 5, 8, 9], 3))
# print(np.searchsorted([1, 2, 5, 8, 9], 4))
# print(np.searchsorted([1, 2, 5, 8, 9], 5))
# print(np.searchsorted([1, 2, 5, 8, 9], 6))
# print(np.searchsorted([1, 2, 5, 8, 9], 7))
# print()

for a, b in AB:
    if a < b:
        r = solver(a - 1, b - 1)
    else:
        r = solvel(a - 1, b - 1)
    print(r)


### FIXED CODE ###

import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
X = list(map(int, sys.stdin.readline().split()))
L = int(sys.stdin.readline())
Q = int(sys.stdin.readline())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]

N += 2
X = [X[0]] + X + [X[-1]]
X = np.array(X, dtype=int)
# dp[d][i]: i番のホテルから(2^d)日で何個右までいけるか
dp = np.zeros((N.bit_length() + 1, N), dtype=int)
dp[0] = np.searchsorted(X, X + L, side="right") - 1
for d in range(1, N.bit_length() + 1):
    dp[d] = dp[d - 1][dp[d - 1]]
dp = dp.tolist()


def solve(l, r):
    ret = 0
    d = len(dp) - 1
    while l + 1 < r:
        while d > 0 and dp[d][l] >= r:
            d -= 1
        ret += 1 << d
        l = dp[d][l]
    if l < r:
        ret += 1
    return ret


ans = []
for a, b in AB:
    ans.append(solve(min(a, b), max(a, b)))
print(*ans, sep='\n')
A=[]
i=0
for l in range(3):
    A.append(list(map(int,input().split())))
N=int(input())
B = [int(input()) for i in range(N)]
for C in B:
    for a in range(3):
        for b in range(3):
            if C==A[a][b]:
                A[a][b]=-1

for a in range(3):
    for b in range(3):
        if A[a][b]==A[-a-1][b]==A[-a-2][b]==-1:
            print("Yes")
            i=1
            break
        elif A[a][b]==A[a][-b-1]==A[a][-b-2]==-1:
            print("Yes")
            i=1
            break
        elif A[1][1]==A[2][2]==A[0][0]==-1:
            print("Yes")
            i=1
            break
        elif A[0][2]==A[1][1]==A[2][0]==-1:
            print("Yes")
            i=1
            break
    if i==1:
        break
if i==0:
    print("No")

### FIXED CODE ###

A=[]
i=0
for l in range(3):
    A.append(list(map(int,input().split())))
N=int(input())
B = [int(input()) for i in range(N)]
for C in B:
    for a in range(3):
        for b in range(3):
            if C==A[a][b]:
                A[a][b]=-1

for a in range(3):
    for b in range(3):
        if A[0][b]==A[1][b]==A[2][b]==-1:
            print("Yes")
            i=1
            break
        elif A[a][0]==A[a][1]==A[a][2]==-1:
            print("Yes")
            i=1
            break
        elif A[1][1]==A[2][2]==A[0][0]==-1:
            print("Yes")
            i=1
            break
        elif A[0][2]==A[1][1]==A[2][0]==-1:
            print("Yes")
            i=1
            break
    if i==1:
        break
if i==0:
    print("No")
N, Q = map(int, input().split())
nodes = {str(i): [] for i in range(1, N+1)}
for _ in range(N-1):
    a, b = input().split()
    nodes[a] += [b]

PX = [input().split() for _ in range(Q)]

ptree_map = {}


def gen_subtree_nodes(node):
    res = [int(node)]
    for n in nodes.get(node, []):
        subtree_nodes = gen_subtree_nodes(n)
        ptree_map[n] = subtree_nodes
        res += subtree_nodes

    return res


ptree_map['1'] = gen_subtree_nodes('1')

node_cnts = [0] * (N+1)
for p, x_str in PX:
    x = int(x_str)
    for n in ptree_map[p]:
        node_cnts[n] += x

print(*node_cnts[1:])


### FIXED CODE ###

N, Q = map(int, input().split())
nodes = [[] for _ in range(2*(10**5)+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    nodes[a] += [b]

PX = [0 for _ in range(2*(10**5)+1)]
for _ in range(Q):
    p, x = map(int, input().split())
    PX[p] += x


node_cnts = [0] * (2*(10**5)+1)

q = [(1, PX[1])]
while q:
    node, count = q.pop()
    node_cnts[node] = count
    for n in nodes[node]:
        subtree_nodes = q.append((n, count + PX[n]))


print(*node_cnts[1:N+1], sep=' ')
import sys
sys.setrecursionlimit(10**9)
from collections import deque
H, W = map(int, input().split()) 
S = [list(input()) for i in range(R)]

Kuro = 0
Shiro = 0
for j in range(H):
    for i in range(W):
        if S[j][i]=='.':
            Shiro += 1
        else:
            Kuro += 1

Dis =[[0]*W for i in range(H)]
X =[-1, 0, 1, 0]
Y =[0, -1, 0, 1]
q = deque()
q.append((0,0))
while True:
    y,x = q.popleft()
    if (y==H-1) and (x==W-1):
        break
    for i in range(4):
        nx = x + X[i]
        ny = y + Y[i]
        if (0<= nx < W) and(0 <= ny < H) and (S[ny][nx]=='.') and(Dis[ny][nx] ==0):
            q.append((ny,nx))
            Dis[ny][nx] = Dis[y][x] +1

print(Shiro-Dis[H-1][W-1]-1)    

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**8)

H, W = map(int, input().split()) 
S = [list(input()) for i in range(H)]

Kuro = 0
Shiro = 0
for j in range(H):
    for i in range(W):
        if S[j][i]=='.':
            Shiro += 1
Dis =[[-1]*W for i in range(H)]
X =[-1, 0, 1, 0]
Y =[0, -1, 0, 1]
q = deque()
q.append((0,0))
Dis[0][0] = 0
a=deque()
while (q != a):
    y,x = q.popleft()
    if (y==H-1) and (x==W-1):
        break
    for i in range(4):
        nx = x + X[i]
        ny = y + Y[i]
        if (0<= nx < W) and(0 <= ny < H) and (S[ny][nx]=='.') and (Dis[ny][nx] ==-1):
            q.append((ny,nx))
            Dis[ny][nx] = Dis[y][x] +1

if (Dis[H-1][W-1]==-1):
    print(-1)
else:
    print(Shiro-Dis[H-1][W-1]-1)
import numpy as np
import pandas as pd
n = int(input())

df = pd.DataFrame([], columns=['num','city','score'],index=range(n))
for i in range(n):
    s, p = input().split()
    df.iloc[i,:] = np.array([i + 1, s, int(p)])

for i in df.sort_values(['city','score'], ascending=[True,False])['num']:
    print(i)

### FIXED CODE ###

from operator import itemgetter

n = int(input())
 
data = []
for i in range(n):
    city, point = input().split()
    data.append([city, int(point), i+1])

data = sorted(data, key=itemgetter(1), reverse=True)
data = sorted(data, key=itemgetter(0), reverse=False)

for i in range(n):
    print(data[i][2])
from math import sqrt
cheeze = map(float,raw_input().split())
cheeze.sort()
supk = sqrt((cheeze[0]/2)**2 + (cheeze[1]/2)**2)
while True:
	k = raw_input()
	if k == "0 0 0": break
	else:
		k = int(k)
		if k < supk: print "OK"
		else: print "NA"

### FIXED CODE ###

from math import sqrt

while True:
    inp = raw_input()
    if inp == "0 0 0": break
    cs = map(int,inp.split())
    cs.sort()
    c = sqrt(cs[0]**2 + cs[1]**2)/2

    n=int(raw_input())

    for gomi in xrange(n):
        r = int(raw_input())
        if c<r: print "OK"
        else: print "NA"
import sys
read = lambda: sys.stdin.readline().rstrip()

def counting_tree(N, D):
    tot = 1
    cnt = [0]*N
    # cnt = collections.Counter(D)
    for i in D:
        cnt[i]+=1
        
    for i in D[1:]:
        tot = tot*cnt[i-1]%998244353

    return tot if D[0]!=0 else 0

def main():
    
    N0 = int(read().split())
    D0 = tuple(map(int, read().split()))

    res = counting_tree(N0, D0)

    print(res)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
read = lambda: sys.stdin.readline().rstrip()

def counting_tree(N, D):
    tot = 1
    
    # cnt = collections.Counter(D)
    cnt = [0]*N
    for i in D:
        cnt[i]+=1

    for i in D[1:]:
        tot = tot * cnt[i-1]%998244353

    return tot if D[0]==0 else 0

def main():
    
    N0 = int(read())
    D0 = tuple(map(int, read().split()))

    res = counting_tree(N0, D0)

    print(res)

if __name__ == "__main__":
    main()
data = input().split()
a = data[0]
b = data[1]
print(int(a) * int(b), 2 * (int(a) + int(b))


### FIXED CODE ###

data = input().split()
a = data[0]
b = data[1]
print(int(a) * int(b), 2 * (int(a) + int(b)))
N = int(input())
sum = 0.0
for i in range(N):
    x,u = map(int,input().split())
    if u == 'BTC':
        x *= 380000.0
    sum += x
print(sum)

### FIXED CODE ###

N = int(input())
sum = 0.0
for i in range(N):
    x,u = input().split()
    x = float(x)
    if u == 'BTC':
        x *= 380000.0
    sum += x
print(sum)