Harryxun/stf_run huggingface dataset:
from collections import deque

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

q = deque()

for _ in range(N):
	c = int(input())
	
	if len(q) == M:
		q.popleft()
	
	q.append(c)
	
for _ in reversed(q):
	print(_)

### FIXED CODE ###

N, M = map(int, raw_input().split(' '))

q = [ int(input()) for _ in range(N) ]
poll = set()

cnt = 0

for _ in reversed(q):
	if not _ in poll:
		print(_)
		
		cnt = cnt + 1
		
		if cnt == M:
			break	
		
		poll.add(_)
ans = 0
N = int(input())
for i in range(N):
  r1, r2 = input().sprit()
  ans += int(r2) - int(r1) + 1
print(ans)

### FIXED CODE ###

ans = 0
for i in range(int(input())):
  r1, r2 = input().split()
  ans += int(r2) - int(r1) + 1
print(ans)
n, q = map(int, input().split())
c = [0] * n
l = {}
for i in range(n - 1):
    a, b = map(int, input().split())
    l[b] = a
for i in range(q):
    p, x = map(int, input().split())
    c[p - 1] += x
for i in range(2, n + 1):
    c[i - 1] += c[l[i] - 1]
print(*c)


### FIXED CODE ###

from collections import defaultdict, deque
import sys
sys.setrecursionlimit(10**9)


N, Q = map(int, input().split())
count = [0] * N
parent = defaultdict(int)
t = [[] for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    t[a - 1].append(b)
    t[b - 1].append(a)

for i in range(Q):
    p, x = map(int, input().split())
    count[p - 1] += x


f = [False] * N
q = deque([1])
while(q):
    n = q.popleft()
    f[n-1] = True
    for i in t[n-1]:
        if f[i-1]:
            continue
        q.append(i)
        count[i-1]+=count[n-1]
        f[i-1] = True
#for i in range(1, N):
#    count[i] += count[parent[i + 1] - 1]
#print(parent)
print(*count)
# -*- coding: utf-8 -*-

# 入力
N, X = map(int, input().split())
m = [int(input()) for i in range(N)]

cnt = 0

# 最初に全種類生産
for i in m:
    X -= i
    cnt += 1

# 最も安く作れるものを量産
m.sort()
cnt += int(X / m[0])

# 出力
print(cnt)

### FIXED CODE ###

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

# 入力
S = input()

y = 700
S = list(S)
for i in S:
    if i == 'o':
        y += 100

# 出力
print(y)
K,X = map(int,input().split())
print(*range(X-K-+1,X+K)))

### FIXED CODE ###

K,X = map(int,input().split())
x = " ".join(map(str,list(range(X-K+1,X+K))))
print(x)
# -*- coding: utf-8 -*-


input()
l = list(map(lambda x: int(x), str(input()).split(" ")))
r = 1
finished = False
for i in l:
    r = r * l
    if r > 10 ** 18:
        print(str(-1))
        finished = True
        break

if not finished:
    print(str(r))

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys

input()
l = list(map(lambda x: int(x), str(input()).split(" ")))
r = 1
finished = False

for i in l:
  if i == 0:
    print(str(0))
    sys.exit()
    
for i in l:
    r = r * i
    if r > 10 ** 18:
        print(str(-1))
        sys.exit()

print(str(r))
#include <iostream>
#include <string>
#include <vector>
#include <string.h>
#include <algorithm>

using namespace std;


int main(){
  int n;
  cin >> k >> s;
  count=0;
  for(int x=0; x<<k+1; x++){
    for(int y=0; y<<k+1; y++){
      for(int z=0; z<<k+1; z++){
        if(x+y+z==s){
          count++;
        }
      }  
    }
  }
  cout << count << endl;
  return 0;
}


### FIXED CODE ###

k,s= list(map(int, input().split()))
count=0
for x in range(k+1):
    for y in range(k+1):
            if 0<=s-x-y <=k:
                count+=1
print(count)
import fraction

