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

def main():
    from bisect import bisect_left
    I=10**9+1
    n,q,*t=map(int,open(0).read().split())
    d=tuple(t[-q:])
    t=t[:-q]
    N0=2**(q-1).bit_length()
    data=[I]*2*N0
    for x,l,r in sorted(((x,bisect_left(d,s-x)+N0,bisect_left(d,t-x)+N0)for s,t,x in zip(t[::3],t[1::3],t[2::3])),reverse=1):
        while l<r:
            if r%2:
                r-=1
                data[r-1]=x
            if l%2:
                data[l-1]=x
                l+=1
            l//=2
            r//=2
    a=[]
    for k in range(N0-1,q+N0-1):
        s=I
        while~k:
            if data[k]<s:s=data[k]
            k=(k-1)//2
        a.append(-(s==I)or s)
    print('\n'.join(map(str,a)))
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    from bisect import bisect_left
    def update(l,r,v):
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=v
            if L&1:
                data[L-1]=v
                L+=1
            L>>=1
            R>>=1
    def query(k):
        k+=N0-1
        s=10**18
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        return s
    n,*t=open(0)
    n,q=map(int,n.split())
    d=[-10**18]+list(map(int,t[n:]))+[10**18]
    N0=2**(q+1).bit_length()
    data=[10**18]*2*N0
    for x,t,s in sorted(list(map(int,t.split()))[::-1]for t in t[:n])[::-1]:
        l=bisect_left(d,s-x)
        r=bisect_left(d,t-x)
        update(l,r,x)
    for i in range(q):
        a=query(i+1)
        print(-(a==10**18)or a)
if __name__=='__main__':
    main()
### BUGGY CODE ###

a = int(input())
b = input()

def func(c):
    x = c.count("1")
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        nsum += n * int(c[i])
        if n > x:
            n = n % x
        if n == 0:
            break
        n *= 2
    nsum %= x
    cans = bin(nsum).count("1")
    if cans == 0:
        return 1
    else:
        return 1 + func(bin(nsum)[2:])

for i in range(a):
    s = list(b)
    s[i] = "0" if s[i] == "1" else "1"
    print(str(func("".join(s))))

### FIXED CODE ###

from functools import lru_cache


a = int(input())
b = input()
X = b.count("1")
ans1 = []
ans2 = []

@lru_cache(maxsize=None)
def func1(c):
    x = X + 1
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        ans1.append(n)
        nsum += n * int(c[i])
        n = n % x if n > x else n
        n *= 2
    return nsum
    
@lru_cache(maxsize=None)
def func2(c):
    x = X - 1
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        ans2.append(n)
        nsum += n * int(c[i])
        n = n % x if n > x else n
        n *= 2
    return nsum    

def func(c):
    x = c.count("1")
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        nsum += n * int(c[i])
        n = n % x if n > x else n
        if n == 0:
            break
        n *= 2
    nsum %= x
    cans = bin(nsum).count("1")
    if cans == 0:
        return 1
    else:
        return 1 + func(bin(nsum)[2:])
    
allans1 = func1(b)
allans2 = func2(b)
ans1 = ans1[::-1]
if allans2 == 0:
    ans2 = [0] * a
else:
    ans2 = ans2[::-1]

c = list(b)
for i in range(a):
    if c[i] == "0":
        ans = (allans1 + ans1[i]) % (X + 1)
        ans = func(bin(ans)[2:]) + 1
        print(str(ans))
    else:
        if allans2 - ans2[i] == 0 and X - 1 == 0:
            print("0")
        else:
            ans = (allans2 - ans2[i]) % (X - 1)
            ans = func(bin(ans)[2:]) + 1
            print(str(ans))
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp0 = [[0] * (k + 1)] * n
dp1 = [0] * n
for i in range(1, n):
    for j in range(k + 1):
        if j <= i and j != 0:
            dp0[i][j] = dp1[i - j] + abs(h[i] - h[i - j])
        else:
            dp0[i][j] = 10 ** 9
    dp1[i] = min(dp0[i])
