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

from collections import deque
import sys
input = sys.stdin.readline

def bfs():
    H, W = map(int, input().split())
    ls = deque([])
    D = [[0] * (W+2)]
    D += ([[0] + [float("inf")]*W + [0] for i in range(H)])
    D.append([0]*(W+2))
    for i in range(H):
        line = input()
        for j in range(W):
            if line[j] == "#":
                ls.append([i+1, j+1, 0])
                D[i+1][j+1] = 0

    while len(ls) > 0:
        h, w, depth = ls.popleft()
        if depth + 1 < D[h+1][w]:
            ls.append([h+1, w, depth+1])
            D[h+1][w] = depth + 1
        if depth + 1 < D[h-1][w]:
            ls.append([h-1, w, depth+1])
            D[h-1][w] = depth + 1
        if depth + 1 < D[h][w+1]:
            ls.append([h, w+1, depth+1])
            D[h][w+1] = depth + 1
        if depth + 1 < D[h][w-1]:
            ls.append([h, w-1, depth+1])
            D[h][w-1] = depth + 1

    return depth
    
print(bfs())

### FIXED CODE ###

import sys
input = sys.stdin.readline

H, W = map(int, input().split())
G = [[i for i in input()] for j in range(H)]

ls = []
dp = [[-1 for i in range(W)] for j in range(H)]
for h in range(H):
    for w in range(W):
        if G[h][w] == "#":
            ls.append([h,w])
            dp[h][w] = 1

ans = -1
while len(ls) > 0:
    ans += 1
    temp = []
    for h, w in ls:
        if 0 <= h+1 <= H-1 and dp[h+1][w] == -1:
            dp[h+1][w] = 1
            temp.append([h+1,w])
        if 0 <= h-1 <= H-1 and dp[h-1][w] == -1:
            dp[h-1][w] = 1
            temp.append([h-1,w])
        if 0 <= w+1 <= W-1 and dp[h][w+1] == -1:
            dp[h][w+1] = 1
            temp.append([h,w+1])
        if 0 <= w-1 <= W-1 and dp[h][w-1] == -1:
            dp[h][w-1] = 1
            temp.append([h,w-1])
    ls = temp

print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
answer = 'Yes'
score = 1
for i in range(K):
    score *= A[i]

for i in range(N - K):
    next_score = score * A[K + i] // A[i]
    print('Yes' if next_score > score else 'No')
    score = next_score



### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
answer = 'Yes'
score = 0
for i in range(K):
    score += A[i]

for i in range(N - K):
    next_score = score + A[K + i] - A[i]
    print('Yes' if next_score > score else 'No')
    score = next_score
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

N, S = MAP()
A = LIST()

acc = list(accumulate(A))
# dp[i][j][k] := j番目の要素まで見て、総和がjで、使う区間がk=0,1,2(0:未確定, 1:L確定済, 2:LR確定済)の状態の通り数
dp = list3d(N+1, S+1, 3, 0)
dp[0][0][0] = 1
for i, a in enumerate(A):
    for j in range(S+1):
        # 枝刈り
        if j > acc[i]:
            break
        for k in range(3):
            if dp[i][j][k] == 0:
                continue
            for l in range(k, 3):
                # aを総和に足さない遷移は全部OK
                dp[i+1][j][l] += dp[i][j][k]
                dp[i+1][j][l] %= MOD
                # aを総和に足す遷移は、遷移元が状態2と遷移先が状態0は無理
                if j+a <= S and k != 2 and l != 0:
                    dp[i+1][j+a][l] += dp[i][j][k]
                    dp[i+1][j+a][l] %= MOD
ans = dp[N][S][2]
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

N, S = MAP()
A = LIST()

