Harryxun/stf_run huggingface dataset:
ans = [,,,]
while True:
  sides = [,,]
  for i in range(3):
    side[i] = int(input())
  sides = sorted(sides)
  if sides[2] >= sides[1] + sides[0]:
    print(ans[0], ans[1], ans[2], ans[3])
    break
  if sides[2]**2 >= sides[1]**2 + sides[0]**2:
    ans[3]+=1
  elif sides[2]**2 == sides[1]**2 + sides[0]**2:
    ans[2]+=1
  else:
    ans[1]+=1


### FIXED CODE ###

ans = [0 for i in range(4)]
while True:
  sides = sorted([int(inp) for inp in input().split()])
  if sides[2] >= sides[1] + sides[0]:
    print(ans[0], ans[1], ans[2], ans[3])
    break
  if sides[2]**2 > sides[1]**2 + sides[0]**2:
    ans[3]+=1
  elif sides[2]**2 == sides[1]**2 + sides[0]**2:
    ans[1]+=1
  else:
    ans[2]+=1
  ans[0]+=1
import sys
import math
from collections import deque

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(N, A, B, C, inputs):
    bamboos = [int(i) for i in inputs]

    def cost(cursor, a, b, c):
        if cursor == N:
            if min(a, b, c) > 0:
                return abs(A-a) + abs(B-b) + abs(C-c) - 30
            else:
                return 1000000000

        t = bamboos[cursor]
        results = []
        results.append(cost(cursor+1, a, b, c))
        results.append(cost(cursor+1, a + t, b, c) + 10)
        results.append(cost(cursor+1, a, b + t, c) + 10)
        results.append(cost(cursor+1, a, b, c + t) + 10)

        return min(results)

    return cost(0, 0, 0, 0)


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    [N, A, B, C] = string_to_int(inputs(1))
    ret = solve(N, A, B, C, inputs(N))
    print(ret)


### FIXED CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(N, A, B, C, inputs):
    bamboos = [int(i) for i in inputs]

    def cost(cursor, a, b, c):
        if cursor == N:
            if min(a, b, c) > 0:
                return abs(A-a) + abs(B-b) + abs(C-c) - 30
            else:
                return 1000000000

        t = bamboos[cursor]
        results = []
        results.append(cost(cursor+1, a, b, c))
        results.append(cost(cursor+1, a + t, b, c) + 10)
        results.append(cost(cursor+1, a, b + t, c) + 10)
        results.append(cost(cursor+1, a, b, c + t) + 10)

        return min(results)

    return cost(0, 0, 0, 0)


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    [N, A, B, C] = string_to_int(input())
    ret = solve(N, A, B, C, inputs(N))
    print(ret)
import numpy as np

b, c = map(int, input().split())
if b < c:
  print('0')
  else:
    print('10')

### FIXED CODE ###

a = input().split()
if a[0] < a[1]:
  print('0')
else:
  print('10')
mport sys

n = int(input())
nums = []
for _ in range(n):
    nums.append(int(input()))
s = sum(nums)
if s % 10 != 0:
    print(s)
else:
    nums.sort()
    for num in nums:
        t = s - num
        if t % 10 != 0:
            print(t)
            break
    else:
        print(0)

### FIXED CODE ###

# https://atcoder.jp/contests/abc063/tasks/arc075_a

n = int(input())
nums = []
for _ in range(n):
    nums.append(int(input()))

total = sum(nums)
dp = [[False for _ in range(total + 1)] for _ in range(n + 1)]
dp[0][0] = True
for i in range(n):
    num = nums[i]
    dp[i + 1][num] = True
    for j in range(total + 1):
        if dp[i][j] and num + j <= total:
            dp[i + 1][num + j] = True

        dp[i + 1][j] = dp[i][j] or dp[i + 1][j]

for i in range(len(dp[0]))[::-1]:
    if dp[-1][i] and i % 10 != 0:
        print(i)
        break
else:
    print(0)
def kaibun(s):
  n=len(s)
  a=True
  if n%2==0:
    for i in range(n/2):
      if s[i]!=s[n-1-i]:
        a=False
  else:
    for i in range((n-1)/2):
      if s[i]!=s[n-1-i]:
        a=False
  return a
if kaibun(S)==True and kaibun(S[0:(len(S)-1)/2])==True and kaibun(S[(len(S)+3)/2-1:len(S)])==True:
  return "Yes"
else:
  return "No"

### FIXED CODE ###

