Harryxun/stf_run huggingface dataset:
from collections import defaultdict, deque

N, M, P = map(int, input().split())
# G = defaultdict(lambda: defaultdict(lambda: 0))
# G_rev = defaultdict(lambda: defaultdict(lambda: 0))
G = dict()
G_rev = dict()

for _ in range(M):
    A, B, C = map(int, input().split())
    if A not in G.keys():
        G[A] = dict()
    if B not in G_rev.keys():
        G_rev[B] = dict()
    G[A][B] = P - C
    G_rev[B][A] = 1

reachable_N = [0] * (N + 1)
reachable_N[N] = 1
queue = deque([N])

while len(queue) > 0:
    p = queue.popleft()
    for q in G_rev[p].keys():
        if reachable_N[q] == 0:
            reachable_N[q] = 1
            queue.append(q)

reachable_1 = [0] * (N + 1)
reachable_1[1] = 1
queue = deque([1])

while len(queue) > 0:
    p = queue.popleft()
    for q in G[p].keys():
        if reachable_1[q] == 0:
            reachable_1[q] = 1
            queue.append(q)

reachable = [reachable_1[i] * reachable_N[i] for i in range(N + 1)]

dist = [10000000000] * (N + 1)
res = 0
dist[1] = 0
queue = deque([1])
cnt = 0

update = True

while update:
    update = False
    for p in range(1, N + 1):
        if reachable[p] == 0:
            continue
        for q in G[p].keys():
            if reachable[q] == 0:
                pass
            elif dist[p] + G[p][q] < dist[q]:
                dist[q] = dist[p] + G[p][q]
                update = True
    cnt += 1
    if cnt > N:
        res = -1
        break

if res == -1:
    print(res)
else:
    print(max(0, -dist[N]))


### FIXED CODE ###

from collections import defaultdict, deque

N, M, P = map(int, input().split())
G = defaultdict(lambda: defaultdict(lambda: 10000000))
G_rev = defaultdict(lambda: defaultdict(lambda: 10000000))

for _ in range(M):
    A, B, C = map(int, input().split())
    G[A][B] = min(G[A][B], P - C)
    G_rev[B][A] = 1

reachable_N = [0] * (N + 1)
reachable_N[N] = 1
queue = deque([N])

while len(queue) > 0:
    p = queue.popleft()
    for q in G_rev[p].keys():
        if reachable_N[q] == 0:
            reachable_N[q] = 1
            queue.append(q)

reachable_1 = [0] * (N + 1)
reachable_1[1] = 1
queue = deque([1])

while len(queue) > 0:
    p = queue.popleft()
    for q in G[p].keys():
        if reachable_1[q] == 0:
            reachable_1[q] = 1
            queue.append(q)

reachable = [reachable_1[i] * reachable_N[i] for i in range(N + 1)]

dist = [10000000000 for i in range(N + 1)]
res = 0
dist[1] = 0
queue = deque([1])
cnt = 0

update = True

while update:
    update = False
    for p in range(1, N + 1):
        if reachable[p] == 0:
            continue
        for q in G[p].keys():
            if reachable[q] == 0:
                pass
            elif dist[p] + G[p][q] < dist[q]:
                dist[q] = dist[p] + G[p][q]
                update = True
    cnt += 1
    if cnt > N:
        res = -1
        break

if res == -1:
    print(res)
else:
    print(max(0, -dist[N]))
h,w=map(int,input().split())
s=[]
s.append("."*(h+2))

for i in range(w):
    s.append("."+input()+".")
    
s.append("."*(h+2))

for i in range(1,w+1):
    for j in range(1,h+1):
        #print(i,j)
        if s[i][j]=="#":
            if s[i][j+1]=="#" or s[i][j-1]=="#" or s[i+1][j]=="#" or s[i-1][j]=="#":
                pass
            else:
                print("No")
                exit()
        

print("Yes")

### FIXED CODE ###

h,w=map(int,input().split())
s=[]
s.append("."*(w+2))

for i in range(h):
    s.append("."+input()+".")
    
s.append("."*(w+2))

