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

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

mod = 10**9+7
N = 10**5+50
fac = [1]*(N+1)
finv = [1]*(N+1)
for i in range(N):
    fac[i+1] = fac[i] * (i+1) % mod
finv[-1] = pow(fac[-1], mod-2, mod)
for i in reversed(range(N)):
    finv[i] = finv[i+1] * (i+1) % mod

def cmb1(n, r, mod):
    if r <0 or r > n:
        return 0
    r = min(r, n-r)
    return fac[n] * finv[r] * finv[n-r] % mod

ans = 0
for i in range(n*m-1):
    xi, yi = divmod(i, m)
    for j in range(i, n*m):
        xj, yj = divmod(j, m)
        d = abs(xi-xj)+abs(yi-yj)
        ans += d
        #ans += d*cmb1(n*m-2, k-2, mod)
ans *= cmb1(n*m-2, k-2, mod)
ans %= mod
print(ans)


### FIXED CODE ###

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

mod = 10**9+7
N = 2*10**5+50
fac = [1]*(N+1)
finv = [1]*(N+1)
for i in range(N):
    fac[i+1] = fac[i] * (i+1) % mod
finv[-1] = pow(fac[-1], mod-2, mod)
for i in reversed(range(N)):
    finv[i] = finv[i+1] * (i+1) % mod

def cmb1(n, r, mod):
    if r <0 or r > n:
        return 0
    r = min(r, n-r)
    return fac[n] * finv[r] * finv[n-r] % mod

ans = 0
for i in range(n*m):
    x, y = divmod(i, m)
    # x
    ans += x*m*cmb1(n*m-2, k-2, mod)*x
    ans -= (n-1-x)*m*cmb1(n*m-2, k-2, mod)*x
    # y
    ans += y*n*cmb1(n*m-2, k-2, mod)*y
    ans -= (m-1-y)*n*cmb1(n*m-2, k-2, mod)*y

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

import sys,queue,math,copy,itertools,bisect,collections
from heapq import *

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**3
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    P = LI()

    path = [[0] * N for _ in range(N)]
    seat = [[1] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            path[i][j] = min(min(i,N-1-i),min(j,N-1-j))

    ans = 0
    for a in P:
        i = (a-1) % N
        j = (a-1) // N
        ans += path[i][j]

        seat[i][j] = 0

        q = collections.deque()
        q.append((i,j,path[i][j]))
        while q:
            x,y,z = q.popleft()
            z += seat[x][y]
            for dx,dy in ((0,1),(1,0),(0,-1),(-1,0)):
                if 0 <= x+dx < N and 0 <= y+dy < N:
                    if path[x+dx][y+dy] > z:
                        path[x+dx][y+dy] = z
                        q.append((x+dx,y+dy,z))
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    P = LI()

    s = []
    for i in range(N):
        for j in range(N):
            s.append(min(i,N-1-i,j,N-1-j))

    r = [1] * (N*N)

    ans = 0
    q = []
    for p in P:
        p -= 1
        ans += s[p]
        r[p] = 0
        q.append(p)
        while q:
            a = q.pop()
            nc = s[a] + r[a]

            if a >= N:
                if s[a-N] > nc:
                    s[a-N] = nc
                    q.append(a-N)
            if a + N < N*N:
                if s[a+N] > nc:
                    s[a+N] = nc
                    q.append(a+N)
            if a % N:
                if s[a-1] > nc:
                    s[a-1] = nc
                    q.append(a-1)
            if a % N < N -1:
                if s[a+1] > nc:
                    s[a+1] = nc
                    q.append(a+1)

    print(ans)

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

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

def gcd(li):
    li.sort()
    for i in range(1,li[0]+1):
        for ii in li:
            if ii%i != 0:
                break
        else:
            gdc = i
    return(gdc)

x_list.append(X)
x_list.sort()

x_len = list()
for i in range(1,N+1):
    x_len.append(x_list[i]-x_list[i-1])

print(gcd(x_len))

### FIXED CODE ###

import fractions
import functools

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

x_list.append(X)
x_list.sort()

x_len = list()
for i in range(1,N+1):
    x_len.append(x_list[i]-x_list[i-1])

x_len.sort(reverse = True)

result = functools.reduce(fractions.gcd,x_len)

print(result)
### BUGGY CODE ###

import math
def make_divisors(n):
    divisors = []
    for i in range(1, int(math.sqrt(n))+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors 
def main():
    n = int(input())
    r = len(make_divisors(n-1)) - 1
    d = make_divisors(n)
    for i in d:
        if i == 1:
            continue
        if i == 2:
            r += 1
            continue
        t = n
        while True:
            if t % i == 0:
                t = t // i
            else:
                t = t - i
            if t == 1:
                r += 1
                break
            if t <= 0:
                break
    return r
print(main())


### FIXED CODE ###

import math
def make_divisors(n):
    divisors = []
    for i in range(1, int(math.sqrt(n))+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors 
def main():
    n = int(input())
    r = len(make_divisors(n-1)) - 1
    d = make_divisors(n)
    for i in d:
        if i == 1:
            continue
        if i == 2:
            r += 1
            continue
        t = n
        while t % i == 0:
            t = t // i
        t = t % i
        if t == 1:
            r += 1
    return r
print(main())
### BUGGY CODE ###

#https://atcoder.jp/contests/dp/tasks/dp_f
#2019-01-14
S = input()
T = input()

#初期化
dp = [[0 for i in range(len(T)+1)] for j in range(len(S)+1)]

#DP
for i in range(len(S)):
    for j in range(len(T)):
        dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j], dp[i][j] + (S[i] == T[j]))

st = []

x = len(S)
y = len(T)
while x > 0 and y > 0:
    if dp[x][y] == dp[x-1][y]: x -= 1
    elif dp[x][y] == dp[x][y-1]: y -= 1
    else: 
        x -= 1
        y -= 1
        st += S[x]
print("".join(reversed(st)))

### FIXED CODE ###

#https://atcoder.jp/contests/dp/tasks/dp_f
#2019-01-14
S = input()
T = input()

#初期化
dp = [[0 for i in range(len(T)+1)] for j in range(len(S)+1)]

#DP
for i in range(len(S)):
    for j in range(len(T)):
        dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j], dp[i][j] + (S[i] == T[j]))

