Harryxun/stf_run huggingface dataset:
import sys
input = sys.stdin.buffer.readline
MOD = 10**9 + 7
N, K = map(int, input().split())
A = list(map(int, (input().split())))
ap = []
neg_cnt = 0
zero_cnt = 0
for a in A:
    if a<0:
        ap.append((-a, 1))
        neg_cnt += 1
    elif a==0:
        ap.append((0, 0))
        zero_cnt += 1
    else:
        ap.append((a, -1))
ap.sort(reverse=True)
# print(ap)
ans = 1
if neg_cnt==N and K%2:      # 全てが負で奇数個選ぶので、答えは負
    for i in range(K):
        ans *= ap[N-i-1][0] * ap[N-i-1][1] * -1
        ans %= MOD
else:                       # 答えは正
    neg_num = 0
    for i in range(K):
        if ap[i][1] == 1:
            neg_num += 1
    if neg_num % 2:     # 負の数が奇数だったら、-1して偶数回にし、K+1個見る
        neg_num -= 1
        K += 1
    for i in range(K):
        if ap[i][1] == 1:  # 負の数だったら、neg_num回まで
            if neg_num == 0:
                continue
            else:
                neg_num -= 1
        ans *= ap[i][0] * ap[i][1] * -1
        ans %= MOD

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
MOD = 10**9 + 7
N, K = map(int, input().split())
A = list(map(int, (input().split())))
pos, neg = [], []
for a in A:
    if a<0:
        neg.append(a)   # 負
    else:
        pos.append(a)   # 0以上
if pos:
    if N==K:    # 全て選択で負の数が奇数ならfalse（正にできない）
        ok = (len(neg)%2 == 0)
    else:
        ok = True
else:
    ok = (K%2 == 0) # すべて負で奇数ならfalse（正にできない）
ans = 1
if ok == False: # false（正にできない）場合、絶対値が小さいものからk個かける
    A.sort(key=abs)
    for i in range(K):
        ans *= A[i]
        ans %= MOD