# dp0[i][j][ := j番目の要素まで見て、総和がjで、使う区間が未確定の状態の通り数
dp0 = list2d(N+1, S+1, 0)
# dp1[i][j][ := j番目の要素まで見て、総和がjで、使う区間がL確定済の状態の通り数
dp1 = list2d(N+1, S+1, 0)
# dp2[i][j][ := j番目の要素まで見て、総和がjで、使う区間がLR確定済の状態の通り数
dp2 = list2d(N+1, S+1, 0)
dp0[0][0] = 1
for i, a in enumerate(A):
    for j in range(S+1):
        # aを総和に足さない遷移は全部OK
        dp0[i+1][j] += dp0[i][j]
        dp1[i+1][j] += dp0[i][j] + dp1[i][j]
        dp2[i+1][j] += dp0[i][j] + dp1[i][j] + dp2[i][j]
        # aを総和に足す遷移は、遷移元が状態2と遷移先が状態0は無理
        if j+a <= S:
            dp1[i+1][j+a] += dp0[i][j] + dp1[i][j]
            dp2[i+1][j+a] += dp0[i][j] + dp1[i][j]
        dp0[i+1][j] %= MOD
        dp1[i+1][j] %= MOD
        dp2[i+1][j] %= MOD
ans = dp2[N][S]
print(ans)
### BUGGY CODE ###