def kaibun(s):
  n=len(s)
  a=True
  if n%2==0:
    for i in range(n//2):
      if s[i]!=s[n-1-i]:
        a=False
  else:
    for i in range((n-1)//2):
      if s[i]!=s[n-1-i]:
        a=False
  return a
S=input()
N=len(S)
if kaibun(S)==True and kaibun(S[0:(N-1)//2])==True and kaibun(S[(N+3)//2-1:N])==True:
  print("Yes")
else:
  print("No")
S = input()
T = ''
U = ['dreamer', 'dream', 'eraser', 'erase']

answer = 'NO'


def possible(current):
    possible = []
    for string in U:
        if S.startswith(current + string):
            possible.append(string)
    return possible


def judge(current):
    if current == S:
        global answer
        answer = 'YES'
        return
    if answer == 'YES' or len(S) < len(current):
        return
    else:
        if possible(current) == []:
            return
        else:
            for candidate in possible(current):
                new = current + candidate
                if len(S) >= len(new):
                    judge(current + candidate)


for string in U:
    judge(string)

print(answer)


### FIXED CODE ###

S = input()
T = ''
U = ['dreamer', 'dream', 'eraser', 'erase']
answer = 'NO'
list = [T]
done = 0

while done == 0:
    for l in list:
        list.remove(l)
        for u in U:
            if S.startswith(l + u):
                if S == l + u:
                    answer = 'YES'
                    done = 1
                list.append(l + u)
    if list == []:
        done = 1
print(answer)
apple = input()
kakera = input()
ans = int((int(apple) * 3  + int(kakera))/2)


print(ans) 

### FIXED CODE ###

A, P = input().strip().split()

ans = int((int(A) * 3  + int(P))/2)


print(ans)
h = input()
w = input()
n = input()
count = 0
if h < w:
  a = w
  b = h
else:
  a = h
  b = w
 
x = int(n/a)
if n%a != 0:
  x += 1
print(x)

### FIXED CODE ###

h = int(input())
w = int(input())
n = int(input())
count = 0
if h < w:
  a = w
  b = h
else:
  a = h
  b = w
 
x = int(n/a)
if n%a != 0:
  x += 1
print(x)
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and a[q]+a[p]<=md:
            p+=1
    except:
        p=n
    if p==n: break
    cnt+=n-p
    ans+=a[q]*(n-p)*2


ans+=(m-cnt)*md
print(ans)

### FIXED CODE ###

import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2
md=(r+l)//2
while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and a[q]+a[p]<=md:
            p+=1
    except:
        b=1
        while True:
            b+=1

    if p==n: break
    cnt+=n-p
    ans+=a[q]*(n-p)*2


ans+=(m-cnt)*md
print(ans)
for i in range(1, 10):
  for j in range(1, 10):
    print i + '×' + j + '=' + i*j

### FIXED CODE ###

for i in range(1, 10):
  for j in range(1, 10):
    print str(i) + 'x' + str(j) + '=' + str(i*j)
t = int(input())

return 48-t

### FIXED CODE ###

M = int(input())
x = 48 - M

print(x)
l=[]
for i in range(10):
	l.append(int(input()))
l.sort().reversed()
print(l[0])
print(l[1])
print(l[2])

### FIXED CODE ###

l=[]
for i in range(10):
	l.append(int(input()))
l.sort(reverse=True)
print(l[0])
print(l[1])
print(l[2])
K, N = map(int, input().split())
L = list(map(int, input().split())).sort(reverse=True)
print(sum(L[:K]))


### FIXED CODE ###

N, K = map(int, input().split())
L = list(map(int, input().split()))
L.sort(reverse=True)
print(sum(L[:K]))
x = imput('>>>')
x = x*x*x
print(x)


### FIXED CODE ###

x = input('')
y = int(x)**3
print(y)
#ベルマンフォード法
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford

n,m=map(int,input().split())
edge=np.array([input().split() for _ in range(m)],dtype=np.int64).T
graph=csr_matrix(((-edge[2],edge[:2]-1)),(n,n))

while True:
    try:
        #False->無向グラフ True->有効グラフ
        ans=bellman_ford(graph,directed=True,indices=[0])[0].astype(int)
        print(-ans[-1])
        break
    except:
        #負経路の場合
        print("inf")
        break

### FIXED CODE ###

n,m=map(int,input().split())
abc=[]
for i in range(m):
    abc.append([int(j) for j in input().split()])
b=[float("INF")]*(n+1)
b[1]=0
for i in range(1,n+1):
    for s,t,u in abc:
        if b[t]>b[s]-u:
            b[t]=b[s]-u
            if i==n and t==n:
                print("inf")
                exit()
print(-b[-1])
from math import gcd
n=int(input())
l=list(map(int,input().split()))
mal=max(l)
e=[0 for i in range(mal+1)]

import numpy as np
def searchPrimeNum(N):
    ma = int(np.sqrt(N))
    searchList = [i for i in range(2,N+1)]
    primeNum = []
    while searchList[0] <= ma:
        primeNum.append(searchList[0])
        tmp = searchList[0]
        for i in searchList:
            if i%tmp==0:
                e[i]=tmp
        searchList = [i for i in searchList if i % tmp != 0]
        primeNum.extend(searchList)
    return primeNum
searchPrimeNum(mal)
#print(e)    
s=set()
f=1
for i in l:
  st = set()
  while i > 1:
    st.add(e[i])
    i//=e[i]
  if not s.isdisjoint(st):
    f=1
    break
  s |= st

if f==0:
    print('pairwise coprime')
    exit()
p=l[0]
for i in range(1,n):
    p=gcd(p,l[i])
if p==1:
    print('setwise coprime')
else:
    print('not coprime')

### FIXED CODE ###

from math import gcd
n=int(input())
l=list(map(int,input().split()))
mal=max(l)
e=[i for i in range(mal+1)]

x=2
while x*x <= mal:
    if x == e[x]:
        for m in range(x, len(e), x):
            if e[m] == m:
                e[m] = x
    x+=1
#print(e)    
s=set()
f=0
for i in l:
  st = set()
  while i > 1:
    st.add(e[i])
    i//=e[i]
  if not s.isdisjoint(st):
    f=1
    break
  s |= st

if f==0:
    print('pairwise coprime')
    exit()
p=l[0]
for i in range(1,n):
    p=gcd(p,l[i])
if p==1:
    print('setwise coprime')
else:
    print('not coprime')
N = int(input())
S = input()
Q = int(input())
Ks= list(map(int, input().split()))

for K in Ks:
    cnt_d, cnt_m, sum_dm = 0,0,0
    ans = 0
    for i in range(N):
        if i-K>=0:
            if S[i-K]=="D":
                cnt_d -= 1
                sum_dm -= cnt_m
            elif S[i-K]=="M":
                cnt_m -= 1

        if S[i]=="D":
            cnt_d += 1
        elif S[i]=="M":
            sum_dm += cnt_d
            cnt_m += 1
        elif S[i]=="C":
            ans += sum_dm

    print(ans)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
ave = sum(a)/N
for i in range(len(a)):
    a[i] = abs(a[i]-ave)

mina, minid = 1e9,-1
for i in range(len(a)):
    if mina>=a[N-1-i]:
        mina, minid = a[N-1-i], N-1-i
print(minid)
A,B,C,K=map(int,input().split())
A=[1]*A
B=[0]*B
C=[-1]*C
D=A+B+C
print(sum(D[:K]))


### FIXED CODE ###

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

if A>=K:print(K)
elif A+B>=K:print(A)
else: print(A-(K-(B+A)))
N, K = map(int, input().split())
a = L = list(map(int, input().split()))
count = 0
if sum(a) >= K:
    count +=1
for n in range(1,N):
    for i in range(N):
        if sum(a[i:i+n]) >= K:
            count += 1
print(count)

### FIXED CODE ###

X, A = map(int, input().split())
if X >= A:
    print(10)
else:
    print(0)
N = int(input())
X = input()
f = [0]*(N+1)
for i in range(1, N):
    a = sum(list(map(int, bin(i)[2:])))
    f[i] = f[i%a]+1

for i in range(N):
    if X[i] == '1':
        x = int(X[0:i]+'0'+X[i+1:], 2)
    else:
        x = int(X[0:i]+'1'+X[i+1:], 2)
    a = sum(list(map(int, bin(x)[2:])))
    print(f[x%a]+1)

### FIXED CODE ###

N = int(input())
X_2 = input()
X_10 = int(X_2, 2)

y = X_2.count('1')

a = X_10%(y+1)
if y==1:
    b = 0
else:
    b = X_10%(y-1)

for i in range(N):
    if X_2[i] == '1' and y == 1:
        print(0)
        continue
    elif X_2[i] == '1':
        x = (b-pow(2, N-1-i, y-1))%(y-1)
    else:
        x = (a+pow(2, N-1-i, y+1))%(y+1)
    count = 1
    while x!=0:
        x %= bin(x)[2:].count('1')
        count += 1
    print(count)
x=int(input())
for i in range(-120,120):
  for j in range(-120.120):
    if i**5-j**5==x:
      print(i,j)
      break

### FIXED CODE ###

x=int(input())
for i in range(-120,120):
  for j in range(-120,120):
    if i**5-j**5==x:
      print(i,j)
      exit()
s=str(input())

p1 = '01'
p2 = '10'
s = s[::-1]
c = 0
flag = True
while flag:
  flag = False
  for i in range(len(s)):
    if s[i:i+4] == in('0011','1100','1010','0101','1001','0110'):
      s = s[:i] + s[i+4:]
      c += 4
      flag = True
      break
    
    
    if s[i:i+2] in [p1,p2]:
      s = s[:i] + s[i+2:]
      c += 2
      flag = True
      break
print(c)

### FIXED CODE ###

s=str(input())
c1 = 0
c0 = 0
for i in range(len(s)):
  if s[i] == '1':
    c1 += 1
  if s[i] == '0':
    c0 += 1
print(2*min(c1,c0))
def find_root(components, n):
    if components[n] == n:
        return n
    elif components[components[n]] == components[n]:
        return components[n]
    else:
        components[n] = find_root(components, components[n])
        return components[n]

N, M = [int(s) for s in input().split(' ')]
bridges = []
for i in range(M):
    bridges.append([int(s)-1 for s in input().split(' ')])
components = [i for i in range(N)]
componentsLen = [1 for i in range(N)]
inconvenience = [int(N * (N-1) / 2)]
for i in range(M-1, -1, -1):
    a, b = bridges[i]
    a_root = find_root(components, a)
    b_root = find_root(components, b)
    if a_root != b_root:
        inconvenience.append(inconvenience[-1] - componentsLen[a_root] * componentsLen[b_root])
        components[b_root] = a_root
        componentsLen[a_root] += componentsLen[b_root]
    else:
        inconvenience.append(inconvenience[-1])
for i in range(M-1, -1, -1):
    print(inconvenience[i])


### FIXED CODE ###

def find_root(components, n):
    if components[n] == n:
        return n
    elif components[components[n]] == components[n]:
        return components[n]
    else:
        components[n] = find_root(components, components[n])
        return components[n]

N, M = [int(s) for s in input().split(' ')]
bridges = []
for i in range(M):
    bridges.append([int(s)-1 for s in input().split(' ')])
components = [i for i in range(N)]
componentsLen = [1 for i in range(N)]
inconvenience = [int(N * (N-1) / 2)]
for i in range(M-1, -1, -1):
    a, b = bridges[i]
    a_root = find_root(components, a)
    b_root = find_root(components, b)
    if a_root != b_root:
        inconvenience.append(inconvenience[-1] - componentsLen[a_root] * componentsLen[b_root])
        if componentsLen[a_root] < componentsLen[b_root]:
            a_root, b_root = b_root, a_root
        componentsLen[a_root] += componentsLen[b_root]
        components[b_root] = a_root
    else:
        inconvenience.append(inconvenience[-1])
for i in range(M-1, -1, -1):
    print(inconvenience[i])
k,s=map(int,input().split())
ans = 0
for i in range(1,k+1):
  for j in range(1,k;1):
    if s-i-j<=k:
      ans+=1
print(ans)

### FIXED CODE ###

k,s=map(int,input().split())
ans = 0
for i in range(k+1):
  for j in range(k+1):
    if 0<=s-i-j<=k:
      ans+=1
print(ans)
import sys
sys.setrecursionlimit(2000)
h,w=map(int,input().split())
s=['#'*(w+2)]+['#'+input()+'#' for _ in [0]*h]+['#'*(w+2)]
l=[[0]*(w+2) for _ in [0]*(h+2)]
for i in range(h+2):
    for j in range(w+2):
        if s[i][j]=='#':
            l[i][j]=-1
def sol(m,n):
    global l
    if l[m][n]>=0:
        for [i,j] in [[m-1,n],[m+1,n],[m,n-1],[m,n+1]]:
            if l[i][j]==0 and [i,j]!=[1,1]:
                l[i][j]=l[m][n]+1
                sol(i,j)
            elif l[i][j]>l[m][n]+1:
                l[i][j]=l[m][n]+1
                sol(i,j)
sol(1,1)
if l[h][w]==0:print(-1)
else:print(h*w-l[h][w]-(sum(x.count('#') for x in s)-2*h-2*w-4)-1)


### FIXED CODE ###

import sys
sys.setrecursionlimit(3000)
h,w=map(int,input().split())
s=['#'*(w+2)]+['#'+input()+'#' for _ in [0]*h]+['#'*(w+2)]
l=[[0]*(w+2) for _ in [0]*(h+2)]
for i in range(h+2):
    for j in range(w+2):
        if s[i][j]=='#':
            l[i][j]=-1
def sol(m,n):
    global l
    if l[m][n]>=0:
        for i,j in [(m-1,n),(m+1,n),(m,n-1),(m,n+1)]:
            if l[i][j]==0 and [i,j]!=[1,1]:
                l[i][j]=l[m][n]+1
                sol(i,j)
            elif l[i][j]>l[m][n]+1:
                l[i][j]=l[m][n]+1
                sol(i,j)
sol(1,1)
if l[h][w]==0:print(-1)
else:print(h*w-l[h][w]-(sum(x.count('#') for x in s)-2*h-2*w-4)-1)
a,b = map(int,input().split())
	if a % 3 == 0 or b % 3 == 0 or (a+b) % 3 == 0:
    	print('Possible')
    else:
        print('Impossible')

### FIXED CODE ###

a,b = map(int,input().split())
if a % 3 == 0 or b % 3 == 0 or (a+b) % 3 == 0:
    print('Possible')
else:
    print('Impossible')
h, w = map(int, input().split())
s = [input() for _ in range(w)]
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            flag = 0
            L = []
            if i == 0 and j == 0:
                L.extend([(0, 1), (1, 0)])
            elif i == 0 and j == w - 1:
                L.extend([(-1, 0), (1, 0)])
            elif i == h - 1 and j == 0:
                L.extend([(-1, 0), (0, 1)])
            elif i == h - 1 and j == w - 1:
                L.extend([(-1, 0), (0, -1)])
            elif i == 0:
                L.extend([(1, 0), (0, -1), (0, 1)])
            elif i == h - 1:
                L.extend([(-1, 0), (0, 1), (0, -1)])
            elif j == 0:
                L.extend([(-1, 0), (1, 0), (0, 1)])
            elif j == w - 1:
                L.extend([(-1, 0), (1, 0), (0, -1)])
            else:
                L.extend([(-1, 0), (1, 0), (0, -1), (0, 1)])
            
            for dx, dy in L:
                    if s[i + dx][j + dy] == '#':
                        flag = 1
            if flag == 0:
                print('No')
                exit()
else:
    print('Yes')


### FIXED CODE ###

h, w = map(int, input().split())
s = [input() for _ in range(h)]
dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            flag = 0
            for k in range(4):
                ny = i + dy[k]
                nx = j + dx[k]
                if nx < 0 or w <= nx:
                    continue
                if ny < 0 or h <= ny:
                    continue
                if s[ny][nx] == '#':
                    flag = 1
            if flag == 0:
                print('No')
                exit()
else:
    print('Yes')
import math


def m():
    a, b, n = map(int, input().split())

    def calc(x):
        return math.floor((a * x) / b) - (a * math.floor(x / b))

    if calc(1) < calc(n // 2):
        return max([calc(i) for i in range(n // 2, n + 1)])
    else:
        return max([calc(i) for i in range(1, n // 2 + 1)])


print(m())


### FIXED CODE ###

def m():
    a, b, n = map(int, input().split())

    def calc(x):
        return int((a * x) / b) - (a * int(x / b))

    return calc(min(n, b-1))

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

gridA = [[v for v in input()] for _ in range(N)]
gridB = [[v for v in input()] for _ in range(M)]

for x_A in range(N):
    for y_A in range(N):
        ok = True
        for x_B in range(M):
            for y_B in range(M):
                if gridA[x_A+x_B][y_A+y_B] == gridB[x_B][y_B]:
                    continue
                else:
                    ok = False
                    break
            else:
                continue
            break
        else:
            print("Yes")
            exit()
print("No")


### FIXED CODE ###

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

gridA = [[v for v in input()] for _ in range(N)]
gridB = [[v for v in input()] for _ in range(M)]

for x_A in range(N):
    for y_A in range(N):
        ok = True
        for x_B in range(M):
            for y_B in range(M):
                if x_A+x_B >= N or y_A+y_B >= N:
                    break
                if gridA[x_A+x_B][y_A+y_B] == gridB[x_B][y_B]:
                    continue
                else:
                    ok = False
                    break
            else:
                continue
            break
        else:
            print("Yes")
            exit()
print("No")
n = int(input())
A = list(map(int,input().split()))
data = [0]*3
ans = 1
mod = pow(10,9)+7
for i in A:
    ans *= data.count(i)
    ans %= mod
    data[data.index(i)] += 1
print(ans)

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
data = [0]*3
ans = 1
mod = pow(10,9)+7
for i in A:
    ans *= data.count(i)
    ans %= mod
    if ans == 0:
        break
    data[data.index(i)] += 1
print(ans)
N = int(input())
H = list(map(int, input().split()))
k = 0
while H[i] >= H[i+1] for i in range(N):
    k += 1
print(k)

### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
k = 0
m = 0
for i in range(N):
    if k < m:
        k = m
    if i != N - 1 and H[i] >= H[i+1]:
        m += 1
    else:
        m =0
print(k)
N, M, L = map(int,input().split())
MAX=999999999
A=[]
B=[]
C=[]
D=[[MAX for _ in range(N)] for _ in range(N)]
F=[[MAX for _ in range(N)] for _ in range(N)]
s=[]
t=[]
 
for i in range(M):
    l=list(map(int,input().split()))
    A.append(l[0]-1)
    B.append(l[1]-1)
    C.append(l[2])
 
 
 
Q=int(input())
 
for i in range(Q):
    m=list(map(int,input().split()))
    s.append(m[0]-1)
    t.append(m[1]-1)
 
 
for i in range(M):
    if C[i]>L : continue
    D[A[i]][B[i]]=C[i]
    D[B[i]][A[i]]=C[i]
 
for i in range(N):  D[i][i]=0
 
for k in range(N):
    for i in range(N):
        for j in range(N):
            if (D[i][k]+D[k][j])<D[i][j] :
                D[i][j]=D[i][k]+D[k][j]
 
for i in range(N):
    for j in range(N):
        if i==j : continue
        if D[i][j]<=L: F[i][j]=1
 
 
for i in range(N):  F[i][i]=0
 
for k in range(N):
    for i in range(N):
        for j in range(N):
            if (F[i][k]+F[k][j])<F[i][j] :
                F[i][j]=F[i][k]+F[k][j]
 
 
for p in range(Q) :
    if F[s[p]][t[p]] < MAX :
        print(F[s[p]][t[p]]-1)
    else :
        print(-1)

### FIXED CODE ###

A,B=map(int,input().split())
if A>=2*B:
    Ans = A-(2*B)
else:
    Ans=0
print(Ans)
sys.setrecursionlimit(2000000)
S = [-1]*(101010)
def opt_S(h,n):
    if(n == 0):return 0
    elif(n == 1):return abs(h[1]-h[0])
    else :
        if(S[n] != -1):return S[n]
        s1 = opt_S(h,n-1) + abs(h[n-1]-h[n])
        s2 = opt_S(h,n-2) + abs(h[n-2]-h[n])
        S[n] = min(s1,s2)
        return S[n]



N = int(input())
h = list(map(int,input().split()))
print(opt_S(h,N-1))



### FIXED CODE ###

import sys
sys.setrecursionlimit(200000) #追加
S = [-1]*(101010)
def opt_S(h,n):
    if(n == 0):return 0
    elif(n == 1):return abs(h[1]-h[0])
    else :
        if(S[n] != -1):return S[n]
        s1 = opt_S(h,n-1) + abs(h[n-1]-h[n])
        s2 = opt_S(h,n-2) + abs(h[n-2]-h[n])
        S[n] = min(s1,s2)
        return S[n]



N = int(input())
h = list(map(int,input().split()))
print(opt_S(h,N-1))
N = int(input())
c = list(map(str, input().split()))

a=0
b=0

a = c.count("R")

for i in range(N):
    if c[i] == 'R':
        a -= 1
    else:
        b += 1

    now = max(a,b)
    ans = min(ans, now)

print(ans)


### FIXED CODE ###

N = int(input())
c = list(input())

a=0
b=0

a = c.count("R")
ans = c.count("R")
for i in range(N):
    if c[i] == "R":
        a -= 1
    else:
        b += 1

    now = max(a,b)
    ans = min(ans, now)

print(ans)
D=int(input())
T=int(input())
S=int(input())

if T*S>=D:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

a=list(map(int,input().split()))
D=a[0]
T=a[1]
S=a[2]
if T*S>=D:
  print('Yes')
else:
  print('No')