Harryxun/stf_run huggingface dataset:
while True:
    value = [int(x) for x in raw_input().split()]
    if value == 0:
        break
    print(sum(value))

### FIXED CODE ###

while True:
    value = [int(x) for x in raw_input()]
    if value[0] == 0:
        break
    print(sum(value))
import functools
import math
N = int(input())
a = list(map(int, input().split()))

gcd = []
for i in range(N) :
    list_not_i = a.copy()
    list_not_i.remove(a[i])
    gcd.append(functools.reduce(math.gcd, list_not_i))

print(int(max(gcd)))

### FIXED CODE ###

import functools
import fractions
N = int(input())
a = list(map(int, input().split()))

L = [0] * N
for i in range(N) :
        if i == 0 :
                L[0] = 0
        elif i == 1 :
                L[1] = a[0]
        else :
                L[i] = fractions.gcd(L[i-1], a[i-1])

a.reverse()
R = [0] * N
for i in range(N) :
        if i == 0 :
                R[0] = 0
        elif i == 1 :
                R[1] = a[0]
        else :
                R[i] = fractions.gcd(R[i-1], a[i-1])
R.reverse()
a.reverse()

gcd = [0] * N
for i in range(N) :
        if i == 0 :
                gcd[0] = R[0]
        elif i == N-1 :
                gcd[N-1] = L[N-1]
        else :
                gcd[i] = fractions.gcd(L[i],R[i])

print(max(gcd))
n, m, x = map(int, input().split())
a=list(map(int,input().split()))

ans = 0

for i in x:
  if (i in a):
    ans = ans + 1
  else:
    continue

print(min(ans, m-ans))

### FIXED CODE ###

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

ans = 0

for i in a:
  if i < x:
    ans += 1

print(min(ans, m-ans))
s=input()
k=int(input())
l=list(s)

for i in range(len(s)):
  f=-ord(s[i])+ord("z")+1
  if f<=k:
    l[i]="a"
    k-=f
l[-1]=chr(ord(s[-1])+k)
print("".join(l))

### FIXED CODE ###

s=input()
k=int(input())
l=list(s)

for i in range(len(s)):
  f=(-ord(s[i])+ord("z")+1)%26
  if f<=k:
    l[i]="a"
    k-=f

k=k%26
a=ord(l[-1])+k 
if a> ord("z"):a-=26
l[-1]=chr(a)
print("".join(l))
n, k = map(int, input().split())
*V, = map(int, input().split())
M = [v if v < 0 else 0 for v in V]
S = []
for i in range(min(k, n)):
    for j in range(i):
        s = sum(V[:i-j])+sum(V[n-j:])
        M_sub = sorted(M[:i-j]+M[n-j:])
        s -= sum(M_sub[:k-i])
        S += [s]
print(max(S))

### FIXED CODE ###

n, k = map(int, input().split())
*V, = map(int, input().split())
M = [v if v < 0 else 0 for v in V]
S = [0]
for i in range(1, min(k+1, n+1)):
    for j in range(i+1):
        s = sum(V[:i-j])+sum(V[n-j:])
        M_sub = sorted(M[:i-j]+M[n-j:])
        s -= sum(M_sub[:k-i])
        S += [s]
print(max(S))
lis = "abcdefghijklmnopqrstuvwxyz"
dic = {}

z = imput()

for a in range(len(lis)-1):
  if z = lis[a]:
    print(lis[a+1])
    exit()


### FIXED CODE ###

lis = "abcdefghijklmnopqrstuvwxyz"
 
z = input()
 
for a in range(len(lis)-1):
  if z == lis[a]:
    print(lis[a+1])
    exit()
# coding: utf-8
# Your code here!
import bisect

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

zero=bisect.bisect_left(X,0)

ans=10**18
start=max(0,zero-K)
for i in range(start,start+N-K+1):
    m=min(0,X[i])
    M=max(0,X[i+K-1])
    ans=min((abs(m)+abs(M)*2),(abs(m)*2+abs(M)),ans)
    
print(ans)



### FIXED CODE ###

# coding: utf-8
# Your code here!
import bisect

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

zero=bisect.bisect_left(X,0)

ans=10**18
start=max(0,zero-K)
for i in range(start,start+N-K+1):
    #print(i)
    m=min(0,X[i])
    M=max(0,X[i+K-1])
    ans=min((abs(m)+abs(M)*2),(abs(m)*2+abs(M)),ans)
    if i+K==N:
        break
    