r1, c1, r2, c2 = map(int, input().split())
mod = int(1e+9) + 7
def inved(x):
  a, b, c, d, k, l = 1, 0, 0, 1, x, mod
  while l != 0:
    a, b, c, d = c, d, a - c * (k // l), b - d * (k // l)
    k, l = l, k & l
  return a % mod
frac = [1]
for i in range(r2 + c2 + 2):
  frac.append(((i+1) * frac[i]) % mod)
fracr2c2 = frac[r2 + c2 + 2]
fracr1c2 = frac[r1 + c2 + 1]
fracr2c1 = frac[r2 + c1 + 1]
fracr1c1 = frac[r1 + c1]
fracr2 = frac[r2 + 1]
fracr1 = frac[r1]
fracc2 = frac[c2 + 1]
fracc1 = frac[c1]
g = 0
g += (fracr2c2 * inved(fracr2) * inved(fracc2)) % mod
g %= mod
g += (fracr1c1 * inved(fracr1) * inved(fracc1)) % mod
g %= mod
g -= (fracr1c2 * inved(fracr1) * inved(fracc2)) % mod
g %= mod
g -= (fracr2c1 * inved(fracr2) * inved(fracc1)) % mod
g %= mod
print(g)

### FIXED CODE ###

r1, c1, r2, c2 = map(int, input().split())
mod = int(1e+9) + 7
def inved(x):
  a, b, c, d, k, l = 1, 0, 0, 1, x, mod
  while l != 0:
    a, b, c, d = c, d, a - c * (k // l), b - d * (k // l)
    k, l = l, k % l
  return a % mod
frac = [1]
for i in range(r2 + c2 + 2):
  frac.append(((i+1) * frac[i]) % mod)
fracr2c2 = frac[r2 + c2 + 2]
fracr1c2 = frac[r1 + c2 + 1]
fracr2c1 = frac[r2 + c1 + 1]
fracr1c1 = frac[r1 + c1]
fracr2 = frac[r2 + 1]
fracr1 = frac[r1]
fracc2 = frac[c2 + 1]
fracc1 = frac[c1]
g = 0
g += (fracr2c2 * inved(fracr2) * inved(fracc2)) % mod
g %= mod
g += (fracr1c1 * inved(fracr1) * inved(fracc1)) % mod
g %= mod
g -= (fracr1c2 * inved(fracr1) * inved(fracc2)) % mod
g %= mod
g -= (fracr2c1 * inved(fracr2) * inved(fracc1)) % mod
g %= mod
print(g)
### BUGGY CODE ###

def cf(x1,x2):
    cf=[]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

a, b = map(int, input().split())
ab = cf(a, b)
i = 0
for ab_i in ab:
    for ab_j in ab[i+1:]:
        if ab_j%ab_i==0:
            for k, ab_k in enumerate(ab):
                if ab_k == ab_j:
                    del ab[k]
    i += 1
print(len(ab)+1)

### FIXED CODE ###

def pf(n:int):
    r = []
    while n%2==0:
        r.append(2)
        n//=2
    f=3
    while f*f<=n:
        if n%f==0:
            r.append(f)
            n//=f
        else:
            f+=2
    if n!=1:
        r.append(n)
    return r

a, b = map(int, input().split())
a = pf(a)
b = pf(b)
a = set(a)
b = set(b)
print(len(set(a&b))+1)
### BUGGY CODE ###

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

top = 0
for i in range(M):
  A = sorted(A, reverse=True)
  A[0] = A[0] // 2

print(sum(A))

### FIXED CODE ###

import heapq
import math

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

hq = []
for a in A:
  heapq.heappush(hq, a * -1)

for i in range(M):
  n = math.ceil(heapq.heappop(hq) / 2)
  heapq.heappush(hq, n)

b = []
for hqi in hq:
  b.append(hqi * -1)
  
print(sum(b))
### BUGGY CODE ###

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

for i in range(a,b+1):
    if i>=a+x and i<=b-x:
        continue
    else:
        print(i)

### FIXED CODE ###

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

if b-a+1<=2*k:
    for i in range(a,b+1):
        print(i)
    exit()

else:
    for i in range(a,a+k):
        print(i)
    for j in range(b-k+1,b+1):
        print(j)
### BUGGY CODE ###

s = input()
k = int(input())
day = 5 * (10 ** 15)

for c in s:
  i = int(c)
  l = i ** day
  if k <= l:
    print(c)
    exit()
  else:
    k -= l

### FIXED CODE ###

s = input()
k = int(input())

for c in s:
  if c != '1':
    print(c)
    exit()
  else:
    k -= 1
    if k == 0:
      print(1)
      exit()
print(1)
### BUGGY CODE ###

from collections import deque
S=deque(input())
q=int(input())
for i in range(q):
  c=list(input().split())
  if c[0]=='1':
    S.reverse()
  elif c[0]=='2':
    if c[1]=='1':
      S.appendleft(c[2])
    elif c[1]=='2':
      S.append(c[2])
ans=''.join(S)
print(ans)

### FIXED CODE ###

from collections import deque
S=deque(input())
q=int(input())
rev=False
for i in range(q):
  c=list(input().split())
  if c[0]=='1':
    rev=not rev
  elif c[1]=='1' and rev==False:
    S.appendleft(c[2])
  elif c[1]=='2' and rev==True:
    S.appendleft(c[2])
  else:
    S.append(c[2])
if rev:
  S.reverse()
ans=''.join(S)
print(ans)
### BUGGY CODE ###

import math
import heapq
xs,ys,xt,yt=map(int,input().split())
N=int(input())
x=[xs]+[0 for i in range(N)]+[xt]
y=[ys]+[0 for i in range(N)]+[yt]
r=[0]+[0 for i in range(N)]+[0]
for i in range(1,N+1):
    x[i],y[i],r[i]=map(int,input().split())
dist=[10**15 for i in range(N+2)]
dist[0]=0
adjlist=[[0 for i in range(N+2)] for j in range(N+2)]
for i in range(N+2):
    for j in range(N+2):
        if i==j:
            continue
        adjlist[i][j]=max(math.sqrt((x[i]-x[j])**2+(y[i]-y[j])**2)-r[i]-r[j],0)
q=[]
heapq.heappush(q,(0,0))
while(len(q)>0):
    d,p=heapq.heappop(q)
    if dist[p]<d:
        continue
    for j in range(N+2):
        if p==j:
            continue
        cost=adjlist[p][j]
        if dist[j]>dist[p]+cost:
            dist[j]=dist[p]+cost
            heapq.heappush(q,(dist[j],j))
print(dist[N+1])

### FIXED CODE ###

import math
import heapq
xs,ys,xt,yt=map(int,input().split())
N=int(input())
x=[xs]+[0 for i in range(N)]+[xt]
y=[ys]+[0 for i in range(N)]+[yt]
r=[0]+[0 for i in range(N)]+[0]
for i in range(1,N+1):
    x[i],y[i],r[i]=map(int,input().split())
dist=[10**15 for i in range(N+2)]
dist[0]=0
adjlist=[[0 for i in range(N+2)] for j in range(N+2)]
for i in range(N+2):
    for j in range(N+2):
        if i==j:
            continue
        adjlist[i][j]=max(math.sqrt((x[i]-x[j])**2+(y[i]-y[j])**2)-r[i]-r[j],0)
q=[]
heapq.heappush(q,(0,0))
while(len(q)>0):
    d,p=heapq.heappop(q)
    if dist[p]<d:
        continue
    for j in range(N+2):
        if p==j:
            continue
        cost=adjlist[p][j]
        if dist[j]>dist[p]+cost:
            dist[j]=dist[p]+cost
            heapq.heappush(q,(dist[j],j))
print(dist[N+1])
### BUGGY CODE ###

n,m=map(int,input().split())
lst=[list(map(int,input().split())) for i in range(m)]
con=[[] for i in range(n+1)]
check=[0 for i in range(n+1)]
for x in lst: con[x[0]].append(x[1]);con[x[1]].append(x[0])
check[1]=1
dis=[[1]]
i=0
while check.count(0)>1:
    work=[]
    for x in dis[i]:
        for y in con[x]:
            if check[y] : continue
            else : 
                work.append(y)
                check[y]=x
    dis.append(work)
    i+=1
print("Yes")
for j in range(2,n+1):
    print(check[j])


### FIXED CODE ###

n,m=map(int,input().split())
graph=[[] for _ in range(n)]

for _ in range(m):
    a,b=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

sign=[-1]*n
sign[0]=0
work=[]
work_next=graph[0]
for x in work_next:
    sign[x]=0


while work_next:
    work=work_next[:]
    work_next=[]
    for x in work:
        for y in graph[x]:
            if sign[y]>=0 : continue
            if y in work_next : continue
            sign[y]=x
            work_next.append(y)

if -1 in sign : print("No");exit()
print("Yes")
for i in range(1,n):
    print(sign[i]+1)
### BUGGY CODE ###

# P3:
def get_gcd(numbers):
    """Helper function to get GCD of list of numbers."""
    import math
    from functools import reduce

    # gcd is associative
    return reduce(lambda x, y: math.gcd(x, y), numbers)


def sum_of_gcd_tuples():
    K = int(input())
    total = 0
    for a in range(1, K + 1):
        for b in range(1, K + 1):
            for c in range(1, K + 1):
                if a == b and b == c:
                    total += a
                    continue
                if a == 1 or b == 1 or c == 1:
                    total += 1
                    continue
                else:
                    total += get_gcd([a, b, c])

    print(total)


sum_of_gcd_tuples()

### FIXED CODE ###

def sum_of_gcd_tuples():
    from math import gcd
    K = int(input())
    total = 0

    for a in range(1, K + 1):
        for b in range(1, K + 1):
            for c in range(1, K + 1):
                total += gcd(gcd(a, b), c)

    print(total)


sum_of_gcd_tuples()
### BUGGY CODE ###

N = int(input())
li = []
for i in range(N):
  tmp = input()
  if tmp not in li:
    li.append(tmp)
print(len(li))

### FIXED CODE ###

N = int(input())
li = []
for i in range(N):
  tmp = input()
  li.append(tmp)
ans = set(li)
print(len(ans))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
S = 0
for i in range(N-1):
  for j in range(i+1, N):
    S = S + (A[i] * A[j]) % (10**9 + 7)
S = S % (10**9 + 7)
print(S)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
S = 0
ans = 0
for k in range(N):
  S = S + A[k]

for i in range(N-1):
  S = S - A[i]
  ans = ans + S * A[i]

ans = ans % (10**9 + 7)
print(ans)
### BUGGY CODE ###



N=int(input())
'''
count=0
for i in range(1,N+1):
    n=N//i
    count=n*(i+i*n)//(2)+count
print(count)
'''
count=0
wa=0
for i in range(N,0,-1):

    count=0
    for j in range(1,N+1):
        if(i%j==0):
            count=count+1
    wa=count*i+wa
print(wa)


### FIXED CODE ###



N=int(input())
count=0
for i in range(1,N+1):
    n=N//i
    count=n*(i+i*n)//(2)+count
print(count)
### BUGGY CODE ###

import math
from functools import reduce
 
k = int(input())
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
def gcd_list(numbers):
    return reduce(math.gcd, numbers)
 
lst = []
for i in range(k):
    a = i + 1
    for j in range(k):
        b = j + 1
        for l in range(k):
            c = l + 1
            koyakusu = gcd(a, b, c)
            lst.append(koyakusu)
kotae = sum(lst)
print(kotae)

### FIXED CODE ###

import math
from functools import reduce
 
k = int(input())
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
kotae = 0
for i in range(k):
    a = i + 1
    for j in range(k):
        b = j + 1
        for l in range(k):
            c = l + 1
            koyakusu = gcd(a, b, c)
            kotae += koyakusu
print(kotae)
### BUGGY CODE ###

n = int(input())
a_list = [int(input()) for _ in range(n)]

cnt=0
for i in set(a_list):
  if a_list.count(i)%2==1:
    cnt+=1
print(cnt)

### FIXED CODE ###

n = int(input())
a_list = [int(input()) for _ in range(n)]

my_set = set()
for i in a_list:
  if i in my_set:
    my_set.remove(i)
  else:
    my_set.add(i)
print(len(my_set))
### BUGGY CODE ###

def solve(string):
    n, m, *ab = map(int, string.split())
    p = [[] for _ in range(n)]
    for a, b in zip(*[iter(ab)] * 2):
        p[a - 1].append(b - 1)
        p[b - 1].append(a - 1)
    s, ans, d = [0], [0] * n, [0] + [n] * (n - 1)
    while s:
        c = s.pop()
        for t in p[c]:
            if d[c] + 1 < d[t]:
                d[t] = d[c] + 1
                ans[t] = c + 1
                if t not in s:
                    s.append(t)
    return "Yes\n" + "\n".join(map(str, ans[1:]))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))


