Harryxun/stf_run huggingface dataset:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def gindex(l, r):
    L = l + N0; R = r + N0
    lm = (L // (L & -L)) >> 1
    rm = (R // (R & -R)) >> 1
    while L < R:
        if R <= rm:
            yield R
        if L <= lm:
            yield L
        L >>= 1; R >>= 1
    while L:
        yield L
        L >>= 1
 
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if v is None:
            continue
        lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
        lazy[i-1] = None
 
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)
 
    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] = data[R-1] = x
        if L & 1:
            lazy[L-1] = data[L-1] = x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])
 
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r
 
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s


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

N=1000000000
INF = 2**31-1
 
LV = (N-1).bit_length()
N0 = 2**LV
data = [INF]*(2*N0)
lazy = [None]*(2*N0)
 

a=[list(map(int,input().split())) for i in range(n)]
a.sort(key=lambda x:x[2],reverse=True)

a=[ [ max(0,a[i][0]-a[i][2]) , max(0,a[i][1]-a[i][2]) , a[i][2] ] for i in range(n)]

for i in range(n):
    l,r,x=a[i][0],a[i][1],a[i][2]
    update(l,r,x)

for i in range(Q):
    dp=int(input())
    ans=query(dp,dp+1)
    print(-1 if ans==INF else ans)

### FIXED CODE ###

def main():
    from heapq import heappush, heappop
    import sys
    sys.setrecursionlimit(10 ** 7)

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

    event=[]
    for _ in range(n):
        s,t,x=map(int,input().split())
        event.append((s-x,1,x))
        event.append((t-x,-1,x))

    for i in range(q):
        event.append((int(input()),2,i))
    event.sort()

    ans=[0]*q

    stop=set()
    hq=[]
    for t,op,x in event:
        if op==1:
            heappush(hq,x)
            stop.add(x)
        elif op==-1:
            stop.remove(x)

        else:
            while hq and hq[0] not in stop:
                heappop(hq) 
            ans[x]=hq[0] if hq else -1
        
    for x in ans:
        print(x)

main()
mport sys
from collections import deque

stack = deque()
input = sys.stdin.readline

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

link = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    link[a - 1].append(b)
    #link[b - 1].append(a)
    
states = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    states[p - 1] += x

check = [0] * N
stack.append(1)
check[0] = 1
while stack:
    node = stack.pop()
    for next_node in link[node - 1]:
        if check[next_node - 1]:
            continue
        states[next_node - 1] += states[node - 1]
        check[next_node - 1] = 1
        stack.append(next_node)

# Output
print(*states)


### FIXED CODE ###

import sys
from collections import deque

stack = deque()
input = sys.stdin.readline

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

link = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    link[a - 1].append(b)
    link[b - 1].append(a)
    
states = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    states[p - 1] += x

check = [0] * N
stack.append(1)
check[0] = 1
while stack:
    node = stack.pop()
    for next_node in link[node - 1]:
        if check[next_node - 1]:
            continue
        states[next_node - 1] += states[node - 1]
        check[next_node - 1] = 1
        stack.append(next_node)

# Output
print(*states)
A, B, C = map(int, input().split())
list = [A, B, C]
if list.sort() == [5, 5, 7]:
  return 'Yes'
else:
  return 'No'

### FIXED CODE ###

L = sorted(map(int, input().split()))
 