st = []

x = len(S)
y = len(T)
while x > 0 and y > 0:
    if dp[x][y] == dp[x-1][y]: x -= 1
    elif dp[x][y] == dp[x][y-1]: y -= 1
    else: 
        x -= 1
        y -= 1
        st += S[x]
print("".join(reversed(st)))
### BUGGY CODE ###

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]

MOD = 10 ** 9 + 7

list = [0] * N

for i in range(N):
    if i == 0:
        if (i + 1) in a:
            list[i] = 0
        else:
            list[i] = 1
    elif i == 1:
        if (i + 1) in a:
            list[i] = 0
        elif i in a:
            list[i] = 1
        else:
            list[i] = 2
    else:
        if (i + 1) in a:
            list[i] = 0
        else:
            list[i] = (list[i - 1] + list[i - 2]) % MOD
            
ans = list[N - 1]
print(ans)

### FIXED CODE ###

import sys
N, M = map(int, sys.stdin.readline().split())
a = [int(sys.stdin.readline()) for _ in range(M)]

MOD = 10 ** 9 + 7

list = [0] * N

if M > 0:
    j = 0
    for i in range(N):
        if i == 0:
            if a[j] == 1:
                list[i] = 0
            else:
                list[i] = 1
        elif i == 1:
            if a[j] == 2:
                list[i] = 0
            elif a[0] == 1:
                list[i] = 1
            else:
                list[i] = 2
        else:
            if a[j] == i + 1:
                list[i] = 0
            else:
                list[i] = (list[i - 1] + list[i - 2]) % MOD
        if i + 1 == a[j] and j < M - 1:
            j += 1

else:
    for i in range(N):
        if i == 0:
            list[i] = 1
        elif i == 1:
            list[i] = 2
        else:
            list[i] = (list[i - 1] + list[i - 2]) % MOD
            
ans = list[N - 1]
print(ans)
### BUGGY CODE ###

from sys import stdin

N = int(stdin.readline())
A = [None]*N
B = [None]*N
for i in range(N):
    A[i], B[i] = map(int, stdin.readline().split())

now = 0

for i in range(N):
    job = B.index(min(B))
    now += A.pop(job)
    deadline = B.pop(job)
    if now > deadline:
        print("No")
        quit()
else:
    print("Yes")

### FIXED CODE ###

from sys import stdin

