Harryxun/stf_run huggingface dataset:
n = int(input())
d = [[] for i in range(n)]
for i in range(n-1):
	a,b,x = map(int,input().split())
	a -= 1
	b -= 1
	x = x%2
	d[a].append([b,x])
	d[b].append([a,x])
print(d)
color = [0]*n
used = set()
def dfs(v):
	for e,l in d[v]:
		#print(e)
		if e not in used:
			used.add(e)
			if l == 1:
				color[e] = 1
			dfs(e)
dfs(0)
for c in color:
	print(c)

### FIXED CODE ###

n = int(input())
edges = [set() for _ in range(n)]
for i in range(n-1):
    u,v,w = [int(i)-1 for i in input().split()] 
    edges[u].add((v,w+1))
    edges[v].add((u,w+1))
ans = [-1]*n
q = [(0,0,-1)]
while q:
    v,d,p = q.pop()
    if d%2 == 0:
        ans[v] = 0
    else:
        ans[v] = 1
    for u,w in edges[v]:
        if u == p:
            continue
        q.append((u,d+w,v))
for i in range(n):
    print(ans[i])
N = int(input())
S_list = []
for _ in range(N):
    S_list.append(input())

S_dict = {}
for s in S_list:
    S_dict[s]=0
for s in S_list:
    S_dict[s]+=1

max_kv = max(S_dict.values())

max_k_list = [kv[0] for kv in S_dict.items() if kv[1] == max_kv]
max_k_list.sort()
for k in max_k_list:
    print(k)


### FIXED CODE ###

# https://atcoder.jp/contests/abc155/tasks/abc155_a

A,B,C = map(int,input().split())

S = set([A,B,C])

if len(S) == 2:
    print("Yes")
else:
    print("No")
def digital_root(n):
  return n if n < 10 else digital_root(sum(map(int,str(n))))

n = input()
if(digital_root(n) % 9 == 0):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

def digital_root(n):
  return n if n < 10 else digital_root(sum(map(int,str(n))))
 
n = int(input())
if(digital_root(n) % 9 == 0):
  print("Yes")
else:
  print("No")
X = input()
if X >=30:
  print("Yes")
else :
  print("No")

### FIXED CODE ###

X = int(input())
if X >= 30 :
  print("Yes")
else :
  print("No")
from collections import deque
n,m,k = map(int,input().split())
la = list(map(int,input().split()))
lb = list(map(int,input().split()))
ls = la + lb[::-1]
ls = deque(ls)
inf = float("inf")
dp = [[-inf]*(k+1) for _ in range(n+m+1)]
for j in range(k+1):
    dp[0][j] = 0
for i in range(n+m):
    if ls == deque([]):
        break
    elif ls[0] <= ls[-1]:
        s = ls.popleft()
    elif ls[-1] < ls[0]:
        s = ls.pop()
    for l in range(k+1):
        if l-s >=0:
            dp[i+1][l] = max(dp[i][l],dp[i][l-s]+1)
        else:
            dp[i+1][l] = dp[i][l]
print(dp[-1][k])        

### FIXED CODE ###

n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
la = [0]
lb = [0]
mx = 0
for i in range(n): 
    if la[i] + a[i] > k:
        break
    la.append(la[i]+a[i])
for j in range(m):
    if lb[j] + b[j] > k:
        break
    lb.append(lb[j]+b[j])
now = len(lb)-1
for l in range(len(la)):
    cnt = l
    q = now
    while la[l] + lb[q] > k:
        q -= 1
    now = q
    cnt += q
    if cnt > mx:
        mx = cnt
print(mx)
print(int(input()/111)*111)

### FIXED CODE ###