ans = 'YES' if L == [5, 5, 7] else 'NO'
print(ans)
from sys import stdin
from itertools import repeat
from collections import deque
def main():
    n, m = map(int, stdin.readline().split())
    dat = map(int, stdin.read().split(), repeat(10, 2 * m))
    deg = [0] * n
    la = [None] * n
    xt = [0] * (2 * n)
    for i in xrange(m):
        ui = i * 2
        vi = i * 2 + 1
        u = dat[ui] - 1
        v = dat[vi] - 1
        deg[u] += 1
        deg[v] += 1
        xt[vi] = la[u]
        la[u] = vi
        xt[ui] = la[v]
        la[v] = ui
    so = tr = lo = 0
    q = []
    done = [0] * n
    pu = q.append
    po = q.pop
    for i in xrange(n):
        if done[i]:
            continue
        pu(i)
        done[i] = 1
        nu = [i]
        while q:
            x = po()
            y = la[x]
            while y is not None:
                z = dat[y] - 1
                if not done[z]:
                    done[z] = 1
                    pu(z)
                    nu.append(z)
                y = xt[y]
        sd = 0
        for x in nu:
            sd += deg[x]
        if sd == 0:
            so += 1
        elif sd == len(nu) * 2 - 2:
            tr += 1
        else:
            lo += 1
    print lo * lo + lo * tr * 2 + tr * tr * 2 + so * n * 2 - so * so
main()


### FIXED CODE ###

from sys import stdin
from itertools import repeat
from collections import deque
def main():
    n, m = map(int, stdin.readline().split())
    dat = map(int, stdin.read().split(), repeat(10, 2 * m))
    deg = [0] * n
    la = [None] * n
    xt = [0] * (2 * m)
    for i in xrange(m):
        ui = i * 2
        vi = i * 2 + 1
        dat[ui] -= 1
        dat[vi] -= 1
        u = dat[ui]
        v = dat[vi]
        deg[u] += 1
        deg[v] += 1
        xt[vi] = la[u]
        la[u] = vi
        xt[ui] = la[v]
        la[v] = ui
    so = tr = lo = 0
    q = deque()
    done = [0] * n
    pu = q.append
    po = q.popleft
    for i in xrange(n):
        if done[i]:
            continue
        pu(i)
        done[i] = 1
        nu = [i]
        while q:
            x = po()
            y = la[x]
            while y is not None:
                z = dat[y]
                if not done[z]:
                    done[z] = 3 - done[x]
                    pu(z)
                    nu.append(z)
                y = xt[y]
        sd = 0
        pa = 0
        for x in nu:
            sd += deg[x]
            y = la[x]
            while y is not None:
                z = dat[y]
                if done[x] == done[z]:
                    pa = 1
                y = xt[y]
        if sd == 0:
            so += 1
        elif pa:
            lo += 1
        else:
            tr += 1
    print lo * lo + lo * tr * 2 + tr * tr * 2 + so * n * 2 - so * so
main()
A=int(input())
B=int(input())
if A+B>=A-B and A+B>=A*B:
  print(A+B)
elif A-B>=A+B and A-B>=A*B:
  print(A-B)
else A*B>=A+B and A*B>=A-B:
  print(A*B)

### FIXED CODE ###

A,B=map(int,input().split())
print(max(A+B,A-B,A*B))
age = int(input())
fee = int(input())

if age <= 6:
    print(0)
elif 6 <= age and age <= 12:
    print(fee/2)
elif 13 <= age:
    print(fee)

### FIXED CODE ###

age, fee= map(int, input().split())

if age <= 5:
    print(0)
elif 6 <= age and age <= 12:
    print(int(fee/2))
elif 13 <= age:
    print(fee)
import sys
input = sys.stdin.readline
import math
 
def INT(): return int(input())
def MAPINT(): return map(int, input().split())
def LMAPINT(): return list(map(int, input().split()))
def STR(): return input()
def MAPSTR(): return map(str, input().split())
def LMAPSTR(): return list(map(str, input().split()))
 
f_inf = float('inf')
 
n = INT()
a = sorted(LMAPINT())

ans = [True] * n
for i in range(int(math.sqrt(n))+1):
  if ans[i] is False:
    continue
  for j in range(i+1, n):
    if a[j] % a[i] == 0:
      ans[j] = False
    if a[j] == a[i]:
      ans[i], ans[j] = False, False
 
print(ans.count(True))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
 
xs = [0] * (max(a) + 1)
 