### FIXED CODE ###

def solve(string):
    from collections import deque
    n, m, *ab = map(int, string.split())
    p = [[] for _ in range(n)]
    for a, b in zip(*[iter(ab)] * 2):
        p[a - 1].append(b - 1)
        p[b - 1].append(a - 1)
    s, ans, d = deque([0]), [0] * n, [0] + [n] * (n - 1)
    while s:
        c = s.popleft()
        for t in p[c]:
            if d[c] + 1 < d[t]:
                d[t] = d[c] + 1
                ans[t] = c + 1
                s.append(t)
    return "Yes\n" + "\n".join(map(str, ans[1:]))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))
### BUGGY CODE ###

#!/usr/bin/env python3
 
import sys
# 以下を記述しないとTLEになる, 何故？
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
# ---- ここまで -----------------------

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)


### FIXED CODE ###

from collections import defaultdict
from bisect import bisect_right

def sol():
    S = input()
    T = input()

    setS = set(S)
    setT = set(T)
    for t in setT:
        if not t in setS:
            print('-1')
            return

    posS = defaultdict(list)

    for i, s in enumerate(S):
        posS[s].append(i)

    for s in enumerate(S):
        posS[s].sort()

    prev = -1
    ans = 0
    N = len(S)

    for t in T:
        next = bisect_right(posS[t], prev)
        if next >= len(posS[t]):
            ans += N - prev
            ans += posS[t][0]
            prev = posS[t][0]
        else:
            ans += posS[t][next] - prev
            prev = posS[t][next]

    print(ans)

