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

"""
"""
from math import factorial
from collections import defaultdict


def int_as_array(num): return list(map(int, [y for y in str(num)]))


def array_as_int(arr): return int(''.join(map(str, arr)))


def read_int(): return int(input())


def read_array(): return list(map(int, input().split(' ')))


def array_to_string(arr, sep=' '): return sep.join(map(str, arr))


def matrix_to_string(arr, sep=' '): return '[\n' + '\n'.join(
    [sep.join(map(str, row)) for row in arr]) + '\n]'


cache = {}


def fac(x):
    return factorial(x)


def choose_combination(n, r):
    if r > n:
        return 0
    return int((fac(n) / fac((n - r))) * (1 / fac(r)))


def solve(n, array):
    counts = defaultdict(int)
    for x in array:
        counts[x] += 1
    total_ways = 0
    for x, count in counts.items():
        total_ways += choose_combination(counts[x], 2)
    for k in array:
        ways = choose_combination(counts[k] - 1, 2)
        print(total_ways + ways - choose_combination(counts[k], 2))


N = read_int()
array = read_array()
solve(N, array)


### FIXED CODE ###

"""
"""
from math import factorial
from collections import defaultdict


def int_as_array(num): return list(map(int, [y for y in str(num)]))


def array_as_int(arr): return int(''.join(map(str, arr)))


def read_int(): return int(input())


def read_array(): return list(map(int, input().split(' ')))


def array_to_string(arr, sep=' '): return sep.join(map(str, arr))


def matrix_to_string(arr, sep=' '): return '[\n' + '\n'.join(
    [sep.join(map(str, row)) for row in arr]) + '\n]'


cache = {}


def fac(x):
    return factorial(x)


def choose_combination(n, r):
    if r > n:
        return 0
    # return int((fac(n) / fac((n - r))) * (1 / fac(r)))
    # return (fac(n) // fac((n - 2)) * (1 / 2))
    # return fac((n // n - 2)) * (1 / 2))
    return (n * (n-1)) // 2


def solve(n, array):
    counts = defaultdict(int)
    for x in array:
        counts[x] += 1
    total_ways = 0
    for x, count in counts.items():
        total_ways += choose_combination(counts[x], 2)
    for k in array:
        ways = choose_combination(counts[k] - 1, 2)
        print(total_ways + ways - choose_combination(counts[k], 2))


N = read_int()
array = read_array()
solve(N, array)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
s = input()
N, A, B = map(int, s.split())

a = 0
while N > 0:
  N -= A
  if N >= 0:
  	a += A
  else:
    a += A + N
  N -= B

print(a)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

d = N // (A+B)
m = N % (A+B)

print(d * A + min(m, A))
### BUGGY CODE ###

N = int(input())
l = []
for a in range(1, N+1):
  if N % a == 0:
    b = N // a
    s = max(len(str(a)), len(str(b)))
    l.append(int(s))
print(min(l))


### FIXED CODE ###

N = int(input())
l = []
for a in range(1, 10**5+1):
  if N % a == 0:
    b = N // a
    s = max(len(str(a)), len(str(b)))
    l.append(int(s))
print(min(l))
### BUGGY CODE ###

from collections import Counter
n = int(input())
# アルファベットがキー、要素をカウント数の辞書にして比較する
s = [Counter(input()) for _ in range(n)]
#print(s)
cnt = 0
for i in range(n-1):
  for j in range(i+1,n):
    #print('{} and {}'.format(s[i], s[j]))
    if s[i] == s[j]: cnt+=1
print(cnt)

### FIXED CODE ###

from collections import Counter
n = int(input())
s = [input() for _ in range(n)]
cnt = 0
d = {}
for i in range(n):
  sortsi = ''.join(sorted(s[i]))
  if sortsi in d:
    cnt+=d[sortsi]
    d[sortsi]+=1
  else: 
    d[sortsi]=1
print(cnt)
### BUGGY CODE ###