def gcd_1(a):
    p = fraction.gcd(a[0],a[1])
    if len(a) > 2:
        for i in range(2,len(a)):
            p = gcd_1([p,a[i]])
    else:
        p = fraction.gcd(a[0],a[1])

    return p

n = int(input())
a = [int(i) for i in input().split()]

print(gcd_1(a))


### FIXED CODE ###

import fractions
 
def gcd_1(a):
    p = fractions.gcd(a[0],a[1])
    if len(a) > 2:
        for i in range(2,len(a)):
            p = gcd_1([p,a[i]])
    else:
        p = fractions.gcd(a[0],a[1])
 
    return p
 
n = int(input())
a = [int(i) for i in input().split()]
 
print(gcd_1(a))
#!/usr/bin/env python
# coding: utf-8

# In[23]:


def func():
    N,Q = map(int, input().split())
    ab = []
    nodes = {}
    for _ in range(N-1):
        ab.append(list(map(int, input().split())))
    ab = sorted(ab,key=lambda x:x[0])
    graph = {}
    for a,b in ab:
        if a not in graph:
            graph[a] = [b]
        else:
            graph[a].append(b)
    cnt = [0]*N
    for j in range(Q):
        p,x = map(int, input().split())
        calc(graph,p,cnt,x)
    print(cnt)


# In[26]:


def calc(graph,node,cnt,x):
    cnt[node-1] += x
    if node in graph:
        for n in graph[node]:
            calc(graph,n,cnt,x)
    return cnt


# In[28]:


if __name__ == "__main__":
    func()


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[32]:


from collections import deque


# In[37]:


def func():
    N,Q = map(int, input().split())
    graph = [[] for _ in range(N)]
    for _ in range(N-1):
        a,b = map(int, input().split())
        a,b = a-1,b-1
        graph[a].append(b)
        graph[b].append(a)
    cnt = [0]*N
    for j in range(Q):
        p,x = map(int, input().split())
        cnt[p-1] += x
    q = deque([[0,-1,cnt[0]]])
    d = [-1]*N
    while q:
        cur,fr,p = q.popleft()
        d[cur] = p
        for nex in graph[cur]:
            if nex == fr:
                continue
            q.append([nex,cur,p+cnt[nex]])
    ans = []
    for i in range(N):
        ans.append(d[i])
    print(*ans)


# In[38]:


if __name__ == "__main__":
    func()


# In[ ]:
import sys

S = input()

for i in range(3):
  if S[i] = S[i+1]:
    print("Bad")
    sys.exit()
print("Good")
  

### FIXED CODE ###

import sys

S = input()

for i in range(3):
  if S[i] == S[i+1]:
    print("Bad")
    sys.exit()
print("Good")
import sys

def main():
    N = input()
    A = input()
    x = N % 500
    if x<=A:
        print('Yes')
    else:
        print('No')

main()

### FIXED CODE ###

import sys

def main():
    N = int(input())
    A = int(input())
    x = N % 500
    if x<=A:
        print('Yes')
    else:
        print('No')

main()
N,Q = map(int,input().split())
aLst = [[int(i) for i in input().split()] for _ in range(N-1)]
pLst = [[int(i) for i in input().split()] for _ in range(Q)]
to = [[]for _ in range(N)]

for i in aLst:
    a = i[0] -1
    b = i[1] -1
    to[a].append(b)
    to[b].append(a)

ps = [0]*N
for i in pLst:
    a = i[0] -1
    b = i[1]
    ps[a] += b

def dfs(v, i):
    for j in to[v]:
        if i == j:
            continue
        ps[j] += ps[v]
        dfs(j,v)

dfs(0,-1)
print(' '.join(map(str, ps)))


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,Q = map(int,input().split())
aLst = [[int(x) for x in input().split()] for _ in range(N-1)]
pLst = [[int(x) for x in input().split()] for _ in range(Q)]

tmpLst = [[] for _ in range(N+1)]
for i, j in aLst:
    tmpLst[i].append(j)
    tmpLst[j].append(i)

ansLst = [0] * (N + 1)
for i,j in pLst:
    ansLst[i] += j