print(dp1[n - 1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp0 = [[0] * (k + 1)] * n
dp1 = [0] * n
for i in range(1, n):
    for j in range(k + 1):
        if j <= i and j != 0:
            dp0[i][j] = dp1[i - j] + abs(h[i] - h[i - j])
        else:
            dp0[i][j] = 10 ** 9
    dp1[i] = min(dp0[i])
print(dp1[n - 1])
### BUGGY CODE ###

import numpy as np

N = int(input())
D = list(map(int, input().split()))
if N > 24:
    print(0)
    exit()

# 深さ優先探索で全通りを探索できるのでは curは０からスタート
def dfs(cur, times):
    global answer
    if cur == N:
        times.sort()
        arr = np.array(times)
        result = (arr[1:] - arr[:-1]).min()
        if result > answer:
            answer = result
    else:
        dfs(cur+1, times + [D[cur]])
        dfs(cur+1, times + [24-D[cur]])

answer = 0
dfs(0, [0, 24])
print(answer)


### FIXED CODE ###

import numpy as np

N = int(input())
D = list(map(int, input().split()))
if N > 23:
    print(0)
    exit()
for i in range(13):
    if D.count(i) >= 3:
        print(0)
        exit()
    elif D.count(i) == 2 and D.count(i+1) == 2:
        print(1)
        exit()

# 深さ優先探索で全通りを探索できるのでは curは０からスタート
def dfs(cur, times):
    global answer
    if cur == N:
        times.sort()
        arr = np.array(times)
        result = (arr[1:] - arr[:-1]).min()
        if result > answer:
            answer = result
    else:
        x = D[cur]
        dfs(cur+1, times + [x])
        dfs(cur+1, times + [24-x])

answer = 0
dfs(0, [0, 24])
print(answer)
### BUGGY CODE ###


def main():
    h, n = map(int, input().split())

    magics = []
    max_cost = 0
    for _ in range(n):
        at, cost = map(int, input().split())
        max_cost = max(max_cost, cost)
        magics.append((at, cost))

    dp = [float('inf')] * (h+max_cost)
    dp[0] = 0
    for i in range(len(dp)):
        for at, cost in magics:
            if at <= i:
                dp[i] = min(dp[i], dp[i-at] + cost)
    print(min(dp[h:]))

main()


### FIXED CODE ###

h, n = map(int, input().split())
magics = sorted(list(map(int, input().split())) for _ in range(n))
max_cost = max(magic[1] for magic in magics)

dp = [float('inf')] * (h+max_cost)
dp[0] = 0
for i in range(h+max_cost):
    for at, cost in magics:
        if at <= i:
            dp[i] = min(dp[i], dp[i-at] + cost)
        else:
            break
print(min(dp[h:]))
### BUGGY CODE ###

n,x,m = map(int,input().split())
set_a = set()
a = []
while len(a)<n:
    if x in a:break
    set_a.add(x)
    a.append(x)
    x = x**2%m

ans = sum(a[:min(n,len(a))])
n -= len(a)
if n<1:
    print(ans)
    exit()

i = a.index(x)
l = len(a)-i
ans += sum(a[i:]) * (n//l)
n %= l
ans += sum(a[i:i+n])
print(ans)



### FIXED CODE ###

n,x,m = map(int,input().split())
set_a = set()
a = []
while len(a)<n:
    if x in a:break
    set_a.add(x)
    a.append(x)
    x = x**2%m

ans = sum(a[:min(n,len(a))])
n -= len(a)
if n<1:
    print(ans)
    exit()

i = a.index(x)
l = len(a)-i
ans += sum(a[i:]) * (n//l)
n %= l
ans += sum(a[i:i+n])
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()

count=0
for i in range(1,N-2 +1):
    for j in range(i+1, N-1 +1):
        for k in range(j+1, N +1):
            if j-i != k-j and S[i-1]!=S[j-1]!=S[k-1]!=S[i-1]:
                count += 1
print(count)
                

### FIXED CODE ###


N=int(input())
S=input()

#(RGB)になる組み合わせをカウント
count= S.count("R")*S.count("G")*S.count("B")
count0=0

#条件を満たさないものを引いていく
for i in range(1,N-2 +1):
    for j in range(i+1,(N+i)//2 +1):
        k=2*j-i
        if S[k-1]!=S[i-1] and S[k-1]!=S[j-1] and S[i-1]!=S[j-1]:
            count0 += 1
print(count-count0)
### BUGGY CODE ###

N, M = map(int, input().split())
A = [int(i) for i in input().split()]

for _ in range(M) :
    B, C = map(int, input().split())
    A += [C] * B

print(sum(sorted(A)[-1:-N-1:-1]))

### FIXED CODE ###

N, M = map(int, input().split())
A = [[1, int(i)] for i in input().split()]
BC = A + [[int(i) for i in input().split()] for _ in range(M)]

BC.sort(key=lambda x: x[1], reverse=True)

i = 0
res = 0

for B, C in BC :
    if i + B <= N :
        res += C * B
        i += B
    else :
        res += C * (N - i)
        break

print(res)
### BUGGY CODE ###

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

ac = []
wa = {str(i): 0 for i in range(1, N + 1)}

for _ in range(M):
    p_i, s_i = input().split()
    if s_i == "AC":
        ac.append(p_i)
    elif s_i == "WA":
        if p_i not in ac:
            wa[p_i] += 1

ac = set(ac)
wa = {p_i: count for p_i, count in wa.items() if p_i in ac}

print(len(ac), sum(wa.values()))

### FIXED CODE ###

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

ac = 0
wa = 0
ac_status = [0 for i in range(N)]
wa_status = [0 for i in range(N)]

for _ in range(M):
    p_i, s_i = input().split()
    if s_i == "AC" and ac_status[int(p_i) - 1] == 0:
        ac += 1
        ac_status[int(p_i) - 1] += 1
        wa += wa_status[int(p_i) - 1]
    if s_i == "WA":
        wa_status[int(p_i) - 1] += 1

print(ac, wa)
### BUGGY CODE ###

import sys
inf=1000002
sys.setrecursionlimit(inf)
from collections import deque
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
c=[input() for i in range(h)]
dp=[[inf if c[i][j]=="." else -1 for j in range(w)] for i in range(h)]
now=deque()
now.append([x1-1,y1-1])
def bfs(d):
    global h,w,k,dp,now,x2,y2
    l=len(now)
    if l==0:
        return
    if dp[x2-1][y2-1]!=inf and dp[x2-1][y2-1]!=-1:
        return
    for i in range(l):
        x,y=now.popleft()
        for j in range(1,min(k+1,w-y)):
            if dp[x][y+j]==inf:
                dp[x][y+j]=d
                now.append([x,y+j])
            if dp[x][y+j]==-1:
                break
        for j in range(1,min(k+1,y+1)):
            if dp[x][y-j]==inf:
                dp[x][y-j]=d
                now.append([x,y-j])
            if dp[x][y-j]==-1:
                break
        for j in range(1,min(k+1,h-x)):
            if dp[x+j][y]==inf:
                dp[x+j][y]=d
                now.append([x+j,y])
            if dp[x+j][y]==-1:
                break
        for j in range(1,min(k+1,x+1)):
            if dp[x-j][y]==inf:
                dp[x-j][y]=d
                now.append([x-j,y])
            if dp[x-j][y]==-1:
                break
    bfs(d+1)
bfs(1)
print(dp[x2-1][y2-1] if dp[x2-1][y2-1]!=inf else -1)

### FIXED CODE ###

import sys
inf=1000002
sys.setrecursionlimit(inf)
from collections import deque
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
c=[input() for i in range(h)]
dp=[[inf if c[i][j]=="." else -1 for j in range(w)] for i in range(h)]
now=deque()
now.append([x1-1,y1-1])
dp[x1-1][y1-1]=0
#kの更新が遅い
def bfs(d):
    global h,w,k,dp,now,x2,y2
    l=len(now)
    if l==0:
        return
    dp_sub=deque()
    cand=set()
    for i in range(l):
        x,y=now.popleft()
        for j in range(1,min(k+1,w-y)):
            if dp[x][y+j]==inf:
                dp_sub.append([x,y+j,d])
                #dp[x][y+j]=d
                cand.add((x,y+j))
                #now.append([x,y+j])
            else:
                break
        for j in range(1,min(k+1,y+1)):
            if dp[x][y-j]==inf:
                dp_sub.append([x,y-j,d])
                #dp[x][y-j]=d
                cand.add((x,y-j))
                #now.append([x,y-j])
            else:
                break
        for j in range(1,min(k+1,h-x)):
            if dp[x+j][y]==inf:
                dp_sub.append([x+j,y,d])
                #dp[x+j][y]=d
                cand.add((x+j,y))
                #now.append([x+j,y])
            else:
                break
        for j in range(1,min(k+1,x+1)):
            if dp[x-j][y]==inf:
                dp_sub.append([x-j,y,d])
                #dp[x-j][y]=d
                cand.add((x-j,y))
                #now.append([x-j,y])
            else:
                break
    while dp_sub!=deque([]):
        e=dp_sub.popleft()
        dp[e[0]][e[1]]=e[2]
    for i in cand:
        now.append(i)
    bfs(d+1)
bfs(1)
print(dp[x2-1][y2-1] if dp[x2-1][y2-1]!=inf else -1)
### BUGGY CODE ###

n = int(input())
p = [int(i) for i in input().split()]
a = [0 for i in range(n)]
b = [0 for i in range(n)]

for i in range(n):
	a[p[i]-1] = i + 1
	b[p[i]-1] = i + 1
for i in range(1,n):
	d = min(a[i] - a[i-1],b[i-1] - b[i])
	if d <= 0:
		a[i] -= d - 1
		b[i] += d - 1
a = [str(i+1-min(a)) for i in a] 
b = [str(i+1-min(b)) for i in b]

print(" ".join(a))
print(" ".join(b))

### FIXED CODE ###

n = int(input())
p = [int(i) for i in raw_input().split()]
a = [0 for i in range(n)]
b = [0 for i in range(n)]
p.reverse()
for i in range(n):
	k = p.pop()
	a[k-1] = i + 1
	b[k-1] = i + 1
for i in range(1,n):
	d = min(a[i] - a[i-1],b[i-1] - b[i])
	if d <= 0:
		a[i] -= d - 1
		b[i] += d - 1
ma = min(a)
mb = min(b)
a = [str(i+1-ma) for i in a] 
b = [str(i+1-mb) for i in b]
print(" ".join(a))
print(" ".join(b))
### BUGGY CODE ###

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

answer="Yes"

for i in range(N):
    if i>=1:
        if max(H[:i])>H[i]+1:
            answer="No"
            break
        else:
            pass
print(answer)

### FIXED CODE ###

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

answer="Yes"

for i in range(1,N,):
    if H[N-i]>=H[N-i-1]:
        pass
    else:
        H[N-i-1]-=1
        if H[N-i]<H[N-i-1]:
            answer="No"

print(answer)
### BUGGY CODE ###

N,K = (int(i) for i in input().split())
li = [int(i) for i in input().split()]

li.sort()
max = li[-1]

while(len(li) > 1):
    v = li[0]
    for i in range(1, len(li)):
        li[i] = li[i]%v
    for _ in range(li.count(0)):
        li.remove(0)
    li.sort()

if K <= max:
    if K%li[0] == max%li[0]:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')


### FIXED CODE ###

N,K = (int(i) for i in input().split())
li = [int(i) for i in input().split()]

max = max(li)

b = min(li)
for a in li:
    while True:
        if a%b == 0:
            break
        tb = b
        b = a%b
        a = tb

if K <= max:
    if K%b == max%b:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')
### BUGGY CODE ###

s = str(input())
K = int(input())

str_list = set()
for i in range(len(s)+1):
    for j in range(i+1, len(s)+1):
        str_list.add(s[i:j])

str_list = list(str_list)
str_list.sort()
print(str_list[K-1])

### FIXED CODE ###

# C - K-th Substring

s = str(input())
K = int(input())

str_list = set()
for i in range(len(s)+1):
    for j in range(i+1, i+K+1):
        if j > len(s):
            break
        str_list.add(s[i:j])

str_list = list(str_list)
str_list.sort()
print(str_list[K-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    H, W, K = map(int, input().split())
    cake = [[0]*W for _ in range(H)]
    sb = []
    for y in range(H):
        s = input().strip()
        for x, c in enumerate(s):
            if c == "#":
                sb.append((y, x))

    for i, (y, x) in enumerate(sb):
        cake[y][x] = i+1

    for i, s in enumerate(sb):
        y = s[0]
        for x in range(1, W):
            if cake[y][x] == 0:
                cake[y][x] = cake[y][x-1]
        for x in range(W-2, -1, -1):
            if cake[y][x] == 0:
                cake[y][x] = cake[y][x+1]

    for y in range(1, H):
        for x in range(W):
            if cake[y][x] == 0:
                cake[y][x] = cake[y-1][x]
    for y in range(H-2, -1, -1):
        for x in range(W):
            if cake[y][x] == 0:
                cake[y][x] = cake[y+1][x]

    for c in cake:
        print(*c)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    H, W, K = map(int, input().split())
    cake = [[0]*W for _ in range(H)]
    sb = []
    for y in range(H):
        s = input().strip()
        for x, c in enumerate(s):
            if c == "#":
                sb.append((y, x))
    for i, (y, x) in enumerate(sb):
        cake[y][x] = i + 1

    for i, s in enumerate(sb):
        i += 1
        y = s[0]
        x0 = x1 = s[1]
        for x in range(s[1]-1, -1, -1):
            if cake[y][x] != 0:
                break
            cake[y][x] = i
            x0 = x
        for x in range(s[1]+1, W):
            if cake[y][x] != 0:
                break
            cake[y][x] = i
            x1 = x
        for y in range(s[0]-1, -1, -1):
            if cake[y][x0:x1+1].count(0) != x1-x0+1:
                break
            for x in range(x0, x1+1):
                cake[y][x] = i
        for y in range(s[0]+1, H):
            if cake[y][x0:x1+1].count(0) != x1-x0+1:
                break
            for x in range(x0, x1+1):
                cake[y][x] = i
    for c in cake:
        print(*c)


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

#! /usr/bin/env python3

import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())

m = map(int, read().split())
A, B = zip(*zip(m, m))
A = np.array(A[::-1])
B = np.array(B[::-1])

cnt = 0
for i in range(N):
    while A[i] % B[i] != 0:
        A[i:] += 1
        cnt += 1

print(cnt)


### FIXED CODE ###

#! /usr/bin/env python3

import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())

m = map(int, read().split())
A, B = zip(*zip(m, m))
A = np.array(A[::-1])
B = np.array(B[::-1])

cnt = 0
for i in range(N):
    acc = B[i] - A[i] % B[i] if A[i] % B[i] != 0 else 0
    A[i:] += acc
    cnt += acc

print(cnt)
### BUGGY CODE ###

n=int(input())
num=[int(i) for i in input().split()]

ans=1
s={num[0]}
st=set()
for i in range(1,n):
  #print(s)
  if set(list(range(1,num[i]))) & s == st:
    ans+=1
  s.add(num[i])
#print(set(list(range(8))))
print(ans)
  

### FIXED CODE ###

n=int(input())
num=[int(i) for i in input().split()]

ans=1
ch=num[0]
for i in range(1,n):
  if  num[i]<=ch:
    ans+=1
  ch=min(ch,num[i])
print(ans)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right
from operator import itemgetter
import sys
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    constructions = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        constructions[i] = (S, T, X)
    D = [int(input()) for _ in range(Q)]
    ans = [-1] * Q
    for S, T, X in constructions:
        l = bisect_left(D, S-X)
        r = bisect_right(D, T-X-1)
        for idx in range(l, r):
            if ans[idx] == -1 or ans[idx] > X:
                ans[idx] = X
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from bisect import bisect_left, bisect_right
from operator import itemgetter
import sys
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    constructions = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        constructions[i] = (S, T, X)
    constructions.sort(key=itemgetter(2))
    D = [int(input()) for _ in range(Q)]
    ans = [-1] * Q
    nxt = list(range(1, Q+1))
    for S, T, X in constructions:
        l = bisect_left(D, S-X)
        r = bisect_right(D, T-X-1)
        idx = l
        while idx < r:
            if ans[idx] == -1:
                ans[idx] = X
            nidx = nxt[idx]
            nxt[idx] = max(nxt[idx], r)
            idx = nidx
    for a in ans:
        print(a)


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

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

dp = [0] * (weights + 1)

while N:
    w, v = map(int, input().split())
    for i in range(weights, -1, -1):
        if i - w >= 0:
            dp[i] = max(dp[i], dp[i - w] + v)
    # print(dp)
    N -= 1
print(dp[-1])

### FIXED CODE ###

import numpy as np

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

# dp = [0] * (weights + 1)
dp = np.zeros(weights + 1, dtype=np.int64)

while N:
    w, v = map(int, input().split())
    np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])
    # for i in range(weights, -1, -1):
    #     if i - w >= 0:
    #         dp[i] = max(dp[i], dp[i - w] + v)
    # print(dp)
    N -= 1
print(dp[-1])
### BUGGY CODE ###

N,M,L = map(int, input().split())
RL=[list(map(int, input().split())) for _ in range(M)]
Q=int(input())
QL=[list(map(int, input().split())) for _ in range(Q)]
inf=float('inf')
fuel=[[inf]*N for _ in range(N)]
dist=[[inf]*N for _ in range(N)]
for i in range(N):
    fuel[i][i]=dist[i][i]=0
for I in RL:
    fuel[I[0]-1][I[1]-1]=fuel[I[1]-1][I[0]-1]=I[2]
for k in range(N):
    for i in range(N):
        for j in range(N):
            fuel[i][j]=min(fuel[i][j],fuel[i][k]+fuel[k][j])
for i in range(N):
    for j in range(N):
        if fuel[i][j] <= L:
            dist[i][j]=min(dist[i][j],1)
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])
for i in range(Q):
    print(dist[QL[i][0]-1][QL[i][1]-1]-1 if dist[QL[i][0]-1][QL[i][1]-1] != inf else -1)


### FIXED CODE ###

def w(d):
    n=len(d)
    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
N,M,L = map(int, input().split())
inf=float('inf')
fuel=[[inf]*N for _ in range(N)]
for i in range(N):
    fuel[i][i]=0
for _ in range(M):
    a,b,c=map(int,input().split())
    fuel[a-1][b-1]=fuel[b-1][a-1]=c
Q=int(input())
ST=[list(map(int, input().split())) for _ in range(Q)]
fuel = w(fuel)
for i in range(N):
    for j in range(N):
        if 0 < fuel[i][j] <= L:
            fuel[i][j]=1
        elif fuel[i][j] != 0:
            fuel[i][j] = inf
fuel = w(fuel)
for st in ST:
    print(fuel[st[0]-1][st[1]-1]-1 if fuel[st[0]-1][st[1]-1] != inf else -1)
### BUGGY CODE ###

def divisor_num(m):
    i = 1
    cnt = 0
    while i * i <= m:
        if m % i == 0:
            cnt += 2
            if i * i == m:
                cnt -= 1
        i += 1
    return cnt


n = int(input())
res = sum([i * divisor_num(i) for i in range(1, n+1)])
print(res)


### FIXED CODE ###

n = int(input())
board = [1] * (n+1)

def divisor_num(n, board):
    for i in range(2, n+1):
        j = 1
        while i*j <= n:
            board[i*j] += 1
            j += 1

divisor_num(n, board)
res = sum([i * board[i] for i in range(1, n+1)])
print(res)
### BUGGY CODE ###

N=int(input())
yakusu=[]
for c in range(1,N):
    for i in range(1,N-c+1):
        if (N-c)%i==0:
            yakusu.append(i)
print(len(yakusu))

### FIXED CODE ###

n = int(input())
ans = 0
for a in range(1, n):
  ans += (n - 1) // a
print(ans)
### BUGGY CODE ###


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

def gcd(a,b):
    if a < b:
        a, b = b, a
    while  a % b != 0:
        a, b = b, a % b
    return b
def lcm(c,d):
    return c*d // gcd(c,d)
# half all the array
A = set([a//2 for a in aa])
# calc lcm of all
LCM = 1
for each in A:
    LCM = lcm(LCM, each)
for each in A:
    if (LCM // each) % 2 == 0:
        print(0)
        break
else:
    print(m//LCM - m//(LCM*2))

### FIXED CODE ###


from functools import lru_cache
n, m = map(int, input().split())
aa = set(list(map(int, input().split())))

@lru_cache(maxsize=4095)
def gcd(a,b):
    if a < b:
        a, b = b, a
    while  a % b != 0:
        a, b = b, a % b
    return b
@lru_cache(maxsize=4095)
def lcm(c,d):
    return c*d // gcd(c,d)
# half all the array
A = set([a//2 for a in aa])
# calc lcm of all
LCM = 1
for each in A:
    LCM = lcm(LCM, each)
    if LCM > m:
        print(0)
        break
else:
    for each in A:
        if (LCM // each) % 2 == 0:
            print(0)
            break
    else:
        print(m//LCM - m//(LCM*2))
### BUGGY CODE ###

import math

n = int(input())
l0 = list(map(int, input().split()))
mini = max(l0) + 1
maxii = 0
for i in l0:
    if i != max(l0) and (abs(max(l0)/2 - i)) < mini:
        mini = max(l0)/2 - i
        maxii = i

print(max(l0), maxii)

### FIXED CODE ###

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

l0 = sorted(l0)
m = l0.pop()

mini = m + 1
maxii = 0
ans = 0
for i in range(len(l0)):
    if l0[i] < m/2:
        ipred = l0[i]
        continue
    if abs((m/2 - l0[i-1])) >= abs((m/2 - l0[i])):
        ans = m, l0[i]
    else:
        ans = m, l0[i-1]
    break

if not ans:
    print(m, ipred)
else:
    for i in ans:
        print(i, end=' ')