N = int(stdin.readline())
Job = [None]*N
for i in range(N):
    Job[i] = tuple(map(int, stdin.readline().split()))[::-1]

Job.sort()

Now = 0
for i in range(N):
    Deadline = Job[i][0]
    Now += Job[i][1]
    if Now > Deadline:
        print("No")
        quit()

else:
    print("Yes")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
n, q = map(int, input().split())

edge = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    edge[a].append(b)
    edge[b].append(a)

imos = [0 for i in range(n)]
for i in range(q):
    p, x = map(int, input().split())
    p -= 1
    imos[p] += x

def dfs(v, p):
    for u in edge[v]:
        if u != p:
            imos[u] += imos[v]
            dfs(u, v)

dfs(0, -1)
print(' '.join([str(x) for x in imos]))


### FIXED CODE ###

from collections import deque

n, q = map(int, input().split())
edge = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    edge[a].append(b)
    edge[b].append(a)

imos = [0 for _ in range(n)]
for i in range(q):
    p, x = map(int, input().split())
    p -= 1
    imos[p] += x

dq = deque([(0, -1)])
while dq:
    v, p = dq.popleft()
    for u in edge[v]:
        if u == p:
            continue
        imos[u] += imos[v]
        dq.append((u, v))

print(' '.join([str(x) for x in imos]))
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
A = [a for a in A if a <K]
N = len(A)
dp = [1] + [0]*K
dp2 = [1] + [0]*K
dpm = [[1] + [0]*K for _ in range(N+1)]
for i, a in enumerate(A):
    for j in range(K-1, 0, -1):
        if j-a>=0:
            dp[j] = dp[j] + dp[j-a]
    dpm[i+1][-1] = dp[-1]
    for j in range(K-1, -1, -1):
        dpm[i+1][j] = dp[j] + dpm[i+1][j+1]

r = 0
for i, a in enumerate(A[::-1]):
#    print(i, N-i-1, a)
    for j in range(K-1, -1, -1):
        # 後ろiこの合計がjのもの
#        print("bb", i, j, K-j-a, K-j)
        if dp2[j] > 0:
            # K-j > x >= K-j-a
            if dpm[N-i-1][max(0, K-j-a)] > dpm[N-i-1][K-j]:
                break
    else:
        r += 1
    for j in range(K-1, 0, -1):
        if j-a>=0:
            dp2[j] = dp2[j] + dp2[j-a]
#        print("aa", i, N-i-1)
print(r)


### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
A = [a for a in A if a <K]
N = len(A)
#dpm = [+1) for _ in range(N+1)]
dpm = [0]*(N+1)
dpm[0] = 1<<(K-1)
for i, a in enumerate(A):
    dpm[i+1] = dpm[i] | (dpm[i] >> a)

r = 0
dp2 = 1
for i, a in enumerate(A[::-1]):
    for j in range(a):
        if dp2 & dpm[N-i-1]:
            break
        dpm[N-i-1] >>= 1
    else:
        r += 1
    dp2 |= dp2<<a
    dp2 &= (1<<K)-1
print(r)
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0
for i in range(n-2):
  for j in range(i+1, n-1):
    if s[i] != s[j]:
      for k in range(j+1, n):
        if s[j] != s[k] and s[k]!= s[i]:
          if j-i != k-j:
            ans +=1
print(ans)

### FIXED CODE ###

import statistics as st
n = int(input())
s = input()
NGs = 0
r = set()
g = set()
b = set()
for i in range(n):
  if s[i] == "R":
    r.add(i)
  elif s[i] == "G":
    g.add(i)
  else:
    b.add(i)