for v in a:
    if xs[v] == 0:
        for j in range(v, len(xs), v):
            xs[j] += 1
    else:
        xs[v] += 1
print(len(list(filter(lambda v: xs[v] == 1, a))))
max = 0
i = 0
j = 0
k = 0
n_max = 7

price = []
for k in range(n_max):
    price.attend(int(raw_input())
    
for i in range(n_max)
    for j in range(k, n_max)
        if max <= price[j] - price[i]:
            max = price[j] - price[i]
print max

### FIXED CODE ###

import sys

n = int(raw_input())

min_R = int(raw_input())
nums = map(int, sys.stdin.readlines())

ans = -10**9

for num in nums:
    if num - min_R > ans:
        ans = num - min_R
    if num < min_R:
        min_R = num
        
print ans
S = list(input())
res = len(S)
kind_all = set(S)
for i in kind_all:
    temp = S.split(i)
    cnt = 0
    for j in temp:
        cnt = max(cnt,len(j))
    res = min(res,cnt)
print(res)

### FIXED CODE ###

S = input()
res = len(S)
kind_all = set(S)
for i in kind_all:
    temp = S.split(i)
    cnt = 0
    for j in temp:
        cnt = max(cnt,len(j))
    res = min(res,cnt)
print(res)
from collections import defaultdict
N, K = map(int, input().split())
a_bs = [tuple(map(int, input().split())) for _ in range(N - 1)]

def search_tree(t, queue):
    if tree[t][1]:
        return -1
    tree[t][1] = True
    global sum_
    k = K - sum(queue)
    sum_ = (sum_ * k) % (10**9 + 7)
    queue[0] = queue[1]
    queue[1] = 1
    for next_ in tree[t][0]:
        queue[0] += search_tree(next_, queue[:])
        queue[0] += 1
    return 0


tree = defaultdict(lambda: [[], False])
for a, b in a_bs:
    tree[a][0].append(b)
    tree[b][0].append(a)

sum_ = 1
search_tree(1, [0, 0])
print(sum_)

### FIXED CODE ###

import sys
from collections import defaultdict

sys.setrecursionlimit(10**5)

N, K = map(int, input().split())
a_bs = [tuple(map(int, input().split())) for _ in range(N - 1)]

def culc_tree(t, used_num):
    tree[t][1] = False
    global answer
    k = K - used_num
    answer = (answer * k) % (10 ** 9 + 7)
    childs = [next_ for next_ in tree[t][0] if tree[next_][1]]
    for i, child in enumerate(childs, 2):
        culc_tree(child, i)


tree = defaultdict(lambda: [[], True])
for a, b in a_bs:
    tree[a][0].append(b)
    tree[b][0].append(a)

answer = K
tree[1][1] = False
for i, child in enumerate(tree[1][0], 1):
    culc_tree(child, i)
print(answer)
import math
while 1:
    e = int(input().strip())
    if e ==0:break
    m=e
    for z in range(e):
        for y in range(int(math.sqrt(e))):
            x = e - y**2 - z**3 
            if x < 0:break
            if m > x+y+z: m = x+y+z
    print(m)


### FIXED CODE ###

import math
while 1:
    e = int(input().strip())
    if e ==0:break
    m=e
    z =0
    while z**3 <= e:
        y = int(math.sqrt(e-z**3))
        x = e - y**2- z**3 
        if x < 0:break
        if m > x+y+z: m = x+y+z    
        z+=1
    print(m)
N=int(inpiut())
L=list(map(int,input().split()))
ans=0
for i in range(N-2):
    for j in range(i,N-1):
        for k in range(j,N):
            if L[i]<L[j]+L[k] and L[j]<L[i]+L[k] and L[k]<L[i]+L[j]:
                ans+=1
print(ans)


### FIXED CODE ###

from bisect import bisect_left
N=int(input())
L=list(map(int,input().split()))

L.sort()
result=0
for i in range(N-2):
    for j in range(i+1,N-1):
        result+=bisect_left(L,L[i]+L[j])-j-1
print(result)
print(sum(sorted(input().split())[:2]))

### FIXED CODE ###

print(sum(sorted(list(map(int, input().split())))[:2]))
input()
S = raw_input().split()
input()
T = raw_input().split()
print len(S & T)

### FIXED CODE ###

input()
S = set(raw_input().split())
input()
T = set(raw_input().split())
print len(S & T)
n = int(input())
a - int(input())
print(n**2-a)

### FIXED CODE ###

n = int(input())
a = int(input())
print(n**2-a)
import math
#from scipy.special import comb
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def groupby(a):
    a2=[[a[0],1]]
    for i in range(1,len(a)):
        if a2[-1][0]==a[i]:
            a2[-1][1]+=1
        else:
            a2.append([a[i],1])
    return a2

N,A,B=map(int,input().split())
v=[int(i) for i in input().split()]
v.sort(reverse=True)
v=groupby(v)

if A<=v[0][1]:
    #こっちが間違ってる
    m=min(v[0][1],B)
    co=2**m
    for i in range(A):
        co-=combinations_count(m,i)
    print(v[0][0])
    print(co)
    if A==m:
        r
else:
    al=0
    l=len(v)
    C=0
    for i in range(l):
        C+=v[i][1]
        if C<=A:
            al+=(v[i][0]*v[i][1])
        else:
            C-=v[i][1]
            al+=(v[i][0]*(A-C))
            k=combinations_count(v[i][1],A-C)
            break
    print(al/A)
    print(k)


### FIXED CODE ###

import math
#from scipy.special import comb
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def groupby(a):
    a2=[[a[0],1]]
    for i in range(1,len(a)):
        if a2[-1][0]==a[i]:
            a2[-1][1]+=1
        else:
            a2.append([a[i],1])
    return a2

N,A,B=map(int,input().split())
v=[int(i) for i in input().split()]
v.sort(reverse=True)
v=groupby(v)

if A<=v[0][1]:
    #こっちが間違ってる
    m=min(v[0][1],B)
    co=0
    for i in range(A,m+1):
        co+=combinations_count(v[0][1],i)
    print(v[0][0])
    print(co)
else:
    al=0
    l=len(v)
    C=0
    for i in range(l):
        C+=v[i][1]
        if C<=A:
            al+=(v[i][0]*v[i][1])
        else:
            C-=v[i][1]
            al+=(v[i][0]*(A-C))
            k=combinations_count(v[i][1],A-C)
            break
    print(al/A)
    print(k)
K=int(input())
A,B=map(int,input().split())
a=0
for i in range(A,B+1):
  if i%k==0:
    a=1
if a==1:
  print("OK")
else:
  print("NG")
    


### FIXED CODE ###

K=int(input())
A,B=map(int,input().split())
a=0
for i in range(A,B+1):
  if i%K==0:
    a=1
if a==1:
  print("OK")
else:
  print("NG")
N = int(input())
arr = []
for i in range(N):
  arr.append(int(input()))
c = 0
col_min = []

for i in range(N-1, -1, -1):
  if i == N-1:
    col_min.append(arr[i])
    c += 1
  else:
    check = 0
    for k, v in enumerate(col_min):
      if v > arr[i]
      	col_min[k] = arr[i]
        check = 1
        break
    if check == 0:
      col_min.append(arr[i])
      c += 1
print(c)
        

### FIXED CODE ###

import bisect
N = int(input())
arr = [int(input()) for i in range(N)]
dp = [-1 for _ in range(N)]
for i in arr:
    dp[bisect.bisect_left(dp, i) - 1] = i
print(sum([i >= 0 for i in dp]))
N, M = map(int, input().split())
dp = [0 for _ in range(N+1)]
skip = []

for _ in range(M):
    skip.append(int(input()))

dp[1] = 1
dp[2] = 2

if 1 in skip:
    dp[1] = 0
    dp[2] = 1
if 2 in skip:
    dp[2] = 0

for i in range(3, N+1):
    if i in skip:
        continue
    else:
        dp[i] = (dp[i-1] + dp[i-2]) % 1000000007

print(dp[N])


### FIXED CODE ###

N, M = map(int, input().split())
dp = [0 for _ in range(N+1)]
skip = {}

for _ in range(M):
    skip[int(input())] = 1

dp[0] = 1
if 1 not in skip:
    dp[1] = 1

for i in range(2, N+1):
    if i in skip:
        continue
    dp[i] += (dp[i-1] + dp[i-2]) % 1000000007

print(dp[N])
INPUT = [input() for i in range(2)]
INPUT = list(map(int, INPUT))

def check_even(l):
    return sum([i % 2 for i in INPUT]) == 0

check_even(INPUT)

count = 0
while True:
    if check_even(INPUT):
        INPUT = [i / 2 for i in INPUT]
        count+=1
    else:
        break
print(count)

### FIXED CODE ###

_ = input()
INPUT = list(map(int, input().split()))

def check_even(l):
    return sum([i % 2 for i in INPUT]) == 0

check_even(INPUT)

count = 0
while True:
    if check_even(INPUT):
        INPUT = [i / 2 for i in INPUT]
        count+=1
    else:
        break
print(count)
b = []
for i in range(3):
  lst = list(map(int,input().split()))
  b.append(lst)
n = int(input())
for i in range(n):
  a = int(input())
  for j in range(3):
    for k in range(3):
      if (b[j][k] == a):
        b[j][k] = 0
if (b[0][0] = b[0][1] = b[0][2] or b[1][0] = b[1][1] = b[1][2] or b[2][0] = b[2][1] = b[2][2] or b[0][0] = b[1][0] = b[2][0] or b[0][1] = b[1][1] = b[2][1] or b[0][2] = b[1][2] = b[2][2] or b[0][0] = b[1][1] = b[2][2] or b[0][2] = b[1][1] = b[2][0]):
  print("Yes")
else:
  print("No")
  

### FIXED CODE ###

b = []
for i in range(3):
  lst = list(map(int,input().split()))
  b.append(lst)
n = int(input())
for i in range(n):
  a = int(input())
  for j in range(3):
    for k in range(3):
      if (b[j][k] == a):
        b[j][k] = 0
if (b[0][0] == b[0][1] == b[0][2] or b[1][0] == b[1][1] == b[1][2] or b[2][0] == b[2][1] == b[2][2] or b[0][0] == b[1][0] == b[2][0] or b[0][1] == b[1][1] == b[2][1] or b[0][2] == b[1][2] == b[2][2] or b[0][0] == b[1][1] == b[2][2] or b[0][2] == b[1][1] == b[2][0]):
  print("Yes")
else:
  print("No")
a=input()
a[3]='8'
print(a)

### FIXED CODE ###

a=input()

print(a[:3]+'8'+a[4:])
n = int(input())
a = list(map(int,input().split()))
a.sort()
b = [2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 
     131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 
     67108864, 134217728, 268435456, 536870912]

t = []
bIdx = 0
for aa in a :
    while b[bIdx] <= aa:
        bIdx += 1   
    t.append(b[bIdx]-aa)

t.reverse()
a.sort(reverse=True)

sum = 0
i = 0

#print(t,a)

while True:
    
    for j in range(i+1,len(a)):
        if a[j] == t[i] :
            sum += 1
            a.pop(j)

    i = i + 1
    if i >= len(a)-1:
        break

print(sum)

### FIXED CODE ###

from bisect  import bisect_left

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

sum = 0
for i in range (len(a)-1,-1,-1):

    b = 1
    while b <= a[i]:
        b = b<<1
    t = b - a[i]
    #print("2^",t)

    k = bisect_left(a,t)
    if a[k] == t and k < i:
        sum += 1
        a[k] -= 0.1
        a[i] += 0.1
print(sum)
# ソートが悪かったりします？
N, Q = map(int, input().split())
ab = [[0, 0]] * (N - 1)
for i in range(N - 1):
    ab[i] = list(map(int, input().split()))
# ab = sorted(ab, key=lambda x: x[0])
px = [[0, 0]] * (N - 1)
for i in range(Q):
    px[i] = list(map(int, input().split()))
# px = sorted(px, key=lambda x: x[0])
nodes = [0] * (N)
for p, x in px:
    nodes[p - 1] += x
for a, b in ab:
    nodes[b - 1] += nodes[a - 1]
print(' '.join(map(str, nodes)))


### FIXED CODE ###

N,Q = map(int,input().split())
parents = {1:0}
for _ in range(N-1):
    a,b = map(int,input().split())
    key,val = max(a,b), min(a,b)
    parents[key] = val
counts = [0]*(N+1)
for _ in range(Q):
    p,x = map(int,input().split())
    counts[p] += x
results = [0]*(N+2)
for i in range(1,N+1):
    results[i] = counts[i]+results[parents[i]]
    print(results[i], end=' ')
from collections import deque
import sys
input = sys.stdin.readline
h,w=map(int, input().split(' '))
a = [input() for i in range(h)]
q = deque()
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            a[i][j] = 0
            q.append([i,j,0])
        else:
            a[i][j] = -1
while q:
    [s,t,cnt] = q.popleft()
    if s>0 and nl[s-1][t] == -1:
        q.append([s-1,t,cnt+1])
        a[s-1][t] = cnt+1
    if s<h-1 and nl[s+1][t] == -1:
        q.append([s+1,t,cnt+1])
        a[s+1][t] = cnt+1
    if t>0 and nl[s][t-1] == -1:
        q.append([s,t-1,cnt+1])
        a[s][t-1] = cnt+1
    if t<w-1 and nl[s][t+1] == -1:
        q.append([s,t+1,cnt+1])
        a[s][t+1] = cnt+1
ans = 0
for i in range(h):
    ans = max(ans,max(a[i]))
print(ans)

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
h,w=map(int, input().split(' '))
a = [input() for i in range(h)]
nl = [[] for i in range(h)]
q = deque()
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            nl[i].append(0)
            q.append([i,j,0])
        else:
            nl[i].append(-1)
while q:
    [s,t,cnt] = q.popleft()
    if s>0 and nl[s-1][t] == -1:
        q.append([s-1,t,cnt+1])
        nl[s-1][t] = cnt+1
    if s<h-1 and nl[s+1][t] == -1:
        q.append([s+1,t,cnt+1])
        nl[s+1][t] = cnt+1
    if t>0 and nl[s][t-1] == -1:
        q.append([s,t-1,cnt+1])
        nl[s][t-1] = cnt+1
    if t<w-1 and nl[s][t+1] == -1:
        q.append([s,t+1,cnt+1])
        nl[s][t+1] = cnt+1
ans = 0
for i in range(h):
    ans = max(ans,max(nl[i]))
print(ans)
k = input()
if k[0] == k[1] or k[1] ==k[2] or k[2]==k[3]:
    print("Yes")
else:
    print("No")
   


### FIXED CODE ###

N = input()
if '7' in str(N):
    print('Yes')
else:
    print('No')
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
INF = 10**12
N, M, L = map(int, input().split())

A = []; B = []; C = []
for i in range(M):
    a, b, c = map(int, input().split())
    A.append(a - 1); B.append(b - 1); C.append(c)
A = np.array(A); B = np.array(B); C = np.array(C)

graph = csr_matrix((C, (A, B)), (N, N))
d = floyd_warshall(graph, directed=False)

d[0 < d <= L] = 1
#d[d > L] = INF

d = floyd_warshall(d, directed=False)

Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    if d[s - 1][t - 1] != 0:
        print(int(d[s - 1][t - 1]) - 1)
    else:
        print(- 1)

### FIXED CODE ###

import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
INF = 10**12
N, M, L = map(int, input().split())

A = []; B = []; C = []
for i in range(M):
    a, b, c = map(int, input().split())
    A.append(a - 1); B.append(b - 1); C.append(c)
A = np.array(A); B = np.array(B); C = np.array(C)

graph = csr_matrix((C, (A, B)), (N, N))
d = floyd_warshall(graph, directed=False)

d[d <= L] = 1
d[d > L] = INF

d = floyd_warshall(d, directed=False)

Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    if d[s - 1][t - 1] != INF:
        print(int(d[s - 1][t - 1]) - 1)
    else:
        print(- 1)
import sys
sys.setrecursionlimit(5000)
MOD=998244353
def dfs(d,tot,num):
    global A,N,S,how
    if tot==S:
        how[num]+=1
        return
    if d==N:
        return
    if d>0 and A[d]==A[d-1]:
    if tot+A[d]<=S:
        dfs(d+1,tot+A[d],num+1)
        dfs(d+1,tot,num)
        
    

N,S=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
how=[0]*(N+1)
dfs(0,0,0)
cur=1
res=0
for i in range(N,0,-1):
    res+=(how[i]*cur)%MOD
    cur=cur*2%MOD
print(res)

### FIXED CODE ###

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

def f(N,S,A):
    MOD=998244353
    dp=[0]*(S+1)
    dp[0]=pow(2,N,MOD)
    div=pow(2,MOD-2,MOD)
    m=0
    for a in A:
        m+=a
        for i in range(min(m,S),a-1,-1):
            dp[i]=(dp[i]+dp[i-a]*div)%MOD
    return dp[S]

print(f(N,S,A))
def extract(string, i):
    split = "".join(string.split("01")).split("10")
    i += len(split) - 1
    split_concat = "".join(split)
    if "01" in split_concat or "10" in split_concat:
        return extract(split_concat, i)
    else:
        return i * 2

S = input()
print(extract(S,0))


### FIXED CODE ###

S = input()

print(min(S.count('0'), S.count('1')) * 2)
import math

N, X = map(int, input().split())
arr = [int(_) for _ in input().split(' ')]

a = 1000000000000000

for i in range(N):
    for j in range(N):
        if math.gcd(abs(arr[i] - X), abs(arr[j] - X)) < a:
            a = math.gcd(abs(arr[i] - X), abs(arr[j] - X))

print(a)

### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

N, X = map(int, input().split())
x = [int(_) for _ in input().split(' ')]

dist = [abs(i - X) for i in x]

ans = dist[0]

for i in range(N-1):
    ans = gcd(ans, dist[i+1])

print(ans)
s = input()
l = len(s)
h = l // 2
lis1 = []
lis2 = []
for i in range(0, l + 1):
  lis1.append(s[i])
  lis2.append(s[-(i + 1)])
count = 0
for a, b in zip(lis1, lis2):
  if a != b:
    count += 1
print(count)

### FIXED CODE ###

s = input()
l = len(s)
h = l // 2
lis1 = []
lis2 = []
for i in range(0, h):
  lis1.append(s[i])
  lis2.append(s[-(i + 1)])
count = 0
for a, b in zip(lis1, lis2):
  if a != b:
    count += 1
print(count)
n = int(input())
h = [int(i) for i in input().split()]
if h[j+1] - h[j] < -1 for j in range(n):
  print("No")
elif h[k+2] < h[k+1] and h[k+1] <= h[k] for k in range(n-1):
  print("No")
else:
  print("Yes")


### FIXED CODE ###

n = int(input())
h = [int(i) for i in input().split()]
for j in range(n-1):
  if h[j] - h[j+1] > 1:
    print("No")
    exit()
  elif h[j] == h[j+1] + 1:
    h[j+1] += 1
print("Yes")