else:
    pos.sort()              # 後ろから取っていくので正は昇順
    neg.sort(reverse=True)  # 後ろから取っていくので負は降順
    if K%2:
        ans *= pos.pop()    # kが奇数個なら1個は正を選ぶ
    p = []  # 2個ずつかけた数を格納
    while len(pos)>=2:
        p.append(pos.pop() * pos.pop())
    while len(neg)>=2:  # 負を2回かけるのでxは正
        p.append(neg.pop() * neg.pop())
    p.sort(reverse=True)
    for i in range(K//2):   # 降順にk//2個見ていく
        ans *= p[i]
        ans %= MOD
print(ans)
n=int(input())

count=0
c_list=[]
for i in range(n):
    d1, d2=map(int, input().split())
    if d1==d2:
        count+=1
        c_list.append(count)
    else:
        count=0
        
if max(c_list)>=3:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

n=int(input())

count=0
c_list=[1]

for i in range(n):
    d1, d2=map(int, input().split())
    if d1==d2:
        count+=1
        c_list.append(count)
        #print(c_list)
    else:
        count=0
        
if max(c_list)>=3:
    print("Yes")
else:
    print("No")
import math

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

# 最小公倍数を求める
l = (N * M) // math.gcd(N, M)

ans = {1: S[0]}
for i in range(1, N):
    c_num = i*l//N+1
    ans[c_num] = S[i]

for i in range(M):
    if i == 1:
        if ans[1] != T[0]:
            print(-1)
            exit(0)

    c_num = i*l//M+1
    if c_num in ans:
        if ans[c_num] != T[i]:
            print(-1)
            exit(0)
    else:
        ans[c_num] = T[i]
print(l)


### FIXED CODE ###

import fractions

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

# 最小公倍数を求める
l = (N * M) // fractions.gcd(N, M)

ans = {1: S[0]}
for i in range(1, N):
    c_num = i*l//N+1
    ans[c_num] = S[i]

for i in range(M):
    if i == 1:
        if ans[1] != T[0]:
            print(-1)
            exit(0)

    c_num = i*l//M+1
    if c_num in ans:
        if ans[c_num] != T[i]:
            print(-1)
            exit(0)
    else:
        ans[c_num] = T[i]
print(l)
N,C,K = map(int,input().split())
T = []
for i in range(N):
  L.append(int(input()))
  
ans = 1
T = sorted(T)
ind = 0

for i in range(T):
    if T[i] > T[ind]+K:
        ans += 1
        ind = i
    elif i >= ind + C:
        ans += 1
        ind = i
    
print(ans)

### FIXED CODE ###

N,C,K=map(int,input().split())
T=[]
for i in range(N):
    p=int(input())
    T.append(p)
  
ans = 1
T = sorted(T)
ind = 0
 
for i in range(len(T)):
    if T[i] > T[ind]+K:
        ans += 1
        ind = i
    elif i >= ind + C:
        ans += 1
        ind = i
print(ans)
while True:	
	H,W = map(int, input().split())
	if H==0 and W==0: break
	for y in range(0,H):
		for x in range(0,W):
			print("#",end="")
	    print('\n')
    print()


### FIXED CODE ###

while True:	
	H,W = map(int, input().split())
	if H==0 and W==0: break
	for y in range(0,H):
		for x in range(0,W):
			print("#",end="")
			
		print()
	print()
a = [int(i) for i in input().split()]
f = lambda x: max(0,x-x%2)
print(max(a[1]+f(a[0])+f(a[3])+f(a[4]),a[1]+f(a[0]-1)+f(a[3]-1)+f(a[4]-1)+3))

### FIXED CODE ###

x,y = (int(i) for i in input().split())
if abs(x)>abs(y):
	if x<0 and y<=0: answer = y-x
	elif (x<0 and y>0) or (x>0 and y<=0): answer = abs(x)-abs(y)+1
	elif x>0 and y>0: answer = abs(x)-abs(y)+2
elif abs(x)==abs(y): answer = 1
elif abs(x)<abs(y):
	if x>=0 and y>0: answer = y-x
	elif (x>=0 and y<0) or (x<0 and y>0): answer = abs(y)-abs(x)+1
	elif x<0 and y<0: answer = abs(y)-abs(x)+2
print(answer)
n=input()
if n==1:
  print("Hello World")
else:
  a=input()
  b=input()
  print(a+b)


### FIXED CODE ###

n=input()
if int(n) == 1:
  print("Hello World")
else:
  a=input()
  b=input()
  print(int(a)+int(b))
n = input()
A = map( int , raw_input().split() )
q = input()
mi = map( int , raw_input().split() )

def solve(i, m)
  if m == 0:
    return True
  if i >= n:
    return False
res = solve( i+1 , m ) or solve( i+1 , m-A[i] )
return res

for m in mi
  if solve( 0 , m ):
    print 'yes'
  else:
    print 'no'
   

### FIXED CODE ###

n = input()
A = map( int , raw_input().split() )
q = input()
mi = map( int , raw_input().split() )

def solve(i, m):
  if m == 0:
    return True
  elif i >= n or m > sum(A):
    return False

  res = solve( i+1 , m ) or solve( i+1 , m-A[i] )
  return res

for m in mi:
  if solve( 0 , m ): print "yes"
  else: print "no"
import sys
import copy
import bisect

sys.setrecursionlimit(202020)

N = int(input())
a = list(map(int, input().split()))
to = [[] for _ in range(N)]
for i in range(N-1):
    u, v = map(int, input().split())
    u -= 1; v -= 1
    to[u].append(v)
    to[v].append(u)

ans = [1 for _ in range(N)]

def dfs(u, p, L, length):
    print(u)
    ans[u] = length
    for v in to[u]:
        if v == p:
            continue
        L_copy = copy.deepcopy(L)
        if L[-1] < a[v]:
            L_copy.append(a[v])
            dfs(v, u, L_copy, length+1)
        else:
            p = bisect.bisect_left(L_copy, a[v])
            L_copy[p] = a[v]
            dfs(v, u, L_copy, length)

dfs(0, -1, [a[0]], 1)
for i in range(N):
    print(ans[i])


### FIXED CODE ###

import sys
import copy
import bisect

sys.setrecursionlimit(202020)

INF = 10**12
MAX_N = 202020

N = int(input())
a = list(map(int, input().split()))
to = [[] for _ in range(N)]
for i in range(N-1):
    u, v = map(int, input().split())
    u -= 1; v -= 1
    to[u].append(v)
    to[v].append(u)

dp = [INF for _ in range(MAX_N)]
ans = [0 for _ in range(N)]

def dfs(v, p=-1):
    i = bisect.bisect_left(dp, a[v])
    old = dp[i]
    dp[i] = a[v]
    ans[v] = i
    if p != -1:
        ans[v] = max(ans[v], ans[p])
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)
    dp[i] = old