for i in range(1,h+1):
    for j in range(1,w+1):
        #print(i,j)
        if s[i][j]=="#":
            if s[i][j+1]=="#" or s[i][j-1]=="#" or s[i+1][j]=="#" or s[i-1][j]=="#":
                pass
            else:
                print("No")
                exit()
        

print("Yes")
#AIsing2020 d
 
N = int(input())
X = input()
X10 = int('0b'+X,2)
X10_num1 = X.count('1')
X10_pulse = X10%(X10_num1+1)
X10_ninus = X10%(X10_num1-1)


for i in range(N,0,-1):
    a = X10
    if a>>(i-1) & 1:
        a -= 2**(i-1)
        amari = (X10_ninus - (2**(i-1))%(X10_num1-1))%(X10_num1-1)
    else:
        a += 2**(i-1)
        amari = (X10_pulse + (2**(i-1))%(X10_num1+1))%(X10_num1+1)
    nc = amari
    if a ==0:
        co = 0
    else:
        co = 1
        while nc >0:
            bin_str = bin(nc)
            cou1 = bin_str.count('1')
            nc = nc%cou1
            co +=1
    
    print(co)


### FIXED CODE ###

#AIsing2020 d

def f(n):
        cnt = 0
        while n:
            cnt+= 1
            n = n%bin(n).count('1')
        return cnt

def main():
    N = int(input())
    X = input()
    X10 = int(X,2)
    X10_num1 = X.count('1')
    X10_pulse = X10%(X10_num1+1)
    X10_ninus = X10%(X10_num1-1) if X10_num1 >1 else 0


    for i in range(N,0,-1):
        j = N-i
        if (X[j] == '1') and X10_num1 >1:
            mod = X10_num1-1
            amari = (X10_ninus - pow(2,i-1,mod))%(mod) 
        elif (X[j] == '1') and X10_num1 ==1:
            print(0)
            continue
        else:
            mod = X10_num1+1
            amari = (X10_pulse + pow(2,i-1,mod))%(mod)

        print(1+f(amari))


main()
N = int(input())
A = int(input().split())
for i in range(N):
    if A[i]%2==0:
        if A[i]%15!=0:
            print("DENIED")
        else:
            print("APPROVED")



            

### FIXED CODE ###

N = int(input())#.split()
A = input().split()
den = False
for i in range(N):
    if int(A[i]) % 2 == 0:
        if int(A[i]) % 3 != 0 and int(A[i]) % 5 != 0:
            print("DENIED")
            exit(0)
            den = True
if not den:
    print("APPROVED")
x,y,z,q=map(int,input().split())
*a,=map(int,input().split())
*b,=map(int,input().split())
*c,=map(int,input().split())
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

class bisect:
  def bisect(self,l,r):
    cnt=(l+r)//2
    if cnt==l:
      return l-1+self.judge(l)
    if self.judge(cnt):
      return self.bisect(cnt+1,r)
    else:
      return self.bisect(l,cnt)
  def judge(self,thr):
    m=0
    for i in a:
      for j in b:
        for k in c:
          if i+j+k>thr:
            m+=1
            if m>=q:
              return True
    return False

def make(thr):
  m=0
  l=[]
  for i in a:
    for j in b:
      for k in c:
        n=i+j+k
        if n>thr:
          m+=1
          l+=[n]
          if m>=q:
            l.sort(reverse=True)
            return l

s=bisect()
thr=s.bisect(0,a[0]+b[0]+c[0]+1,0)
ans=make(thr)
for w in ans:
  print(w)

### FIXED CODE ###

x,y,z,q=map(int,input().split())
a=sorted(map(int,input().split()),reverse=True)
b=sorted(map(int,input().split()),reverse=True)
c=sorted(map(int,input().split()),reverse=True)
 
def bisect(l,r):
  cnt=(l+r)//2
  if cnt==l:
    return l-1+judge(l)
  if judge(cnt):
    return bisect(cnt+1,r)
  else:
    return bisect(l,cnt)
def judge(thr):
  m=0
  for i in range(x):
    for j in range(y):
      if i*j>q:
        break
      for k in range(z):
        if i*j*k>q or a[i]+b[j]+c[k]<thr:
          break
        m+=1
        if m>=q:
          return True
  return False