S = input()[::-1]
n = len(S)
dp = [0]*2019
dp[0] = 1
X = 0
Y = 1
for s in S:
    X = (X+int(s)*Y)%2019
    dp[X] += 1
    Y *= 10
answer = 0
for i in range(2019):
    answer += dp[i]*(dp[i]-1)/2
print(int(answer))

### FIXED CODE ###

S = input()[::-1]
n = len(S)
dp = [0]*2019
dp[0] = 1
X = 0
Y = 1
for s in S:
    Z=(int(s)*Y)%2019
    X = (X+Z)%2019
    dp[X] += 1
    Y = (10*Y)%2019
answer = 0
for i in range(2019):
    answer += dp[i]*(dp[i]-1)/2
print(int(answer))
### BUGGY CODE ###

r,g,b,n=map(int,input().split())
rm=n//r
gm=n//g
bm=n//b
ans=0
for i in range(rm,-1,-1):
    for j in range(gm,-1,-1):
        for k in range(bm,-1,-1):
            t=i*r+j*g+k*b
            if t<n:
                break
            elif t==n:
                ans+=1
print(ans)

### FIXED CODE ###

r,g,b,n=map(int,input().split())
ans=0
for i in range(n//r+1):
    for j in range((n-(r*i))//g+1):
        if (n-(r*i)-(g*j))%b==0:
            ans+=1
print(ans)
### BUGGY CODE ###

from bisect import bisect_right

N, M = map(int, input().split())
w = sorted([tuple(map(int, input().split())) for _ in range(N)])
days = [x[0] for x in w]
pays = [x[0] for x in sorted(w[:], key=lambda x: x[1], reverse=True)]
ans = 0
for i in range(M):
    c = bisect_right(days, M-i) - 1
    if c < 0:
        break
    e = c
    for j in range(1, M-i):
        d = bisect_right(days, M - i - j) - 1
        e = e if w[e][1] >= w[d][1] else d
    ans += w[e][1]
    del w[e]
    del days[e]

print(ans)

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
w = [list(map(int, input().split())) for _ in range(N)]
ans = 0

daylist = [[] for _ in range(10**5)]
for a, b in w:
    daylist[a-1].append(b)

q = []
for i in range(M):
    for b in daylist[i]:
        heapq.heappush(q, -b)
    if q:
        ans += -heapq.heappop(q)
print(ans)
### BUGGY CODE ###

N, Q=map(int, input().split())
S=input()
for _ in range(Q):
  l, r=map(int, input().split())
  print(S[l-1:r].count("AC"))

### FIXED CODE ###

N, Q=map(int, input().split())
S=input()
count=0
ac=[0]
for i in range(N-1):
  if S[i]=="A" and S[i+1]=="C":
    count+=1
  ac.append(count)
for _ in range(Q):
  l, r=map(int, input().split())
  l-=1
  r-=1
  print(ac[r]-ac[l])
### BUGGY CODE ###

import bisect
from sys import stdin


def main():
    N = int(stdin.readline().rstrip())
    As = [int(stdin.readline().rstrip()) for x in range(N)]
    array = []
    for A in As:
        idx = bisect.bisect_left(array, A)
        if idx == 0:
            array = [A] + array
        else:
            array[idx - 1] = A
    print(len(array))


if __name__ == "__main__":
    main()


### FIXED CODE ###

import bisect
from collections import deque
from sys import stdin


def main():
    N = int(stdin.readline().rstrip())
    As = [int(stdin.readline().rstrip()) for x in range(N)]
    dq = deque([])
    for A in As:
        idx = bisect.bisect_left(dq, A)
        if idx == 0:
            dq.appendleft(A)
        else:
            dq[idx - 1] = A
    print(len(dq))


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

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

dp = [10**9+7]*N
dp[0] = 0
for i in range(N):
  for j in range(1,K+1):
    if((i+j) < N):
      dp[i+j] = min(dp[i+j], dp[i]+abs(H[i]-H[i+j]))
    else:
      break
print(dp[N-1])

### FIXED CODE ###

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

dp = [1e9]*N
dp[0] = 0
for i, b in enumerate(H):
  if i != 0:
    x = max(0, i-K)
    dp[i] = min([abs(b-d)+p for d, p in zip(H[x:i], dp[x:i])])
print(dp[-1])
### BUGGY CODE ###

x = int(raw_input())
y = 1

for i in range(1, x + 1):
    y *= i

print y % (10**9+7)


### FIXED CODE ###

x = int(raw_input())
y = 1

for i in range(1, x + 1):
    y *= i
    if y > (10**9 + 7):
        y %= 10 ** 9 + 7

print y
### BUGGY CODE ###

def ABC073D():
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    ABC = [list(map(int, input().split())) for i in range(M)]
    root = [[1000000000 for i in range(N)] for j in range(N)]
    for i, j, k in ABC:
        root[i - 1][j - 1] = k
        root[j - 1][i - 1] = k

    import itertools
    def kumiawase(list_name):  # list_name(リスト)のすべての並び替え
        return itertools.permutations(list_name)

    #for i in range(N):
     #   for j in range(N):
      #      for k in range(N):
       #         if root[i][j] > root[i][k] + root[k][j]:
        #            root[i][j] = root[i][k] + root[k][j]

    for i in range(N):
        for j in range(N):
            for k in range(N):
                if root[N - i - 1][N - j - 1] > root[N - i - 1][N - k - 1] + root[N - k - 1][N - j - 1]:
                    root[N - i - 1][N - j - 1] = root[N - i - 1][N - k - 1] + root[N - k- 1][N - j - 1]

    a = kumiawase(r)
    ans = float("inf")
    for i in a:
        key = 0
        for j in range(len(i) - 1):
            key += root[i[j] - 1][i[j + 1] - 1]
        if ans > key:
            ans = int(key)
    #print(root)
    print(ans)
ABC073D()

### FIXED CODE ###

def ABC073D():
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    ABC = [list(map(int, input().split())) for i in range(M)]
    root = [[1000000000 for i in range(N)] for j in range(N)]
    for i, j, k in ABC:
        root[i - 1][j - 1] = k
        root[j - 1][i - 1] = k

    import itertools
    def kumiawase(list_name):  # list_name(リスト)のすべての並び替え
        return itertools.permutations(list_name)


    from scipy.sparse import csgraph
    root = csgraph.floyd_warshall(root)

    a = kumiawase(r)
    ans = float("inf")
    for i in a:
        key = 0
        for j in range(len(i) - 1):
            key += root[i[j] - 1][i[j + 1] - 1]
        if ans > key:
            ans = int(key)
    #print(root)
    print(ans)
ABC073D()
### BUGGY CODE ###

def f(n):
    pairs = set()
    for x in range(1, 45):
        for y in range(x, 45):
            temp = - 3 * (x + y) ** 2 + 4 * n + 4 * x * y
            if temp < 0:
                continue
            temp2 = int(temp ** .5)
            if temp2 * temp2 != temp:
                continue
            temp3 = - (x + y) + temp2
            temp4 = - (x + y) - temp2
            z1 = temp3 // 2
            z2 = temp4 // 2
            if z1 >= 1 and temp3 % 2 == 0:
                key = tuple(sorted((x, y, z1)))
                if key in pairs:
                    continue
                pairs.add(key)
            if z2 >= 1 and temp4 % 2 == 0:
                key = tuple(sorted((x, y, z2)))
                if key in pairs:
                    continue
                pairs.add(key)
    res = 0
    for x, y, z in pairs:
        if x == y == z:
            res += 1
        elif x == y or y == z or z == x:
            res += 3
        else:
            res += 6
    return res


N = int(input())
for i in range(1, N + 1):
    print(f(i))

### FIXED CODE ###

def g(x, y, z):
    return x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x


N = int(input())
count = [0] * (N + 1)
for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            cur = g(x, y, z)
            if cur <= N:
                count[cur] += 1
for i in range(1, N + 1):
    print(count[i])
### BUGGY CODE ###

#!/usr/bin/env python
from functools import *
import math

n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7

p = 1 
for i in range(n):
    p *= a[i]

def lcm(a, b): 
    return a*b//math.gcd(a, b)

l = a[0]
for i in range(n):
    l = lcm(l, a[i])

ans = 0 
for i in range(n):
    ans += (l//a[i])%mod

print(ans%mod)


### FIXED CODE ###

#!/usr/bin/env python
import math
n = int(input()) 
a = list(map(int, input().split()))

mod = 10**9+7

def lcm(a, b): 
    return a*b//math.gcd(a, b)

l = a[0]
for i in range(n):
    l = lcm(l, a[i])
l %= mod 

ans = 0 
for i in range(n):
    inv = pow(a[i], mod-2, mod)
    ans += (l*inv)%mod

print(ans%mod)
### BUGGY CODE ###

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

min_n = 10**9

 
for i in l:
  num = 0
  while num < min_n:
    if i % 2 == 0:
      i = i//2
      num += 1
  min_n = num

print(min_n)


### FIXED CODE ###

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

min_n = 10**9

 
for i in l:
  num = 0
  while num < min_n:
    if i % 2 == 0:
      i = i//2
      num += 1
    else:
      break
  min_n = num

print(min_n)
### BUGGY CODE ###

import fractions
import itertools
# print(math.gcd(1000000000, 1000000000))

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

result = 10 ** 9 + 1

for comb in list(itertools.combinations(monsters,2)):
    gcd = fractions.gcd(comb[0], comb[1]) 
    if gcd < result:
        result = gcd

print(result)

### FIXED CODE ###

import fractions
import itertools
from functools import reduce
# print(math.gcd(1000000000, 1000000000))


def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

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

result = 10 ** 9 + 1

print(gcd(*monsters))
### BUGGY CODE ###

n = int(input())
tree = [None] * n
formatted_tree = [None] * n


def register_node(i, node, searching):
    for si, st in enumerate(searching[1]):
        if type(st) is int:
            if st == i:
                searching[1][si] = node
                return True
        else:
            if register_node(i, node, st):
                return True
    return False


def format(node, parent, depth):
    (i, cs) = node
    cis = [format(c, i, depth + 1) for c in cs]
    formatted_tree[i] = 'node {0}: parent = {1}, depth = {2}, {3}, [{4}]'.format(
        i, parent, depth,
        'root' if not depth else 'internal node' if cis else 'leaf',
        ', '.join(cis)
    )
    return str(i)


while n:
    l = list(map(int, input().split()))
    i, c = l[0], l[2:]
    node = (i, c)
    for p in tree:
        if not p:
            continue
        if register_node(i, node, p):
            break
    else:
        tree[i] = node

    for i, ci in enumerate(c):
        if tree[ci]:
            c[i] = tree[ci]
            tree[ci] = None

    n -= 1

format(next(filter(None, tree)), -1, 0)

for fn in formatted_tree:
    print(fn)

### FIXED CODE ###

n = int(input())
tree = [None] * n
root = set(range(n))


def set_pd(i, parent, depth):
    node = tree[i]
    node[1], node[2] = parent, depth
    for child in node[0]:
        set_pd(child, i, depth + 1)


while n:
    l = list(map(int, input().split()))
    c = l[2:]
    tree[l[0]] = [c, None, None]
    root -= set(c)
    n -= 1

set_pd(root.pop(), -1, 0)

for i, node in enumerate(tree):
    c, p, d = node
    print('node {}: parent = {}, depth = {}, {}, [{}]'.format(
        i, p, d, 'root' if not d else 'internal node' if c else 'leaf', ', '.join(map(str, c))
    ))
### BUGGY CODE ###

N, Q = map(int, raw_input().split())
string = raw_input()
a = []
for i in range(Q):
    a.append(map(int, raw_input().split()))
for temp in a:
    str_sub = string[temp[0]-1:temp[1]]
    #print(str_sub)
    result = 0
    print(str_sub.count('AC'))

### FIXED CODE ###

N, Q = map(int, raw_input().split())
string = raw_input()
cnt = [0]
for i in range(N):
#    print(i)
#    print(string[i-2:i])
#    if i == 0:
#        cnt.append(0)
#        continue
    if string[i-1:i+1] == 'AC':
        cnt.append(cnt[i]+1)
        continue
    cnt.append(cnt[i])

for j in range(Q):
    #print(j)
    pare = map(int, raw_input().split())
    print(cnt[pare[1]] - cnt[pare[0]])
### BUGGY CODE ###

#!/usr/bin/env python3

import heapq

h,w=map(int,input().split())
sy,sx=map(int,input().split())
sy-=1
sx-=1
gy,gx=map(int,input().split())
gy-=1
gx-=1
board=''
for _ in range(h):
  board+=input()
costs=[10**18]*(w*h)
costs[sy*w+sx]=0
q=[]
heapq.heappush(q,(0,sy,sx))
while len(q)!=0:
  cost,y,x=heapq.heappop(q)
  cur_pos=y*w+x
  for dy,dx in [[-1,0],[1,0],[0,-1],[0,1]]:
    next_pos=cur_pos+dy*w+dx
    if 0<=y+dy<h and 0<=x+dx<w and board[next_pos]=='.' and costs[next_pos]>costs[cur_pos]:
      costs[next_pos]=costs[cur_pos]
      heapq.heappush(q,(cost,y+dy,x+dx))
  for dy in range(-2,3):
    for dx in range(-2,3):
      if dy==0 and dx==0:
        continue
      next_pos=cur_pos+dy*w+dx
      if 0<=y+dy<h and 0<=x+dx<w and board[next_pos]=='.' and costs[next_pos]>costs[cur_pos]+1:
        costs[next_pos]=costs[cur_pos]+1
        heapq.heappush(q,(cost+1,y+dy,x+dx))
if costs[gy*w+gx]==10**18:
  print(-1)
else:
  print(costs[gy*w+gx])

### FIXED CODE ###

#!/usr/bin/env python3

import collections
import sys
input=sys.stdin.readline

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=[['#']*(w+2)]+[list('#'+input().replace('\n','')+'#') for _ in range(h)]+[['#']*(w+2)]
scores=[[10**18]*(w+2) for _ in range(h+2)]
scores[sy][sx]=0
q=collections.deque()
q.append((sy,sx))
count=0
while len(q)!=0:
  y,x=q.popleft()
  for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
    if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]:
      scores[y+dy][x+dx]=scores[y][x]
      q.appendleft((y+dy,x+dx))
  for dy in range(-2,3):
    for dx in range(-2,3):
      if dx==0 and dy==0:
        continue
      if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]+1:
        scores[y+dy][x+dx]=scores[y][x]+1
        q.append((y+dy,x+dx))
if scores[gy][gx]==10**18:
    print(-1)
else:
    print(scores[gy][gx])
### BUGGY CODE ###

N=int(input())
S=[input() for _ in range(N)]
cnt=[0]*N
cnt[0]=1
for i in range(1,N):
    if S[i] in S[:i]:
        cnt[S.index(S[i])]+=1
    else:
        cnt[i]=1
cmax=max(cnt)
ans=[]
for j in range(N):
    if cnt[j]==cmax:
        ans.append(S[j])
ans.sort()
for k in ans:
    print(k)

### FIXED CODE ###

N=int(input())
S=[input() for _ in range(N)]
S.sort()
cnt=1
sheet=[[],[]]

for i in range(1,N):
    if S[i]==S[i-1]:
        cnt+=1
        if i==N-1:
            sheet[0].append(S[i-1])
            sheet[1].append(cnt)
    else:
        sheet[0].append(S[i-1])
        sheet[1].append(cnt)
        cnt=1
        if i==N-1:
            sheet[0].append(S[i])
            sheet[1].append(cnt)

cmax=max(sheet[1])
for j in range(len(sheet[1])):
    if sheet[1][j]==cmax:
        print(sheet[0][j])
### BUGGY CODE ###

import math
def formula(x):
    return math.floor(A*x/B)-(A*math.floor(x/B))
A,B,n=[int(x) for x in input().split()]
maxi=formula(1)
for i in range(2,n+1):
    maxi=max(formula(i),maxi)
print(maxi)

### FIXED CODE ###

import math
def formula(x):
    return math.floor(A*x/B)-(A*math.floor(x/B))
A,B,n=[int(x) for x in input().split()]
if(n<=B-1):
    x=n
else:
    x=B-1
maxi = formula(x)
print(maxi)
### BUGGY CODE ###

def f(X):
    return max(X)-min(X)

N, K = map(int, input().split())
A = [int(x) for x in input().split()]
import itertools
res = 0
for x in itertools.combinations(A, K):
    res = (res + f(x))%(10**9+7)
print(res)


### FIXED CODE ###

N, K = map(int, input().split())
A = [int(x) for x in input().split()]
A.sort()
res = 0
MOD = 10**9+7
nCk_2 = dict()
fac, finv, inv = [0]*(N+1), [0]*(N+1), [0]*(N+1)
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,N+1):
    fac[i] = fac[i-1]*i%MOD
    inv[i] = MOD-inv[MOD%i]*(MOD//i)%MOD
    finv[i] = finv[i-1]*inv[i]%MOD
def comb(n, k):
    return (fac[n]*((finv[k]*finv[n-k])%MOD))%MOD
s = [1,-1]
for m in range(2):
    for i in range(K-1,N):
        res = (res + s[m]*int((A[i])*comb(i,K-1)))%MOD
    A = sorted(A, reverse=True)
print(res)
### BUGGY CODE ###

import numpy as np

def main():
    N, K = map(int,input().split())
    h = list(map(int,input().split()))
    
    dp = np.zeros(N, dtype=int)
    
    for i in range(1, N):
        dp[i] = min(dp[j] + abs(h[i] - h[j]) for j in range(max(0, i - K), i))
    
    print(dp[-1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N, K = map(int,input().split())
    h = list(map(int,input().split()))
    
    dp = [0] * N
    dp[1] = abs(h[0] - h[1])
    
    for i in range(2, N):
        dp[i] = min(dp[j] + abs(h[i] - h[j]) for j in range(max(0, i - K), i))
    
    print(dp[-1])

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

def sieve(N):#エラトステネスの篩
    prime = [0]*(N+1)
    isprime = [True]*(N+1)
    isprime[0]=isprime[1] = False
    num = 0
    for p in range(2,N+1):
        if isprime[p]:
            prime[p] = p
            num += 1
            for j in range(2*p,N+1,p):
                isprime[j] = False
    return prime

lis = sieve(10**5)
prime = set(lis)-{0}
for i in range(10**5+1):
    if lis[i] != 0:
        if (lis[i]+1)//2 in prime:continue
        else:lis[i] = 0
    else:continue
Q = int(input())
for _ in range(Q):
    l,r = map(int,input().split())
    t = lis[l:r+1].count(0)
    print(r-l+1-t)


### FIXED CODE ###

def sieve(N):#エラトステネスの篩
    prime = [0]*(N+1)
    isprime = [True]*(N+1)
    isprime[0]=isprime[1] = False
    num = 0
    for p in range(2,N+1):
        if isprime[p]:
            prime[num] = p
            num += 1
            for j in range(2*p,N+1,p):
                isprime[j] = False
    return prime
from bisect import bisect_left as bl
from bisect import bisect_right as br
lis = sieve(10**5)
prime = set(lis)-{0}
for i in range(len(lis)):
    if lis[i] != 0:
        if (lis[i]+1)//2 in prime:continue
        else:lis[i] = 0
    else:continue
Q = int(input())
lis = set(lis)-{0}
lis = sorted(tuple(lis))
for _ in range(Q):
    l,r = map(int,input().split())
    t = bl(lis,l)
    s = br(lis,r)
    tmp = s-t
    print(tmp)
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
count = 0
tof = True


for i in range(1, n+1):
    if p[i-1] <= min(p[:i]):
        count += 1

print(count)

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
count = 0
m = [0] * n

memo = n
for i in range(n):
    if memo > p[i]:
        m[i] = p[i]
        memo = p[i]
    else:
        m[i] = memo

for i in range(1, n+1):
    if p[i-1] <= m[i-1]:
        count += 1

print(count)
### BUGGY CODE ###

#import sys
import heapq
#from collections import deque
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split()) 
DBG = True  and False
BIG = 1234567890

def ddprint(x):
  if DBG:
    print(x)

n,m,l = inm()

distance = [ [BIG] * n for i in range(n) ]
hops = [ [(BIG,0)] * n for i in range(n) ]
for i in range(n):
  distance[i][i] = 0
  hops[i][i] = (0,0)

dst = [ [] for i in range(n) ]
for i in range(m):
  a,b,c = inm()
  if c>l:
    continue
  a -= 1
  b -= 1
  distance[a][b] = distance[b][a] = c
  dst[a].append(b)
  dst[b].append(a)

for i in range(n):
  #for j in range(n):
  #  if j==i:
  #    continue
  #  if hops[i][j] > hops[j][i]:
  #    hops[i][j] = hops[j][i]

  #q = deque([ (x,(0,distance[i][x])) for x in dst[i] ])
  q = [ ((0,distance[i][x]), x) for x in dst[i] ]
  heapq.heapify(q)
  while len(q)>0:
    #y,e = q.popleft()
    e,y = heapq.heappop(q)
    #ddprint("y {} e {} {}".format(y,e[0],e[1]))
    if e>=hops[i][y]:
      continue
    #ddprint("upd i {} y {}".format(i,y))
    hops[i][y] = e
    for f in dst[y]:
      ds = distance[y][f]
      #ddprint("y {} f {} ds {}".format(y,f,ds))
      if e[1]+ds > l:
        newd = (e[0]+1, ds)
      else:
        newd = (e[0], e[1]+ds)
      if newd < hops[i][f]:
        heapq.heappush(q,(newd,f))
        #q.append((f,newd))

if DBG:
  for i in range(n):
    print(hops[i])

B2 = BIG//2
#for i in range(n):
#  for j in range(n):
#    if hops[i][j][0] > B2:
#      hops[i][j] = (-1,0)

p = inn()
for i in range(p):
  s,t = inm()
  #ddprint("q {} s {} t {}".format(i,s,t))
  x = hops[s-1][t-1][0]
  print(x if x<B2 else -1)


### FIXED CODE ###

import sys
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
BIG = 9999999999

def ddprint(x):
  if DBG:
    print(x)

def ws(dist):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j],
                              dist[i][k]+dist[k][j])

n,m,l = inm()
dst = [ [] for i in range(n) ]
for i in range(m):
    a,b,c = inm()
    dst[a-1].append((b-1,c))
    dst[b-1].append((a-1,c))

dist1 = [ [BIG]*n for i in range(n) ]
for i in range(n):
    dist1[i][i] = 0
    for j,c in dst[i]:
        dist1[i][j] = c

ws(dist1)

dist2 = [ [BIG]*n for i in range(n) ]
for i in range(n):
    dist2[i][i] = 0
    for j in range(n):
        if dist1[i][j] <= l:
            dist2[i][j] = 1

ws(dist2)

q = inn()
for i in range(q):
    s,t = inm()
    d = dist2[s-1][t-1]
    print(d-1 if d<BIG else -1)