def dfs(v, p):
    for i in tmpLst[v]:
        if i == p:
            continue
        ansLst[i] += ansLst[v]
        dfs(i, v)


dfs(1, 0)

ans = ' '.join(map(str, ansLst[1:]))
print(ans)
K = int(input())
X = int(input())
K = K *500
if K >= X:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

k,x = [int(x) for x in input().split()]

k = k * 500 

if k >= x:
  print("Yes")
else:
	print("No")
N = int(input())
A = list(map(int, input().split()))

Stock = 0
Money = 1000
 
for i in range(N-1):
    if A[i] < A[i + 1]:

        Stock = Money // A[i]
        Money %= A[i]
        Money += Stock * A[i+1]
print(Money)

### FIXED CODE ###

import numpy as np
a = int(input())
print(int( np.ceil((2000-a)/200)))
alphabet = 'abcdefghijklmnopqrstuvwxyz'
num_2_alpha = {i:alphabet[i - 1] for i in range(1,27)}

def named(N):
  _ = ''
  while N > 0:
    a = N % 26
    N //= 26
    _ += num_2_alpha[a]
  
  return _[-1::-1]

N = int(input())
print(named(N))

### FIXED CODE ###

alpha = [chr(i + 97) for i in range(26)] 
N = int(input())
name = ''
while N >= 1:
  N -= 1
  _ = N % 26
  name += alpha[_]
  N //= 26
  
print(name[-1::-1])
N=int(input())
A=[int(i) for i in input().split()]
T=[[A[0],A[1]]]
k=0
for i in range(2,N):
    if len(T[k])<=1:
        T[k].append(A[i])
        continue
    if not((T[k][0]>=A[i-2]>=A[i-1]>=A[i]) or (T[k][0]<=A[i-2]<=A[i-1]<=A[i])):
        k+=1
        T.append([A[i]])
    else:
        T[k].append(A[i])
print(len(T))


### FIXED CODE ###

N=int(input())
A=[int(i) for i in input().split()]
if N==1:
    print(1)
    exit()
T=[[A[0],A[1]]]
k=0
for i in range(2,N):
    if len(T[k])<=1:
        T[k].append(A[i])
        continue
    if not((T[k][0]>=A[i-2]>=A[i-1]>=A[i]) or (T[k][0]<=A[i-2]<=A[i-1]<=A[i])):
        k+=1
        T.append([A[i]])
    else:
        T[k].append(A[i])
print(len(T))
def popcount(n):
    return bin(n).count("1")


def f(n):
    tmp = n
    count = 0
    while tmp > 0:
        tmp %= popcount(tmp)
        count += 1
    return count


n = int(input())
# f(0)~f(n)までを計算しておく
F = [f(i) for i in range(n + 2)]
x = input()
pcx = x.count("1")
# xをpcx-1,pcx+1で割ったあまりをそれぞれ計算
a, b = 0, 0
if pcx > 0:
    for i in range(n):
        if x[i] == "1":
            a += pow(2, n - i - 1, pcx - 1)
            a %= (pcx - 1)
            b += pow(2, n - i - 1, pcx + 1)
            b %= (pcx + 1)
else:
    for i in range(n):
        print(1)
    exit()
for i in range(n):
    if x[i] == "1":
        print(1 + f((a - pow(2, n - i - 1, pcx - 1)) % (pcx - 1)))
    else:
        print(1 + f((b + pow(2, n - i - 1, pcx + 1)) % (pcx + 1)))


### FIXED CODE ###

def popcount(n):
    return bin(n).count("1")


def f(n):
    tmp = n
    count = 0
    while tmp > 0:
        tmp %= popcount(tmp)
        count += 1
    return count


n = int(input())
# f(0)~f(n)までを計算しておく
F = [f(i) for i in range(n + 2)]
x = input()
pcx = x.count("1")
# xをpcx-1,pcx+1で割ったあまりをそれぞれ計算