def make(thr):
  m=0
  l=[]
  for i in a:
    for j in b:
      for k in c:
        n=i+j+k
        if n<thr+1:
          break
        m+=1
        l+=[n]
  l.sort(reverse=True)
  return l+[thr]*(q-len(l))
thr=bisect(0,a[0]+b[0]+c[0]+1)
ans=make(thr)
for w in ans:
  print(w)
import math
N = int(input())
for i in N+1
    if math.floor(i*1.08) = N
    print(i)
    exit()
    
print(":(")
    

### FIXED CODE ###

import math
N = int(input())

for i in range(N+1):
    if math.floor(1.08 * i) == N:
        print(i)
        exit()

print(":(")
n,k=map(int,input().split())
l=list(map(int,input().split()))

for i in range(n-k):
    if max(l[i:i+k]) < l[i+k]:
        m=l[i+1:i+k+1]
    else:
        m=l[i:i+k]

result=float(0)
for i in range(len(m)):
    t=m[i]
    if t%2==0:
        result += (1+t)*(t/2)/t
    else:
        result += ((1+t)*(t//2)+(t//2+1))/t
    
print(result)

### FIXED CODE ###

N, K = map(int, input().split())
num = list(map(int, input().split()))
 
# 各サイコロの期待値を出す
expect = []
for i in range(N):
  expect.append((1 + num[i]) / 2)
 
# 累積和を作る
cs = [0]
for i in range(N):
    cs.append(cs[i]+expect[i])

max = 0
for i in range(K, N+1): # 配列0番目に初期値0が増えてるので1足す
  if max < cs[i] - cs[i-K]:
    max = cs[i] - cs[i - K]
print(max)
n, k = map(int, input().split())
p = [int(x) for x in input().split()]
ans = 0
for i in range(n-k+1):
    a = 0
    for j in range(k):
        a += ((1+p[i+j])*p[i+j])/2
    if ans <= a:
        ans = a

ans_list.sort(reverse=True)
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
p = [int(x) for x in input().split()]
ans_list = [0]
a = 0
ans = 0
ans_ = 0
for i in range(n):
    a += (1+p[i])/2
    ans_list.append(a)
for i in range(n-k+1):
    ans_ = ans_list[i+k]-ans_list[i]
    ans = max(ans, ans_)
    
print(ans)
print(str(3r**2))

### FIXED CODE ###

r=int(input())
print(str(3*r**2))
N, L = [int(_) for _ in raw_input()]
if L == 1:
  print 0
else:
  print N - L 

### FIXED CODE ###

N, K = [int(_) for _ in raw_input().split(" ")]
if K == 1:
  print 0
else:
  print (N - K)
S = input()
N = len(S)
ans = [0] * N
index = 0
rcount = 0
lcount = 0
for i in range(N):
    if S[i] == 'R' and S[i+1] == 'R':
        rcount += 1
    if S[i] == 'L' and S[i+1] == 'L':
        lcount += 1
    if S[i] == 'R' and S[i+1] == 'L':
        if lcount != 0:
            ans[index] += lcount // 2 + lcount % 2
            ans[index + 1] += lcount // 2
            lcount = 0
        index = i
        ans[i] = 1
        ans[i+1] = 1
        if rcount != 0:
            ans[i] += rcount // 2
            ans[i+1] += rcount // 2 + rcount % 2
            rcount = 0
        i += 1
if lcount != 0:
    ans[index] += lcount // 2 + lcount % 2
    ans[index + 1] += lcount // 2
    lcount = 0

for i in range(N):
    print(ans[i],end= ' ')

### FIXED CODE ###

S = input()
N = len(S)
 
ans = [0] * N
 
index = 0
lcount = 0
rcount = 0
for i in range(N):
    if S[i] == 'R' and S[i + 1] == 'R':
        rcount += 1
    if S[i] == 'L' and S[i - 1] == 'L':
        lcount += 1
    if S[i] == 'R' and S[i + 1] == 'L':
        if lcount != 0:
            ans[index] += lcount // 2 + lcount % 2
            ans[index + 1] += lcount // 2
            lcount = 0
        index = i
        ans[i] = 1
        ans[i + 1] = 1
        if rcount != 0:
            ans[i] += rcount // 2
            ans[i + 1] += rcount // 2 + rcount % 2
            rcount = 0
        i += 1
if lcount != 0:
    ans[index] += lcount // 2 + lcount % 2
    ans[index + 1] += lcount // 2
    lcount = 0
    
for i in range(N):
    print(ans[i], end=" ")
N = int(input())
p = [int(i) for i in input().split()]
ans = 1

if 0 in p:
  print(0)
  exit()
  
for i in range(n):
  ans*=p[i]
  
if ans > 10 ** 18:
  print(-1)
  exit()
  
print(ans)

### FIXED CODE ###

N = int(input())
p = [int(i) for i in input().split()]
ans = 1

if 0 in p:
  print(0)
  exit()
  
for i in range(N):
  ans*=p[i]
  if ans > 10 ** 18:
    print(-1)
    exit()
print(ans)
K, S = list(map(int, input().split()))
if S <= K:
	print(int((S + 2) * (S + 1) / 2))
elif S <= 2 * K:
	ans = (S - K + 1) * (2 * K - S) * int((S - K) (S - K + 1) / 2)
	print(ans)
else:
	print(int((3 * K - S + 1) * (3 * K - S + 2) / 2))

### FIXED CODE ###

K, S = list(map(int, input().split()))
if S <= K:
	print(int((S + 2) * (S + 1) / 2))
elif S <= 2 * K:
	ans = (-3 * (K ** 2) + 3 * K + 6 * S * K - 2 * (S ** 2) + 2) // 2
	print(int(ans))
else:
	print(int((3 * K - S + 1) * (3 * K - S + 2) / 2))
from sys import stdin
import math

lines = [line for line in stdin]

for line in lines:
    a, b = [float(n) for n in line]
    print(math.floor(math.log10(a + b)))
    # x1, y1, x2, y2, x3, y3, xp, yp = [float(r) for r in line]
    # print(x1, y1, x2, y2, x3, y3, xp, yp)

### FIXED CODE ###

from sys import stdin
import math
import fileinput

for line in fileinput.input():
    a, b = [int(n) for n in line.split()]
    print(math.floor(math.log10(a + b) + 1))
    # x1, y1, x2, y2, x3, y3, xp, yp = [float(r) for r in line]
    # print(x1, y1, x2, y2, x3, y3, xp, yp)
import sys
sys.setrecursionlimit(2000000)
t=input()
x=0
tl=list(t)
while x != -1:
    x=t.find("?")
    if tl[x+1]=="D":
        tl[x]="P"
    elif tl[x+1]=="?":
        tl[x]="P"
    else:
        tl[x]="D"
    t="".join(tl)
    x=t.find("?")
print(t)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
t=input()
tl=list(t)
tln=len(t)
x=0
for x in range(tln):
    if tl[x] == "?":
        if x == tln-1:
            tl[x]="D"
            break
        elif x==0:
            if tl[x+1]=="?":
                tl[x]="P"
                tl[x+1]="D"
            else:
                tl[x]="D"
        elif tl[x-1]=="P":
            tl[x]="D"
        elif tl[x+1]=="?":
            tl[x]="P"
            tl[x+1]="D"
        elif tl[x+1]=="D":
            tl[x]="P"
        else:
            tl[x]="D"
t="".join(tl)
print(t)
L, R = map(int, input().split())

if R - L >= 2019:
    print(0)
else:
    mod_l = L%2019
    mod_r = R%2019
    ans = 2019
    for i in range(mod_l, mod_r+1):
        for j in range(i+1, mod_r+1):
            if (i * j)%2019 == 0:
                ans = 0
                break
            ans = min(ans, (i * j)%2019)
print(ans)

### FIXED CODE ###

L, R = map(int, input().split())

if R - L >= 2019:
    print(0)
else:
    mod_l = L%2019
    mod_r = R%2019
    ans = 2019
    for i in range(mod_l, mod_r):
        for j in range(i+1, mod_r+1):
            if (i * j)%2019 == 0:
                ans = 0
                break
            ans = min(ans, (i * j)%2019)
        else:
            continue
        break
    print(ans)
def main():
    import sys
    import numpy as np
    ikimasu = sys.stdin.buffer.readline
    ini = lambda: int(ins())
    ina = lambda: list(map(int, ikimasu().split()))
    ins = lambda: ikimasu().strip()
    n,k = ina()
    tmp = [[] for _ in range(n)]
    for _ in range(n-1):
        x,x1=  ina()
        x-=1
        x1-=1
        tmp[x].append(x1)
        tmp[x1].append(x)
    def dfs(teiru,ta):
        rick = 1
        coulduse = k-1 if ta==-1 else k-2
        if(coulduse<len(tmp[teiru])):
            return 0
        for i in tmp[teiru]:
            if i == ta:
                continue
            print(rick,coulduse)
            rick*=coulduse
            rick%=1000000007
            coulduse-=1
            rick*=dfs(i,teiru) 
            rick%=1000000007
        return rick
    print(k,dfs(0,-1))
    print(k*dfs(0,-1)%1000000007)
    

    


        
        
        


    
        


        


    




















if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    import sys
    sys.setrecursionlimit(311111)
    import numpy as np
    ikimasu = sys.stdin.buffer.readline
    ini = lambda: int(ins())
    ina = lambda: list(map(int, ikimasu().split()))
    ins = lambda: ikimasu().strip()
    n,k = ina()
    tmp = [[] for _ in range(n)]
    for _ in range(n-1):
        x,x1=  ina()
        x-=1
        x1-=1
        tmp[x].append(x1)
        tmp[x1].append(x)
    def dfs(teiru,ta):
        rick = 1
        coulduse = k-1 if ta==-1 else k-2
        for i in tmp[teiru]:
            if i == ta:
                continue
            rick*=coulduse
            rick%=1000000007
            coulduse-=1
            rick*=dfs(i,teiru) 
            rick%=1000000007
        return rick
    print(k*dfs(0,-1)%1000000007)
    

    


        
        
        


    
        


        


    




















if __name__ == "__main__":
    main()
N,K,X,Y=map(int,input().split())

S=X*K+Y*(N-K)

print(S)

### FIXED CODE ###

N=int(input())
K=int(input())
X=int(input())
Y=int(input())

if N >= K:
  S=X*K+Y*(N-K)

elif N < K:
  S=N*X

print(S)
s = input()
k=int(input())
def ss(s,k):
    M=len(s)
    l=[]
    for i in range(M):
        for j in range(i+1,M+1):
            tmp = s[i:j]
            l.append(tmp)
    l.sort()
    #print(l)
    ret = l[k-1]
    return(ret)

print(ss(s,k))

### FIXED CODE ###

s = input()
k = int(input())

M=len(s)
sss=set()
for i in range(M):
    for j in range(i+1,i+k+1):
        tmp = s[i:j]
        sss.add(tmp)
l = list(sss)
l.sort()
print(l[k-1])
n = list(map(int,input().split()))
n.sort()
print(n[0],n[1],n[2],sep=())

### FIXED CODE ###

n = list(map(int,input().split()))
n.sort()
print(n[0],n[1],n[2],sep=" ")
N = int(input())

print( 0.5 if N % == 0 else ((N//2)+1) /N )


### FIXED CODE ###

N = int(input())
print(0.5 if N % 2 == 0 else ((N//2)+1)/N)
if len(a)==1: print(abs(a[-1]-w))
elif abs(a[-2]-a[-1])>abs(a[-1]-w):
    print(abs(a[-2]-a[-1]))
else: print(abs(a[-1]-w))

### FIXED CODE ###

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

if len(a)==1: print(abs(a[-1]-w))
elif abs(a[-2]-a[-1])>abs(a[-1]-w):
    print(abs(a[-2]-a[-1]))
else: print(abs(a[-1]-w))
n = int(input())
a = input().split()
pl = []
sb = []
for i in range(len(a)):
	pl.append(i+int(a[i])+1)
	if i - int(a[i]) > 1:
		sb.append(i-int(a[i])+1)


if len(sb) == 0:
	print('0')
else:

# spl = sorted(pl)
	isb = [int(i) for i in sb]
	ipl = [int(i) for i in pl]
	ssb = sorted(isb)
	t = min(ssb)
	tl = [0] * max(ipl)
	for i in ssb:
		tl[int(i)-1] += 1
	# print(pl)
	# print(sb)
	# print(tl)
	cnt = 0
	for i in pl:
		cnt += tl[int(i)-1]

	print(cnt)
	



### FIXED CODE ###

n = int(input())
a = input().split()
pl = []
sb = []
for i in range(len(a)):
	pl.append(i+int(a[i])+1)
	if i - int(a[i]) > 0:
		sb.append(i-int(a[i])+1)


if len(sb) == 0:
	print('0')
else:

# spl = sorted(pl)
	isb = [int(i) for i in sb]
	ipl = [int(i) for i in pl]
	ssb = sorted(isb)
	t = min(ssb)
	# tl = [0] * max(ipl)
	tl = [0] * 2000000	
	for i in ssb:
		if int(i)-1 < len(tl):
			tl[int(i)-1] += 1
	# print(pl)
	# print(sb)
	# print(tl)
	cnt = 0
	for i in pl:
		if int(i)-1 < len(tl):
			cnt += tl[int(i)-1]

	print(cnt)
x,a=map(int,input())

if x < a:
    print(0)
else:
    print(10)


### FIXED CODE ###

n=input().split()

if n[0]<n[1]:
    print('0')
else:
    print('10')
S = input()
T = input()

ans = 1000000  # 適当に1001以上を初期値にしておきます

# Tが1文字のときlen(S)回、2文字のときlen(S) - 1回 …… なので、
# len(S) - len(T) + 1 パターンあります

for i in range(len(S) - len(T) + 1):
    score = 0
    U = S[i:i + len(T)]  # Sのi文字目から連続するlen(T)文字を、Uとします
    for j in range(len(T)):
        if U[j] != T[j]:
            score += 1
    ans = min(ans, cur)

print(ans)


### FIXED CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    S = input()
    T = input()
    ls = len(S)
    lt = len(T)

    ans = INF
    for i in range(ls - lt + 1):
        cur = 0
        for j in range(lt):
            if S[i + j] != T[j]:
                cur += 1
        ans = min(ans, cur)

    print(ans)


if __name__ == '__main__':
    main()
# -*- coding: utf-8 -*-
test = input()
a, b, c = map(int, test.split())  # 変数a,b,cにそれぞれN、A、Bをint型にして入力する　
x = []
for i in range(1,a+1):  # list型の変数xに１からNまでの要素を入れる
    x.append(i)


len_x = len(x)  # リスト型の変数xの要素数を獲得

d = 0  # リストの各行の和を入れるための変数
f = []  # 各行の和がA以上B以下の要素を入れるための変数
x = map(str, x)  # リストxの書く要素をstr型に変換

for i in range(len_x):
    e = x[i]           # xのi番目の要素を抽出
    e = list(e)  # xのi番目の要素を一文字ずつのstr型としてリスト型の変数に入れる
    e = map(int, e)  # xのi番目の要素をint型に変換
    e_number = len(e)  # リスト型の変数eの要素数を取得
    d = 0              # 位の合計の判定用の変数
    for g in range(e_number):
        d += e[g]  # 位の合計
    if b <= d <= c:  # 位の合計がA以上B以下ならリストfに要素を追加
        f.append(x[i])
answer = 0  # 条件位合う要素の合計を入れる変数
f = map(int, f)
for h in f:  # 要素に合う要素の合計
    answer += h
print(answer)




### FIXED CODE ###

a = int(input())
b = []
for i in range(a):
    b.append(input())
c = set(b)
print(len(c))
a,b=map(int,input().split())
print(a//b,a%b."{0:10.20f}".format(a/b))


### FIXED CODE ###

a,b=map(int,input().split());print(a//b,a%b,"{:.10f}".format(a/b))
n = int(input())
A = [0]*(10**9+5)
for i in range(n):
    a = int(input())
    A[a]+=1
    A[a]%=2
print(sum(A))


### FIXED CODE ###

n = int(input())
A = {}
for i in range(n):
    a = int(input())
    A[a] = A.get(a, 0)+1
    A[a] %= 2
s = 0
for v in A.values():
    s += v
print(s)
a,b = map(int,input())
print(max(a+b,a-b,a*b))

### FIXED CODE ###

def main():
    a,b = map(int,input().split())
    print(max(a+b,a-b,a*b))

if __name__ == '__main__':
    main()
S = input()
flg = 0
for i in a:
    if flg == 0 and i not in S:
        print(i)
        flg = 1
if flg == 0:
    print("None")

### FIXED CODE ###

a = "abcdefghijklmnopqrstuvwxyz"
S = input()
flg = 0
for i in a:
    if flg == 0 and i not in S:
        print(i)
        flg = 1
if flg == 0:
    print("None")
import math
from functools import reduce

def gcd(numbers):
    return reduce(math.gcd, numbers)

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

a = []
for i in b:
    if i != x:
        a.append(abs(i-x))
print(gcd(a))

### FIXED CODE ###

import fractions
from functools import reduce

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

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

a = []
for i in b:
    if i != x:
        a.append(abs(i-x))
print(gcd(a))
n = int(input())
a = list(map(int, input().split()))
q = int(input())
from collections import Counter
x = Counter(a)
r = sum(a)
for i in range(q):
    b, c = map(int, input().split())
    if b in x:
        m = x[b]
        x.pop(b)
        if c in x:
            x[c] += m
        else:
            x[c] = m
    r += m*(c-b)
    print(r)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
from collections import Counter
x = Counter(a)
r = sum(a)
for i in range(q):
    b, c = map(int, input().split())
    m = 0
    if b in x:
        m = x[b]
        x.pop(b)
        if c in x:
            x[c] += m
        else:
            x[c] = m
    r += m*(c-b)
    print(r)
K, X = map(int, input().split())

ans = [X]

for i in range(K-1):
    ans.append(X+i+1)

ans.reverse()
for i in range(K-1):
    ans.append(X-(i+1))

ans.reverse()
print("".join(ans))


### FIXED CODE ###

K, X = map(int, input().split())
cule = [i for i in range(X-K+1, X+K)]

print(" ".join(repr(i) for i in cule))
x=int(input())

b=0
while True:
    p,m=b, -b
    xp, xm = x+p**5, x+m**5
    if (xp**(1/5)).is_integer():
        ans=[int(xp**(1/5)),p]
        break
    if (xm**(1/5)).is_integer():
        ans=[int(xm**(1/5)),m]
        break
    b+=1

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

### FIXED CODE ###

import math
x=int(input())

b=0
while True:
    p,m=b, -b
    xp, xm = x+p**5, x+m**5
    flag=False
    for i in range(math.ceil(abs(xp)**0.2)+1):
        if i**5 - p**5 == x:
            ans=[i,p]
            flag=True
            break
        if (-1*i)**5 - p**5 == x:
            ans=[-1*i,p]
            flag=True
            break
    for i in range(math.ceil(abs(xm)**0.2)+1):
        if i**5 - m**5 == x:
            ans=[i,m]
            flag=True
            break
        if (-1*i)**5 - m**5 == x:
            ans=[-1*i,m]
            flag=True
            break
    if flag:
        break
    b+=1

print(" ".join(list(map(str,ans))))
N,M = (int(x) for x in input().split())
list = [int(x) for x in input().split()]
tenbou = [input().split() for l in range(M)]
jj = [1] * N

#print(list)
#print(tenbou)

for i in range(N-1):
    x = int(tenbou[i][0]) - 1
    y = int(tenbou[i][1]) - 1
    if list[x] >= list[y]:
        jj[y] = 0
    elif list[y] > list[x]:
        jj[x] = 0


        
#print(jj)
print(jj.count(1))

### FIXED CODE ###

N,M = (int(x) for x in input().split())
hight = [int(x) for x in input().split()]
tenbou = [input().split() for l in range(M)]
result = [1] * N


for i in range(M):
    x = int(tenbou[i][0]) - 1
    y = int(tenbou[i][1]) - 1
    if hight[x] > hight[y]:
        result[y] = 0
    elif hight[y] == hight[x]:
        result[x] = 0
        result[y] = 0
    elif hight[y] > hight[x]:
        result[x] = 0
#print(result)
print(result.count(1))
3 4
5 6
3 3
0 0


### FIXED CODE ###

while True:
    H,W = map(int,input().split())
    if H==W==0:
        break
    print("#"*W)
    for i in range(0,H-2):
        print("#"+"."*(W-2)+"#")
    print("#"*W)
    print()