Harryxun/stf_run huggingface dataset:
from functools import lru_cache

N, M = map(int, input().split())
b = tuple([int(input()) for i in range(M)])

mod = 10**9+7

@lru_cache(maxsize=None)
def Fib(n, a):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    elif (n-2 in a) and n!=0:
        return 0
    else:
        return (Fib(n-1, a) + Fib(n-2, a)) % mod

print(Fib(N+2, b))

### FIXED CODE ###

N, M = map(int, input().split())
#A = [int(input()) for i in range(M)]
flag = [0]*N
for i in range(M):
    flag[int(input())-1] = 1
#A = [i*3 for i in range(N//3)]
#for i in range(N//3):
    #flag[i] = 1

mod = 10**9+7

dp = [0] * N

if flag[0]==0:
#if 1 not in A:
    dp[0] = 1
    if N>1:
        if flag[1]==0:
    #if (2 not in A) and N > 1:
            dp[1] = 2
elif N > 1:
    if flag[1]==0:
    #if 2 not in A:
        dp[1] = 1
    else:
        dp[1] = 0

loop = []
'''
for i in range(2, N):
    if i not in A:
        loop.append(i)
'''
for i in range(2, N):
    if flag[i]==0:
        dp[i] = (dp[i-2] + dp[i-1]) % mod
        #dp[i] = (sum(dp[i-2:i])) % mod

print(dp[N-1])
#print(dp)
import sys
N = int(input())
S = input()
s_list = list(S)
temp_start = N+1
count_1 = 0
count_2 = 0
for i in range(N-1):
    if s_list[i] == "#":
        temp_start = i
        break
if temp_start == N+1:
    print(0)
    sys.exit()
for i in range(N)[::-1]:
    if s_list[i] != "#":
        temp_end = i
        break
for i in range(temp_start,temp_end + 1):
    if s_list[i] == "#":
        count_1 += 1
    else :
        count_2 += 1
print(min(count_1,count_2))

### FIXED CODE ###

import fractions,math,sys
from collections import Counter
n = int(input())
s = list(input())
cnt = Counter(s)
white_l = 0
black_l = 0
min = cnt['.']
for i in range(n):
    if s[i] == '#':
        black_l += 1
        cnt['#'] -= 1
    else:
        white_l += 1
        cnt['.'] -= 1
    if black_l + cnt['.'] < min:
        min = black_l + cnt['.']
print(min)
n = int(input())
li = list(map(int,input().split()))
a = 1
for i in range(n):
  a *= li[i]
if a > 10**18:
  print("-1")
else:
  print(a)

### FIXED CODE ###

a, b = map(int,input().split())
print(a*b)
# N = int(input())

import numpy as np

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

visited = set()
from2to = {}
for i,a in enumerate(As):
    from2to[i+1] = a

id2n_warp = {}
current = 1
loop_anchor = -1
n_warp = 0
visited.add(1)
id2n_warp[1] = 0
while True:
    n_warp += 1
    next_ = from2to[current]
    if n_warp == K:
        print(next_)
        exit()
    if next_ in visited:
        loop_anchor = next_
        break
    else:
        id2n_warp[n_warp] = next_
        visited.add(next_)
    current = next_

K -= id2n_warp[loop_anchor]
# print(n_warp)
# print(K)
# print(id2n_warp[loop_anchor])
K = K % (n_warp - id2n_warp[loop_anchor]) if n_warp - id2n_warp[loop_anchor] > 0 else K

current = loop_anchor
for i in range(K):
    next_ = from2to[current]
    current = next_

print(next_)


### FIXED CODE ###

# N = int(input())

import numpy as np

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

visited = set()
from2to = {}
for i,a in enumerate(As):
    from2to[i+1] = a

id2n_warp = {}
current = 1
loop_anchor = -1
n_warp = 0
visited.add(1)
id2n_warp[1] = 0
while True:
    n_warp += 1
    next_ = from2to[current]
    if n_warp == K:
        print(next_)
        exit()
    if next_ in visited:
        loop_anchor = next_
        break
    else:
        id2n_warp[next_] = n_warp
        visited.add(next_)
    current = next_