for i in range(n-2):
  for d in range((n-i-1)//2+1):
    j = i+d
    k = j+d
    if i in r and j in g and k in b:
      NGs += 1
    elif i in r and j in b and k in g:
      NGs += 1
    elif i in g and j in r and k in b:
      NGs += 1
    elif i in g and j in b and k in r:
      NGs += 1
    elif i in b and j in r and k in g:
      NGs += 1
    elif i in b and j in g and k in r:
      NGs += 1
print(len(r)*len(g)*len(b)-NGs)
### BUGGY CODE ###

N = int(input())
A = [list(map(lambda x:int(x)-1,input().split())) for i in range(N)]
B = [0]*N
S = 0
ans = 0
while True:
    C = [0]*N
    k=1
    while k!=0:
        k = 0
        for n in range(N):
            if C[n]==0 and B[n]!=N-1:
                b = A[n][B[n]]
                if C[b]==1:continue
                if A[b][B[b]]==n:
                    B[n]+=1
                    B[b]+=1
                    C[n]=1
                    C[b]=1
                    k=1
    if sum(C)==0:break
    ans +=1
print(ans if sum(B)==N*(N-1) else -1)

### FIXED CODE ###

import time
start = time.time()
N = int(input())
A = [list(map(lambda x:int(x)-1,input().split())) for i in range(N)]
B = [0]*N
S = 0
ans = 0
while True:
    C = [0]*N
    for n in range(N):
        if C[n]==0 and B[n]!=N-1:
            b = A[n][B[n]]
            if C[b]==1: continue
            if A[b][B[b]]==n:
                B[n]+=1
                B[b]+=1
                C[n],C[b]=1,1
    if sum(C)==0:break
    ans +=1
    if time.time()-start>1.7:
        print(N*(N-1)//2)
        exit()
print(ans if sum(B)==N*(N-1) else -1)
### BUGGY CODE ###

n = int(input())
Ratio = [list(map(int,input().split())) for _ in range(n)]
t,a = Ratio[0][0],Ratio[0][1]

for i in range(1,n):
    count = 1
    while True:
        if Ratio[i][0]*count >= t and Ratio[i][1]*count >= a:
            t,a = Ratio[i][0]*count,Ratio[i][1]*count
            break
        else:
            count += 1

print(t+a)

### FIXED CODE ###

n = int(input())
Ratio = [list(map(int,input().split())) for _ in range(n)]
t,a = 1,1

for i in range(n):
    x = max((t+Ratio[i][0]-1)//Ratio[i][0],(a+Ratio[i][1]-1)//Ratio[i][1])
    t,a = Ratio[i][0]*x,Ratio[i][1]*x
print(int(t+a))
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
from collections import Counter
a = list(map(int, input().split()))
c = Counter(a)
s = set()
for k,v in c.items():
    if v>=2:
        s.add(k)
        
a.sort()
tmp = set()

# while True:
#     v = a[0]
#     if v*2>a[-1]:
#         for item in a:
#             tmp.add(item)
#     tmp.add(v)
#     a = [item for item in a if item%v!=0]
#     if not a:
#         break

tmp = [a[0]]
for i in range(1, n):
    num = a[i]
#     for i in range(len(tmp)-1, -1, -1):
    for i in range(len(tmp)):
        item = tmp[i]
        if num%item==0:
            break
        if item*2>num:
            tmp.append(num)
            break
    else:
        tmp.append(num)
tmp = set(tmp) - s
print(len(tmp))

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
from collections import Counter
a = list(map(int, input().split()))
c = Counter(a)
s = set()
for k,v in c.items():
    if v>=2:
        s.add(k)
        
a.sort()
ok = set()
p = set(list(range(1, 10**6+1)))
ck = list(c.keys())
ck.sort()
for num in ck:
    if num in p:
        ok.add(num)
    i = 2
    while num*i<=10**6:
        if num*i in p:
            p.remove(num*i)
        i += 1
tmp = ok
tmp = set(tmp) - s
print(len(tmp))
### BUGGY CODE ###

N, M, Q = map(int, input().split())
tL = []
tR = []
for i in range(M):
    a, b = map(int, input().split())
    tL.append(a)
    tR.append(b)
ql = []
qr = []
for j in range(Q):
    c, d = map(int, input().split())
    ql.append(c)
    qr.append(d)

for j in range(Q):
    count = 0
    for i in range(M):
        if ql[j] <= tL[i] and tR[i] <= qr[j]:
            count += 1
    print(count)

### FIXED CODE ###

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

G = [[0]*(N+1) for _ in range(N+1)]

for _ in range(M):
  L, R = map(int, input().split())
  G[L][R] += 1

for i in range(N+1):
  for j in range(1, N+1):
    G[i][j] += G[i][j-1]

for _ in range(Q):
  p, q = map(int, input().split())
  ans = 0
  for i in range(p, q+1):
    ans += G[i][q]
  print(ans)
### BUGGY CODE ###


from collections import defaultdict
import math
n=int(input())
d=defaultdict(int)

if n>2:
    for l in range(1,n):
        for i in range(1,l-1):
            for j in range(1,l-i):
                k=l-i-j
                N=i*i+j*j+k*k+i*j+j*k+k*i
                d[N]+=1
for i in range(1,n+1):
    print(d[i])

### FIXED CODE ###

from collections import defaultdict
import math
n=int(input())
d=defaultdict(int)

if n>2:
    m=int(math.sqrt(n))
    for k in range(1,m):
        for i in range(1,m):
            for j in range(1,m):
                N=i*i+j*j+k*k+i*j+j*k+k*i
                d[N]+=1
for i in range(1,n+1):
    print(d[i])
### BUGGY CODE ###

N=int(input())
L=list(map(int,input().split()))
Q=int(input())
for i in range(Q):
  A,B=map(int,input().split())
  R=[B for K in L if K==A]
  L=[i for i in L if i!=A]
  L.extend(R)
  print(sum(L))

### FIXED CODE ###

import sys
input = sys.stdin.readline 
N=int(input())
L=list(map(int,input().split()))
Q=int(input())
R=[0]*(10**5)
for i in L:
  R[i-1]+=1
ans=sum(L)
for i in range(Q):
  a,b=map(int,input().split())
  R[b-1]+=R[a-1]
  ans+=(b-a)*R[a-1]
  R[a-1]=0
  print(ans)
### BUGGY CODE ###

a,b,k=map(int,input().split())

for i in range(a,b+1):
    if i<=a+k-1 or i>=b-k+1 :
        print(i)


### FIXED CODE ###

a,b,k=map(int,input().split())

st=a
while st<=min(a+k-1,b) :
    print(st)
    st+=1
st=max(st,b-k+1)
while st<=b :
    print(st)
    st+=1
### BUGGY CODE ###

n = int(input())
S = [int(s) for s in input().split()]
q = int(input())
T = [int(s) for s in input().split()]

print(sum([t in S for t in T]))

### FIXED CODE ###

def binarySearch(t):
	left,right = 0,n
	while right > left+1:
		mid = (left+right) // 2
		if S[mid] == t:
			return True
		elif S[mid] > t:
			right = mid
		else:
			left = mid
	return False

n = int(input())
S = [int(s) for s in input().split()]
q = int(input())
T = [int(s) for s in input().split()]

print(sum([binarySearch(t) for t in T]))
### BUGGY CODE ###

a,b=map(int,input().split())
s=input()
for i in range(b):
  x,y=map(int,input().split())
  print(s[x-1:y].count('AC'))

### FIXED CODE ###

import itertools

n,q=map(int,input().split())
s=input()
lst=[0]*(n-1)

for i in range(n-1):
  if s[i:i+2]=='AC':
    lst[i]+=1
    
lst=list(itertools.accumulate(lst))
lst=[0]+lst

for i in range(q):
  s,t=map(int,input().split())
  print(lst[t-1]-lst[s-1])
### BUGGY CODE ###

def main():
  h,*s=open(0)
  h,w,k=map(int,h.split())
  s=[list(map(int,t[:w]))for t in s]
  m=9e9
  for i in range(1<<h-1):
    t,v,l=[],0,1
    for j in range(h):
      if i>>j&1:
        t+=j+1,
        l+=1
    t+=h,
    c=[0]*l
    for i in range(w):
      b=f=g=0
      u=[]
      for j,x in enumerate(t):
        d,b=sum(s[j][i]for j in range(b,x)),x
        u+=d,
        if d>k:
          g=1
          break
        c[j]+=d
        f|=c[j]>k
      else:
        if f:
          c=u
          v+=1
      if g:break
    else:
      if v+l-1<m:m=v+l-1
  print(m)
main()

### FIXED CODE ###

h,*s=open(0)
h,w,k=map(int,h.split())
s=[list(map(int,t[:w]))for t in s]
m=9e9
for i in range(1<<h-1):
  t=[]
  b=v=l=0
  for j in range(h):
    if i>>j&1:
      t+=s[b:j+1],
      b=j+1
      l+=1
  t+=s[b:],
  l+=1
  c=[0]*l
  for i in range(w):
    f=g=0
    u=[]
    for j in range(l):
      d=sum(t[i]for t in t[j])
      u+=d,
      if d>k:
        g=1
        break
      c[j]+=d
      f|=c[j]>k
    else:
      v+=f
      if f:c=u
    if g:break
  else:m=min(m,v+l-1)
print(m)
### BUGGY CODE ###

import math
N,K = map(int,input().split())
A = list(map(int,input().split()))
for j in range(min(K,int(2*(math.log2(N)))+1)):
	B = [0]*N
	for i in range(N):
		l = max(0,i-A[i])
		r = min(N-1,i+A[i])
		B[l] += 1
		if r < N-1:
			B[r+1] -= 1
	for i in range(1,N):
		B[i] += B[i-1]
	A = B
print(' '.join(map(str,A)))


### FIXED CODE ###

import math
N,K = map(int,input().split())
A = list(map(int,input().split()))
for j in range(min(K,50)):
	B = [0]*N
	for i in range(N):
		l = max(0,i-A[i])
		r = min(N-1,i+A[i])
		B[l] += 1
		if r < N-1:
			B[r+1] -= 1
	for i in range(1,N):
		B[i] += B[i-1]
	A = B
print(' '.join(map(str,A)))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))
Li = 0
Ri = len(x) - 1
while Li + 1 < Ri:
    i = (Li + Ri) // 2
    xi = x[i]
    a1 = [(ak > xi) * 2 - 1 for ak in a]
    lr = []
    s = 0
    M = 0
    for a1k in a1:
        s += a1k
        lr += [s]
        M += (s >= 0) * 2 - 1
    for l in range(1, n):
        for r in range(l, n):
            lr[r] -= lr[l - 1]
            M += (lr[r] >= 0) * 2 - 1
    if M >= 0:
        Li = i
    else:
        Ri = i
print(x[Ri])


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))
n_sub = n * (n + 1) // 2
Li = 0
Ri = len(x)
while Ri > Li + 1:
    i = (Li + Ri) // 2
    xi = x[i]
    UorD = [1 if ak >= xi else -1 for ak in a]
    cnt_sum = [0] * (2 * n + 1)
    cumsum = 0
    cnt_sum[cumsum + n] = 1
    judge = 0
    s = 0
    for uk in UorD:
        cumsum += uk
        if uk == 1:
            s += cnt_sum[cumsum + n] + 1
        else:
            s -= cnt_sum[cumsum + n + 1] - 1
        cnt_sum[cumsum + n] += 1
        judge += s
        if judge >= n_sub // 2:
            Li = i
            break
    else:
        Ri = i