dp[0] = -INF
dfs(0)
print(*ans)
import networkx as nx
n,m=map(int,input().split())
s=[list(map(int,input().split())) for i in range(m)]

g=nx.Graph()
g.add_edges_from(s)
di=nx.predecessor(g,source=1)

print("Yes)
for x in range(2,n+1):
      print(di[x][0])


### FIXED CODE ###

import networkx as nx
n,m=map(int,input().split())
s=[list(map(int,input().split())) for i in range(m)]

g=nx.Graph()
g.add_edges_from(s)
di=nx.predecessor(g,source=1)

print("Yes")
for x in range(2,n+1):
      print(di[x][0])
N = str(input())
if N[2] == 3:
  print("bon")
elif N[2] == 0 or N[2] == 1 or N[2] == 6 or N[2] == 8:
  print("pon")
else:
  print("hon")

### FIXED CODE ###

N = input()
if N[-1] == "3":
  print("bon")
elif N[-1] == "0":
  print("pon")
elif N[-1] == "1":
  print("pon")
elif N[-1] == "6":
  print("pon")
elif N[-1] == "8":
  print("pon")
else:
  print("hon")
text  = []
ptext = []

while True:
    try:


        text = list(map(str,raw_input()))
#        print text
        f = 0
        ptext = []

        for i in range(len(text)):
            if text[i] == '@':
#                print text[i]

                for k in range(int(text[i+1])-1):
                    ptext.append(text[i+2])

                f = 1

            else:
                if f == 0:
                    ptext.append(text[i])
                else:
                    f = 0            

### FIXED CODE ###

text  = []                                                                                                
ptext = []

while True:
    try:
        text = list(map(str,raw_input()))
        f = 0
        ptext = []

        for i in range(len(text)):
            if text[i] == '@':

                for k in range(int(text[i+1])-1):
                    ptext.append(text[i+2])

                f = 1

            else:
                if f == 0:
                    ptext.append(text[i])
                else:
                    f = 0

        print "".join(map(str,ptext))

    except EOFError:
        break
text  = []                                                                                                
ptext = []

while True:
    try:
        text = list(map(str,raw_input()))
        f = 0
        ptext = []

        for i in range(len(text)):
            if text[i] == '@':

                for k in range(int(text[i+1])-1):
                    ptext.append(text[i+2])

                f = 1

            else:
                if f == 0:
                    ptext.append(text[i])
                else:
                    f = 0

        print "".join(map(str,ptext))

    except EOFError:
        break
from collections import defaultdict
from math import factorial

N = int(input())
st = set()
d = defaultdict(int)
for _ in range(N):
    s = input()
    s_sorted = "".join(sorted(s))
    if s_sorted in st:
        d[s_sorted] += 1
    else:
        st.add(s_sorted)

ans = 0
for _, v in d.items():
    x = factorial(v + 1) / factorial(2)
    ans += x

print(round(ans))


### FIXED CODE ###

from math import factorial

N = int(input())
d = {}
for _ in range(N):
    s = input()
    s_sorted = "".join(sorted(s))
    if not d.get(s_sorted):
        d[s_sorted] = 1
    else:
        d[s_sorted] += 1

ans = 0
for _, v in d.items():
    if v == 1:
        continue
    ans += v * (v - 1) // 2

print(round(ans))
l = list(map(int, input().split()))                     
                                                        
N = l[0]                                                
Y = l[1]                                                
ans = [-1,-1,-1]                                        
                                                        
if Y/10000 < N:                                         
    for i in range(int(Y/10000)+1):                     
    ¦   a = i                                           
    ¦   n = N - a                                       
    ¦   Y1 = Y - (a * 10000)                            
    ¦   if Y1/5000 < n:                                 
    ¦   ¦   for j in range(int(Y1/5000)+1):             
    ¦   ¦   ¦   b = j                                   
    ¦   ¦   ¦   c = n - j                               
    ¦   ¦   ¦   if 10000 * a + 5000 * b + 1000 * c == Y:
    ¦   ¦   ¦   ¦   ans = [a,b,c]                       
                                                        
print(ans)                                              

### FIXED CODE ###

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

N = l[0]
Y = l[1]
ans = [-1,-1,-1]

if Y/10000 <= N:
    for i in range(int(Y/10000)+1):
        a = i
        n = N - a
        Y1 = Y - (a * 10000)
        if Y1/5000 <= n:
            for j in range(int(Y1/5000)+1):
                b = j
                c = n - j
                if 10000 * a + 5000 * b + 1000 * c == Y:
                    ans = [a,b,c]

print(ans[0],ans[1],ans[2])
a,b = map(int, input().split())
c = a*b
mod = c % 2
if mod==0
   print("Even")
else print("Odd")


### FIXED CODE ###

a,b = map(int, input().split())
c = a*b
mod = c % 2
if mod==0:
   print("Even")
else:
   print("Odd")
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
MOD = 10**9+7
# MOD = 998244353

n = int(input())
E = [list(map(int, input().split())) for i in range(n)]
d = defaultdict(int)
for e in E:
    if e[0] == 0 and e[1] == 0:
        d[(0, 0)] += 1
    elif e[0] == 0:
        k = 1 if e[1] > 0 else -1
        d[(0, k)] += 1
    elif e[1] == 0:
        k = 1 if e[0] > 0 else -1
        d[(k, 0)] += 1
    else:
        gcd = math.gcd(e[0], e[1])
        a, b = e[0]//gcd, e[1]//gcd
        if b < 0:
            a, b = -a, -b
        d[(a, b)] += 1

pd = 1
non = n
for k in d:
    if k[0] >= 0 and (-k[1], k[0]) in d:
        a, b = d[k], d[(-k[1], k[0])]
        pd = (pd*(pow(2, a, MOD) + pow(2, b, MOD) - 1))%MOD
        # print(a, b, pd)
        non -= (a+b)

# print(non, pd)
total = (pow(2, non, MOD)*pd - 1)%MOD
print(total)


### FIXED CODE ###

from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
MOD = 10**9+7
# MOD = 998244353

n = int(input())
E = [list(map(int, input().split())) for i in range(n)]
d = defaultdict(int)
for e in E:
    if e[0] == 0 and e[1] == 0:
        d[(0, 0)] += 1
    elif e[0] == 0:
        d[(0, 1)] += 1
    elif e[1] == 0:
        d[(1, 0)] += 1
    else:
        g = math.gcd(e[0], e[1])
        a, b = e[0]//g, e[1]//g
        if b < 0:
            a, b = -a, -b
        d[(a, b)] += 1

pd = 1
non = n - d[(0, 0)]
for k in d:
    if k == (0, 0) or k == (1, 0):
        continue

    elif k == (0, 1) and (1, 0) in d:
        a, b = d[(0, 1)], d[(1, 0)]
        pd = (pd * (pow(2, a, MOD) + pow(2, b, MOD) - 1)) % MOD
        non -= (a + b)

    elif k[0] > 0 and (-k[1], k[0]) in d:
        a, b = d[k], d[(-k[1], k[0])]
        pd = (pd*(pow(2, a, MOD) + pow(2, b, MOD) - 1))%MOD
        # print(a, b, pd)
        non -= (a+b)

# print(non, pd)
total = (pow(2, non, MOD)*pd - 1 + d[(0, 0)])%MOD
print(total)
N, X, T = map(int,input().split())

if N % x == 0
    print(( N // X ) * T )
else:
    print(( N // X + 1 ) * T )

### FIXED CODE ###

N, X, T = map(int,input().split())

A = N % X

if ( A ) == 0:
    print(( N // X ) * T )
elif ( N % X ) != 0:
    print(( N // X + 1 ) * T )
N, K = map(int, input().split())
A = list(map(int, input().split()))
A_max = max(A)
if K == 0:
    print(A_max)
else:
    X = A_max+1//2
    y = (X+1)//2
    while True:
        c = 0
        d = 0
        for i in range(N):
            c += A[i]//X
            d += A[i]//(X+1)
        if d <= K and c > K:
            print(X+1)
            break
        elif d > K:
            X += y
            y = (y+1) // 2
        elif c <= K:
            X -= y
            y = (y+1) // 2

### FIXED CODE ###

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

def is_ok(mid):
    s = 0
    for j in range(N):
        if mid < A[j]:
            s += A[j] // mid
    return s <= K

max_A = 10**9 + 1
ng = 0
ok = max_A

while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if is_ok(mid):
        ok = mid
    else:
        ng = mid
        
print(ok)
for e in iter(input,'0'):
 a=[list(map(int,input().split()))for _ in[0]*int(e)]
 b=[list(map(int,input().split()))for _ in[0]*int(input())]
 for s,t in b:
  u,v=a[0]
  x,y=s-u,t-v
  for u,v in a:
   if[u+x,v+y]not in b:break
  else:print(x,y)


### FIXED CODE ###

for e in iter(input,'0'):
 a=[[*map(int,input().split())]for _ in[0]*int(e)]
 s,t=min(a)
 b={tuple(map(int,input().split()))for _ in[0]*int(input())}
 m=max(b)[0]-max(a)[0]+s
 for x,y in b:
  if x<=m:
   for u,v in a:
    if(x+u-s,y+v-t)not in b:break
   else:print(x-s,y-t);break
n = input().split()
a = list(map(int, input().split() ))
count = 0

while(True):
    T = False
    for i in range(len(a)):
        if a[i]%2 != 0:
            T=True

        a[i] = a[i] / 2

    if T:
        break
    
    count+=1

print(count)


### FIXED CODE ###


s = input()
a = [int(c) for c in s]

print(a[0] + a[1] + a[2])
n,m=map(int,input().split())
X=list(map(int,input().split()))
X.sort()

if m==1 :
    print(0)
else :

    sa=[]
    for i in range(m-1):
        sa.append(X[i+1]-X[i])


    sa.sort(reverse=1)


    jo=[]
    for i in range(n-1):
        jo.append(sa[i])


    print(X[m-1]-X[0]-sum(jo))


### FIXED CODE ###

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

if m==1 or n>=m :
    print(0)
else :

    sa=[]
    for i in range(m-1):
        sa.append(X[i+1]-X[i])


    sa.sort(reverse=1)


    jo=[]
    for i in range(n-1):
        jo.append(sa[i])


    print(X[m-1]-X[0]-sum(jo))
import collections,sys
n=int(input())
v=list(map(int,input().split()))
a=[]
b=[]
for i in range(0,n,2):
  a.append(v[i-1])
  b.append(v[i])
c=collections.Counter(a)
d=collections.Counter(b)
C=sorted(c.items(), key=lambda x:-x[1])
D=sorted(d.items(), key=lambda x:-x[1])
A=int(C[0][0])
B=int(D[0][0])
cnt=0
if A!=B:
  for i in range(n//2):
    if a[i]!=A:
      cnt+=1
  for j in range(n//2):
    if b[j]!=B:
      cnt+=1
  print(cnt)
  sys.exit()
if A==B:
  totla=0
  A_=int(C[1][0])
  for i in range(n//2):
    if a[i]!=A_:
      totla+=1
  for j in range(n//2):
    if b[j]!=B:
      totla+=1
  totlb=0
  B_=int(D[1][0])
  for i in range(n//2):
    if a[i]!=A:
      totlb+=1
  for j in range(n//2):
    if b[j]!=B_:
      totlb+=1
  print(min(totla,totlb))
  sys.exit()
  
  
  
  
    
    
    

    





### FIXED CODE ###

import collections,sys
n=int(input())
v=list(map(int,input().split()))
a=[]
b=[]
for i in range(0,n,2):
  a.append(v[i-1])
  b.append(v[i])
c=collections.Counter(a)
d=collections.Counter(b)
C=sorted(c.items(), key=lambda x:-x[1])
D=sorted(d.items(), key=lambda x:-x[1])
A=int(C[0][0])
B=int(D[0][0])
cnt=0
if len(set(v))==1:
  print(n//2)
  sys.exit()
if A!=B:
  for i in range(n//2):
    if a[i]!=A:
      cnt+=1
  for j in range(n//2):
    if b[j]!=B:
      cnt+=1
  print(cnt)
  sys.exit()
if A==B:
  totla=0
  A_=int(C[1][0]) if len(set(a))!=1 else A
  for i in range(n//2):
    if a[i]!=A_:
      totla+=1
  for j in range(n//2):
    if b[j]!=B:
      totla+=1
  totlb=0
  B_=int(D[1][0]) if len(set(b))!=1 else B
  for i in range(n//2):
    if a[i]!=A:
      totlb+=1
  for j in range(n//2):
    if b[j]!=B_:
      totlb+=1
  print(min(totla,totlb))
  sys.exit()
print((int(readline()) + int(readline())) * int(readline()) // 2)


### FIXED CODE ###

import sys
input = sys.stdin.readline

a = int(input())
b = int(input())
h = int(input())
ans = (a+b) * h * 0.5
print(int(ans))
# ABC080 C - Shopping Street
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
n=ni()
f=[nl() for _ in range(n)]
p=[nl() for _ in range(n)]
o = []
ans = -10**8
for i in range(2**10):
    op = [0]*10
    for j in range(10):
        if ((i>>j)&1):
            op[n-1-j]=1
    if not any(op):
        continue
    else:
        o.append(op)

for oo in o:
    value = 0
    for i,ff in enumerate(f):
        t=0
        for j in range(10):
            if oo[j]==1 and ff[j]==1:
                t+=1
        value += p[i][t]
    ans = max(ans,value)

print(ans)



### FIXED CODE ###

# ABC080 C - Shopping Street
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
n=ni()
f=[nl() for _ in range(n)]
p=[nl() for _ in range(n)]
o = []
ans = -10**10
for i in range(2**10):
    op = [0]*10
    for j in range(10):
        if ((i>>j)&1):
            op[10-1-j]=1
    if not any(op):
        continue
    else:
        o.append(op)

for oo in o:
    value = 0
    for i,ff in enumerate(f):
        t=0
        for j in range(10):
            if oo[j]==1 and ff[j]==1:
                t+=1
        value += p[i][t]
    ans = max(ans,value)

print(ans)
n=int(input())
B=list(map(int,input().split()))
ans=B[0]+B[-1]
for i in range(n-1):
  ans+=min(B[i],B[i+1])
print(ans)

### FIXED CODE ###

n=int(input())
B=list(map(int,input().split()))
ans=B[0]+B[-1]
for i in range(n-2):
  ans+=min(B[i],B[i+1])
print(ans)
n = int(input())
s = [input() for i in range(n)]
print("AC x",s.count("AC"))
print("WA x",a.count("WA"))
print("TLE x",a.count("TLE"

### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]
print("AC x",s.count("AC"))
print("WA x",s.count("WA"))
print("TLE x",s.count("TLE"))
print("RE x",s.count("RE"))
n=input();
if n // 100 = 7:
    print('Yes')
elif n // 10 = 7:
    print('Yes')
elif n % 10 = 7:
    print('Yes')
else:
    print('No')    

### FIXED CODE ###

n=int(input())
if n // 100 == 7:
    print('Yes')
elif (n // 10) % 10 == 7:
    print('Yes')
elif n % 10 == 7:
    print('Yes')
else:
    print('No')
A,V=map(int, input().split())
B,W=map(int, input().split())
T=int(input())

if A>B and A-V*T=<B-W*T:
  print("YES")
elif  A<B and A+V*T>=B+W*T:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

A,V=map(int, input().split())
B,W=map(int, input().split())
T=int(input())

if A>B and A-V*T<=B-W*T:
  print("YES")
elif  A<B and A+V*T>=B+W*T:
  print("YES")
else:
  print("NO")
import bisect

N=int(input())
A=[int(input()) for i in range(N)]
lst=[]
nowN=max(A)+1
i=0
while i<N:
    if nowN>=A[i]:
        nowN=A[i]
        lst.append([A[i]])
    else:
        lst2=[n[-1] for n in lst]
        if min(lst2)<A[i]
            for n in range(len(lst2)):
                if lst2[n]<A[i]:
                    lst[n].append(A[i])
                    break
        else:
            lst.append([A[i]])
    i+=1
print(len(lst))


### FIXED CODE ###

import bisect
import collections

N=int(input())
A=[int(input()) for i in range(N)]
B=[0 for i in range(N)]
C=sorted(A)
count=0
lst=collections.deque([])
for i in range(N):
    if A[i]==C[-1]:
        C.pop()
        if lst:
            lst.pop()
        else:
            count+=1
        continue
    idx=bisect.bisect_left(lst,A[i])-1
    #print(idx,lst,A[i])
    if idx<0:
        lst.appendleft(A[i])
        count+=1
    else:
        lst[idx]=A[i]

print(count)
N=int(input())

data=[int(e) for e in input().split()]

data=data.sort(reverse=False)

judge=True

for i in data:
    sum_1=sum_1*i

    if sum_1>1000000000000000000:
        print("-1")
        judge=False
        break

if judge==True:
    print(sum_1)


### FIXED CODE ###

import sys

input = sys.stdin.readline

N = int(input())
x = sorted(list(map(int, input().split())))
t = 1

for num in x:
    t = t * num
    if t > 10 ** 18:
        print(-1)
        sys.exit()

if (t > 10 ** 18):
    print(-1)
else:
    print(t)
n=int(input())
field=[[0 for i in range(20)]for j in range(15)]
for i in range(n):
    b,f,r,v=map(int,input().split())
    h=(b-1)*4+f-1
    w=r*2-1
    n=v
    field[h][w]+=n
for y in range(15):
    for x in range(20):
        if(y%4==3):field[y][x]='#'e
        elif x%2==0 :field[y][x]=' '
        print(field[y][x],end='')
    print()



### FIXED CODE ###

n=int(input())
field=[[0 for i in range(20)]for j in range(15)]
for i in range(n):
    b,f,r,v=map(int,input().split())
    h=(b-1)*4+f-1
    w=r*2-1
    n=v
    field[h][w]+=n
for y in range(15):
    for x in range(20):
        if(y%4==3):field[y][x]='#'
        elif x%2==0 :field[y][x]=' '
        print(field[y][x],end='')
    print()
import sys
r=sys.stdin.readline
I=float('inf')
for e in iter(r,'0 0'):
 n,k=map(int,e.split())
 F=[[I]*-~n for _ in[0]*-~n]
 for i in range(1,n+1):F[i][i]=0
 for _ in[0]*k:
  f=r();g=map(int,f[2:].split())
  if'0'==f[0]:a,b=g;A=F[a][b];print([A,-1][A==I])
  else:
   c,d,e=g
   if e<F[c][d]:
    for i in range(2,n+1):
     for j in range(1,i):
      F[i][j]=F[j][i]=min(F[i][j],F[i][c]+e+F[d][j],F[i][d]+e+F[c][j])


### FIXED CODE ###

def s():
 import sys
 r=sys.stdin.readline
 I=float('inf')
 for e in iter(r,'0 0\n'):
  n,k=map(int,e.split())
  F=[[I]*-~n for _ in[0]*-~n]
  for i in range(1,n+1):F[i][i]=0
  for _ in[0]*k:
   f=r();g=map(int,f[2:].split())
   if'0'==f[0]:a,b=g;A=F[a][b];print([A,-1][A==I])
   else:
    c,d,e=g
    if e<F[c][d]:
     for i in range(2,n+1):
      for j in range(1,i):
       F[i][j]=F[j][i]=min(F[i][j],F[i][c]+e+F[d][j],F[i][d]+e+F[c][j])
s()