Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from itertools import permutations

N,M,R = map(int,input().split())
r = list(map(int,input().split()))

li = [[0 for i in range(N+1)]for j in range(N+1)]

for _ in range(M):
    a,b,c = map(int,input().split())
    li[a][b] = c
    li[b][a] = c

def all_pairs_shortest_paths(W):
    inf = 10**18
    # 頂点の数
    n = len(W)
    # 結果を格納する行列を用意する
    res = [[0] * n for i in range(n)]
    # 用意した行列を初期化する
    for i in range(n):
        for j in range(i, n):
            if i == j:
                val = 0
            elif W[i][j]:
                val = W[i][j]
            else:
                val = inf
            res[i][j] = res[j][i] = val
    # 動的計画法ですべての超点間の最短距離を求める
    for k in range(n):
        for u in range(n):
            for v in range(n):
                res[u][v] = min(res[u][v], res[u][k] + res[k][v])
    return res

lin = all_pairs_shortest_paths(li)

pos = list(permutations(r))

mi = 10**18

for i in pos:
    l = 0
    for j in range(1,R):
        l += lin[i[j-1]][i[j]]
    mi = min(mi,l)

print(mi)

### FIXED CODE ###

from itertools import permutations

N,M,R = map(int,input().split())
r = list(map(int,input().split()))

li = [[0 for i in range(N+1)]for j in range(N+1)]

for _ in range(M):
    a,b,c = map(int,input().split())
    li[a][b] = c
    li[b][a] = c

def all_pairs_shortest_paths(W):
    inf = 10**18
    # 頂点の数
    n = len(W)
    # 結果を格納する行列を用意する
    res = [[0] * n for i in range(n)]
    # 用意した行列を初期化する
    for i in range(n):
        for j in range(i, n):
            if i == j:
                val = 0
            elif W[i][j]:
                val = W[i][j]
            else:
                val = inf
            res[i][j] = res[j][i] = val
    # 動的計画法ですべての超点間の最短距離を求める
    for k in range(n):
        for u in range(n):
            for v in range(n):
                res[u][v] = min(res[u][v], res[u][k] + res[k][v])
    return res

lin = all_pairs_shortest_paths(li)

pos = list(permutations(r))

mi = 10**18

for i in pos:
    l = 0
    for j in range(1,R):
        l += lin[i[j-1]][i[j]]
    mi = min(mi,l)

print(mi)
### BUGGY CODE ###

s = input()
count = 0

while ("01" in s) | ("10" in s):
    if "01" in s:
        count += 2 * s.count("01")
        s = s.replace("01", "")
    else:
        count += 2 * s.count("10")
        s = s.replace("10", "")
print(count)


### FIXED CODE ###

s = input()
print(2 * min(s.count("0"), s.count("1")))
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
place = []
for s in range(N - 1):
	if S[s] == 'A':
		if S[s + 1] == 'C':
			place.append(s)
PlaceCount = len(place)
for q in range(Q):
	num = 0
	l,r = map(int,input().split())
	l -= 1
	r -= 2
	for i in range(PlaceCount):
		if l <= place[i] <= r:
			num += 1
	print(num)

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
r = [0 for n in range(N)]
l = [0 for n in range(N)]
cnt = 0
for s in range(N - 1):
	if S[s] == 'A':
		if S[s + 1] == 'C':
			cnt += 1
	l[s + 1] = cnt
cnt = 0
for s in range(1,N):
	if S[-s] == 'C':
		if S[-s - 1] == 'A':
			cnt += 1
	r[-s - 1] = cnt
for q in range(Q):
	L,R = map(int,input().split())
	print(cnt - l[L - 1] - r[R - 1])
### BUGGY CODE ###


N = int(input())
A = list(map(int,input().split()))
C = [0 for _ in range(N+1)]
for i in range(1,N+1):
    C[i] = C[i-1]^A[i-1]