print(x[Li])
### BUGGY CODE ###


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

sys.setrecursionlimit(100000)
input = sys.stdin.readline


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


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

def warshall_floyd(g):
    d = g
    N = len(g)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


def slv(N, M, L, ABC, Q, ST):
    g = [[sys.maxsize]*(N) for _ in range(N)]
    for a, b, c in ABC:
        g[a-1][b-1] = c
        g[b-1][a-1] = c
    
    d = warshall_floyd(g)
    gg = [[sys.maxsize]*(N) for _ in range(N)]
    for u in range(N):
        for v in range(N):
            if d[u][v] <= L:
                gg[u][v] = 1
    dd = warshall_floyd(gg)

    for s, t in ST:
        d = dd[s-1][t-1]
        if d != sys.maxsize:
            print(d-1)
        else:
            print(-1)



def main():
    N, M, L = read_int_n()
    ABC = [read_int_n() for _ in range(M)]
    Q = read_int()
    ST = [read_int_n() for _ in range(Q)]
    (slv(N, M, L, ABC, Q, ST))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def slove():
    import sys
    input = sys.stdin.readline
    n, m, l = list(map(int, input().rstrip('\n').split()))
    INF = 10 ** 11
    w = [[INF] * n for _ in range(n)]
    wl = [[INF] * n for _ in range(n)]

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

    for i in range(m):
        a, b, c = list(map(int, input().rstrip('\n').split()))
        if c <= l:
            w[a - 1][b - 1] = c
            w[b - 1][a - 1] = c

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

    for i in range(n):
        for j in range(n):
            if w[i][j] <= l:
                wl[i][j] = 1
    for i in range(n):
        for j in range(n):
            for k in range(n):
                wl[j][k] = min(wl[j][k], wl[j][i] + wl[i][k])

    q = int(input().rstrip('\n'))
    for i in range(q):
        s, t = list(map(int, input().rstrip('\n').split()))
        if wl[s-1][t-1] == INF:
            print(-1)
        else:
            print(wl[s-1][t-1] - 1)


if __name__ == '__main__':
    slove()