print(ans)
n, m = map(int, input().split())

def fib(n):
    r5 = 5**0.5
    f = 1/r5*((0.5+r5/2)**n-(0.5-r5/2)**n)
    return int(f)

a = []
for i in range(m):
    a.append(int(input()))
ans = fib(a[0])
for i in range(m-1):
    ans *= fib(a[i+1]-a[i]-1)
    ans %= 1000000007
ans *= fib(n-a[-1])
print(ans%1000000007)


### FIXED CODE ###

import sys
n, m = map(int, input().split())
a=set(int(input()) for i in range(m))
ans = [0 for _ in range(n)]

for i in range(n):
    if i+1 in a:
        ans[i] = 0
    else:
        if i == 0:
            ans[i] = 1
        elif i == 1:
            ans[i] = 1+ans[i-1]
        else:
            ans[i] = (ans[i-1]+ans[i-2])%(10**9+7)
print(ans[-1])
from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations

N = int(input())

a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

def solve(N, a):
    return a[N]

print(solve(N, a))

### FIXED CODE ###

from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations

N = int(input())

a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

def solve(N, a):
    return a[N-1]

print(solve(N, a))
import sys
def main():
    s=list(sys.stdin.readline().strip())
    n,t=len(s),0
    while len(s)>2:
        f=False
        for i in range(1,n-1):
            if s[i-1]!=s[i+1]:
                s.pop(i)
                f,t=True,t^1
                break
        if f is False:
            break
    print('First') if t==1 else print('Second')
if __name__=='__main__':main()

### FIXED CODE ###

import sys
def main():
    s=list(sys.stdin.readline().strip())
    t=0
    while len(s)>2:
        ps,cs,i,f=s[0],s[1],1,False
        for ns in s[2:]:
            if ps!=ns:
                cs,f,t=ns,True,t^1
                s.pop(i)
            else:ps,cs,i=cs,ns,i+1
        if f is False:break
    print('First') if t==1 else print('Second')
if __name__=='__main__':main()
a = input()
b = input()
print(a*b,2*(a+b))

### FIXED CODE ###

ab = input()
num_ab = ab.split()
a = int(num_ab[0])
b = int(num_ab[1])
print(a*b,2*(a+b))
def main():
    d, n = map(int, input().split())
    counter = 0
    for _ in range(n):
        x, y = map(int, input().split())
        if x**2 + y**2 <= d**2:
            counter += 1
    return print(counter)
 
main()

### FIXED CODE ###

def main():
    n, d = map(int, input().split())
    counter = 0
    for _ in range(n):
        x, y = map(int, input().split())
        if x**2 + y**2 <= d**2:
            counter += 1
    return print(counter)
 