a, b = 0, 0
if pcx == 1:
    for i in range(n):
        if x[i] == "1":
            b += pow(2, n - i - 1, pcx + 1)
            b %= (pcx + 1)
    for i in range(n):
        if x[i] == "1":
            print(0)
        else:
            print(1 + f((b + pow(2, n - i - 1, pcx + 1)) % (pcx + 1)))
    exit()

if pcx > 1:
    for i in range(n):
        if x[i] == "1":
            a += pow(2, n - i - 1, pcx - 1)
            a %= (pcx - 1)
            b += pow(2, n - i - 1, pcx + 1)
            b %= (pcx + 1)
else:
    for i in range(n):
        print(1)
    exit()
for i in range(n):
    if x[i] == "1":
        print(1 + f((a - pow(2, n - i - 1, pcx - 1)) % (pcx - 1)))
    else:
        print(1 + f((b + pow(2, n - i - 1, pcx + 1)) % (pcx + 1)))
N = d[0]
T = d[1]
min = 10000
for i in range(0, N-1):
    d = list(map(int,input().strip().split(' ')))
    c = d[0]
    t = d[1]
    if t <= T:
        if min >= c:
            min = c
if min == 10000:
    print("TLE")
    exit()
print(min)


### FIXED CODE ###

d = list(map(int,(input().strip().split(' '))))
N = d[0]
T = d[1]
min = 100000000
for i in range(0, N):
    d = list(map(int,input().strip().split(' ')))
    c = d[0]
    t = d[1]
    if t <= T:
        if min >= c:
            min = c
if min == 100000000:
    print("TLE")
else:
    print(min)
while True:
    m, f, r = [int(i) for i in input().solit()]

    if m == f == r == -1:
        break

    elif m == -1 or f == -1:
        print("F")

    elif m + f >= 80:
        print("A")

    elif 65 <= m + f < 80:
        print("B")

    elif 50 <= m + f < 65:
        print("C")

    elif 30 <= m + f < 50:
        if r > 50:
            print("C")
        else:
            print("D")

    elif m + f < 30:
        print("F")

### FIXED CODE ###

while True:
    m, f, r = [int(i) for i in input().split()]

    if m == f == r == -1:
        break

    elif m == -1 or f == -1:
        print("F")

    elif m + f >= 80:
        print("A")

    elif 65 <= m + f < 80:
        print("B")

    elif 50 <= m + f < 65:
        print("C")

    elif 30 <= m + f < 50:
        if r >= 50:
            print("C")
        else:
            print("D")

    elif m + f < 30:
        print("F")

    elif m + f < 30:
        print("F")
m = input()
print(f"{int(m[0])+int(m[1])+int(m[2])}")

### FIXED CODE ###

m = input()
a = int(m[0]) + int(m[1]) + int(m[2])
print (a)
s,t = map(input())
c=0

for i in range(len(s)):
  if s[i]!=t[i]:
    c +=1

print(c)

### FIXED CODE ###

s = input()
t =input()
c=0

for i in range(len(s)):
  if s[i]!=t[i]:
    c +=1

print(c)
N = int(input())
res = 0
both = 0
h = 0
b = 0
for i in range(N):
  inp = input()
  if 'AB' in inp:
    res += 1
  if 'B'==inp[0] and 'A'==inp[-1]:
    both+=1
  elif 'B'==inp[0]:
    # print (inp)
    h+=1
  elif 'A'==inp[-1]:
    # print (inp)
    b += 1
if max(h,b)>0 or both==0:
    print(res+min(h,b)+both)
elif max(a,b)==0:
    print(res+both-1)

### FIXED CODE ###

n=int(input())
s=[0]*n
ct=0
a=0
b=0
c=0
for i in range(n):
    s[i]=input()
for i in range(n):
    for j in range(len(s[i])):
        t=s[i]
        ts=list(t)
        ts.append(0)
        if ts[j]=='A' and ts[j+1]=='B':
            ct+=1
    if ts[0]=='B' and ts[len(s[i])-1]!='A':
        a+=1
    if ts[len(s[i])-1]=='A' and ts[0]!='B':
        b+=1
    if ts[0]=='B' and ts[len(s[i])-1]=='A':
        c+=1