print(-(-int(input())//111)*111)
N = int(input())
A = list(map(int, input().split())) 
correct_answer_count = 0
for i in range(1, N + 1):
    bat_answer_count = 0
    for j in range(1, i+1):
        if not (A[i] <= A[j]):
            bat_answer_count += 1

    if bat_answer_count == 0:
        correct_answer_count += 1

print(correct_answer_count)    


### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
 
cnt = 0
p_min = p[0]
for i in range(n):
  pi = p[i]
  if pi <= p_min:
    cnt += 1
    p_min = pi
print(cnt)
n = int(inut())
h = list(map(int, input().split()))
t = 0
for i in range(n - 2):
    if h[i] - h[i+1] >= 2:
        print("No")
        t = 1
        break
    elif i <= n - 3:
        if h[i] - h[i+1] == 1 and h[i+1] - h[i+2] == 1:
            print("No")
            t = 1
            break
if t == 0:
    print("Yes")

### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))
t = 0
m = 0
for i in range(n):
    if h[i] > t:
        t = h[i]
    elif t - h[i] >= 2:
        print("No")
        m += 1
        break
if m == 0:
    print("Yes")
l = input().split()
 
l[0], l[1] = l[1], 1[0]
l[0], l[2] = l[2], 1[0]
 
print(l[0]+" "+l[1]+" "+l[2])

### FIXED CODE ###

a = list(map(int,input().split()))
a[0], a[1] = a[1], a[0]
a[0], a[2] = a[2], a[0]
 
print(a[0], a[1], a[2])
S = input()
T = input()
change_index = []

for i in range(len(S)-len(T)+1):
    step = 0
    for j in T:
#        if i + step >= len(S):
#            break
        if S[i+step] != j and S[i+step] != '?':
            break
        step += 1
        if step == len(T):
            change_index.append(i)

if len(change_index) or len(T) == 0:
    Sa_list = list(S.replace('?', 'a'))
    for i in change_index[0]:
        step = 0
        for j in T:
            Sa_list[i+step] = j
            step += 1
    Sa = ''.join(Sa_list)
    print(Sa)
else :
    print('UNRESTORABLE')


### FIXED CODE ###

S = input()
T = input()

index = []
ss = []
flag = False

for i in range(len(S)-len(T)+1):
    for j in range(len(T)):
        if S[i+j] != T[j] and S[i+j] != '?':
            break
        if j == len(T) - 1:
            flag = True
            index.append(i)

if flag:
    for v in index:
        s = ''
        k = 0
        for i in range(len(S)):
            if v <= i <= v + len(T) - 1:
                s += T[k]
                k += 1
                continue
            if S[i] == '?':
                s += 'a'
            else:
                s += S[i]
        ss.append(s)
    ss.sort()
    s = ss[0]
else:
    s = 'UNRESTORABLE'

print(s)
import numpy as np
n,k = map(int,input().split())
a_list = sorted(map(int,input().split()))
mod = 10**9+7
if n-k < a_list.count(0):
    print(0)
    exit()
if sum([1 for a in a_list if np.sign(a)==-1])==k:
    a_list.sort(key = abs)
    ans = 1
    for num in a_list[:k]:
        ans *= num
        ans %= mod
    print(ans)
    exit()
else:
    a_list.sort(key = abs,reverse = True)
    add = 1
    remove = 1
    if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
        negative_min_big = max([num for num in a_list[:k] if np.sign(num)==-1])
        positive_min_big = min([num for num in a_list[:k] if np.sign(num)!=-1])
        negative_max_small = min([num for num in a_list[k:] if np.sign(num)==-1])
        positive_max_small = max([num for num in a_list[k:] if np.sign(num)!=-1])
        if positive_max_small/negative_min_big < negative_max_small/positive_min_big:
            remove = negative_min_big
            add = positive_max_small
        else:
            remove = positive_min_big
            add = negative_max_small
ans = 1
for num in a_list[:k]:
    ans *= num
    ans %= mod
    
if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
    ans *= add
    ans %= mod
    ans *= pow(remove, mod-2, mod)
    ans %= mod

print(ans)

### FIXED CODE ###

import numpy as np
import sys
n,k = map(int,input().split())
a_list = sorted(map(int,input().split()))
mod = 10**9+7
if n-k < a_list.count(0):
    print(0)
    exit()
if (sum([1 for a in a_list if np.sign(a)!=-1])==0 and k%2==1) or (k==n and len([1 for a in a_list if np.sign(a)==-1])%2==1):
    a_list.sort(key = abs)
    ans = 1
    for num in a_list[:k]:
        ans *= num
        ans %= mod
    print(ans)
    exit()
else:
    a_list.sort(key = abs,reverse = True)
    add = 1
    remove = 1
    if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
        negative_big = [num for num in a_list[:k] if np.sign(num)==-1]
        positive_big = [num for num in a_list[:k] if np.sign(num)!=-1]
        negative_small = [num for num in a_list[k:] if np.sign(num)==-1]
        positive_small = [num for num in a_list[k:] if np.sign(num)!=-1]
        
        
        if len(negative_big)==0 or len(positive_small)==0:
            remove = min(positive_big)
            add = min(negative_small)
        elif len(positive_big)==0 or len(negative_small)==0:
            remove = max(negative_big)
            add = max(positive_small)
        else:
            positive_small_max = max(positive_small)
            negative_big_max = max(negative_big)
            negative_small_min = min(negative_small)
            positive_big_min = min(positive_big)
            if positive_small_max*positive_big_min > negative_small_min*negative_big_max:
                remove = negative_big_max
                add = positive_small_max
            else:
                remove = positive_big_min
                add = negative_small_min
ans = 1
for num in a_list[:k]:
    ans *= num
    ans %= mod
    
if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
    ans *= add
    ans %= mod
    ans *= pow(remove, mod-2, mod)
    ans %= mod

print(ans)
N, K = map(int, input().split())
X    = list(map(int, input().split()))

X_pos = [x for x in X if x >= 0]
X_neg = [x for x in X if x <  0]

X_neg.reverse()

l_pos = len(X_pos)
l_neg = len(X_neg)

R = []

if l_neg == 0:
    R.append(X_pos[K-1])
elif l_pos == 0:
    R.append(-1 * X_neg[K-1])
else:
    for k in range(K):
        if k < l_pos and K-k-2 < l_neg:
            R.append(2 * X_pos[k] - X_neg[K-k-2])
        else:
            break
    for k in range(K):
        if k < l_neg and K-k-2 < l_pos:
            R.append(-2 * X_neg[k] + X_pos[K-k-2])
        else:
            break

print(min(R))

### FIXED CODE ###

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

X_pos = [x for x in X if x >= 0]
X_neg = [x for x in X if x <  0]

X_neg.reverse()

l_pos = len(X_pos)
l_neg = len(X_neg)

R = []

if l_neg == 0:
    R.append(X_pos[K-1])
elif l_pos == 0:
    R.append(-1 * X_neg[K-1])
else:
    for k in range(K):
        if k < l_pos and K-k-2 < l_neg:
            R.append(2 * X_pos[k] - X_neg[K-k-2])
        elif k >= l_pos:
            break
    for k in range(K):
        if k < l_neg and K-k-2 < l_pos:
            R.append(-2 * X_neg[k] + X_pos[K-k-2])
        elif k >= l_neg:
            break

print(min(R))
N, M = map(int, input().split())
lis = [0]*N
S = []
C = []
ERROR = False
for _ in range(N):
  s,c = map(int, input().split())
  S.append(s)
  C.append(c)
for i in range(len(S)-1):
  for j in range(i+1,len(S)):
    if S[i] == S[j] and C[i] != C[j]:
      ERROR = True
if ERROR:
  print(-1)
else:
  output = ''
  for i in range(len(S)):
    lis[S[i]-1] = C[i]
  for i in range(N):
    output += str(lis[i])
  if lis[0] == '0':
    print(-1)
  else:
    print(output)

### FIXED CODE ###

N, M = map(int, input().split())
lis = [0]*N
SC = []
ERROR = False
for _ in range(M):
  sc = list(map(int, input().split()))
  SC.append(sc)
for i in range(len(SC)-1):
  for j in range(i+1,len(SC)):
    if SC[i][0] == SC[j][0] and SC[i][1] != SC[j][1]:
      ERROR = True
for i in range(len(SC)):
  if N > 1 and SC[i][0] == 1 and SC[i][1] == 0:
    ERROR = True
if ERROR:
  print(-1)
else:
  output = ''
  for i in range(M):
    lis[SC[i][0]-1] = SC[i][1]
  if N > 1 and lis[0] == 0:
    lis[0] = 1
  for i in range(N):
    output += str(lis[i])
  print(int(output))
from collections import deque

def push(duque, d, x):
    if d == 0:
        duque.append(x)
    else:
        duque.insert(len(duque), x)
    return duque.appendleft(x)

def randomAccess(duque, p):
    print(duque.index(p))

def pop(duque, d):
    if d == 0:
        duque.pop()
    else:
        duque.popleft()
    return duque

if __name__ == '__main__':
    l = deque([])
    n = int(input())
    for i in range(n):
        j= input().split()

        if int(j[0]) == 0:
            push(l, int(j[1]), int(j[2]))
        elif int(j[0]) == 1:
            randomAccess(l, int(j[1]))
        else:
            pop(l, int(j[1]))


### FIXED CODE ###

from collections import deque

def push(duque, d, x):
    if d == 1:
        duque.append(x)
    else:
        duque.appendleft(x)
    return duque

def randomAccess(duque, p):
    print(duque[p])

def pop(duque, d):
    if d == 1:
        duque.pop()
    else:
        duque.popleft()
    return duque

if __name__ == '__main__':
    l = deque([])
    n = int(input())
    for i in range(n):
        j= input().split()

        if int(j[0]) == 0:
            push(l, int(j[1]), int(j[2]))
        elif int(j[0]) == 1:
            randomAccess(l, int(j[1]))
        else:
            pop(l, int(j[1]))
n = int(input())
numbers = [int(n) for n in input().split()]
res = 1
numbers.sort()
printou = False
for i in numbers:
	if(i == 0):
		print(0)
		printou = True
		break
	res *= i
	if(res > 1000000000000000000):
		print(-1)
		printou = True
		break

if not printou:
	print(res)



### FIXED CODE ###

n = int(input())
numbers = [int(n) for n in input().split()]
res = 1
numbers.sort()
printou = False
for i in numbers:
	if(i == 0):
		print(0)
		printou = True
		break
	res *= i
	if(res > 1000000000000000000):
		print(-1)
		printou = True
		break

if not printou:
	print(res)
from collections import defaultdict
def inpl(): return list(map(int, input().split()))

N = int(input())
XY = sorted([inpl() for _ in range(N)])
D = defaultdict(int)
for i in range(N):
    for j in range(i+1, N):
        D[(XY[j][0] - XY[i][0]), (XY[j][1] - XY[i][1])] += 1
print(N - max(D.values()))

### FIXED CODE ###

from collections import Counter, deque, defaultdict
from operator import itemgetter, xor, mul

import sys
#input = sys.stdin.readline
from sys import setrecursionlimit
setrecursionlimit(10**9)

def inpl(): return list(map(int, input().split()))
g0 = itemgetter(0)
N = int(input())
X, Y = [0]*N, [0]*N
P = []
for i in range(N):
    P.append(inpl())
P = sorted(P)
for i in range(N):
    X[i], Y[i] = P[i]

U = [(X[i]-X[j], Y[i] - Y[j])for i in range(N) for j in range(N) if i != j]
D = defaultdict(int)
for i in range(N):
    D[(X[i], Y[i])] = i+1

ans = N
for ux, uy in U:
    if ux < 0:
        continue
    tmp = 0
    searched = [0]*(N)
    for i in range(N):
        if not searched[i]:
            tmp += 1
            searched[i] = 1
        j = D[(X[i]+ux), (Y[i]+uy)]
        if j:
            searched[j-1] = 1
    ans = min(tmp, ans)
print(ans)
m,n = map(int, input.split())
if n >= 1<<m:
  print(-1)
  
else:
  ans = [i for i in range((1<<m)-1, -1 -1)]
  ans.remove(n)
  ans.append(n)
  for i in range(1<<m):
    if i == n:
      continue
    else:
      ans.append(i)
  ans.append(i)
print(' '.join (map(str，ans)))

### FIXED CODE ###

m,n = map(int, input().split())
if n >= 1<<m:
  print(-1)
   
else:
  if m == 1:
    if n == 1:
      print(-1)
    else:
      print(0,0,1,1)
  else:
    ans = [i for i in range((1<<m)-1, -1, -1)]
    ans.remove(n)
    ans.append(n)
    for i in range(1<<m):
      if i == n:
        continue
      else:
        ans.append(i)
    ans.append(n)
    print(" ".join(map(str, ans)))
for k in range (10):
    n = list(map(int,input().split()))
    a,b = n
    fb = 0
    fa = 0
    for i in range (a):
        tmp = b * (10 ** i)
        fb += tmp

    for i in range (b):
        tmp = a * (10 ** i)
        fa += tmp
    if fa > fb:
        print (fb)
    else:
        print (fa)

### FIXED CODE ###

from sys import stdin

def main():
    N,M  = map(int,stdin.readline().split())
    if(N < M):
        res = str(N)
        print(res*M)
    else:
        res = str(M)
        print(res*N)
        
main()
import math
K = int(input())
sum = 0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            ans+=math.gcd(math.gcd(a,b),c)
print(sum(list))


### FIXED CODE ###

import math
k = int(input())
 
ans = 0
for i in range(1, k+1):
  for j in range(1, k+1):
    tmp = math.gcd(i,j)
    for l in range(1, k+1):
      ans += math.gcd(tmp, l)
print(ans)
N, Y, Z = map(int, input().split())
As = list(map(int, input().split()))
dpx, dpy = [0]*(N-1), [0]*(N-1)
#dpx[i] = min(dpy[i+1]...dpy[N-2], abs(As[N-1]-As[i]))
#dpy[i] = max(dpx[i+1]...dpx[N-2], abs(As[N-1]-As[i]))
for i in range(N-2, -1, -1):
    mny, mxx = 10**10, 0
    for j in range(i+1, N-1):
        mny = min(mny, dpy[j])
        mxx = max(mxx, dpx[j])
    dpx[i] = min(mny, abs(As[N-1]-As[i]))
    dpy[i] = min(mxx, abs(As[N-1]-As[i]))
#print(dpx)
print(max(max(dpx),abs(As[N-1]-Z)))


### FIXED CODE ###

N, Y, Z = map(int, input().split())
As = list(map(int, input().split()))
dpx, dpy = [0]*(N-1), [0]*(N-1)
#dpx[i] = min(dpy[i+1]...dpy[N-2], abs(As[N-1]-As[i]))
#dpy[i] = max(dpx[i+1]...dpx[N-2], abs(As[N-1]-As[i]))
for i in range(N-2, -1, -1):
    mny, mxx = 10**10, 0
    for j in range(i+1, N-1):
        mny = min(mny, dpy[j])
        mxx = max(mxx, dpx[j])
    dpx[i] = min(mny, abs(As[N-1]-As[i]))
    dpy[i] = max(mxx, abs(As[N-1]-As[i]))
dpx.append(abs(As[N-1]-Z))
print(max(dpx))
N = input().split
 
if N == list(reversed(N)):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N = input()

N1 = N[2]+N[1]+N[0]
if N == N1:
    print("Yes")
else:
    print("No")
import math
from sys import stdin
N,P=[int(x) for x in stdin.readline().rstrip().split()]
for i in reversed(range(round(math.pow(P,(1/N)))):
    tmp=math.pow(i,N-1)
    if P==1:
        ans=1
        break
    if N==1:
        ans=P
        break
    if (P/i)%tmp==0:
        ans=i
        break
print(ans)

### FIXED CODE ###

from sys import stdin
N=(stdin.readline().rstrip())
print(N.count("2"))
MOD = 10**9 + 7
N = 10**5 + 10

fact = [1]*(N+1)
rfact = [1]*(N+1)
r = 1
for i in range(1, N+1):
  fact[i] = r = r * i % MOD
rfact[N] = r = pow(fact[N], MOD-2, MOD)
for i in range(N, 0, -1):
  rfact[i-1] = r = r * i % MOD

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % MOD

# nCk (mod MOD) を求める
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % MOD

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

p = comb(n*m-2, k-2)

ans = 0
for i in range(1,n):
    ans += i * (n-i) * m * m * p
    ans %= MOD

for i in range(1,m):
    ans += i * (m-i) * n * n * p
    ans %= MOD

print(ans)

### FIXED CODE ###

MOD = 10**9 + 7
N = 10**6 + 10

fact = [1]*(N+1)
rfact = [1]*(N+1)
r = 1
for i in range(1, N+1):
  fact[i] = r = r * i % MOD
rfact[N] = r = pow(fact[N], MOD-2, MOD)
for i in range(N, 0, -1):
  rfact[i-1] = r = r * i % MOD

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % MOD

# nCk (mod MOD) を求める
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % MOD

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

p = comb(n*m-2, k-2)

ans = 0
for i in range(1,n):
    ans += i * (n-i) * m * m * p
    ans %= MOD

for i in range(1,m):
    ans += i * (m-i) * n * n * p
    ans %= MOD

print(ans)
# AOJ 1510 Independent Research
# Python3 2018.7.13 bal4u

mv = [[-1,-1,-1],[-1,-1,0],[-1,-1,1],[-1,0,-1],[-1,0,0],[-1,0,1],[-1,1,-1],[-1,1,0],[-1,1,1],
      [0,-1,-1],[0,-1,0],[0,-1,1],[0,0,-1],[0,0,1],[0,1,-1],[0,1,0],[0,1,1],
      [1,-1,-1],[1,-1,0],[1,-1,1],[1,0,-1],[1,0,0],[1,0,1],[1,1,-1],[1,1,0],[1,1,1]]
				
cno = 0
arr = [[[[0 for x in range(5)] for y in range(5)] for z in range(5)] for k in range(2)]
while True:
	n = int(input())
	if n == 0: break
	for z in range(5):
		for y in range(5): arr[0][z][y] = list(map(int, input()))
		input()
	a, b = [0]*27, [0]*27
	ts = list(map(int, input().split()))
	for t in ts[1:]: a[t] = 1
	ts = list(map(int, input().split()))
	for t in ts[1:]: b[t] = 1
	for j in range(n):
		for z in range(5):
			for y in range(5):
				for x in range(5):
					s = 0;
					for i in range(26):
						xx, yy, zz = x+mv[i][0], y+mv[i][1], z+mv[i][2]
						if xx >= 0 and xx < 5 and yy >= 0 and yy < 5 and zz >= 0 and zz < 5:
							s += arr[j&1][zz][yy][xx] & 1
					if arr[j&1][z][y][x] & 1: arr[1-(j&1)][z][y][x] = b[s]
					else: arr[1-(j&1)][z][y][x] = a[s]
	if cno: print()
	cno += 1
	print("Case ", cno, ":", sep='')
	for z in range(5):
		if z > 0: print()
		for y in range(5): print(*arr[n&1][z][y], sep='')
		


### FIXED CODE ###

# AOJ 1510 Independent Research
# Python3 2018.7.13 bal4u

mv = [[-1,-1,-1],[-1,-1,0],[-1,-1,1],[-1,0,-1],[-1,0,0],[-1,0,1],[-1,1,-1],[-1,1,0],[-1,1,1],
      [0,-1,-1],[0,-1,0],[0,-1,1],[0,0,-1],[0,0,1],[0,1,-1],[0,1,0],[0,1,1],
      [1,-1,-1],[1,-1,0],[1,-1,1],[1,0,-1],[1,0,0],[1,0,1],[1,1,-1],[1,1,0],[1,1,1]]
				
cno = 0
arr = [[[[0 for x in range(5)] for y in range(5)] for z in range(5)] for k in range(2)]
while True:
	n = int(input())
	if n == 0: break
	for z in range(5):
		if z > 0: input()
		for y in range(5): arr[0][z][y] = list(map(int, input()))
	a, b = [0]*27, [0]*27
	ts = input()
	if len(ts) == 0: ts = input()
	ts = list(map(int, ts.split()))
	for t in ts[1:]: a[t] = 1
	ts = list(map(int, input().split()))
	for t in ts[1:]: b[t] = 1
	for j in range(n):
		for z in range(5):
			for y in range(5):
				for x in range(5):
					s = 0;
					for i in range(26):
						xx, yy, zz = x+mv[i][0], y+mv[i][1], z+mv[i][2]
						if xx >= 0 and xx < 5 and yy >= 0 and yy < 5 and zz >= 0 and zz < 5:
							s += arr[j&1][zz][yy][xx] & 1
					if arr[j&1][z][y][x] & 1: arr[1-(j&1)][z][y][x] = b[s]
					else: arr[1-(j&1)][z][y][x] = a[s]
	if cno: print()
	cno += 1
	print("Case ", cno, ":", sep='')
	for z in range(5):
		if z > 0: print()
		for y in range(5): print(*arr[n&1][z][y], sep='')
n,m,l = map(int,input().split())
A = [list(map(int,input().split())) for i in range(m)]
q = int(input())
S = [list(map(int,input().split())) for i in range(q)]

from scipy.sparse.csgraph import floyd_warshall

for i in range(m):  # ノード番号が1始まりで与えられている場合
    for j in range(2):
        A[i][j] -= 1

for i in range(q):  # ノード番号が1始まりで与えられている場合
    for j in range(2):
        S[i][j] -= 1

M = [[float("inf")] * n for i in range(n)]

for i in range(n):
    M[i][i] = 0

for i in range(m):
    M[A[i][0]][A[i][1]] = A[i][2]
    M[A[i][1]][A[i][0]] = A[i][2]

# for k in range(n):
#     for i in range(n):
#         for j in range(n):
#             M[i][j] = min(M[i][j], M[i][k] + M[k][j])

M = floyd_warshall(M)

for i in range(n):
    for j in range(n):
        M[i][j] = 1 if M[i][j] <= l else float("inf")

for i in range(n):
    M[i][i] = 0

# for k in range(n):
#     for i in range(n):
#         for j in range(n):
#             M[i][j] = min(M[i][j], M[i][k] + M[k][j])

M = floyd_warshall(M)

for i in range(q):
    ans = M[S[i][0]][S[i][1]]
    if ans == float("inf"):
        ans = -1
    print(ans)

### FIXED CODE ###

n,m,l = map(int,input().split())
A = [list(map(int,input().split())) for i in range(m)]
q = int(input())
S = [list(map(int,input().split())) for i in range(q)]

from scipy.sparse.csgraph import floyd_warshall

for i in range(m):  # ノード番号が1始まりで与えられている場合
    for j in range(2):
        A[i][j] -= 1

for i in range(q):  # ノード番号が1始まりで与えられている場合
    for j in range(2):
        S[i][j] -= 1

M = [[float("inf")] * n for i in range(n)]

for i in range(n):
    M[i][i] = 0

for i in range(m):
    M[A[i][0]][A[i][1]] = A[i][2]
    M[A[i][1]][A[i][0]] = A[i][2]

# for k in range(n):
#     for i in range(n):
#         for j in range(n):
#             M[i][j] = min(M[i][j], M[i][k] + M[k][j])

M = floyd_warshall(M)

for i in range(n):
    for j in range(n):
        M[i][j] = 1 if M[i][j] <= l else float("inf")

for i in range(n):
    M[i][i] = 0

# for k in range(n):
#     for i in range(n):
#         for j in range(n):
#             M[i][j] = min(M[i][j], M[i][k] + M[k][j])

M = floyd_warshall(M)

for i in range(q):
    ans = M[S[i][0]][S[i][1]]-1
    if ans == float("inf"):
        ans = -1
    print(int(ans))
maze = []
    h, w = map(int,input().split())
    for _ in range(h):
        maze.append(list(input()))
    #print(maze)
    x,y = 0,0
    while True:
        maze[y][x] = "."
        if x == w-1 and  y == h-1:
            break
        if x != w-1 and maze[y][x+1]== "#":
            x += 1
            continue
        if y != h-1 and maze[y+1][x]=="#":
            y += 1
            continue
        break
    from pprint import pprint
    #pprint(maze)
    f= True
    for i in range(h):
        if maze[i].count("#") != 0:
            f = False
    print("Impossible" if not f else "Possible")


### FIXED CODE ###

maze = []
h, w = map(int,input().split())
for _ in range(h):
    maze.append(list(input()))
#print(maze)
x,y = 0,0
while True:
    maze[y][x] = "."
    if x == w-1 and  y == h-1:
        break
    if x != w-1 and maze[y][x+1]== "#":
        x += 1
        continue
    if y != h-1 and maze[y+1][x]=="#":
        y += 1
        continue
    break
from pprint import pprint
#pprint(maze)
f= True
for i in range(h):
    if maze[i].count("#") != 0:
        f = False
print("Impossible" if not f else "Possible")