cnt = 0
cur = 0
for i in range(N):
    cnt += cur-i
    b = C[cur]^C[i]
    b = bin(b)[2:]
    if len(b)<20:
        b = "0"*(20-len(b))+b
    B = [int(b[j]) for j in range(20)]
    while cur<N:
        flag = 0
        for j in range(20):
            a = bin(A[cur])[2:]
            if len(a)<20:
                a = "0"*(20-len(a))+a
            B[j] += int(a[j])
            if B[j]>=2:
                flag = 1
                break
        if flag==1:break
        cnt += 1
        cur += 1
print(cnt)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
C = [0 for _ in range(N+1)]
for i in range(1,N+1):
    C[i] = C[i-1]^A[i-1]
A = [bin(A[i])[2:] for i in range(N)]
A = [A[i] if len(A[i])==20 else "0"*(20-len(A[i]))+A[i] for i in range(N)]
cnt = 0
cur = 0
for i in range(N):
    cnt += cur-i
    b = C[cur]^C[i]
    b = bin(b)[2:]
    if len(b)<20:
        b = "0"*(20-len(b))+b
    B = [int(b[j]) for j in range(20)]
    while cur<N:
        flag = 0
        for j in range(20):
            B[j] += int(A[cur][j])
            if B[j]>=2:
                flag = 1
                break
        if flag==1:break
        cnt += 1
        cur += 1
print(cnt)
### BUGGY CODE ###

def is_ok(mid, gen=None, diff=0):
    print(mid, flush=True)
    res = input()
    if res == "Vacant":
        exit()
    if gen is None:
        return res
    if diff % 2 == 0:
        return gen == res
    else:
        return gen != res


def meguru_bisect_kai(ng, ok, gen):
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if is_ok(mid, gen, ok - mid):
            ok = mid
        else:
            ng = mid
    return ok


n = int(input())
gen = is_ok(n - 1)
ret = meguru_bisect_kai(0, n - 1, gen)
is_ok(ret)

### FIXED CODE ###

n = int(input())

print(0, flush=True)
res = input()
if res == "Vacant":
    exit()

left = 0
right = n
gen = res


while True:
    mid = (left + right) // 2
    print(mid, flush=True)
    res = input()

    if res == "Vacant":
        exit()

    if gen == res:
        if (mid - left) % 2:
            right = mid
        else:
            left = mid
    else:
        if (mid - left) % 2:
            left = mid
            gen = res
        else:
            right = mid
### BUGGY CODE ###

cnt=0
S=str(input())
mc=[0]*2019
L=len(S)

tg=0
digit=1
for s in S[::-1]:
    tg+=int(s)*digit
    mt=tg%2019
    mc[mt]+=1
    digit*=10%2019