ct += max(0,c -1)
if c !=0:
  if a > 0 and b >0:
    ct += 2 + min(a-1,b-1)
  elif a>0:
    ct += 1 + min(a-1,b)
  elif b>0:
    ct += 1 + min(a,b-1)
else:
  ct += min(a,b)
print(ct)
a = int(input())
b = int(input())

if (a == 1 || b == 2) && (a == 1 || b == 2):
    print(3)
elif (a == 2 || b == 3) && (a == 2 || b == 3):
    print(1)
else
    print(2)


### FIXED CODE ###

a = int(input())
b = int(input())
print(6 - a - b)
a,b=map(int,input().split())
print a*b,(a+b)*2

### FIXED CODE ###

[a,b]=map(int,input().split())
print(a*b,(a+b)*2)
s=input()
dic={A:'T',T:'A',C:'G',G:'C'}
print(dic[s])

### FIXED CODE ###

s=str(input())
if s=='A':
  print('T')
elif s=='T':
  print('A')
elif s=='G':
  print('C')
elif s=='C':
  print('G')
a = int(input())
while i < a:
  if i %5 != 0 and i %3 != 0:
    total += a
print(total)

### FIXED CODE ###

a = int(input())
total = 0
for i in range(1, a+1):
  if i % 5 != 0 and i % 3 != 0:
    total += i

print(total)
from statistics import *
while True:
    n = int(input())
    if(n == 0): break
    data = list(map(int,input().split()))
    print(stdev(data))


### FIXED CODE ###

from math import *
while True:
    n = int(input())
    if(n == 0 ): break
    data = list(map(int,input().split()))  
    a = sum(data) / n
    b = 0
    c = 0
    for i in data:
        b += pow(i-a,2)
    c = sqrt(b/n)
    
    print(c)
list(S)
list(T)

a=0

if S[0] = T[0]:
  a = a + 1

if S[1] = T[1]:
  a = a + 1

if S[2] = T[2]:
  a = a +1

### FIXED CODE ###

S = input()
T = input()
 
q = 0
for n in range(3):
  if S[n] ==T[n]:
    q +=1
print(q)
N = float(input())
A = list(map(float, input().split()))
j = float(0)
ans = float(0)
for i in A:
    J += 1/i
ans = 1/j
print(ans)

### FIXED CODE ###

N = float(input())
A = list(map(float, input().split()))
j = float(0)
ans = float(0)
for i in A:
    j += 1/i
ans = 1/j
print(ans)
import numpy as np
m,k=map(int,input().split())
d={int(x) for x in input().split()}
e={np.arange(10)}
f=list(d&e)
ans=[]
for i in f:
    for j in f:
        for k in f:
            for l in f:
                ans.append(1000*i+100*j+10*k+l)
print(min(ans))



### FIXED CODE ###

n,k=map(int,input().split())
s=set(input().split())
while True:
    l=list(str(n))
    for i in l:
        if i in s:
            break
    else:
        break
            
    n += 1
print(n)
n, m = map(int, input().split())

eva = [[0] for _ in range(n)]

ac = 0
wa = 0

for i in range(m):
    a = input().split()
    q = int(a[0])
    s = a[1]
    if "AC" in eva[q]:
        pass
    else:
        if s == "AC":
            ac += 1
            eva[q].append("AC")
        else:
            wa += 1
            eva[q] += 1

print(ac, wa)


### FIXED CODE ###

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

eva = [[0, 0] for _ in range(n)]

ac = 0
penalty = 0

for i in range(m):
    q, s = input().split()
    if eva[int(q) - 1][1] == 0:
        if s == "WA":
            eva[int(q) - 1][0] += 1
        else:
            eva[int(q) - 1][1] += 1
            ac += 1
            penalty += eva[int(q) - 1][0]
    else:
        pass

print(ac, penalty)
a, b = map(int, input().split())
num = int('a'+'b')
import math
sq = math.sqrt(num)
if isinstance(sq, int):
  print('Yes')
else:
  print('No')

### FIXED CODE ###