sol()
### BUGGY CODE ###

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

r , g, b = S.count("R"), S.count("G"), S.count("B")
ans = r * g * b

for i in range(N-2):
    for j in range(i+1, N-1):
        k = 2*(j+1) - (i+1)
        if k > N:continue
        if S[i] != S[j] and S[j] != S[k-1] and S[k-1] != S[i]:
        	ans -= 1
print(ans)

### FIXED CODE ###

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

r , g, b = S.count("R"), S.count("G"), S.count("B")
ans = r * g * b

for i in range(N-2):
    for d in range(N//2+1):
        j = i + d
        k = j + d
        if k >= N:break
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            ans -= 1
print(ans)
### BUGGY CODE ###

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

ans = [0] * n

for i in range(n):
    ans[i] = A.index(i+1) + 1
print(' '.join(map(str, ans)))

### FIXED CODE ###

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

ans = [0] * n

for idx, i in enumerate(A):
    ans[i-1] = idx + 1
    
print(' '.join(map(str, ans)))
### BUGGY CODE ###

n = int(input())
li = list(map(int,input().split()))
for i in range(1,n+1):
    if i in li:
        print(li.count(i))
    else:
        print(0)

### FIXED CODE ###

n = int(input())
li = list(map(int,input().split()))
li.sort(reverse = True)
count = 0
for i in range(1,n+1):
    count = 0
    while True:
        if li:
            if li[-1]==i:
                count+=1
                li.pop()
            else:
                break
        else:
            break
    print(count)
### BUGGY CODE ###

A,B,N=map(int,input().split())
import math
ans=[]
for i in range(1,N+1):
    ans.append(math.floor(A*i/B)-A*math.floor(i/B))
print(max(ans))

### FIXED CODE ###

A,B,N=map(int,input().split())
import math
if N<B:
    print(math.floor(A*N/B))
else:
    print(math.floor(A*(B-1)/B-A*math.floor((B-1)/B)))
### BUGGY CODE ###

from math import sqrt
N = int(input())

for n in range(1, N+1):
    count = 0
    for x in range(1, int(sqrt(n / 3)) + 2):
        for y in range(x,int(sqrt(n * 2 / 3)) + 2):
            for z in range(y, int(sqrt(n))):
                if x**2 + y**2 + z**2 + x*y + y*z + z*x == n:
                    if len(set([x, y, z])) == 3:
                        count += 6
                    elif len(set([x, y, z])) == 2:
                        count += 3
                    elif len(set([x, y, z])) == 1:
                        count += 1
    print(count)

### FIXED CODE ###

from math import sqrt
N = int(input())
ans = [0] * (N+1)

for x in range(1, int(sqrt(N)) + 2):
    for y in range(1,int(sqrt(N)) + 2):
        for z in range(1, int(sqrt(N)) + 2):
            n = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if n <= N:
                ans[n] += 1

for i in range(1, len(ans)):
    print(ans[i])
### BUGGY CODE ###

import numpy as np
n, k = map(int, input().split())
p = np.array(list(map(int, input().split())))
p += 1
max_ans = 0
for i in range(n-k+1):
    max_ans = max(max_ans, np.sum(p[i:k+i]))
print(max_ans/2)

### FIXED CODE ###

import numpy as np
n, k = map(int, input().split())
p = np.array(list(map(int, input().split())))
p += 1
sum_E = np.cumsum(p)
sum_e = np.append([0], sum_E)
ans = -1
for i in range(n-k+1):
    ans = max(ans, sum_e[i+k] - sum_e[i])
print(ans/2)
### BUGGY CODE ###

[x,y]=[int(i) for i in input().split()]
a=0
for i in range(1,10**9):
    if (x*i)%y!=0:
        print(x*i)
        a=1
        break
if a==0:
    print(-1)        


### FIXED CODE ###

[x,y]=[int(i) for i in input().split()]
a=0
if x%y==0:
    print(-1)
else:
    print(x)
### BUGGY CODE ###

N, M, L = map(int, input().split())
dp = [[float('inf')] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    dp[a-1][b-1] = c
    dp[b-1][a-1] = c
for k in range(N):
    for i in range(N):
        for j in range(N):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
#rint('distance={}'.format(dp))


dp2 = [[float('inf')] * N for _ in range(N)]
for a in range(N - 1):
    for b in range(a+1, N):
        if dp[a][b] <= L:
            dp2[a][b] = 1
            dp2[b][a] = 1
for k in range(N):
    for i in range(N):
        for j in range(N):
            dp2[i][j] = min(dp2[i][j], dp2[i][k] + dp2[k][j])
#print('times={}'.format(dp2))


Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    if dp2[s-1][t-1] != float('inf'):
        print(dp2[s-1][t-1] - 1)
    else:
        print(-1)


### FIXED CODE ###

inf = 10 ** 15

N, M, L = map(int, input().split())
dp = [[inf] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    dp[a-1][b-1] = c
    dp[b-1][a-1] = c
for i in range(N):
    dp[i][i] = 0

for k in range(N):
    for i in range(N):
        for j in range(N):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
#print('distance={}'.format(dp))


dp2 = [[inf] * N for _ in range(N)]
for a in range(N - 1):
    for b in range(a+1, N):
        if dp[a][b] <= L:
            dp2[a][b] = 1
            dp2[b][a] = 1
for k in range(N):
    for i in range(N):
        for j in range(N):
            dp2[i][j] = min(dp2[i][j], dp2[i][k] + dp2[k][j])
#print('times={}'.format(dp2))


Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    cost = dp2[s-1][t-1]
    if cost != inf:
        print(cost - 1)
    else:
        print(-1)