ans=sum(m*(m-1)//2 for m in mc)
print(ans+mc[0])


### FIXED CODE ###

S=input()
mc=[0]*2019

tg=0
digit=1
for s in S[::-1]:
    tg+=int(s)*digit
    mc[tg%2019]+=1
    digit=digit*10%2019

ans=sum(m*(m-1)//2 for m in mc)
print(ans+mc[0])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
A = list(map(int, input().split()))

for h in range(1,N+1):
    for i in range(N):
        if A[i] == h:
            print(i + 1)


### FIXED CODE ###

# -*- coding: utf-8 -*-
N = int(input())
A = list(map(int, input().split()))

"""
for h in range(1,N+1):
    for i in range(N):
        if A[i] == h:
            print(i + 1)
#このやり方でもOKだけど、nが馬鹿でかくなった時にTLEしちゃうよ
"""

S = []
for i in range (N):
    S.append([A[i] , i + 1])
S.sort()

for i in range(N):
    print(S[i][1])
### BUGGY CODE ###

import math
N = int(input())
ans = 0
for i in range(1,N):
    if N%i == N//i:
        ans += i
print(ans)

### FIXED CODE ###

import math
def prime_divisor(n):
    ls = []
    i = 2
    while i <= math.floor(n**0.5):
        if n%i == 0:
            ls.append(i)
            ls.append(n//i)
            i += 1
        else:
            i += 1
    if n > 1:
        ls.append(n)
    return ls
N = int(input())
ls1 = prime_divisor(N)
ls2 = [x-1 for x in list(set(ls1)) if x >= 2]
ls2.sort()
ls2.reverse()
ans = 0
for i in range(len(ls2)):
    if N // ls2[i] == N % ls2[i]:
        ans += ls2[i]
print(ans)
### BUGGY CODE ###

A,B,C,K = list(map(int, input().split()))
ans = 0
for i in range(K):
  if i < A:
    ans += 1
  elif A+B-1 < i:
    ans -= 1
    
print(ans)

### FIXED CODE ###

A,B,C,K = map(int,input().split())
 
if K <= A:
    print(str(K))
elif K <= A + B:
    print(str(A))
else:
    print(str(A - (C - (A + B + C - K))))
### BUGGY CODE ###

n,s=map(int,input().split())
N=[i+1 for i in range(n)]
list1=[]
pattern=[]
A=list(map(int,input().split()))

ft=0  
dict={}
dict[s]=[]
for i in range(1,2**n):
    list2=[]
    for j in range(n):
        if (i >> j) &1 == 1:
            list2.append(N[j])
    pattern=[]
    for x in range(1,2**len(list2)):
        pt=[]
        for y in range(len(list2)):
            if (x>>y)&1==1:
                pt.append(list2[y])
        pattern.append(pt)
   # print(pattern)

    for p in pattern:
        sum=0
        if p in dict[s]:
            ft+=1
        else:
            for x in p:
                sum+=A[x-1]
            if sum==s:
                dict[s].append(p)
                ft+=1
                ft=ft%998244353
print(ft%998244353)




### FIXED CODE ###

import numpy as np
def main():
    n,s=map(int,input().split())
    A=list(map(int,input().split()))
    dp=np.array([0 for i in range(min(3001,s+1))])
    dp[0]=1
    for ai in A:
        tmp=dp[:-ai].copy()
        #print(tmp)
        dp*=2
        dp[ai:]+=tmp
        dp%=998244353
    print(dp[s])
    

if __name__=="__main__":
    main()
### BUGGY CODE ###

INT_MAX = (1<<31) - 1

def update():
    for i in range(_N):
        x = i+N-1
        A_bin_tree[x] = arr[i]
        while x > 1:
            x >>= 1
            l, r = A_bin_tree[x<<1], A_bin_tree[(x<<1)+1]
            A_bin_tree[x] = min(l,r)#l if l < r else r

def find(x,y):
    l = x+N-1
    r = y+N-1
    z = INT_MAX
    while l < r:
        if l & 1:
            if(A_bin_tree[l] < z):
                z = A_bin_tree[l]
            l += 1
        if r & 1:
            r -= 1
            if(A_bin_tree[r] < z):
                z = A_bin_tree[r]
        l >>= 1
        r >>= 1
    return z

import sys
input = sys.stdin.readline
_N,k = map(int,input().split())
*arr, = map(int,input().split())
N = 1
while True:
    if(N >= _N):
        break
    N = N << 1
A_bin_tree = [INT_MAX]*(2*N)

update()
res = [find(i,i+k) for i in range(_N-k+1)]
print(*res)



### FIXED CODE ###

INTMAX = (1<<31) - 1

def ans():
    for i in range(k):
        x = i + OFS
        A[x] = arr[i]
        while True:
            if(x <= 0):
                break
            x = (x - 1)//2
            l = A[x*2+1]
            r = A[x*2+2]
            A[x] = l if l < r else r#min(tree[left],tree[right])
    res = []
    c = 0
    for i in range(_N-k):
        res.append(A[0])
        x = c + OFS
        A[x] = arr[i+k]
        while True:
            if(x <= 0):
                break
            x = (x - 1)//2
            l = A[x*2+1]
            r = A[x*2+2]
            A[x] = l if l < r else r
        c += 1
        if(c == k):
            c = 0
    res.append(A[0])
    print(*res)

_N,k = map(int, input().split())
*arr, = map(int,input().split())
if(k==1):
    print(*arr)
else:
    N = 2**(_N-1).bit_length()
    A = [INTMAX]*(2*N)
    OFS = N - 1
    ans()
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from collections import defaultdict
from collections import Counter
from collections import OrderedDict

def solve(N: int, s: "List[str]"):
    count_dict = defaultdict(int)
    for i, string in enumerate(s):
        string = list(string)
        info = sorted(OrderedDict(Counter(string)).items(), key=lambda x:x[0])
        info = tuple([tuple([i, j]) for i, j in info])
        count_dict[info] += 1
    result = 0
    for _, v in count_dict.items():
        result += sum([i for i in range(v)])
    print(result)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    s = [ next(tokens) for _ in range(N) ]  # type: "List[str]"
    solve(N, s)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import defaultdict
from collections import Counter

def solve(N: int, s: "List[str]"):
    count_dict = defaultdict(int)
    for i, string in enumerate(s):
        string = list(string)
        info = sorted(Counter(string).items(), key=lambda x:x[0])
        info = tuple([tuple([i, j]) for i, j in info])
        count_dict[info] += 1

    result = 0
    for _, v in count_dict.items():
        result += int((v-1) * 0.5 * (1 + v-1))
    print(result)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    s = [ next(tokens) for _ in range(N) ]  # type: "List[str]"
    solve(N, s)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

import math
isPrime = [True for i in range(10**5+1)]
for i in range(3, 10**5+1):
    for j in range(2, math.floor(math.sqrt(i))+1):
        if i % j == 0:
            isPrime[i] = False

cntPrime = [0 for i in range(10**5+1)]
for i in range(2,10**5+1):
    if i % 2 == 1 and isPrime[i] and isPrime[(i+1)//2]:
        cntPrime[i] = cntPrime[i-1]+1
    else:
        cntPrime[i] = cntPrime[i-1]

Q = int(input())
for i in range(Q):
    l, r = [int(_) for _ in input().split()]
    print(cntPrime[r]-cntPrime[l-1])


### FIXED CODE ###

import math
isPrime = [True for i in range(10**5+1)]
for i in range(3, 10**5+1):
    for j in range(2, math.floor(math.sqrt(i))+1):
        if i % j == 0:
            isPrime[i] = False

cntPrime = [0 for i in range(10**5+1)]
for i in range(2,10**5+1):
    if i % 2 == 1 and isPrime[i] and isPrime[(i+1)//2]:
        cntPrime[i] = cntPrime[i-1]+1
    else:
        cntPrime[i] = cntPrime[i-1]

Q = int(input())
for i in range(Q):
    l, r = [int(_) for _ in input().split()]
    print(cntPrime[r]-cntPrime[l-1])
### BUGGY CODE ###

from networkx import*
(N,M,*S),*t=[map(int,t.split())for t in open(0)]
G=Graph()
for*u,a,b in t:G.add_edge(*u,y=a,s=b)
b=m=10**15
y,s,*r=map(eval(dir()[761]),(G,G),S,(m,m),'ys')
while N:b=min(b,y[N]+s[N]);r+=m-b,;N-=1
print(*r[::-1])

### FIXED CODE ###

from heapq import*
def dijkstra(n,s,edge):
    g=10**6
    d=[10**18]*n
    used=[True]*n
    d[s]=0
    used[s]=False
    edgelist=[]
    for a,b in edge[s]:heappush(edgelist,a*g+b)
    while edgelist:
        minedge=heappop(edgelist)
        if not used[minedge%g]:continue
        v1=minedge%g
        c1=d[v1]=minedge//g
        used[v1]=False
        for c2,v2 in edge[v1]:
            if used[v2]:heappush(edgelist,(c1+c2)*g+v2)
    return d
def main():
    n,m,s,t,*z=map(int,open(0).read().split())
    e1,e2=[[[]for _ in range(n)]for _ in range(2)]
    for u,v,a,b in zip(*[iter(z)]*4):
        u-=1
        v-=1
        e1[u]+=(a,v),
        e1[v]+=(a,u),
        e2[u]+=(b,v),
        e2[v]+=(b,u),
    c1=dijkstra(n,s-1,e1)
    c2=dijkstra(n,t-1,e2)
    a=[]
    m=0
    for y,s in zip(c1[::-1],c2[::-1]):
        t=10**15-y-s
        if t>m:m=t
        a+=m,
    print(*a[::-1],sep='\n')
main()
### BUGGY CODE ###

import numpy as np
N,K,Q=map(int,input().split())
A=[]
for i in range(Q):
  a=int(input())
  A.append(a)
score=np.full(N,K)
for j in range(Q):
  for k in range(len(score)):
    if k==A[j]-1:
      pass
    else:
      score[k]-=1
for l in range(len(score)):
  if score[l]>0:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

import numpy as np
N,K,Q=map(int,input().split())
score=np.full(N,K)
for i in range(Q):
  a=int(input())
  score[a-1]+=1
for j in score:
  if j-Q>0:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

from sys import stdin

n = stdin.readline().rstrip()
a = stdin.readline().rstrip().split()

total = 1
for i in a:
    total = total*int(i)

if(total > 1000000000000000000): total = -1
print(total)

### FIXED CODE ###

from sys import stdin
import sys

n = stdin.readline().rstrip().split()
a = stdin.readline().rstrip().split()

if '0' in a:
    print(0)
    sys.exit()

total = 1
for i in a:
    total = total*int(i)

    if(total > 1000000000000000000):
        print(-1)
        sys.exit()

print(total)
### BUGGY CODE ###

import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    count2 = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        tmp = count
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count == tmp : count2 += 1
        if count2 > 400 : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
parameter = 0.97
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
  A.append(int(input()))
 
pushed = [1]
 
while True:
  button = A[pushed[-1] - 1]
  if button in pushed:
    print("-1")
    break
  elif button == 2:
    print(len(pushed))
    break
  else:
    pushed.append(button)

### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
  A.append(int(input()))

button = [0] * N
button[0] = 1
next_button = 1
i = 0

while True:
  button[next_button - 1] = 2
  next_button = A[next_button - 1]
  if button[next_button - 1] == 2:
    print("-1")
    break
  elif next_button == 2:
    i += 1
    print(i)
    break
  else:
    button[next_button - 1] = 1
    i += 1
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
bc = []
ans = []
for i in range(q):
  bc.append(list(map(int, input().split())))
for i in range(q):
  b = bc[i][0]
  c = bc[i][1]
  for j in range(n):
    if a[j] == b:
      a[j] = c
  ans.append(sum(a))
for i in range(q):
  print(ans[i])

### FIXED CODE ###

k = [i for i in range(1, 10 ** 5 + 1)]
v = [0] * (10 ** 5)
dic = {key: val for key, val in zip(k, v)}
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
  dic[a[i]] += 1
q = int(input())
ans = [sum(a)]
for i in range(q):
  b, c = map(int, input().split())
  ans.append(ans[-1] + (c - b) * dic[b])
  dic[c] += dic[b]
  dic[b] = 0
for i in range(1, q + 1):
  print(ans[i])
### BUGGY CODE ###

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

from operator import mul
from functools import reduce

a = reduce(mul, x)

if a > pow(10,18):
  print(-1)
else:
  print(a)

### FIXED CODE ###

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

a = 1
if 0 in x:
  print(0)
else:
  for i in x:
    a *= i
    if a > pow(10,18):
      print(-1)
      break
  else:
    print(a)
### BUGGY CODE ###

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

dprint = lambda *x:x

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 998244353 #出力の制限
__N = 8000
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, __N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )



def kumiawase(p, q):
    # dprint(p,q,cmb(p+q-1,q-1 ,mod))
    return cmb(p+q -1,q-1 ,mod)


def solve(n):
    assert n <= K+1
    # 組み合わせの組
    # abs(n-1)//2 + 偶数分 n//2?
    # 2 ->  1,1
    # 3 -> 1,2
    # 4 -> 1,3 2,2
    # 5 -> 1,4 2,3
    # 6 -> 1,5 2,4 3,3
    # 7  3通り

    # 組のうち片方だけ使用する数 p
    ans = 0
    kumi = (n - 1) // 2
    for p in range(kumi+1):
        # dprint("p",p,"n",n)
        if p>N:
            break
        # 使えるのは p個 + 組に関係ないやつ
        ans += 2**p *cmb(kumi,p,mod)* kumiawase(N - p, p+ (K-kumi*2- int(n%2==0) ) )
        # dprint("anstmp1",ans)
        if n % 2 == 0 and N - p -1 >= 0:
            ans += 2**p *cmb(kumi,p,mod) * kumiawase(N - p -1 , p+ (K-kumi*2- int(n%2==0) ) ) # K==n//2を使用
    # dprint("-------",ans)
    return ans


ans = []
for i in range(2, 2 * K +1):
    if i <= K+1:
        tmp = solve(i)%998244353
        ans.append(tmp)
        print(tmp)
    else:
        print(ans[-i + K])


### FIXED CODE ###

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

dprint = lambda *x:x

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 998244353 #出力の制限
__N = 8000
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, __N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )



def kumiawase(p, q):
    # dprint(p,q,cmb(p+q-1,q-1 ,mod))
    return cmb(p+q -1,q-1 ,mod)


def solve(n):
    assert n <= K+1
    # 組み合わせの組
    # abs(n-1)//2 + 偶数分 n//2?
    # 2 ->  1,1
    # 3 -> 1,2
    # 4 -> 1,3 2,2
    # 5 -> 1,4 2,3
    # 6 -> 1,5 2,4 3,3
    # 7  3通り

    # 組のうち片方だけ使用する数 p
    ans = 0
    kumi = (n - 1) // 2
    for p in range(kumi+1):
        # dprint("p",p,"n",n)
        if p>N:
            break
        # 使えるのは p個 + 組に関係ないやつ
        ans += 2**p *cmb(kumi,p,mod)* kumiawase(N - p, p+ (K-kumi*2- int(n%2==0) ) )
        # dprint("anstmp1",ans)
        if n % 2 == 0 and N - p -1 >= 0:
            ans += 2**p *cmb(kumi,p,mod) * kumiawase(N - p -1 , p+ (K-kumi*2- int(n%2==0) ) ) # K==n//2を使用
    # dprint("-------",ans)
    return ans


ans = []
for i in range(2, 2 * K +1):
    if i <= K+1:
        tmp = solve(i)%998244353
        ans.append(tmp)
        print(tmp)
    else:
        print(ans[-i + K])
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n,m,l=map(int,input().split())
INF=10**10
graph=[[INF for i in range(n)] for j in range(n)]
fuel=[[INF for i in range(n)] for j in range(n)]
for i in range(n):
    graph[i][i]=0
for i in range(m):
    a,b,c=map(int,input().split())
    a-=1;b-=1
    if c>l:continue
    graph[a][b],graph[b][a]=c,c
for i in range(n):
  for j in range(n):
    for k in range(n):
      graph[j][k]=min(graph[j][k],graph[j][i]+graph[i][k])
for i in range(n):
    for j in range(n):
        if graph[i][j]<=l:
            fuel[i][j]=1
for i in range(n):
  for j in range(n):
    for k in range(n):
      fuel[j][k]=min(fuel[j][k],fuel[j][i]+fuel[i][k])
q=int(input())
for i in range(q):
    s,t=map(int,input().split())
    s-=1;t-=1
    if fuel[s][t]==INF:print(-1)
    else:print(fuel[s][t]-1)


### FIXED CODE ###

n,m,l=map(int,input().split())
INF=10**10
graph=[[INF for i in range(n)] for j in range(n)]
fuel=[[INF for i in range(n)] for j in range(n)]
for i in range(n):
    graph[i][i]=0
for i in range(m):
    a,b,c=map(int,input().split())
    a-=1;b-=1
    if c>l:continue
    graph[a][b],graph[b][a]=c,c
for i in range(n):
  for j in range(n):
    for k in range(n):
      graph[j][k]=min(graph[j][k],graph[j][i]+graph[i][k])
for i in range(n):
    for j in range(n):
        if graph[i][j]<=l:
            fuel[i][j]=1
for i in range(n):
  for j in range(n):
    for k in range(n):
      fuel[j][k]=min(fuel[j][k],fuel[j][i]+fuel[i][k])
q=int(input())
for i in range(q):
    s,t=map(int,input().split())
    s-=1;t-=1
    if fuel[s][t]==INF:print(-1)
    else:print(fuel[s][t]-1)