num = int(input().replace(" ",""))
print("Yes" if (num**0.5)%1==0 else "No" )
#import time
import numpy as np
from math import *

def main():
    A, B, H, M = list(map(int, input().split()))
    pai = 3.1415926535897323846264338327950
    kakuH = H*360/12 + M*30/60
    kakuM = M*360/60
    kakuS = kakuH - kakuM
    #print(kakuH, kakuM, kakuS)
    ans =(A**2 + B**2 - 2*A*B*np.cos(kakuS*pai/180)) )**(1/2)

    return ans

def absolute(a, b):
    if a>=b:
        if a-b>180:
            return 360-(a-b)
        else:
            return a-b
    else:
        if b-a>180:
            return 360-(b-a)
        else:
            return b-a

if __name__ == '__main__':
    #start = time.time()
    print(main())
    #elapsed_time = time.time() - start
    #print("経過時間:{}".format(elapsed_time * 1000) + "[msec]")

### FIXED CODE ###

#import time
import numpy as np
from math import *

def main():
    A, B, H, M = list(map(int, input().split()))
    pai = 3.1415926535897323846264338327950
    kakuH = H*360/12 + M*30/60
    kakuM = M*360/60
    kakuS = absolute(kakuH, kakuM)
    #print(kakuH, kakuM, kakuS)
    ans =(A**2 + B**2 - 2*A*B*cos(radians(kakuS)) )**(1/2)

    return ans

def absolute(a, b):
    if a>=b:
        if a-b>180:
            return 360-(a-b)
        else:
            return a-b
    else:
        if b-a>180:
            return 360-(b-a)
        else:
            return b-a

if __name__ == '__main__':
    #start = time.time()
    print(main())
    #elapsed_time = time.time() - start
    #print("経過時間:{}".format(elapsed_time * 1000) + "[msec]")
# C
n, m = map(int, input().split())
ab = [0, 0] * n
for i in range(n):
    ab[i] = map(int, input().split())
ab.sort(key=lambda x:x[0])

cost = 0
for i in range(n):
    value = ab[i][0]
    num = ab[i][1]
    if num > m:
        cost += value * m
        break
    else:
        cost += value * num
        m -= num
print(cost)

### FIXED CODE ###

# C
n, m = map(int, input().split())
ab = [[int(i) for i in input().split()] for i in range(n)]
ab.sort(key=lambda x: x[0])
index = 0
ans = 0
while m > 0 and index <= n:
    if ab[index][1] <= m:
        ans += ab[index][0] * ab[index][1]
        m -= ab[index][1]
    else:
        ans += ab[index][0] * m
        m = 0
    index += 1
print(ans)
lst = map(int, input().split())
    print('Yes' if len(set(lst)) >= 2 else 'No')

### FIXED CODE ###

lst = list(map(int, input().split()))
print('Yes' if len(set(lst)) == 2 else 'No')
from collections import deque

def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs


MOD = 10**9+7
fact, fact_inv = prepare(10+10**5, MOD)


n, k = map(int,input().split())
e = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)
    
colored = [False]*n
# 根を決める
for i in range(n):
    if len(e[i]) == 1:
        s = i
colored = [False]*n
# 根を決める
for i in range(n):
    if len(e[i]) == 1:
        s = i
colored[s] = True
num = len(e[s])
ans = fact[k] * fact_inv[k-1-num] % MOD
ans %= MOD
d = deque()
for i in e[0]:
    colored[i] = True
    d.append(i)
while d:
    f = d.pop()
    num = len(e[f]) - 1
    if num == 0:
        continue
    ans *= fact[k-2] * fact_inv[k-2-num] % MOD
    ans %= MOD
    for i in e[f]:
        if not colored[i]:
            colored[i] = True
            d.appendleft(i)
print(ans % MOD)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue Aug 25 08:44:21 2020

