Harryxun/stf_run huggingface dataset:
H,W,D = map(int,input().split())
A = []

for i in range(H):
    AH = map(int,input().split())
    A.append(list(AH))
Q = int(input())

for l in range(Q):
    s=0
    L,R = map(int,input().split())
    
    while L != R:
        for m in A:
            if L in m:
                i=A.index(m)
                j=m.index(L)
            if L+D in m:
                x=A.index(m)
                y=m.index(L+D)
                
        L +=D
        s += abs(x-i)+abs(y-j)
            
    print(s)

### FIXED CODE ###

N = int(input())
print(N//3)
N, K = map(int, input().split())
x = []
for i in range(N):
    x.append(list(map(int, input().split())))
ans = []
for i in range(N):
    for j in range(i+1, N):
        count = 0
        x1 = min(x[i][0], x[j][0])
        x2 = max(x[i][0], x[j][0])
        y1 = min(x[i][1], x[j][1])
        y2 = max(x[i][1], x[j][1])

        for k in range(N):
            if x1 <= x[k][0] and x[k][0] <= x2 and y1 <= x[k][1] and x[k][1] <= y2:
                count += 1
        if count >= K:
            ans.append((x2 - x1) * (y2 - y1))
print(min(ans))


### FIXED CODE ###

N, K = map(int, input().split())
x = []
for i in range(N):
    x.append(list(map(int, input().split())))
ans = []
for i in range(N):
    for j in range(i+1, N):
        for l in range(N):
            for m in range(l+1, N):
                count = 0
                x1 = min(x[i][0], x[j][0])
                x2 = max(x[i][0], x[j][0])
                y1 = min(x[l][1], x[m][1])
                y2 = max(x[l][1], x[m][1])

                for k in range(N):
                    if x1 <= x[k][0] and x[k][0] <= x2 and y1 <= x[k][1] and x[k][1] <= y2:
                        count += 1
                if count >= K:
                    ans.append((x2 - x1) * (y2 - y1))
print(min(ans))
M = input()#5
D = input()#30


caM = []
for i in range(1,int(M)+1):
    caM.append(i)
count = 0
for i in range(2,int(D)+1):
    if len(str(i)) == 2:
        x = str(i)
        y = x[0:1]
        z = x[1:2]
        for j in range(2,int(M) + 1):
            if (int(y) * int(z) == j) and (int(z) != 1) and (int(y) != 1):
                count += 1
print(count)

### FIXED CODE ###

#入力が横に一行並んでるときはこうする↓
M,D = input().split()
 
count = 0
for i in range(2,int(D)+1):
    if len(str(i)) == 2:
        x = str(i)
        y = x[0:1]
        z = x[1:2]
        for j in range(2,int(M) + 1):
            if int(y) * int(z) == j and int(z) != 1 and int(y) != 1:
                count += 1
print(count)
N = int(input())
a = list(int(i) for i in input().split())
for i in range(N):
  a[i] = a[i]-i
a.sort()
if N%2==0:
  b=int((a[int(N/2)]+a[int(N/2+1)])/2)
else:
  b=a[int((N+1)/2)]
sum_1=0
sum_2=0
sum_3=0
for i in range(N):
  sum_1 += abs(a[i]-b)
b-=1
for i in range(N):
  sum_2 += abs(a[i]-b)
b+=2
for i in range(N):
  sum_3 += abs(a[i]-b)
print(min(sum_1,sum_2,sum_3))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A = [x - i - 1 for i, x in enumerate(A)]
A.sort()
mid = A[N // 2]
res1 = 0
for a in A:
    res1 += abs(a - mid)

mid += 1
res2 = 0
for a in A:
    res2 += abs(a - mid)


print(min(res1, res2))
l =[]
for i in range(5):
    a = int(input())
    l.append(a)

x =[]
j=[]
for i in l:
    t = i%10
    if t != 0:
        x.append(t)
        j.append(i+10-t)
    else:
        j.append(i)

print(sum(j)-10+min(x))

### FIXED CODE ###

l =[]
for i in range(5):
    a = int(input())
    l.append(a)

x =[]
j=[]
for i in l:
    t = i%10
    if t != 0:
        x.append(t)
        j.append(i+10-t)
    else:
        j.append(i)

if len(x) == 0:
    print(sum(j))
else:
    print(sum(j)-10+min(x))
s=input()
if s=="Rainy":
    print("Sunny")
 
list=["Sunny","Cloudy","Rainy"]
print(list[list.index(s)+1])

### FIXED CODE ###

s=input()
 
list=["Sunny","Cloudy","Rainy"]
print(list[(list.index(s)+1)%3])
S = input()

ACGT = ['A', 'C', 'G', 'T']
cntList = []
cnt = 0
for s in S:
    if s in ACGT:
        cnt += 1
        cntList.append(cnt)
    else:
        cnt = 0
print(max(cntList))

### FIXED CODE ###

S = input()

ACGT = ['A', 'C', 'G', 'T']
cntList = []
cnt = 0
cntList.append(cnt)
for s in S:
    if s in ACGT:
        cnt += 1
        cntList.append(cnt)
    else:
        cnt = 0
print(max(cntList))
s = input()
n = int(input())
 
count = 0
for i in s:
    count+=1
    if i != "1" or count == n:
        print(i)
        break
else:
    print(1)

### FIXED CODE ###


a,b= map(int, input().split())
print((a-1) * (b-1))
a,b,c,d,e,f=map(int,input().split())

DP=[[0,0] for _ in range(f+1)]
DP[a*100][0]=a*100
DP[b*100][0]=b*100

for i in range(f+1):
    if DP[i][0]==0:continue
    for j in a,b:
        if i+j*100<=f:
            j *=100
            if DP[i][1]*100/(i+j)>=DP[i+j][1]*100/(i+j):
                DP[i+j]=[i+j,DP[i][1]]
    for j in c,d:
        if i+j<=f and 100*(DP[i][1]+j)/(i+j)<=100*e/(100+e):
            if 100*(DP[i][1]+j)/(i+j)>=100*(DP[i+j][1])/(i+j):
                DP[i+j]=[i+j,DP[i][1]+j]

ans,water=0,[a*100,0]
for x,y in DP:
    if x==0:continue
    if 100*y/x>ans:
        ans=100*y/x
        water=[x,y]
print(*water)

### FIXED CODE ###

inf=10**8
a,b,c,d,e,f=map(int,input().split())
a,b=100*a,100*b
DP=[inf]*(f+max(a,b)+1)
DP[a],DP[b]=0,0

for i in range(f+1):
    if DP[i]!=inf:
        DP[i+a]=DP[i]
        DP[i+b]=DP[i]
        for j in c,d:
            if 100*(DP[i]+j)/(i+j)<=100*e/(100+e):
                DP[i+j]=max(DP[i],DP[i]+j)

ans,index=0,[a,0]
for i in range(f+1):
    if DP[i]!=inf:
        if ans<100*DP[i]/i:
            ans=100*DP[i]/i
            index=[i,DP[i]]

print(*index)
n=int(input())
h=list(map(int,input().split()))
answer=[]
for i in range(n-1):
  ans=0
  for j in range(n-i-1):
    #print(str(h[i+j])+'と'+str(h[i+j+1])+'を比較')
    if h[i+j]>=h[i+j+1]:
      ans+=1
    if h[i+j]<h[i+j+1]:
      answer.append(ans)
      #print('第'+str(i+1)+'ループ終わり')
      break
    if i+j+1==n-1:
      answer.append(ans)
      #print('第'+str(i+1)+'ループ終わり')
      break
  ans=0
print(max(answer))

### FIXED CODE ###

N = int(input())
H = list(map(int,input().split()))
x = 0
lis = []
for i in range(0,len(H)-1) :
    if H[i] - H[i+1] >=0:
        x += 1
    else:
        lis.append(x)
        x =0
lis.append(x)
print(max(lis))
import numpy as np
N, K = map(int, input().split(" "))
P = np.array(list(map(int, input().split(" "))))
ans_max = 0
for i in range(N - K + 1):
    p = P[i: i + K]
    p_i = np.array([k for k in range(1, p[0] + 1)])
    for p_k in p[1:]:
        p_i = np.array([p_i + k for k in range(1, p_k + 1)]).flatten()
    ans_max = max(np.sum(p_i) / np.prod(p), ans_max)
print(ans_max)

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split(" "))
p = list(map(int, input().split(" ")))
ex = [i + 1 for i in p]
ans = sum(ex[0: K])
max_ans = ans
for i in range(K, N):
    ans += ex[i] - ex[i - K]
    max_ans = max(ans, max_ans)
print(max_ans / 2.0)
n = int(input())
p = list(map(int, input().split()))

cnt = 0
for i in range(n-2):
    if sorted([p[i], p[i+1], p[i+2])[1] == p[i+1]:
        cnt += 1
print(cnt)


### FIXED CODE ###

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

cnt = 0
for i in range(n - 2):
    if sorted([p[i], p[i + 1], p[i + 2]])[1] == p[i + 1]:
        cnt += 1
print(cnt)
N = int(input())
A = list(map(int,input().split()))
S = [0] * (10 ** 5)
for i,a in enumerate(A):
    S[a] = i + 1
    # print(A[i] + 1)
    # print(a)

for n in range(1,N + 1):
    if n == N + 1 or n == N:
        print(S[n])
    else:
        print(S[n],end=" ")




### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
S = [0] * (10 ** 5 + 2)
for i,a in enumerate(A):
    S[a] = i + 1
    # print(A[i] + 1)
    # print(a)

for n in range(1,N + 1):
    if n == N + 1 or n == N:
        print(S[n])
    else:
        print(S[n],end=" ")
N = input()
len = len(N)
cnt = 1
for i in range(0, len, 1):
    cnt = 1
    for j in range(i + 1, len, 1):
        if (N[i] != N[j]):
            break
        else:
            cnt += 1
    num = max(num, cnt)
print("Yes" if 3 <= num else "No")

### FIXED CODE ###

N = list(input())
len = len(N)
num = 0
for i in range(0, len, 1):
    cnt = 1
    for j in range(i + 1, len, 1):
        if (N[i] != N[j]):
            break
        else:
            cnt += 1
    num = max(num, cnt)
print("Yes" if 3 <= num else "No")
import collections
import itertools

N, M=map(int, input().split())
a = []
for i in range(N):
  b = []
  b = list(map(int, input().split()))
  del b[0]
  a.extens(b)

counter = collections.Counter(a)

mode_v = counter.most_common()[0][-1]
it = itertools.takewhile(
    lambda kv: kv[-1] == mode_v, counter.most_common()
)
if len(it)>=N:
	print(len(it)>=N)
else:
  	print(0)
 
 
  
 

### FIXED CODE ###

import collections
import itertools

N, M=map(int, input().split())
a = []
for i in range(N):
  b = []
  b = list(map(int, input().split()))
  del b[0]
  a.extend(b)

counter = collections.Counter(a)

ret = [letter for letter,count in counter.most_common() if count == counter.most_common()[0][1]]
if N == counter.most_common()[0][1]:
	print(len(ret))
else:
  print(0)
strings = ["dream","dreamer","erase","eraser"]

def isDaydream(s):
    if s == "":
        return True
    for string in strings:
        if s.startswith(string):
            if(isDaydream(s[len(string):])):
                return True
    return False
if(isDaydream(input())):
    print("YES")
else:
    print("NO")

### FIXED CODE ###

def isDaydream(s):
    while s != "":
        if s.endswith("dream"):
            s = s[:-5]
        elif s.endswith("dreamer"):
            s = s[:-7]
        elif s.endswith("erase"):
            s = s[:-5]
        elif s.endswith("eraser"):
            s = s[:-6]
        else :
            return False
    return True

if(isDaydream(input())):
    print("YES")
else:
    print("NO")
N,K=map(int, input().split())
H=list(map(int, input().split()))

H_sort = sorted(H, reverse=True)

for i in range(K):
    del H_sort[i]

print(sum(H_sort))
    

### FIXED CODE ###

n, k = map(int, input().split())
h = sorted(map(int, input().split()))
 
x = 0

if n - k <= 0:
    print(0)
else:
    for i in range(n-k):
        x += h[i]
    print(x)
c=[x+' '+y for x in'SHCD'for y in range(1,14)]
for _ in range(int(input())):
 c.remove(input())
print('\n'.join(c))

### FIXED CODE ###

n=int(input())
e=[input()for _ in[0]*n]
for s in"SHCD":
 for r in range(1,14):
  if f'{s} {r}'not in e:print(s,r)
all = list(map(int, input().split()))

N = all[0]
Y = all[1]

check = 0
for i in range(N):
    for j in range(N-(i+j)):
        c = (N-(i+j))
        total = 10000*i + 5000*j + 1000*c
        if Y!=total:
            continue
        else:
            yu = i
            hi = j
            no = c
            check += 1
            break
    else:
        continue 
    break

if check==100:
    yu = -1
    hi = -1
    no = -1

print(yu)
print(" ")
print(hi)
print(" ")
print(no)
print(" ")


### FIXED CODE ###

all = list(map(int, input().split()))

N = all[0]
Y = all[1]

yu = -1
hi = -1
no = -1
for i in range(N+1):
    for j in range((N+1)-i):
        c = (N-(i+j))
        total = 10000*i + 5000*j + 1000*c
        if Y==total:
            yu = i
            hi = j
            no = c
            break
        else:
            continue
    else:
        continue 
    break

print(str(yu) + " " + str(hi) + " " + str(no))
a = int(input())
b = str(a)
over = int(b[:2])
under = int(b[2:])
if 0<over<13 and 0<under<13:
   print("AMBIGUOUS")
elif 0<over<13 and (1>under or under>12):
   print("YYMM")
elif(0<under<13 and (1>over or over>12):
   print("MMYY")
else:
   print("NA")

### FIXED CODE ###

a = input()
over = int(a[:2])
under = int(a[2:])
if 0<over<13 and 0<under<13:
   print("AMBIGUOUS")
elif 0<over<13 and (1>under or under>12):
     print("MMYY")
elif 0<under<13 and (1>over or over>12):
     print("YYMM")
else:
     print("NA")
import fractions

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

S=list(input())
T=list(input())

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

NM=lcm(N,M)

array=[0]*NM


Scount=0
for i in range(0,NM,NM//N):
  array[i]=S[Scount]
  Scount+=1
  #print(array)

Tcount=0

for j in range(0,NM,NM//M):
  
  if array[j]!=0 and array[j]!=T[Tcount]:
    print(-1)
    exit()
  else:
    array[j]=T[Tcount]
    Tcount+=1
  #print(array)
  
print(NM)

### FIXED CODE ###

import fractions

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

S=list(input())
T=list(input())

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

NM=lcm(N,M)

#array=[0]*NM

battingS=[]
battingT=[]
#Scount=0
for i in range(0,N,NM//M):
  battingS.append(S[i])
  #Scount+=1
  #print(array)

Tcount=0

for j in range(0,M,NM//N):
  battingT.append(T[j])
  #Scount+=1
  '''
  if array[j]!=0 and array[j]!=T[Tcount]:
    print(-1)
    exit()
  else:
    array[j]=T[Tcount]
    Tcount+=1
  #print(array)
  '''

for i in range(len(battingS)):
  if battingS[i]!=battingT[i]:
    print(-1)
    exit()
#print(battingS,battingT)
print(NM)
nm=list(map(int,input().split()))
ps=[]
for i in range(nm[1]):
    ps.append(list(input().split()))
    ps[-1][0]=int(ps[-1][0])
ac=[0]*nm[0]
wa=0
for i in range(nm[1]):
    if ps[i][1]=="AC":
        if ac[ps[i][0]]==0:
            ac[ps[i][0]]=1
        else:
            pass
    else:
        if ac[ps[i][0]]==0:
            wa+=1
        else:
            pass
print(sum(ac),wa)


### FIXED CODE ###

nm=list(map(int,input().split()))
ps=[]
for i in range(nm[1]):
    ps.append(list(input().split()))
    ps[-1][0]=int(ps[-1][0])
ac=[0]*nm[0]
wa=[0]*nm[0]
for i in range(nm[1]):
    if ps[i][1]=="AC":
        if ac[ps[i][0]-1]==0:
            ac[ps[i][0]-1]=1
        else:
            pass
    else:
        if ac[ps[i][0]-1]==0:
            wa[ps[i][0]-1]+=1
        else:
            pass
ans=0
for i in range(nm[0]):
    if ac[i]==1:
        ans+=wa[i]
print(sum(ac),ans)
N=input()
sn = 0
for n in N:
    sn += int(n)

if N % sn == 0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

N=input()
sn = 0
for n in N:
    sn += int(n)

if int(N) % sn == 0:
    print('Yes')
else:
    print('No')
R =int(input())

if R < 1200:
    print("ABC")
elif 1200 < R < 2800:
    print("ARC")
elif 2800 < R
    print("AGC")

### FIXED CODE ###

R = int(input())

if R < 1200:
    print("ABC")
elif  R < 2800:
    print("ARC")
else:
    print("AGC")
def calc(s):
    t=s.split()
    a=int(t[0])
    b=int(t[2])
    op=t[1]
    if op=="+":
        return ("{0}".format(a+b))
    if op == "-":
        return ("{0}".format(a - b))
    if op == "*":
        return ("{0}".format(a * b))
    if op == "/":
        return ("{0}".format(a // b))
w="yj s npi"
a=[]
while(w.split()[1]!="?"):
    w=input()
    a.append(w)
a.remove("0 ? 0")
for st in a:
    print("{0}".format(calc(st)))

### FIXED CODE ###

def calc(s):
    t=s.split()
    a=int(t[0])
    b=int(t[2])
    op=t[1]
    if op=="+":
        return ("{0}".format(a+b))
    if op == "-":
        return ("{0}".format(a - b))
    if op == "*":
        return ("{0}".format(a * b))
    if op == "/":
        return ("{0}".format(a // b))
w="yj s npi"
a=[]
while(w.split()[1]!="?"):
    w=input()
    a.append(w)
a.pop()
for st in a:
    print("{0}".format(calc(st)))
n, m = map(int, input().split())
 
a = []
for i in range(m):
    a.append(int(input()))
 
dp = [0] * (n + 1)
dp[0] = 1
for now in range(0, n + 1):
    print(now, dp[now])
    for next_step in range(now + 1, min(n + 1, now + 3)):
        if not next_step in a:
            dp[next_step] += dp[now]
            dp[next_step] %= 1000000007

print(dp[n])

### FIXED CODE ###

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

a = []
for i in range(m):
    a.append(int(input()))
a = set(a)

dp = [0] * (n + 1)
dp[0] = 1
for now in range(0, n + 1):
    for next_step in range(now + 1, min(n + 1, now + 3)):
        if not next_step in a:
            dp[next_step] += dp[now]
            dp[next_step] %= 1000000007

print(dp[n])
#参考
#https://atcoder.jp/contests/aising2019/submissions/3995168

import bisect

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

A=list(map(int,input().split()))
Asum=[0]*N
Asum2=[0]*N
total=0

for i in range(N):
  total+=A[i]
  Asum[i]=total
  if i>1:
    Asum2[i]=A[i]+Asum2[i-2]
  else:
    Asum2[i]=A[i]

X=[] 
for i in range(Q):
  X.append((int(input()),i))
X.sort(key=lambda x :x[0])
  

#yで高橋くんと青木くんの取りたいカードが初めて衝突すると考える。
#このようなyは半分より小さい所にはないので初期値を半分のところとする。
#yがNまで来た時は最初から交互に取る
#Xを小さい順から計算することで、yの値が単調増加になる
y=N//2-1
ans=[0]*Q
for x,i in X:
  while x>A[y] and y<=N-1:
    y+=1
  while y<=N-1:
    takahashi=N-y
    aoki=y+1-bisect.bisect_left(A,x-(A[y]-x))
    if takahashi>aoki:
      y+=1
    else:
      break
  #右端からA[y]までは全て高橋くんが取る
  ans[i]+=Asum[N-1]-Asum[y-1]
  #青木くんはyからN-y個取っているので、その下のところから交互に取る
  if y-(N-y)-1<0:
    continue
  ans[i]+=Asum2[y-(N-y)-1]

for i in range(Q):
  print(ans[i])

### FIXED CODE ###

#参考
#https://atcoder.jp/contests/aising2019/submissions/3995168

import bisect

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

A=list(map(int,input().split()))
Asum=[0]*N
Asum2=[0]*N
total=0

for i in range(N):
  total+=A[i]
  Asum[i]=total
  if i>1:
    Asum2[i]=A[i]+Asum2[i-2]
  else:
    Asum2[i]=A[i]

X=[] 
for i in range(Q):
  X.append((int(input()),i))
X.sort(key=lambda x :x[0])
  

#yで高橋くんと青木くんの取りたいカードが初めて衝突すると考える。
#このようなyは半分より小さい所にはないので初期値を半分のところとする。
#yがNまで来た時は最初から交互に取る
#Xを小さい順から計算することで、yの値が単調増加になる
y=N//2-1
ans=[0]*Q
for x,i in X:
  while y<=N-1 and x>A[y]:
    y+=1
  while y<=N-1:
    takahashi=N-y
    aoki=y+1-bisect.bisect_left(A,x-(A[y]-x))
    if takahashi>aoki:
      y+=1
    else:
      break
  #右端からA[y]までは全て高橋くんが取る
  ans[i]+=Asum[N-1]-Asum[y-1]
  #青木くんはyからN-y個取っているので、その下のところから交互に取る
  if y-(N-y)-1<0:
    continue
  ans[i]+=Asum2[y-(N-y)-1]

for i in range(Q):
  print(ans[i])
import numpy as np
n,t=map(int,input().split())
s=[list(map(int,input().split()))for i in range(n)]
a,b=np.zeros((n+1,t+1)),np.zeros((n+1,t+1))
for i in range(n):
    a[i+1]=a[i]
    a[i+1][s[i][0]:]=np.maximum(a[i+1][s[i][0]:],a[i][:t+1-s[i][0]]+s[i][1])
    b[n-i-1]=b[n-i]
    b[n-i-1][s[n-i-1][0]:]=np.maximum(b[n-i-1][s[n-i-1][0]:],b[n-i][:t-s[n-i-1][0]+1]+s[n-i-1][1])
p=0
print(a,b)
for i in range(n):
    for j in range(t):
        p=max(p,a[i][j]+b[i+1][t-1-j]+s[i][1])
print(int(p))

### FIXED CODE ###

import numpy as np
n,t=map(int,input().split())
a=[list(map(int,input().split()))for i in range(n)]
b=np.zeros((n+1,t))
c=np.zeros((n+1,t))
for i in range(n):
    b[i+1]=b[i]
    b[i+1][a[i][0]:]=np.maximum(b[i+1][a[i][0]:],b[i][:-a[i][0]]+a[i][1])
    c[-i-2]=c[-i-1]
    c[-i-2][a[-i-1][0]:]=np.maximum(c[-i-2][a[-i-1][0]:],c[-i-1][:-a[-i-1][0]]+a[-i-1][1])
q=0
for i in range(n):
    q=max(q,max(b[i]+c[i+1][::-1])+a[i][1])
print(int(q))
n = input('');
k = input('');
 
int32(1);
for 1:n
  min(int32(2)*ans, ans+k);
end
 
fprintf("%d\n", ans);

### FIXED CODE ###

r = int(input())
g = int(input())
print( g*2 - r )
n,m,c = int(map,input().split())
b = int(map,input().split())
count = 0
for i in range(n):
    sum = 0
    a = int(map, input().split())
    for j in range(m):
        sum += a[j] * b[j]
    sum += c
    if sum > 0:
        count += 1
print(count)

### FIXED CODE ###

n,m,c = map(int,input().split())
b = map(int,input().split())
b = list(b)
count = 0
for i in range(n):
    sum = 0
    a = map(int, input().split())
    a = list(a)
    for j in range(m):
        sum += a[j] * b[j]
    sum += c
    if sum > 0:
        count += 1
print(count)
N = input()
S = sum(map(int, N))

if N % S == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N = input()
S = sum(map(int, N))

if int(N) % S == 0:
    print("Yes")
else:
    print("No")
N = input()
S = input()
t = []
for i in S:
    if ord(i) + N >= 91:
        t.append(chr(ord(i) + N - 26))
    else:
        t.append(chr(ord(i) + N))
print(''.join(t))

### FIXED CODE ###

N = int(input())
S = input()
t = []
for i in S:
    if ord(i) + N >= 91:
        t.append(chr(ord(i) + N - 26))
    else:
        t.append(chr(ord(i) + N))
print(''.join(t))
a,b = map(int,input().split())
c = a+b
if c%3 == 0:
  print('Possible')
else:
  print('Impossible
')

### FIXED CODE ###

a,b = map(int,input().split())
c = a+b
if c%3 == 0 or a%3 ==0 or b%3 == 0:
  print('Possible')
else:
  print('Impossible')
A = [0]*3
for i in range(3):
    A[i] = list(map(int,input().split()))
N = int(input())
B = []
for _ in range(N):
    B.append(int(input())
             
for k in range(3):
    for j in range(3):
        if A[k][j] in B:
             A[k][j] = 0
answer = 'No'
for i in range(3):
    if sum(A[i])==0:
        answer = 'Yes'
        break
    count = 0
    for j in range(3):
        count += A[j][i]
print(answer)

### FIXED CODE ###

A = [0]*3
for i in range(3):
    A[i] = list(map(int,input().split()))
N = int(input())
B = []
for _ in range(N):
    B.append(int(input()))
             
for k in range(3):
    for j in range(3):
        if A[k][j] in B:
             A[k][j] = 0
answer = 'No'
for i in range(3):
    if sum(A[i])==0:
        answer = 'Yes'
        break
    count = 0
    for j in range(3):
        count += A[j][i]
    if count == 0:
        answer = 'Yes'
if A[0][0]+A[1][1]+A[2][2]==0:
    answer = 'Yes'
if A[0][2]+A[1][1]+A[2][0]==0:
    answer = 'Yes'
print(answer)
s=input()
w=['Sunny','Cloudy','Rainy']
print(w[w.index(s)+1])

### FIXED CODE ###

s=input()
if s == 'Sunny':
 print('Cloudy')
elif s == 'Cloudy':
 print('Rainy')
else:
 print('Sunny')
from itertools import product, combinations

INF = float('inf')
def floyd_warshall(V, E):
    dist = {u: {v: INF for v in V} for u in V}
    for v in V:
        dist[v][v] = 0
        for u, c in E[v]: dist[v][u] = c
    for k in V:        
        for i, j in product(V, repeat=2):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
    return dist

N, M, L = map(int, input().split())
V = list(range(N))
E = [[] for _ in V]
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a-1].append((b-1, c))
    E[b-1].append((a-1, c))

dist = floyd_warshall(V, E)
E_charge = [[] for _ in V]
for u, v in combinations(V, 2):
    if dist[u][v] <= L: E_charge[u][v] = 1; E_charge[v][u] = 1;
charge = floyd_warshall(V, E_charge)

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

### FIXED CODE ###

from itertools import product, combinations

INF = float('inf')
def floyd_warshall(E):
    N = len(E)
    dist = [[INF for _ in range(N)] for _ in range(N)]
    for v in range(N):
        dist[v][v] = 0
        for u, c in E[v]: dist[v][u] = c
    for k in range(N):        
        for i, j in product(range(N), repeat=2):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
    return dist

N, M, L = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a-1].append((b-1, c))
    E[b-1].append((a-1, c))
dist = floyd_warshall(E)

E_charge = [[] for _ in range(N)]
for u, v in combinations(range(N), 2):
    if dist[u][v] <= L:
        E_charge[u].append((v, 1))
        E_charge[v].append((u, 1))
charge = floyd_warshall(E_charge)

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