K -= id2n_warp[loop_anchor]
# print(n_warp)
# print(K)
# print(id2n_warp[loop_anchor])
K = K % (n_warp - id2n_warp[loop_anchor])
# K = K % (n_warp - id2n_warp[loop_anchor]) if n_warp - id2n_warp[loop_anchor] > 0 else K

current = loop_anchor
for i in range(K):
    next_ = from2to[current]
    current = next_

print(next_)
N = int(input())
A = sorted(map(int, input().split()))
print(sum(A[N:2*N])

### FIXED CODE ###

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

ans = 0
for i in range(2 * N):
    if i % 2 == 1:
        ans += A[3 * N - i - 1]

print(ans)
N=int(input())
num=0
if (N%2==0)or(N%5==0):
    print(-1)
else:
    for i in range(1,N):
        num+=i*7
        if num%N==0:
            break
    print(i)

### FIXED CODE ###

N=int(input())
num = 7
i=1
a=[]
prir1=1
while i<=N:
    xx=num%N
    if xx==0:
        print(i)
        prir1=0
        break
    num=10*xx+7
    i+=1
if prir1:
    print(-1)
import numpy as np

H, W, M = map(int, input().split())
h_t = [0]*H
w_t = [0]*W
t = np.zeros((300000, 300000))
for i in range(M):
    h, w = map(int, input().split())
    t[h-1][w-1] = 1
    h_t[h-1]+=1
    w_t[w-1]+=1
h_max = max(h_t)
h_max_list = [i for i in range(len(h_t)) if h_t[i] == h_max]
w_max = max(w_t)
w_max_list = [i for i in range(len(w_t)) if w_t[i] == w_max]

for h in h_max_list:
    for w in w_max_list:
        if t[h][w] == 0:
            print(h_max + w_max)
            exit()
print(h_max + w_max - 1)

### FIXED CODE ###

import numpy as np

H, W, M = map(int, input().split())
h_t = [0]*H
w_t = [0]*W
t = {}
for i in range(M):
    h, w = map(int, input().split())
    t[(h-1, w-1)] = 1
    h_t[h-1]+=1
    w_t[w-1]+=1
h_max = max(h_t)
h_max_list = [i for i in range(len(h_t)) if h_t[i] == h_max]
w_max = max(w_t)
w_max_list = [i for i in range(len(w_t)) if w_t[i] == w_max]

for h in h_max_list:
    for w in w_max_list:
        if (h, w) not in t:
            print(h_max + w_max)
            exit()
print(h_max + w_max - 1)
a,b=map(int,input().split())
if a*b % 2 = 0:
    print("Even")
else:
    print("Odd")
    
 

### FIXED CODE ###

a, b = map(int, input().split())
if a*b % 2 == 0:
    print('Even')
else:
    print('Odd')
import math

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

result = 0

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

if M == 0:
    for i in range(math.floor((N-1)/2) + 1):
        result += cmb(N - List[M-1]-1-i,i) 
    result = result % 1000000007 
    print(result)

else:
    List = [int(input()) for i in range(M)]
    
    for i in range(math.floor((List[0]-1)/2) + 1):
        result += cmb(List[0]-1-i,i) 
            
    for i in range(M-1):
        if List[i+1] - List[i] == 1:
            result = 0
            break
        else:
            tmp = 0
            for j in range(math.floor((List[i+1]-List[i]-2)/2) + 1):
                tmp += cmb(List[i+1]-List[i]-2-j,j)
            result = result * tmp

    tmp = 0
    for i in range(math.floor((N - List[M-1]-1)/2) + 1):
        tmp += cmb(N - List[M-1]-1-i,i) 

    result = result * tmp
    result = result % 1000000007 
    print(result)

### FIXED CODE ###

N, M = map(int, input().split())
a = [int(input()) for i in range(M)]
a.append(-1)

dp = [0 for i in range(N + 1)]
dp[0] = 1
point = 0
if a[point] == 1:
    dp[1] = 0
    point += 1
else:
    dp[1] = 1
for i in range(2, N + 1):
    if i == a[point]:
        dp[i] = 0
        point += 1
    else:
        dp[i] = (dp[i - 2] + dp[i - 1]) % (10 ** 9 + 7)
print(dp[N])
n = int(input())
s = str(input())
k = int(input())

s =list(s)

for i in range(n):
    if s[i] != s[k]:
        s[i] = '*'

print(''.join(s))

### FIXED CODE ###

n = int(input())
s = str(input())
k = int(input())

s =list(s)

for i in range(n):
    if s[i] != s[k-1]:
        s[i] = '*'

print(''.join(s))
A, B = map(int,input().split())
if B % A == 0:
  print(A+B)
 else:
  print(B-A)
    

### FIXED CODE ###

A, B = list(map(int,input().split()))
if B % A == 0:
  print(A+B)
else:
  print(B-A)
input_data=input()
N,D=map(int,input_data.split())
X=[] 
for n in range(N) :
    X_data=input() 
    X.append(list(map(int,X_data.split())))

output=0

for i in range(N):
    for j in range(N):
        if i>j:
            dist=0
            for y, z in zip(X[i],X[j]):
                dist=dist+(y-z)**2
            if int(dist**(1/2))==dist**(1/2):
                output=output+1
            else:
                output=output+0
        else: pass
print(output)

### FIXED CODE ###

input_data=input()
input_data=input_data.split()
a=int(input_data[0])
b=int(input_data[1])
c=int(input_data[2])

if a*b<c:
    output=a*b
    
else :
    output=c

print(output)
N = int(input())
H = list(map(int,input.split()))
ANS = True
for i in range(1,N):
    if H[N-i] >= H[N-i-1]:
        continue
    else if (H[N-i] - H[N-i-1]) == -1:
        H[N-i-1] += 1
    else:
        ANS = False
        break
if ANS:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

N = int(input())
H = list(map(int,input().split()))
ANS = True
if N == 1:
    pass
else:
    for i in range(N-2,-1,-1):
        if (H[i] - H[i+1]) >= 2:
            ANS = False
            break
        elif (H[i] - H[i+1]) == 1:
            H[i] -= 1

print('Yes' if ANS else 'No')
if __name__ == "__main__":
  N = int(input())
  A = [int(x) for x in input().split()]
  Q = int(input())
  for i in range(Q):
    A.sort()
    B, C = [int(x) for x in input().split()]
    A = [x if x!=B else C for x in A]
    print(sum(A))

### FIXED CODE ###

x = str(input())
if(x.islower()):
  print('a')
else:
  print('A')
n=int(input())
a,b=map(int,input().split())
if n==1:
  print("Hello World")
else:
  print(a+b)


### FIXED CODE ###

n=int(input())
if n==1:
  print("Hello World")
else:
  a=int(input())
  b=int(input())
  print(a+b)
n, y = map(int, raw_input().split())
print("-1 -1 -1")


### FIXED CODE ###

def solve(n, y):
    for man in range(n + 1):
        for gosen in range(n - man + 1):
            sen = n - man - gosen
            if 10000*man + gosen*5000 + sen*1000 == y and man + gosen + sen == n:
                print('{} {} {}'.format(man, gosen, sen))
                return
    print("-1 -1 -1")
    return            

#main
n, y = map(int, raw_input().split())
solve(n, y)
n=int(input())
v=list(map(int,input().split()))
odd=[[0,0] for i in range(10**5+1)]
even=[[0,0] for i in range(10**5+1)]
for i in range(1,10**5+1):
    odd[i][1]=i
    even[i][1]=i
for i in range(n):
    if (i+1)%2==1:
        odd[v[i]][0]+=1
    else:
        even[v[i]][0]+=1
odd=sorted(odd,reverse=True)
even=sorted(even,reverse=True)
ans=0
if(odd[0][0]+even[0][0]==n): #odd[0][0]=n//2
    if(odd[0][1]==even[0][1]):
        ans=n//2
    else:
        ans=0

else:
    # odd 19,1 even 20,19のときに、(1+20)=21よりも(19+19)=38のほうがいいい。
    if(odd[0][1]==even[0][1]):
        if(odd[0][0]+even[1][0]<=odd[1][0]+even[0][0]):
            ans=(n//2-odd[1][0])+(n//2-even[0][0])
        else:
            ans=(n//2-odd[0][0])+(n//2-even[1][0])

    else:
        ans=(n//2-odd[0][0])+(n//2-even[0][0])
print(ans)


### FIXED CODE ###

n=int(input())
n2=list(str(n))
for i in range(3):
    if n2[i]=="1":
        n2[i]="9"
    else:
        n2[i]="1"
new_n="".join(n2)
print(new_n)
a, b = int(input().split())
if a*b % 2 == 0:
  print("Even")
else:
  print("Odd")

### FIXED CODE ###

a, b = map(int, input().split())
if a*b % 2 == 0:
  print("Even")
else:
  print("Odd")
N, M = map(int, input().split())
Ai = [list(map(int, input().split())) for _ in range(M)]

groups = [-1 for i in range(N + 1)] #0番目は使わない
sizes = [1 for _ in range(N + 1)]
Ai.reverse()

value = N * (N - 1) // 2
answers = []
answers.append(value)

def parent(n):
    if groups[n] < 0:
        return n
    return parent(groups[n])

for a in Ai:
    if value <= 0:
        answers.append(0)
        continue
    p1 = parent(a[0])
    p2 = parent(a[1])
    if p1 == p2:
        answers.append(value)
        continue

    value -= sizes[p1] * sizes[p2]
    if p1 > p2:
        sizes[p2] += sizes[p1]
        groups[p1] = p2
    else:
        sizes[p2] += sizes[p1]
        groups[p1] = p2
    answers.append(value)

answers.reverse()
answers = answers[1:]
for a in answers:
    print(a)

### FIXED CODE ###

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

for i in range(0, m):
    a, b = map(int, input().split())
    bridge.append([a - 1, b - 1])

bridge = bridge[1:]
bridge = reversed(bridge)
result = []


parent = [-1] * n
size = [1] * n
def root(v):
    p = parent[v]
    if p >= 0:
        return root(p)
    return v

value = n * (n - 1) // 2
result.append(value)

for b in bridge:
    if value <= 0:
        result.append(0)
        continue
    p0 = root(b[0])
    p1 = root(b[1])
    if p0 == p1:
        result.append(value)
        continue
    s0 = size[p0]
    s1 = size[p1]
    if p0 < p1:
        parent[p1] = p0
        size[p0] += size[p1]
    else:
        parent[p0] = p1
        size[p1] += size[p0]
    value -= s0 * s1
    result.append(max(value, 0))

result = reversed(result)
for r in result:
    print(r)
MOD = 10**9 + 7
N = int(input())
*A, = map(int, input().split())
hats = [0] * 3
ans = 1
for a in A:
    ans = (ans * len([h for h in hats if h == a])) % MOD
    idx = hats.index(a)
    hats[idx] += 1
print(ans)

### FIXED CODE ###

MOD = 10**9 + 7
N = int(input())
*A, = map(int, input().split())
hats = [0] * 3
ans = 1
for a in A:
    ans = (ans * hats.count(a)) % MOD
    for i in range(3):
        if hats[i] == a:
            hats[i] += 1
            break
print(ans)
lengh,num = map(int,input().split())
lis = [input() for i in range(num)]
print("".join(sorted(lis)))

### FIXED CODE ###

num,lengh = map(int,input().split())
lis = [input() for i in range(num)]
print("".join(sorted(lis)))
N,M = list(map(int,input().split()))
xarray = list(map(int,input().split()))
xarray.sort()
print(xarray)
diff = []
if len(xarray) == 1:
    print(0)
else:
    for i in range(len(xarray)-1):
        diff.append(abs(xarray[i+1]-xarray[i]))
    if len(diff) == 0:
        print(0)
    else:
        diff2 = sorted(diff, reverse = True)
        print(diff)
        print(diff2)

        if N == 1:
            
            print(sum(diff2))
        else:
            for j in range(N-1):
                diff2[j] = 0
            print(sum(diff2))
    

### FIXED CODE ###

N,M = list(map(int,input().split()))
xarray = sorted(list(map(int,input().split())))
 
diff = []
if len(xarray) == 1:
    print(0)
elif N >= M:
    print(0)
else:
    for i in range(len(xarray)-1):
        diff.append(abs(xarray[i+1]-xarray[i]))
 
    if len(diff) == 0:
        print(0)
    else:
        diff2 = sorted(diff, reverse = True)
        
 
        if N == 1:
            
            print(sum(diff2))
        else:
            for j in range(N-1):
                diff2[j] = 0
            
            print(sum(diff2))
a = raw_input()
b = raw_input()

a = "".join( sorted( list(a) ) )
b = "".join( sorted( list(b) ) )

yes = True
printed = False

if len(a) < len(b):
    i = 0
    while i < len(a):
        if a[i] != b[i]:
            yes = False
            break
        i += 1
    if yes:
        print "Yes"
        printed = True

if not printed and len(b) > 0:
    i = 0
    b = "".join( sorted( list(b), reverse = True ) )

    while i < len(a):
        if a[i] < b[i]:
            print "Yes"
            printed = True
            break
        elif a[i] > b[i]:
            print "No"
            printed = True
            break
        i += 1
if not printed:
    print "No"


### FIXED CODE ###

a = raw_input()
b = raw_input()

a = "".join( sorted( list(a) ) )
b = "".join( sorted( list(b) ) )

yes = True
printed = False

if len(a) < len(b):
    i = 0
    while i < len(a):
        if a[i] != b[i]:
            yes = False
            break
        i += 1
    if yes:
        print "Yes"
        printed = True

if not printed and len(b) > 0:
    i = 0
    b = "".join( sorted( list(b), reverse = True ) )

    while i < len(a) and i < len(b):
        if a[i] < b[i]:
            print "Yes"
            printed = True
            break
        elif a[i] > b[i]:
            print "No"
            printed = True
            break
        i += 1
if not printed:
    print "No"
import numpy as np

s = input()[::-1]

dp = np.zeros((len(s),13), dtype="uint64")

if s[0] =="?":
    dp[0] = [1]*10+[0]*3
else:
    dp[0][int(s[0])] =1

L1 = range(1, len(s))

for i in L1:
    if s[i] == "?":
        mod = pow(10, i, 13)
        mod_list = ((mod*i)%13 for i in range(10))
        for j in mod_list:
            dp[i, :] += np.roll(dp[i - 1, :], j)
        dp[i, :] %= (10**9+7)
    else:
        mod = (pow(10, i, 13)*int(s[i]))%13
        dp[i, :] += np.roll(dp[i - 1, :], mod)

print(int(dp[-1][5])%(10**9+7))

### FIXED CODE ###

s=input()
l=len(s)

mod=10**9+7

dp=[[0 for j in range(13)] for i in range(l)]

if s[0] =="?":
    dp[0] = [1]*10+[0]*3
else:
    dp[0][int(s[0])] =1

for i in range(1, l):
 if s[i]=='?':
   for j in range(10):
     for k in range(13):
       dp[i][(k*10+j)%13]+=dp[i-1][k]%mod
 else:
   for k in range(13):
     dp[i][(k*10+int(s[i]))%13]+=dp[i-1][k]%mod
print(dp[-1][5]%mod)
n, m = list(map(int, input().split()))
s = []
c = []
for _ in range(m):
    s_i, c_i = list(input().split())
    s.append(int(s_i))
    c.append(c_i)
for i in range(10 ** n):
    num = list(str(i))
    for j in range(m):
        if len(num) != n or num[s[j] - 1] != c[j]:
            break
    else:
        print(i)
        return
print(-1)

### FIXED CODE ###

n, m = list(map(int, input().split()))
s = []
c = []
for _ in range(m):
    s_i, c_i = list(input().split())
    s.append(int(s_i))
    c.append(c_i)
for i in range(10 ** n):
    num = str(i)
    if len(num) == n and all([num[s[j] - 1] == c[j] for j in range(m)]):
        print(num)
        exit()
print(-1)
x= input()
a = int(x[0])
b = int(x[2])
print(a*b,a*2+b*2)

### FIXED CODE ###

x=input().split()
a = int(x[0])
b = int(x[1])

print( a*b , a*2+b*2 )
n = input()
A = map(int, raw_input().split())

Q = input()
m = map(int, raw_input().split())

f = []
f[0] = 1

for i in range(n):
  for j in range(2000):
    if(j + A < 2000 && f[j] == 1):
      f[j + A] == 1
    
for i in range(Q):
    if(f[m] == 1):
    print "yes"
  else:
    print "no"

### FIXED CODE ###

n = int(raw_input())
A = map(int,raw_input().split())
Q = int(raw_input())
m = map(int,raw_input().split())

def s(i, m):
  if m == 0:
    return True
  if i >= n or m > sum(A):
    return False
  r = s(i + 1, m) or s(i + 1, m - A[i])
  return r

for j in range(Q):
  if s(0, m[j]):
    print "yes"
  else:
    print "no"
if int(input) in [7, 5, 3]: print("YES")
else: print("NO")

### FIXED CODE ###

print("YES" if int(input()) in [3, 5, 7] else "NO")
a, b = map(int, input().split())
if a*b%2 == 0{
  print("Even")
}else{
  print("Odd")
}


### FIXED CODE ###

# -*- coding: utf-8 -*-
a, b = map(int, input().split())
if a*b%2 == 0:
  print("Even")
else:
  print("Odd")
N = int(input())
h = list(map(int, input().split())) + [0]*10010

dp = [float("inf")]*10010
dp[0] = 0

for i in range(N):
    dp[i+1] = min(dp[i+1], dp[i] + abs(h[i+1] - h[i]))
    dp[i+2] = min(dp[i+2], dp[i] + abs(h[i+2] - h[i]))
    # print(dp)
print(dp[N-1])

### FIXED CODE ###

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

dp = [0]*n
for i in range(n):
    if i >= 2:
        dp[i] = min(dp[i-1]+abs(a[i]-a[i-1]), dp[i-2]+abs(a[i]-a[i-2]))
    elif i == 1:
        dp[i] = abs(a[i]-a[i-1])
print(dp[-1])
list=input().split()
l=len(list)
output=""
for i in l:
	if list[i]=="0" or "1":
		output=output+list[i]
	else:
		if i!=0:
			output=output-list[i-1]
print(output)

### FIXED CODE ###

nyu=input()
shutu=[]
for i in nyu:
	if i=="B":
		if len(shutu)!=0:
			shutu.pop(-1)
	else:
		shutu.append(i)
kekka="".join(shutu)
print(kekka)
import sys
sys.setrecursionlimit(100000)
N, A, B, C = map(int, input().split())
l = [int(input()) for i in range(n)]
inf = 10 ** 9

def dfs(cur, a, b, c):
    if cur == N:
        return abs(a-A)+abs(b-B)+abs(c-C) - 30 if min(a, b, c) >0 else inf
    ret0 = dfs(cur+1, a,b,c)
    ret1 = dfs(cur+1, a+l[cur], b, c) + 10
    ret2 = dfs(cur+1, a, b+l[cur], c) +10
    ret3 = dfs(cur+1, a,b,c+l[cur]) +10
    return min(ret0, ret1, ret2, ret3)

print(dfs(0, 0, 0, 0))

### FIXED CODE ###

N, A, B, C = map(int, input().split())
l = [int(input()) for i in range(N)]
inf = 10 ** 9

def dfs(cur, a, b, c):
    if cur == N:
        return abs(a-A)+abs(b-B)+abs(c-C) - 30 if min(a, b, c) >0 else inf
    ret0 = dfs(cur+1, a,b,c)
    ret1 = dfs(cur+1, a+l[cur], b, c) + 10
    ret2 = dfs(cur+1, a, b+l[cur], c) +10
    ret3 = dfs(cur+1, a,b,c+l[cur]) +10
    return min(ret0, ret1, ret2, ret3)

print(dfs(0, 0, 0, 0))
h,w=map(int,input().split())
a=[]
for i in range(h):
	d=input()
	if d.count("#")!=0:
		a.append(d)
ss=0
for i in range(w-ss-1):
	cnt=0
	for j in range(len(a)):
		if a[j][i]=="#":
			cnt+=1
	if cnt==0:
		for jj in range(len(a)):
			a[jj]=a[jj][:i]+a[jj][i+1:]
			ss+=1
for i in range(len(a)):
	print(a[i])


### FIXED CODE ###

A=[]
h,w=map(int,input().split())
for i in range(h):
	s=input()
	if s.count("#")!=0:
		A.append(s)
B=[]
C=[]
for i in range(w):
	cnt=0
	for j in range(len(A)):
		if A[j][i]==".":
			cnt+=1
	if cnt==len(A):
		B.append(i)
for i in range(w):
	c=""
	for j in range(len(A)):
		if i not in B:
			c+=A[j][i]
	if len(c)>0:
		C.append(c)
for j in range(len(C[0])):
	p=""
	for i in range(len(C)):
		p+=C[i][j]
	print(p)
# AOJ GRL_1_A
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A

INF = 100000000

def solve(v, e, dic):
    dp = []
    for i in range(0, v):
        dp += [[INF] * v ]
        for t, d in dic[i]:
            dp[i][t] = d
        dp[i][i] = 0
    for k in range(0, v):
        for i in range(0, v):
            for j in range(0, v):
                if dp[i][j] > dp[i][k] + dp[k][j]:
                    dp[i][j] = dp[i][k] + dp[k][j]
    return dp

dic = {}
dp = []
line = input()
v, e, r = list(map(int, list(line.split())))
for _ in range(0, e):
    line = input()
    s, t, d = list(map(int, list(line.split())))
    if s not in dic:
        dic[s] = [[t, d]]
    else:
        dic[s] += [[t, d]]
dp = solve(v, e, dic)
for i in range(0, v):
    print(dp[r][i] if dp[r][i] != INF else "INF")


### FIXED CODE ###

# AOJ GRL_1_A
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A

from heapq import heappush, heappop

INF = 10000000000

def solve(r, v, dic):
    dp = []
    q = []
    dp = [INF] * v
    dp[r] = 0
    heappush(q, (0, r))
    while q:
        cost, vtx = heappop(q)
        if dp[vtx] < cost:
            continue
        if vtx not in dic:
            continue
        for vtx1, cost1 in dic[vtx]:
            if cost + cost1 < dp[vtx1]:
                dp[vtx1] = cost + cost1
                heappush(q, (cost + cost1, vtx1))
    return dp

dic = {}
dp = []
line = input()
v, e, r = list(map(int, line.split()))
for _ in range(0, e):
    line = input()
    s, t, d = list(map(int, line.split()))
    if s not in dic:
        dic[s] = [[t, d]]
    else:
        dic[s] += [[t, d]]
dp = solve(r, v, dic)
for t in range(0, v):
    print(dp[t] if dp[t] != INF else "INF")