main()
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N = INT()
    A = LIST()

    C = Counter(A)
    print(C)

    X = 0
    for v in C.values():
        X += factorial(v) // (factorial(2) * factorial(v-2))

    for i in range(N):
        print(X - C[A[i]] + 1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N = INT()
    A = LIST()

    C = Counter(A)

    X = 0
    for v in C.values():
        X += v * (v - 1) // 2

    for i in range(N):
        print(X - C[A[i]] + 1)


if __name__ == '__main__':
    main()
N,M,K = list(map(int,input().split()))

# DFSテンプレ、計算量=O(N+M)
# N:頂点の数
# M:辺の数

G = [[] for _ in range(N)]
# graphの入力
for _ in range(M):
    a,b = list(map(int,input().split()))
    G[a-1].append(b-1)
    G[b-1].append(a-1)
# print("G:",G)

KG = [[] for _ in range(N)]
# block graphの入力
for _ in range(K):
    a,b = list(map(int,input().split()))
    KG[a-1].append(b-1)
    KG[b-1].append(a-1)
# print("KG:",KG)

# ここまでエラーなし。

def dfs(G,v):
    # global l
    # nを訪問済みにする
    seen[v] = 1
    # l += 1
    # print(v+1)
    seenV.append(v)
    # vから行ける各頂点next_vについて
    for next_v in G[v]:
        if seen[next_v] == 1:
            continue
        else:
            dfs(G,next_v)

# Adj_size = [0]*N
# 全頂点を未訪問に初期化。
Adj = [[] for _ in range(N)]
seen = [0]*N
Y = []
for v in range(N):
    # l = 0
    seenV = []
    if seen[v] == 0:
        dfs(G,v)
        pass
    
        # print("dfs done !!!")
    # print("v=",v+1,"seen:",seen)
    # print("l=",l)
    # print(seenV)
    
    for sv in seenV:
        Adj[sv] = seenV
    
    # print("Adj[",v,"] :",Adj[v])
    
    # 出力
    # y = Adj_size[v] - len(G[v])-1
    y = len(Adj[v]) - len(G[v]) - 1
    for k in KG[v]:
        if k in Adj[v]:
            y += -1
    # print("v=",v+1,"y=",y)
    Y.append(str(y))

# print("ADj",Adj)
# print("Y",Y)
# print("G",G)

print(" ".join(Y))




### FIXED CODE ###

def find(x):
    if par[x]<0:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
 
def unite(x,y):
  x,y=find(x),find(y)
  if x!=y:
    if x>y:
        x,y=y,x
    par[x]+=par[y]
    par[y]=x
    
def same(x,y):
  return find(x)==find(y)
 
def size(x):
  return-par[find(x)]
 
N,M,K = map(int,input().split())
par=[-1]*N
B = [set() for _ in range(N)]
FF = [0]*N
for _ in range(M):
    a,b = map(int,input().split())
    unite(a-1,b-1)
    FF[a-1] += 1
    FF[b-1] += 1
# print(F)
for j in range(K):
    a,b = map(int,input().split())
    B[a-1].add(b-1)
    B[b-1].add(a-1)

Y = []
for i in range(N):
    y = size(i) - FF[i] -1
    for b in B[i]:
        if same(i,b):
            y += -1
    Y.append(str(y))
print(" ".join(Y))
N = int(input())
A = [int(a) for a in input().split()]

import numpy as np

mod = 10**9 + 7

def pairwise_combs_mask(a):
    a = np.array(a, dtype=np.float64)
    n = len(a)
    L = n*(n-1)//2
    out = np.empty((L,2), dtype=a.dtype)
    m = ~np.tri(len(a),dtype=bool)
    out[:,0] = np.broadcast_to(a[:,None],(n,n))[m]
    out[:,1] = np.broadcast_to(a,(n,n))[m]
    return out

comb = pairwise_combs_mask(A)

summa = 0
for c in comb:
    summa += c[0] * c[1]

print(int(summa % mod))

### FIXED CODE ###

N = int(input())
A = [int(a) for a in input().split()]

mod = 10**9 + 7

print(((sum(A)**2 - sum([i**2 for i in A]))//2) % mod)
import string
count = {x: 0 for x in string.ascii_lowercase}

s = input().lower()

for c in s:
    if 'a' <= c <= 'z':
        count[c] += 1
        
for key, num in count:
    print("{0} : {1}".format(key, num))

### FIXED CODE ###

import string

count = {x: 0 for x in string.ascii_lowercase}
lines = ''

while True:
    try:
        lines += input().lower()
    except EOFError:
        break

for c in lines:
    if 'a' <= c <= 'z':
        count[c] += 1

for key in string.ascii_lowercase:
    print("{0} : {1}".format(key, count[key]))
S = str(input())
for i in len(S):
  if S[i]==S[i+1]:
    print('Good')
    break
  else:
    print('Bad')

### FIXED CODE ###

S = str(input())

if (S[0]==S[1]) or (S[1]==S[2]) or (S[2]==S[3]):
  print('Bad')
else:
  print('Good')
a, b = map(int(input().split())
print(a * b)

### FIXED CODE ###

a, b = map(int, input().split())
print(a * b)
n = int(input())
a = sorted(list(map(int, input().split())))

# nCrにおいてrが一定の時にnが最大の時に場合の数が最大になる
# max_xCrをDPで調べればok

import numpy as np
max_a = a[-1]
max_r = a[-2]+1
dp = np.zeros(max_r)
for i in range(max_r-1):
    if i != 0:
        dp[i+1] = dp[i] * (max_a-i) // (i+1)
    else:
        dp[i+1] = max_a

idx = np.argmax(dp[a[:-1]])
print('{:d} {:d}'.format(max_a, a[idx]))


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()

import bisect
import numpy as np
amax = a[-1]
cent = amax // 2

idx = bisect.bisect_left(a, cent)
if idx == len(a)-1:
    print(amax, a[-2])
else:
    max_idx = np.argmin([abs(a[idx]-cent), abs(a[idx-1]-cent)])
    if max_idx:
        print(amax, a[idx-1])
    else:
        print(amax, a[idx])
N = int(input())
print(int(N / 2 + 0.5) / N

### FIXED CODE ###

N = int(input())
if N % 2 == 0:
       print(0.5)
else:
       print((N-int(N/2))/N)
import math
N = int(input())
a = 1
for i in range(N):
    b = int(input())
    a = a * b //math.gcd(a,b)

print(a)


### FIXED CODE ###

def gcd(a,b):
    if a % b ==0:
        return b
    return gcd(b,a%b)

N = int(input())
a = 1
for i in range(N):
    b = int(input())
    a = a * b // gcd(a,b)

print(a)
H, W = map(int, input().split())

m = []
l = []
end = 0
for i in range(H):
    h = list(input())
    m.append(h)
    for j, w in enumerate(h):
        if w == '#':
            l.append([j, i])
            end += 1
HW = H * W
ans = 0
while (end < HW):
    nl = []
    for ll in l:
        if (0 < ll[0]):
            if (m[ll[1]][ll[0] - 1] == '.'):
                m[ll[1]][ll[0] - 1] = '#'
                end += 1
                nl.append([ll[1], ll[0] - 1])

        if (ll[0] < W - 1):
            if (m[ll[1]][ll[0] + 1] == '.'):
                m[ll[1]][ll[0] + 1] = '#'
                end += 1
                nl.append([ll[1], ll[0] + 1])

        if (0 < ll[1]):
            if (m[ll[1] - 1][ll[0]] == '.'):
                m[ll[1] - 1][ll[0]] = '#'
                end += 1
                nl.append([ll[1] - 1, ll[0]])

        if (ll[1] < H - 1):
            if (m[ll[1] + 1][ll[0]] == '.'):
                m[ll[1] + 1][ll[0]] = '#'
                end += 1
                nl.append([ll[1] + 1, ll[0]])
        l = nl
    ans += 1

print(ans)


### FIXED CODE ###



H, W = map(int, input().split())

m = []
l = []
end = 0
for y in range(H):
    h = list(input())
    m.append(h)
    for x, w in enumerate(h):
        if w == '#':
            l.append([y, x])
            end += 1
HW = H * W
ans = 0
# print(m[2][0]) m[y][x]
while (end < HW):
    nl = []
    for ll in l:
        if (0 < ll[1]):
            if (m[ll[0]][ll[1] - 1] == '.'):
                m[ll[0]][ll[1] - 1] = '#'
                end += 1
                nl.append([ll[0], ll[1] - 1])

        if (ll[1] < W - 1):
            if (m[ll[0]][ll[1] + 1] == '.'):
                m[ll[0]][ll[1] + 1] = '#'
                end += 1
                nl.append([ll[0], ll[1] + 1])

        if (0 < ll[0]):
            if (m[ll[0] - 1][ll[1]] == '.'):
                m[ll[0] - 1][ll[1]] = '#'
                end += 1
                nl.append([ll[0] - 1, ll[1]])

        if (ll[0] < H - 1):
            if (m[ll[0] + 1][ll[1]] == '.'):
                m[ll[0] + 1][ll[1]] = '#'
                end += 1
                nl.append([ll[0] + 1, ll[1]])

    l = nl
    ans += 1

print(ans)
N, K = map(int, input().split())
ab_list = sorted([map(int, input().split()) for _ in range(N)])

for a, b in ab_list:
  if b >= K:
    print(a)
    exit()
  else:
    K -= b


### FIXED CODE ###

N, K = map(int, input().split())
ab_list = sorted([list(map(int, input().split())) for _ in range(N)])

for a, b in ab_list:
  if b >= K:
    print(a)
    exit()
  else:
    K -= b
class Imos:
    def __init__(self, n):
        self.B = [0] * n
        self.n = n
        from itertools import accumulate
        self.ac = accumulate

    def __call__(self, l, r):
        l, r = max(l, 0), min(r, self.n - 1)
        self.B[l] += 1
        if r + 1 != self.n:
            self.B[r + 1] -= 1

    def out(self):
        *res, = self.ac(self.B)
        return res

from collections import defaultdict
d = defaultdict(list)
imos = Imos(10 ** 5 + 1)

(N, C), *D = [[*map(int, o.split())] for o in open(0)]
for s, t, c in D:
    d[c] += (s, t),
for p in d.values():
    p.sort()
    ps, pt = p[0]
    for s, t in p[1:] + [[0,0]]:
        if pt == s:
            pt = t
        else:
            imos(ps, pt)
            ps, pt = s, t
print(max(imos.out()))

### FIXED CODE ###

n, a, b = map(int,input().split())
print(min(n*a, b))
N, M = map(int, input().split())
dic = {}
def make_map(a, b, dic):
    if a in dic.keys():
        dic[a].append(b)
    else:
        dic[a] = [b]
for m in range(M):
    a, b = map(int, input().split())
    make_map(a-1, b-1, dic)
    make_map(b-1, a-1, dic)
maplist = [0]*(N)
minlist = [10**5]*N
logs = []
def dfs(point, depth, log):
    if str(point) in log:
        logs.append(log)
        return
    if minlist[point] >= depth:
        minlist[point] = depth
        if len(log) >= 1:
            maplist[point] = int(log[-1])+1
    log+=str(point)
    depth+=1
    for p in dic[point]:
        dfs(p,depth,  log)
dfs(0,0, "")
if 0 in maplist[1:]:
    print("No")
else:
    print("Yes")
    for i in range(N-1):
        print(maplist[i+1])

### FIXED CODE ###

from collections import deque
dic = {}
def make_map(a, b, dic):
    if a in dic.keys():
        dic[a].append(b)
    else:
        dic[a] = [b]
N, M = map(int, input().split())
for m in range(M):
    a, b = map(int, input().split())
    make_map(a-1, b-1, dic)
    make_map(b-1, a-1, dic)
queue = deque([0])
count = 0
dekai = 10**5
lenlist = [dekai]*N
lenlist[0] = 0
while queue:
    a = queue.popleft()
    for i in dic[a]:
        if lenlist[i] ==dekai or a == 0:
            queue.append(i)#今までいったことないなら見るリストに追加
            lenlist[i] = a #今いる座標の距離+!が次の座標の距離
print("Yes")
for n in range(1,N, 1):
    print(lenlist[n]+1)
n, l = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
dp = [[None] * n for _ in range(n)]

Aacc = [A[0]]
for i in range(1, n):
    Aacc.append(Aacc[i - 1] + A[i])

def length(a, b):
    return Aacc[b] - (Aacc[a - 1] if a > 0 else 0)

def search(a, b):
    if dp[a][b] is None:
        if a == b:
            ans = []
        elif length(a, b) >= l:
            for cut in range(a, b):
                left = search(a, cut)
                if left is not False:
                    right = search(cut + 1, b)
                    if right is not False:
                        ans = [cut] + left + right
                        break
            else:
                ans = False
        else:
            ans = False

        dp[a][b] = ans

    return dp[a][b]

ans = search(0, n - 1)
if ans is False:
    print('Impossible')
else:
    print('Possible')
    for a in ans:
        print(a + 1)


### FIXED CODE ###

a, b = [int(x) for x in input().split()]

if a > 0:
    print('Positive')
elif a <= 0 and 0 <= b:
    print('Zero')
elif (b - a) % 2 == 0:
    print('Negative')
else:
    print('Positive')
n = int(input())
s = input()
M = 10**9 + 7

dp = [[None] * n for _ in range(n)]
def dfs(zk, i=0):
    if dp[zk][i] is not None:
        return dp[zk][i]

    if i == n - 1:
        dp[zk][i] = 1
        return 1

    zj = n - i - zk - 1
    cnt = 0

    if s[i] == "<":
        for v in range(zk):
            cnt += dfs(v, i + 1)
    else:
        for v in range(zj):
            cnt += dfs(zk + v, i + 1)
    dp[zk][i] = cnt
    return cnt

def mod(v):
    if v >= M:
        return v % M
    return v

def cumsum(array):
    array = array[:]
    for i in range(len(array) - 1):
        array[i + 1] = mod(array[i + 1] + array[i])
    return array + [0]

for i in reversed(range(n)):
    for zk in range(n):
        if i == n - 1:
            dp[i][zk] = 1
            continue

        zj = n - i - zk - 1
        cnt = 0

        if s[i] == "<":
                # cnt = mod(cnt + dp[i + 1][v])
                cnt = cs[v]
        else:
                # cnt = mod(cnt + dp[i + 1][zk + v])
                cnt = cs[zk + zj - 1] - cs[zk - 1]
        dp[i][zk] = cnt
    cs = cumsum(dp[i])

# for i in range(n):
#     print(dfs(i))
# print(sum(dfs(i) for i in range(n - 1)) % M)
print(sum(dp[0]) % M)


### FIXED CODE ###

n = int(input())
s = input()
M = 10**9 + 7

def mod(v):
    if v >= M:
        return v % M
    return v


dp = [[1] * n + [0] for _ in range(2)]
s = [v == "<" for v in s]
for i in reversed(range(n - 1)):
    for j in range(n - 1):
        dp[1][j + 1] = dp[1][j + 1] + dp[1][j]
        dp[0][j] = dp[1][j]
    dp[0][-2] = dp[1][-2]

    for zk in range(n - i):
        cnt = 0

        if s[i]:
            cnt = dp[0][zk - 1]
        else:
            zj = n - i - zk - 1
            cnt = dp[0][zk + zj - 1] - dp[0][zk - 1]
        dp[1][zk] = mod(cnt)

print(sum(dp[1]) % M)
def sol(i,want):
    num=N//(i+1)
    wa=A[i]

    for j in range(num):
        wa+=A[(i+1)+j*(i+1)-1]
#         print(i+j*i)
#     print(i,wa,A[i])
    wa=wa%2
#     print(i,wa,A[i])
    
    if wa==want:
        x=0
    else:
        x=1
#     print(num)
    return x 

B=A[:]
half=N//2
for i in range(half):
    j=half-1-i
#     print(sol(j,A[j]))
    B[j]=sol(j,A[j])
    
C=[i+1 for i, x in enumerate(B) if x ==1]

m=sum(B)
print(m)
print(*C)

### FIXED CODE ###

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




def sol(i,want):
    num=N//(i+1)
    wa=B[i]

    for j in range(num):
        k=i+j*(i+1)
        wa+=B[k]
#         print(i,wa,B[i])
#         print((i+1)+j*(i+1)-1)
#     print(i,wa,B[i])
    wa=wa%2
#     print(i,wa,A[i])
    
    if wa==want:
        x=0
    else:
        x=1
#     print(num)
    return x 

B=A[:]
half=N//2
for i in range(half):
    j=half-1-i
#     print(j)
    B[j]=sol(j,A[j])
    
C=[i+1 for i, x in enumerate(B) if x ==1]

m=sum(B)
print(m)
print(*C)
n = int(input)
print(n*(n-1)//2)

### FIXED CODE ###

N = int(input())

if N % 2 == 0:
    print((N-1)*N//2)
else:
    print(N*(N-1)//2)
N = int(input())
print(0.5*n*(n+1))

### FIXED CODE ###

N = int(input())
print(int(0.5*N*(N+1)))
import sys
input = sys.stdin.readline

n, m, l = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(m)]
q = int(input())

st = [list(map(int, input().split())) for _ in range(q)]

graph = [[float('inf') for _ in range(n)] for _ in range(n)]


for a, b, c in abc:
    graph[a-1][b-1] = c 
    graph[b-1][a-1] = c
for i in range(n):
    graph[i][i] = 0

# print(graph)

def warshall_floyd(graph):
    d = graph.copy()
    for i in range(n):
        for j in range(n):
            for k in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

graph = warshall_floyd(graph)

for i in range(n):
    for j in range(n):
        if 0 < graph[i][j] <= l:
            graph[i][j] = 1
        if graph[i][j] > l:
            graph[i][j] = float('inf')

graph = warshall_floyd(graph)

for s, t in st:
    print(graph[s-1][t-1]-1 if graph[s-1][t-1] != float('inf') else -1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
 
n, m, l = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(m)]
q = int(input())
 
st = [list(map(int, input().split())) for _ in range(q)]
 
graph = [[float('inf') for _ in range(n)] for _ in range(n)]
 
 
for a, b, c in abc:
    graph[a-1][b-1] = c 
    graph[b-1][a-1] = c
for i in range(n):
    graph[i][i] = 0
 
# print(graph)
 
def warshall_floyd(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
 
graph = warshall_floyd(graph)
 
for i in range(n):
    for j in range(n):
        if 0 < graph[i][j] <= l:
            graph[i][j] = 1
        if graph[i][j] > l:
            graph[i][j] = float('inf')
 
graph = warshall_floyd(graph)
 
for s, t in st:
    print(graph[s-1][t-1]-1 if graph[s-1][t-1] != float('inf') else -1)