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

n, q = map(int, input().split())
*C, = map(int, input().split())
k = 2**19
S = [set()] * (2 * k - 1)
for i in range(n):
    S[k - 1 + i] = {C[i]}
for i in range(k - 1)[::-1]:
    S[i] = S[2 * i + 1] | S[2 * i + 2]


def ans(a=0, b=k, p=0):
    if b <= x or y <= a:
        return set()
    if x <= a and b <= y:
        return S[p]
    left = ans(a, (a + b) // 2, 2 * p + 1)
    right = ans((a + b) // 2, b, 2 * p + 2)
    return left | right


for _ in range(q):
    x, y = map(int, input().split())
    x -= 1
    print(len(ans()))


### FIXED CODE ###

import sys
input = sys.stdin.readline


class BIT:
    def __init__(self, n):
        self.array = [0] * (n + 1)
        self.size = n

    def sum(self, i):
        s = 0
        tmp = i
        while tmp > 0:
            s += self.array[tmp]
            tmp -= tmp & -tmp
        return s

    def add(self, i, x):
        tmp = i + 1
        while tmp <= self.size:
            self.array[tmp] += x
            tmp += tmp & -tmp


def main():
    n, q = map(int, input().split())
    *C, = map(lambda x: int(x) - 1, input().split())
    P = [0] * n
    N = [None] * n
    for i in range(n)[::-1]:
        if P[C[i]]:
            N[i] = P[C[i]]
        P[C[i]] = i
    F = [0] * n
    B = BIT(n)
    for i in range(n):
        if F[C[i]] == 0:
            B.add(i, 1)
            F[C[i]] = 1
    XY = [tuple(map(int, input().split())) for j in range(q)]
    ids = list(range(q))
    ids.sort(key=lambda j: XY[j][0])
    a = 0
    lst = [0] * q
    for j in ids:
        x, y = XY[j]
        for i in range(a, x - 1):
            if N[i]:
                B.add(N[i], 1)
        a = x - 1
        lst[j] = B.sum(y) - B.sum(x - 1)
    print(*lst, sep="\n")


main()
### BUGGY CODE ###

import copy
N, M, Q = [eval(v) for v in input().strip().split(" ")]

a_list, b_list, c_list, d_list = [], [], [], []

for k in range(Q):
    a, b, c, d = [eval(v) for v in input().strip().split(" ")]
    a_list.append(a)
    b_list.append(b)
    c_list.append(c)
    d_list.append(d)

max_value = 0

def calc_score(complete_A):
    score = 0
    for i in range(Q):
        if complete_A[b_list[i]] - complete_A[a_list[i]] == c_list[i]:
            score += d_list[i]
    return score

def search(A, M, depth, a_list, b_list, c_list, d_list, max_value, count):
    # print("%s: %s" % (depth, A))
    # count += 1
    # if count > 20:
    #     exit(0)
    if depth > 0:
        last_A = A[-1]
        for k in range(last_A, M + 1):
            next_A = copy.deepcopy(A)
            next_A.append(k)
            max_value = search(next_A, M, depth - 1, a_list, b_list, c_list, d_list, max_value, count)
    else:
        value = calc_score(A[1:])
        if value > max_value:
            max_value = value
    return max_value

count = 0
A = [1]
print(search(A, M, N + 1, a_list, b_list, c_list, d_list, max_value, count))

### FIXED CODE ###

# import copy
N, M, Q = [eval(v) for v in input().strip().split(" ")]

a_list, b_list, c_list, d_list = [], [], [], []

for k in range(Q):
    a, b, c, d = [eval(v) for v in input().strip().split(" ")]
    a_list.append(a)
    b_list.append(b)
    c_list.append(c)
    d_list.append(d)

max_value = 0

def calc_score(complete_A):
    score = 0
    for i in range(Q):
        if complete_A[b_list[i]] - complete_A[a_list[i]] == c_list[i]:
            score += d_list[i]
    return score

def search(A, M, depth, a_list, b_list, c_list, d_list, max_value, count):
    # print("%s: %s" % (depth, A))
    # count += 1
    # if count > 20:
    #     exit(0)
    if depth > 0:
        last_A = A[-1]
        for k in range(last_A, M + 1):
            # next_A = copy.deepcopy(A)
            # next_A.append(k)
            next_A = A + [k]
            max_value = search(next_A, M, depth - 1, a_list, b_list, c_list, d_list, max_value, count)
    else:
        value = calc_score(A[1:])
        if value > max_value:
            max_value = value
    return max_value

count = 0
A = [1]
print(search(A, M, N + 1, a_list, b_list, c_list, d_list, max_value, count))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
BC = [[int(x) for x in input().split()] for _ in range(M)]
BC = sorted(BC, reverse = True, key = lambda x:x[1])
BC = BC[:N]
for i in BC:
    B, C = i
    A += [C] * B
    A.sort()
    A = A[len(A) - N:]
print(sum(A[len(A) - N:]))

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
BC = [[int(x) for x in input().split()] for _ in range(M)]
BC = sorted(BC, reverse = True, key = lambda x:x[1])
N2 = N
D = []
for i in BC:
    temp = min(N2,i[0])
    D += [i[1]] * temp
    N2 -= temp
    if not N2:
        break
A += D
A.sort()
print(sum(A[len(A) - N:]))
### BUGGY CODE ###

N = int(input())
S = ["".join(sorted(input())) for _ in range(N)]

res = 0
for i in range(N):
    for j in range(i+1, N):
        if S[i] == S[j]:
            res += 1

print(res)


### FIXED CODE ###

N = int(input())
d = dict()

for _ in range(N):
    s = "".join(sorted(input()))
    if s in d:
        d[s] += 1
    else:
        d[s] = 0

print(int(sum(map(lambda x: (x+1)*x/2, d.values()))))
### BUGGY CODE ###

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

# Function of Combination mod M
# set n >= max p expected
M = 10**9+7


if k >= n-1:
    fac = [1]+[0]*(2*n-1)
    for i in range(1,2*n):
        fac[i] = fac[i-1]*i %M
        comb = lambda p,q:(fac[p]*pow(fac[q],M-2,M)*pow(fac[p-q],M-2,M))%M
    y = comb(2*n-1,n-1)
    
else:
    fac = [1]+[0]*n
    for i in range(1,n+1):
        fac[i] = fac[i-1]*i %M
        comb = lambda p,q:(fac[p]*pow(fac[q],M-2,M)*pow(fac[p-q],M-2,M))%M
    y = 1
    for i in range(1,k+1):
        y += (comb(n,i)*comb(n-1,n-1-i))%M
print(y%M)

### FIXED CODE ###

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

# Function of Combination mod M
# set n >= max p expected
M = 10**9+7


if k >= n-1:
    fac = [1]+[0]*(2*n-1)
    for i in range(1,2*n): fac[i] = fac[i-1]*i %M
    comb = lambda p,q:(fac[p]*pow(fac[q],M-2,M)*pow(fac[p-q],M-2,M))%M
    y = comb(2*n-1,n-1)
    
else:
    y = 1
    c1,c2=1,1
    for i in range(1,k+1):
        p = pow(i,M-2,M)
        c1 = c1*(n+1-i)*p%M
        c2 = c2*(n-i)*p%M
        y += c1*c2%M
        # y = (y+c1*c2)%M
print(y%M)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
    n = int(input())
    s = input().rstrip()
    dp = [0]*(n-1)
    ans = 0
    for i in range(1, n):
        for j in reversed(range(i)):
            if s[i] == s[j]:
                dp[j] = 1
                if 0 < j:
                    dp[j] += dp[j-1]
                if i-j < dp[j]:
                    dp[j] = i-j
                if ans < dp[j]:
                    ans = dp[j]
            else:
                dp[j] = 0
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

def check(x, N, S):
    candidate = set()
    for i in range(N - 2*x + 1):
        candidate.add(S[i:i+x])
        if S[i+x:i+2*x] in candidate:
            return True
    return False

def main():
    n = int(input())
    s = input().rstrip()
    l = 0
    r = n
    while l < r:
        mid = (l+r+1) // 2
        if check(mid, n, s):
            l = mid
        else:
            r = mid-1
    print((l+r+1)//2)

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

N = int(input())

A = []
a, *an = map(int, input().split())
A.append(a)
A += an
A.sort()

Node = []
score = 0
Node.append(A.pop())

#print(A)

for n in range(N - 1):
    score += Node.pop(0)
    num = A.pop()
    Node.append(num)
    Node.append(num)

#print(Node)
print(score)

### FIXED CODE ###

N = int(input())

A = []
a, *an = map(int, input().split())
A.append(a)
A += an
A.sort()

Node = []
score = 0
Node.append(A.pop())

#print(A)
start = 0

for n in range(N - 1):
    score += Node[start]
    num = A.pop()
    start += 1
    #Node = Node[1:]
    Node.append(num)
    Node.append(num)

#print(Node)
print(score)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = []

for i in range(1, n+1):
  b.append(a.index(i)+1)

print(' '.join(map(str, b)))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [0]*n

for i in range(n):
  b[a[i]-1] = i+1

print(' '.join(map(str, b)))
### BUGGY CODE ###

kosuu = int(input())
dp = list(map(int,input().split()))
ans = []
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
for i in range(kosuu):
	hako = kosuu - i
	if dp[hako-1] == 1:
		for j in make_divisors(hako)[:-1]:
			dp[j-1] ^= 1
		ans.append(hako)
print(len(ans))
finalans = ''
for i in ans[::-1]:
	finalans += str(i) + ' '
print(finalans[:-1])

### FIXED CODE ###

kosuu = int(input())
dp = list(map(int,input().split()))
ans = []
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return set((lower_divisors + upper_divisors[::-1])[:-1])
for i in range(kosuu):
	hako = kosuu - i
	if dp[hako-1] == 1:
		for j in make_divisors(hako):
			dp[j-1] ^= 1
		ans.append(str(hako))
print(len(ans))
print(' '.join(ans))
### BUGGY CODE ###

n = int(input())
m = 1

for i in range(1, 34):
  count = 2
  
  while i ** count <= n:
    m = max(m, i**count)
    count += 1
print(m)

### FIXED CODE ###

c = 1
a = int(input())
for i in range(1, int(a ** 0.5) + 1):
  for j in range(2, int(a/ 2)):
    if i ** j <= a:
      c = max(c, i**j)
print(c)
### BUGGY CODE ###

S = input()
Q = int(input())
sign = 1
for i in range(Q):
  T = list(map(str, input().split()))
  if T[0] == "1":
    sign *= -1
  else:
    F = int(T[1]) * 2 - 3
    if sign * F == 1:
      S = S[:] + T[2]
    else:
      S = T[2] + S[:]
if sign == 1:
  print(S)
else:
  N = len(S)
  for i in range(N):
    print(S[N-i-1], end = '')
  print()

### FIXED CODE ###

S = input()
N = len(S)
Q = int(input())
sign = 1
L = ["" for i in range(N + 2 * Q)]
for i in range(N):
  L[i+Q] = S[i]
x, y = Q - 1, N + Q
for i in range(Q):
  T = list(map(str, input().split()))
  if T[0] == "1":
    sign *= -1
  else:
    F = int(T[1]) * 2 - 3
    if sign * F == 1:
      L[y] = T[2]
      y += 1
    else:
      L[x] = T[2]
      x -= 1
newS = ""
for i in range(N+2*Q):
  newS = newS[:] + L[i]
if sign == 1:
  print(newS)
else:
  M = len(newS)
  for i in range(M):
    print(newS[M-i-1], end = '')
  print()
### BUGGY CODE ###

n=int(input())
list=[[0]*n]
list=input().split()
for i in range(n):
  list[i]=int(list[i])

yen=1000
stock=0
keikou=0
for i in range(1,n):
  if list[i]-list[i-1]<=0:
    keikou+=1
if keikou!=n-1:
  list2=sorted(list)
  list.index(list2[0])
  
  for t in range(1,n):
    if list[t]-list[t-1]>=0:
      while(yen>=list[t-1]):
        yen-=list[t-1]
        stock+=1
      while(stock>0):
        yen+=list[t]
        stock-=1
print(yen)


### FIXED CODE ###

n=int(input())
list=[[0]*n]
list=input().split()
for i in range(n):
  list[i]=int(list[i])

yen=1000
stock=0
keikou=0
for i in range(1,n):
  if list[i]-list[i-1]<=0:
    keikou+=1
if keikou!=n-1:
  for t in range(1,n):
    if list[t]-list[t-1]>=0:
      stock+=int(yen/list[t-1])
      yen-=list[t-1]*int(yen/list[t-1])
      yen+=list[t]*stock
      stock=0
print(yen)
### BUGGY CODE ###

h,w=map(int,input().split())
a=[list(map(int,input().split()))for i in range(h)]
b=[list(map(int,input().split()))for i in range(h)]
c=[[abs(a[i][j]-b[i][j])for j in range(w)]for i in range(h)]
d=[[set()for i in range(w+1)]for j in range(h+1)]
def f(x,y):
    if x==1 and y==1:
        d[1][1]=set([-c[0][0],c[0][0]])
    else:
        a=d[x-1][y]|d[x][y-1]
        e=set()
        for i in a:
            e.add(i-c[x-1][y-1])
            e.add(i+c[x-1][y-1])
        d[x][y]=e
    if x!=h:
        f(x+1,y)
    if y!=w:
        f(x,y+1)
f(1,1)
print(abs(min(d[h][w],key=abs)))

### FIXED CODE ###

h,w=map(int,input().split())
a=[list(map(int,input().split()))for i in range(h)]
b=[list(map(int,input().split()))for i in range(h)]
s=[0]*w
s[0]=p=1<<6400
for i in range(h):
    for j in range(w):
        d=abs(a[i][j]-b[i][j])
        if j>0:
            s[j]|=s[j-1]
        s[j]=(s[j]<<d)|(s[j]>>d)
t=s[-1]
for i in range(6401):
    if t&(p<<i) or t&(p>>i):
        print(i)
        break
### BUGGY CODE ###

import copy
siken_kazu=int(input())
junbido=[int(i) for i in input().split(" ")]
goukakudo=[int(i) for i in input().split(" ")]
yoyudo=[junbido[i]-goukakudo[i] for i in range(siken_kazu)]
shoki_yoyudo=copy.deepcopy(yoyudo)
k=0
if sum(junbido)<sum(goukakudo):
    k=-1
elif min(yoyudo)>=0:
    pass
else:
    while min(yoyudo)<0:
        a=max(yoyudo)
        for i in range(siken_kazu):
            if yoyudo[i]==a:
                kiroku=i
                break
        for i in range(siken_kazu):
            if yoyudo[kiroku]==0:
                break
            elif yoyudo[i]<0:
                if yoyudo[kiroku]>=-yoyudo[i]:
                    yoyudo[kiroku]-=-yoyudo[i]
                    yoyudo[i]=0
                elif yoyudo[kiroku]<-yoyudo[i]:
                    yoyudo[kiroku]=0
                    yoyudo[i]+=-yoyudo[kiroku]
for i in range(siken_kazu):
    if shoki_yoyudo[i]!=yoyudo[i]:
        k+=1
print(k)
    

### FIXED CODE ###

import copy
siken_kazu=int(input())
junbido=[int(i) for i in input().split(" ")]
goukakudo=[int(i) for i in input().split(" ")]
yoyudo=[junbido[i]-goukakudo[i] for i in range(siken_kazu)]
counter=0
shakkin=0
tyokin=0
if sum(junbido)<sum(goukakudo):
    counter=-1
else:
    for i in yoyudo:
        if i<0:
            counter+=1
            shakkin-=i
    yoyudo=sorted(yoyudo,reverse=True)
    for i in yoyudo:
        if tyokin>=shakkin:
            break
        else:
            tyokin+=i
            counter+=1
print(counter)
### BUGGY CODE ###

from collections import Counter
n=int(input())
wl=[]
for i in range(n):
    w=input()
    wl.append(w)
wl2=Counter(wl)
ans=[]
for i in range(len(wl2)):
    if wl2.most_common()[i][1]==wl2.most_common()[0][1]:
        ans.append(wl2.most_common()[i][0])
ans.sort()
for i in range(len(ans)):
    print(ans[i])


### FIXED CODE ###

n=int(input())
wl={}
for i in range(n):
    w=input()
    if w not in wl:
        wl[w]=0
    wl[w]+=1
wm=max(wl.values())
wl3=sorted(wl.items())
for i in range(len(wl3)):
    if wl3[i][1]==wm:
        print(wl3[i][0])
### BUGGY CODE ###

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

sorted_num = sorted(nums)

res = 1
for i in range(sorted_num[1], 0, -1):
    nums_div_i = [num % i for num in nums]

    _len = len(tuple(filter(lambda x: x > 0, nums_div_i)))
    if _len == 1 or not _len:
        res = i
        break

print(res)


### FIXED CODE ###

#!/snap/bin/pypy3
def gcd(a, b):
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)


def main():
    N = int(input())
    nums = list(map(int, input().split()))

    L = [0 for _ in range(N + 1)]
    R = [0 for _ in range(N + 1)]

    for i, num in enumerate(nums):
        L[i + 1] = gcd(L[i], num)

    for i in range(N - 2, -1, -1):
        R[i] = gcd(R[i + 1], nums[i + 1])

    print(max(gcd(L[i], R[i]) for i in range(N)))


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

import numpy as np
n = int(input())
v = np.array(list(map(int,input().split()))) 
c = np.array(list(map(int,input().split())))
ans = -(1<<60)
for i in range(2**n):
    temp = (bin(i)[2:]).zfill(n)
    temp = np.array(list(map(int, temp)))
    X = np.dot(temp, v)
    Y = np.dot(temp,c)
    ans = max(ans,X-Y)
print(ans)

### FIXED CODE ###

import numpy as np
n = int(input())
v = list(map(int,input().split())) 
c = list(map(int,input().split()))
ans = 0
for i in range(n):
    if v[i]-c[i]>=0:
        ans += v[i]-c[i]
print(ans)
### BUGGY CODE ###

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

x = 0
y = 0
comb = 1
mod = 10**9+7
for i in range(min(K-2, N*M-K)):
    comb *= (N*M-2-i)
for i in range(min(K-2, N*M-K)):
    comb //= i+1
    
comb %= mod
for d in range(1, N):
    x += d*(N-d)*M**2
for d in range(1, M):
    y += d*(M-d)*N**2
    
ans = x+y
ans %= mod
    
print((ans*comb)%mod)

### FIXED CODE ###

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

mod = 10**9+7
a = 1
b = 1
for i in range(min(K-2, N*M-K)):
    a *= (N*M-2-i)
    a %= mod
    b *= i+1
    b %= mod
comb = a * pow(b, mod - 2, mod) % mod

ans = (((N*N*(N+1)//2-N*(N+1)*(2*N+1)//6)*M**2 + (M*M*(M+1)//2-M*(M+1)*(2*M+1)//6)*N**2)*comb)%mod
print(ans)
### BUGGY CODE ###

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# dp[i+1][j] i番目までの魔法を使ってモンスターへの攻撃jにする魔力の最小値
# (j=0の時まだ攻撃していない)
H, N = lr()
INF = 10 ** 10
dp = [INF] * (H+10**4+10)
dp[0] = 0
for i in range(N):
    a, b = lr()
    for j in range(a, H+a+1):
        if dp[j-a] == INF:
            continue
        dp[j] = min(dp[j], dp[j-a] + b)

answer = min(dp[H:])
print(answer)


### FIXED CODE ###

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# dp[i+1][j] i番目までの魔法を使ってモンスターへの攻撃jにする魔力の最小値
# (j=0の時まだ攻撃していない)
H, N = lr()
INF = 10 ** 10
dp = [INF] * (H+10**4+10)
dp[0] = 0
for i in range(N):
    a, b = lr()
    for j in range(a, H+a+1):
        if dp[j-a] == INF:
            continue
        dp[j] = min(dp[j], dp[j-a] + b)

answer = min(dp[H:])
print(answer)
### BUGGY CODE ###

N, W = list(map(int, input().split()))
wvList = [map(int, input().split()) for _ in range(N)]

DP = [0] * (W + 1)
for w, v in wvList:
    for rj in range(W, w - 1, -1):
        num = DP[rj - w] + v
        if num > DP[rj]:
            DP[rj] = num

print(max(DP))


### FIXED CODE ###

import sys

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

ans = 0
DP = [0] * (W + 1)
for i in range(N):
    dp = []
    w, v = map(int, sys.stdin.readline().split())
    for j, element in enumerate(DP):
        if j >= w:
            dp.append(DP[j - w] + v if element < DP[j - w] + v else element)
        else:
            dp.append(element)
    DP = dp

print(max(DP))
### BUGGY CODE ###

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

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

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
cnt = [0] * N
for i in range(1, N):
    if S[i-1:i+1] == 'AC':
        cnt[i] = cnt[i-1] + 1
    else:
        cnt[i] = cnt[i-1]

ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(cnt[r-1] - cnt[l-1])

print('\n'.join(list(map(str, ans))))
### BUGGY CODE ###

N = int(input())
A = [int(s) for s in input().split()]
B = [int(s) for s in input().split()]
C = [int(s) for s in input().split()]
A.sort()
B.sort()
C.sort()
def isOK(lis,index,key):
    if lis[index] > key:
        return True
    else:
        return False

def binary_search(lis,key):
    ng = -1
    ok = len(lis)

    while(abs(ok-ng)>1):
        mid = int((ok+ng)/2)
        if isOK(lis,mid,key):
            ok = mid
        else:
            ng = mid
    return ok

ans = 0
lis = []
for i in range(N):
    b_index = binary_search(B,A[i])
    lis.extend(B[b_index:len(B)])
for b in lis:
    c_index = binary_search(C,b)
    ans += len(C) - c_index
print(ans)

### FIXED CODE ###

N = int(input())
A = [int(s) for s in input().split()]
B = [int(s) for s in input().split()]
C = [int(s) for s in input().split()]
A.sort()
B.sort()
C.sort()
def isOK(lis,index,key):
    if lis[index] > key:
        return True
    else:
        return False

def binary_search(lis,key):
    ng = -1
    ok = len(lis)

    while(abs(ok-ng)>1):
        mid = int((ok+ng)/2)
        if isOK(lis,mid,key):
            ok = mid
        else:
            ng = mid
    return ok

count = 0
count_lis = []
for b in B[::-1]:
    b_index = binary_search(C,b)
    if b_index != N:
        count += N - b_index
    count_lis.append(count)

count_lis = count_lis[::-1]
ans = 0
for a in A:
    a_index = binary_search(B,a)
    if a_index != N:
        ans += count_lis[a_index]
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n,m,l = map(int,input().split())
A = [list(map(int,input().split())) for i in range(m)]
q = int(input())
S = [list(map(int,input().split())) for i in range(q)]

# from scipy.sparse.csgraph import floyd_warshall

for i in range(m):  # ノード番号が1始まりで与えられている場合
    for j in range(2):
        A[i][j] -= 1

for i in range(q):  # ノード番号が1始まりで与えられている場合
    for j in range(2):
        S[i][j] -= 1

M = [[float("inf")] * n for i in range(n)]

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

for i in range(m):
    M[A[i][0]][A[i][1]] = A[i][2]
    M[A[i][1]][A[i][0]] = A[i][2]

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

# M = floyd_warshall(M)

for i in range(n):
    for j in range(n):
        M[i][j] = 1 if M[i][j] <= l else float("inf")

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

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

# M = floyd_warshall(M)

for i in range(q):
    ans = M[S[i][0]][S[i][1]]-1
    if ans == float("inf"):
        ans = -1
    print(int(ans))

### FIXED CODE ###

n,m,l = map(int,input().split())
A = [list(map(int,input().split())) for i in range(m)]
q = int(input())
S = [list(map(int,input().split())) for i in range(q)]

from scipy.sparse.csgraph import floyd_warshall

for i in range(m):  # ノード番号が1始まりで与えられている場合
    for j in range(2):
        A[i][j] -= 1

for i in range(q):  # ノード番号が1始まりで与えられている場合
    for j in range(2):
        S[i][j] -= 1

M = [[float("inf")] * n for i in range(n)]

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

for i in range(m):
    M[A[i][0]][A[i][1]] = A[i][2]
    M[A[i][1]][A[i][0]] = A[i][2]

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

M = floyd_warshall(M)

for i in range(n):
    for j in range(n):
        M[i][j] = 1 if M[i][j] <= l else float("inf")

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

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

M = floyd_warshall(M)

for i in range(q):
    ans = M[S[i][0]][S[i][1]]-1
    if ans == float("inf"):
        ans = -1
    print(int(ans))
### BUGGY CODE ###


def main():
    n = list(map(int, input().split()))
    N, M = n[0], n[1]

    import numpy as np

    M_list = []
    y_array = np.array([[10000000000]*M]*N)
    for i in range(M):
        tmp = list(map(int, input().split()))
        M_list.append(tmp[0])
        y_array[tmp[0]-1,i] = tmp[1]

    num_array = np.zeros([N,M])
    ynum_array = np.ones([N,M])

    a = np.argsort(y_array, axis=1)
    for k in range(N):
        tmp = 1
        for l in a[k]:
            #print(int(y_array[k][l]))
            if int(y_array[k][l]) == 10000000000:
                #print('break')
                break
            ynum_array[k][l] = tmp
            tmp += 1

    for j in range(M):
        ac = (str(M_list[j]).zfill(6)) + (str(int(ynum_array[M_list[j]-1][j])).zfill(6))
        print(ac)
        
    #print(y_array)

if __name__ == '__main__':
    main()




### FIXED CODE ###

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

city_list = []
for i in range(m):
    p, y = map(int, input().split())
    city_list.append([p, y, i])

city_list.sort(key=lambda x: (x[0], x[1]))

#print(city_list)

tmp_list = [0]*m
tmp_num = 1
for num,j in enumerate(city_list):
    if num == 0:
        tmp_list[j[2]] = str(j[0]).zfill(6)+str(tmp_num).zfill(6)
        j_tmp = j[0]
        tmp_num += 1
    else:
        if j[0] != j_tmp:
            j_tmp = j[0]
            tmp_num = 1
            tmp_list[j[2]] = str(j[0]).zfill(6)+str(tmp_num).zfill(6)
            tmp_num += 1
        else:
            tmp_list[j[2]] = str(j[0]).zfill(6)+str(tmp_num).zfill(6)
            tmp_num += 1

for k in tmp_list:
    print(k)