@author: teppe
"""

from collections import deque

def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs

MOD = 10**9+7
fact, fact_inv = prepare(10+10**5, MOD)

def perm(n,k):
  if k > n or k < 0:
    return 0
  return fact[n] * fact_inv[n-k] % MOD


n, k = map(int,input().split())
e = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)
 
colored = [False]*n
colored[0] = True
num = len(e[0])
ans = perm(k, 1+num)
d = deque()
for i in e[0]:
    colored[i] = True
    d.append(i)
while d:
    f = d.pop()
    num = len(e[f]) - 1
    if num == 0:
        continue
    ans *= perm(k-2, num)
    ans %= MOD
    for i in e[f]:
        if not colored[i]:
            colored[i] = True
            d.appendleft(i)
print(ans % MOD)
S=list(input())
q=int(input())
T=['1' for j in range(10**5)]
for i in range(q):
  query=list(input().split())
  if query[0]=='1':
    p=len(S)
    for k in range(p):
      T[k]=S[p-1-k]
    S=T[:p]  
  else:
    if query[1]=='1':
      S.insert(0,query[2])
    else:
      S.append(query[2])
moji=''.join(S)
print(moji)

### FIXED CODE ###

t=list(input())
q=int(input())
s=[]

for i in range(q):
  query=list(input().split())
  if query[0]=='1':
    s,t=t,s
  else:
    if query[1]=='1':
      s.extend(query[2])
    else:
      t.extend(query[2])
if s==[]:
  s=t
else:
  s.reverse()
  s.extend(t)

moji=''.join(s)
print(moji)
N = int(input())
S = [input() for i in range(N)]
a = set(S)
print(len(a))

### FIXED CODE ###

S, W = map(int, input().split())
print('unsafe' if W>=S else 'safe')
H,W,K = map(int, input().split())
fields = [list(input()) for i in range(H)]
bins = []
hs = [] #区切る位置
ws = []
for i,f in enumerate(fields):
    if "#" in f:
        hs.append(i)
hs = hs+[H]
ans = [[0]*(W+1) for i in range(H+1)]
cnt = 0
# print(hs)
for i in range(1,len(hs)):
    h_fr = hs[i-1] 
    h_to = hs[i]
    f = fields[h_fr:h_to]
    ws = []
    for j in range(W):
        for i in range(h_fr,h_to):
             if fields[i][j] == "#":
                 ws.append(j)
    ws += [W]
    # print(h_fr,h_to,ws)
    for j in range(1,len(ws)):
        cnt += 1
        w_fr = ws[j-1]
        w_to = ws[j]
        # print(cnt,[[cnt]*(w_to-w_fr) for i in range(h_to-h_fr)] )
        f = [[cnt]*(w_to-w_fr) for i in range(h_to-h_fr)]
        for i in range(h_fr,h_to):
            for j in range(w_fr,w_to):
              ans[i][j] = f[i-h_fr][j-w_to]


for i in range(H):
    prev = ans[i][-1]
    for j in range(W,-1,-1):
        if j == prev: continue
        if ans[i][j] == 0:
            ans[i][j] = prev
        if ans[i][j] != 0:
            prev = ans[i][j]

for i in range(H):
    print(*ans[1:])

### FIXED CODE ###

H,W,K = map(int, input().split())
fields = [list(input()) for i in range(H)]
bins = []
hs = [] #区切る位置
ws = []
for i,f in enumerate(fields):
    if "#" in f:
        hs.append(i)
hs = hs+[H]
cnt = 0
ans = []
h_fr = 0
for i in range(1,len(hs)):
    h_to = hs[i]
    if h_fr - h_to == 0:continue
    f = fields[h_fr:h_to]
    # print(i,h_fr,h_to,f)
    ws = []
    for j in range(W):
        for i in range(h_fr,h_to):
             if fields[i][j] == "#":
                 ws.append(j)
    ws += [W]
    cnts = []
    w_fr = 0
    for j in range(1,len(ws)):
        w_to = ws[j]
        if w_to-w_fr > 0:
            cnt += 1
            cnts.extend([cnt]*(w_to-w_fr))
            w_fr = w_to
    for i in range(h_to-h_fr):
        ans.append(cnts)
    h_fr = h_to
# print(ans)
for f in ans:
    print(*f)