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

k,s=map(int, input().split());
ans=int(0);
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z==s:
                ans+=1;
print(ans);

### FIXED CODE ###

k,s=map(int,input().split())
ans=0
for i in range(k+1):
    for j in range(k+1):
        z=s-i-j
        if 0<=z<=k:
            ans+=1
print(ans)
### BUGGY CODE ###

x = input()
y = x.split(" ")
parameters = [int(i) for i in y]
N = parameters[0]
M = parameters[1]
i = N
count = 0
A = [[0] * M for i in range(N)]
while(i > 0):
    x = input()
    y = x.split(" ")
    A[count] = [int(i) for i in y]
    count += 1
    i -= 1

cash = 0
while(M > 0):
    i = 0
    min = 1000000001
    index = 0
    while(i < N):
        if(min > A[i][0]):
            min = A[i][0]
            index = i
        i += 1
    if(M - A[index][1] >= 0):
        M -= A[index][1]
        cash += A[index][1] * A[index][0]
    else:
        cash += A[index][0] * M
        M -= A[index][1]
    del A[index]
    N -= 1

print(cash)


### FIXED CODE ###

NM = [int(i) for i in input().split()]
N = NM[0]
M = NM[1]
datalist = []
index = 0
cost = 0
num = 1
total_cost = 0
while(N > 0):
    data = [int(i) for i in input().split()]
    datalist.append(data)
    N -= 1
datalist.sort(key=lambda x:x[0])
while(M > 0):
    M -= datalist[index][num]
    total_cost += datalist[index][cost] * datalist[index][num]
    if(M < 0):
        n = abs(M)
        total_cost -= n * datalist[index][cost]
    index += 1
print(total_cost)
### BUGGY CODE ###

s = input()
mod = 2019
l = [0]*mod
ans = 0

for i in range(len(s)):
    a = int(s[i:])%mod
    l[a] += 1
l[0] += 1

for i in range(2019):
    ans += l[i]*(l[i] - 1)//2

print(ans)

### FIXED CODE ###

s = input()
mod = 2019
l = [0]*mod
l[0] = 1 #余りが0の場合が1足りないので補う
ans = 0
r = 0
t = 1

for i in s[::-1]:
    r += int(i)*t
    r %= mod # 余りをrに代入してしまっても、後の計算に支障が無い。
    l[r] += 1
    t *= 10
    t %= mod # t *= 10を使用しても、ここの余りを使用しても、r%modの答えは変わらない。

for i in l:
    ans += i*(i - 1)//2

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

N, W = map(int, input().split())
weights, values = [], []

for _ in range(N):
    x, y = map(int, input().split())
    weights.append(x)
    values.append(y)

dp = [[-float('inf') for _ in range(W + 1)] for _ in range(N + 1)]


def dp_rec(item, w):

    if dp[item][w] > -float('inf'):
        return dp[item][w]
    if item == N:
        return 0
    if w-weights[item] >= 0:
        res = max(dp_rec(item+1, w-weights[item]) + values[item], dp_rec(item+1, w))
    else:
        res = dp_rec(item+1, w)

    dp[item][w] = res
    return res


dp_rec(0, W)
print(dp[0][W])


### FIXED CODE ###

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

w, v = [], []
for _ in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)

# dp[in_n_items][below_w_weight] = max_value
dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]

for i in range(1, N + 1):
    for j in range(W + 1):
        if j - w[i - 1] >= 0:
            if dp[i - 1][j - w[i - 1]] + v[i - 1] > dp[i - 1][j]:
                dp[i][j] = dp[i - 1][j - w[i - 1]] + v[i - 1]
            else:
                dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = dp[i - 1][j]
print(dp[N][W])
### BUGGY CODE ###

n = input()
a = input().split()

def dup(listOfElems):
    for elem in listOfElems:
            if listOfElems.count(elem) > 1:
                return True
    return False

du = dup(a)
print('YES' if not du else 'NO')

### FIXED CODE ###

n = int(input())
a = input().split()
b = set(a)
if len(b)<len(a):
    print("NO")
else:
    print("YES")
### BUGGY CODE ###

# import math
# import decimal
# import queue
# import bisect
# import heapq
# import time
# import itertools

mod = int(1e9+7)

def main():
    n,k = map(int,input().split())
    p = list(map(int,input().split()))
    x = [0]
    _sum = 0
    for i in range(1,max(p)+1):
        _sum += i
        x.append(_sum)
    v = []
    ans = 0
    for i in range(n):
        v.append(x[p[i]]/p[i])
        if i >= k - 1:
            ans = max(ans,sum(v[i-k+1:i+1]))
    print(ans)
    return

if __name__=='__main__':
    main()


### FIXED CODE ###

# import math
# import decimal
# import queue
# import bisect
# import heapq
# import time
# import itertools

mod = int(1e9+7)

def main():
    n,k = map(int,input().split())
    p = list(map(int,input().split()))
    x = [0]
    _sum = 0
    for i in range(1,max(p)+1):
        _sum += i
        x.append(_sum)
    v = []
    ans = 0
    res = 0
    for i in range(n):
        v.append(x[p[i]]/p[i])
        if i >= k:
            res += v[i] - v[i-k]
        else:
            res += v[i]
        ans = max(ans,res)
    print(ans)
    return

if __name__=='__main__':
    main()
### BUGGY CODE ###

N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
S.append(0)
T.append(0)
MOD = 10 ** 9 + 7

dp0 = [[0 for _ in range(2005)] for _ in range(2005)]
dp1 = [[0 for _ in range(2005)] for _ in range(2005)]

dp0[0][0] = 1
for i in range(N + 1):
  for j in range(M + 1):
    dp0[i + 1][j] += dp0[i][j]
    dp1[i][j] += dp0[i][j]
    dp1[i][j + 1] += dp1[i][j]

    if S[i] == T[j]:
      dp0[i + 1][j + 1] += dp1[i][j]
ans = dp1[N][M]
print(ans % MOD)

### FIXED CODE ###

N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
S.append(0)
T.append(0)
MOD = 1000000007

dp0 = [[0 for _ in range(2005)] for _ in range(2005)]
dp1 = [[0 for _ in range(2005)] for _ in range(2005)]

dp0[0][0] = 1
for i in range(N + 1):
  for j in range(M + 1):
    dp0[i + 1][j] += dp0[i][j] % MOD
    dp1[i][j] += dp0[i][j] % MOD
    dp1[i][j + 1] += dp1[i][j] % MOD

    if S[i] == T[j]:
      dp0[i + 1][j + 1] += dp1[i][j] % MOD
ans = dp1[N][M]
print(ans % MOD)
### BUGGY CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

def make_divisors(n):
    res = []
    x = n
    y = 2
    while y*y <= x:
        while x % y == 0:
            res.append(y)
            x //= y
        y += 1
    if x > 1:
        res.append(x)
    return res

n = ni()
a = na()

wa = set(make_divisors(a[0]))
s = len(wa)

for i in range(1,n):
    ii = set(make_divisors(a[i]))
    s += len(ii)
    wa = wa | ii
    if s != len(wa): # not pairwise
        break
else:
    print('pairwise coprime')
    exit()

import math
k = a[0]
for i in a:
    k = math.gcd(k,i)
    if k == 1:
        print('setwise coprime')
        exit()

print('not coprime')

### FIXED CODE ###

from operator import truediv
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

def make_divisors(n):
    res = []
    x = n
    y = 2
    while y*y <= x:
        while x % y == 0:
            res.append(y)
            x //= y
        y += 1
    if x > 1:
        res.append(x)
    return res

n = ni()
a = na()
g = [0]*1000000

for i in range(n):
    ii = list(set(make_divisors(a[i])))
    b = True
    for p in ii:
        if g[p] == 0:
            g[p] += 1
        else:
            b = False
            break
    if not b:
        break
else:
    print('pairwise coprime')
    exit()

import math

k = a[0]
for i in a:
    k = math.gcd(k,i)
    if k == 1:
        print('setwise coprime')
        exit()

print('not coprime')
### BUGGY CODE ###

N,M=map(int,input().split())
H=list(map(int,input().split()))
A=[i for i in range(1,N+1)]
for i in range(M):
    a,b=map(int,input().split())
    if H[a-1]>H[b-1]:
        if b in A:
            A.remove(b)
    elif H[b-1]>H[a-1]:
        if a in A:
            A.remove(a)
    else:
        if a in A:
            A.remove(a)
        if b in A:
            A.remove(b)
 
print(len(A))

### FIXED CODE ###

N,M=map(int,input().split())
H=list(map(int,input().split()))
A=[i for i in range(N)]
B=[]
for i in range(M):
    a,b=map(int,input().split())
    if H[a-1]>H[b-1]:
        B.append(b)
    elif H[b-1]>H[a-1]:
        B.append(a) 
    else:
        B.append(a)
        B.append(b)

B=list(set(B))
print(len(A)-len(B))
### BUGGY CODE ###

import sys

input = sys.stdin.readline


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


inf = float("inf")


def main():
    d, g = MI()
    pc = [LI() for _ in range(d)]

    ans = inf
    for bit in range(2 << d):
        c = 0
        score = 0
        for i in range(d):
            if bit & (1 << i):
                c += pc[i][0]
                score += pc[i][0] * 100 * (i + 1) + pc[i][1]

        while score < g:
            for i in reversed(range(d)):
                if bit & (1 << i):
                    continue
                for _ in range(pc[i][0]):
                    if score >= g:
                        break
                    score += 100 * (i + 1)
                    c += 1

        ans = min(ans, c)

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import math

input = sys.stdin.readline


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


inf = float("inf")


def main():
    d, g = MI()
    pc = [LI() for _ in range(d)]

    ans = inf
    for bit in range(2 << d):
        c = 0
        score = 0
        for i in range(d):
            if bit & (1 << i):
                c += pc[i][0]
                score += pc[i][0] * 100 * (i + 1) + pc[i][1]

        if score >= g:
            ans = min(ans, c)
        else:
            for i in reversed(range(d)):
                if bit & (1 << i):
                    continue
                res = math.ceil((g - score) / (100 * (i + 1)))
                if res < pc[i][0]:
                    ans = min(ans, c + res)
                break

    print(ans)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

def main():
  s = input()
  
  answer = 0
  
  while ("0" in s) and ("1" in s):
    answer += s.count("10")
    s.replace("10", "")
    answer += s.count("01")
    s.replace("01", "")
  
  print(answer)


if __name__ == "__main__":
  main()


### FIXED CODE ###

def main():
  s = input()
  
  answer = 0
  
  print(2 * min(s.count("1"), s.count("0")))


if __name__ == "__main__":
  main()
### BUGGY CODE ###

import queue

def readInts():
	return list(map(int, input().split()))

def addRoad(a,b):
	global ab
	ab[a].append(b)
	ab[b].append(a)

def addFlag(fr,toarr):
	global flg
	for i in toarr:
		if flg[i]==-1:
			flg[i]=fr
def addQueue(arr):
	global q
	for i in arr:
		q.put(i)
def addFQ(item):
	global flg
	global q
	global ab
	for i in ab[item]:
		if puted[i]==0:
			flg[i-1]=item
			q.put(i)
			puted[i]=1

n,m = readInts()
puted = [0]*(n+1)

ab = [[] for i in range(n+1)]
for i in range(m):
	a,b = readInts()
	addRoad(a,b)

q = queue.Queue()
flg = [-1]*n
flg[0] = 0
q.put(1)

while -1 in flg or q.empty():
	item = q.get()
	#addFlag(item,ab[item])
	#addQueue(ab[item])
	addFQ(item)

if -1 in flg:
	print("No")
	exit()

print("Yes")
for i in range(1,len(flg)):
	print(flg[i])


### FIXED CODE ###

import queue

n,m = list(map(int, input().split()))
puted = [0]*(n+1)

ab = [[] for i in range(n+1)]
for i in range(m):
	a,b = list(map(int, input().split()))
	ab[a].append(b)
	ab[b].append(a)

q = queue.Queue()
flg = [-1]*n
flg[0] = 0
q.put(1)

while not q.empty():
	item = q.get()
	for i in ab[item]:
		if puted[i]==0:
			flg[i-1]=item
			q.put(i)
			puted[i]=1

if -1 in flg:
	print("No")
	exit()

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

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

div = 10**9+7
ans=0
for i in range(n-1):
    for j in range(i+1, n):
        ans += a[i]^a[j]
        ans %= div

print(ans)


### FIXED CODE ###

from itertools import accumulate
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
aa = list(accumulate(a))
aa = aa[::-1]
a.sort()
div = 10**9+7
ans=0

ls = [0]*60
for i in range(60):
    for j in a:
        if j&(1<<i):
            ls[i]+=1
        else:
            ls[i]-=1
    
for i in range(n-1):
    ans+=aa[i+1]
    for j in range(60):
        if a[i]&(1<<j):
            ls[j]-=1
            ans-=ls[j] * 2**j
        else:
            ls[j]+=1
    
    ans %= div

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



from collections import defaultdict
from collections import deque

def main():
        
    N = int(input())
    """
    before[(i,j)]
    iとjの試合より前に終わらせておく必要のある直前の対戦者の組の数

    nxt[(i,j)]
    iとjの試合より後に行える対戦者の組

    例２
    4
    2 3 4
    1 3 4
    4 1 2
    3 1 2
    について、
    before[(1,3)] = 2
    before[(1,4)] = 2
    nxt[(1,2)] = set((1,3), (2,3))
    みたいな
    """
    before = defaultdict(int)
    nxt = defaultdict(set)

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

    for i in range(N):

        for j,a in enumerate(A[i]):
            l, h = min(i+1, a), max(i+1, a)
            if j == 0:
                b = (l,h)
            else:
                before[(l,h)] += 1
                nxt[b].add((l,h))
                b = (l,h)



    match_today = deque()

    for i in range(1, N):
        for j in range(i+1, N+1):
            if before[(i, j)] == 0:
                match_today.append((i,j))
                

    
    ans = 0
    cnt_match = 0 
    while match_today:
        #print( match_today)
        ans += 1
        
        for _ in range(len(match_today)):
            l,h = match_today.popleft()
            cnt_match += 1
            for nl, nh in nxt[(l,h)]:
                before[(nl, nh)] -= 1
                
                if before[(nl, nh)] == 0:
                    match_today.append((nl, nh))
        
       


    if cnt_match == N*(N-1) // 2:
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

### FIXED CODE ###


from collections import deque

N = int(input())
match_order = [deque(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]


q = deque(range(N))
finish_by = [0] * N
next_opponent = [None] * N

while q:
    a = q.popleft()
    # aの残りの順で一番初めに戦う対戦相手を取り出す
    b = match_order[a].popleft()
    if next_opponent[b] == a:
        finish_by[a] = finish_by[b] = max(finish_by[a], finish_by[b]) + 1
        # a,bについて、まだ対戦相手が残っているならキューに積む
        if match_order[a]:
            q.append(a)
        if match_order[b]:
            q.append(b)
    # bの残りの順で戦う相手がaではないなら、順番が来るまで待つ
    else:
        next_opponent[a] = b

# 対戦相手が残っている人がいる場合、条件通りに終わることができない
if any(match_order):
    print(-1)
else:
    print(max(finish_by))
### BUGGY CODE ###

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

B=[0]*N
C=''

for i in range(N):
    B[i]=A.index(i+1)
    B[i]+=1
    C+=str(B[i])+' '
print(C[0:-1])

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
B=[0]*N
C=''
 
for i in range(N):
    B[A[i]-1]=i+1
 
for i in range(N):
    C+=str(B[i])+' '
 
print(C[0:-1])
### BUGGY CODE ###

h,w=map(int,input().split())
maplis=[input() for i in range(h)]

que=[[0,0,1]]
used=[[0,0]]
bcount =0
for i in maplis:
    bcount+=i.count("#")


def check(x,y,c):
    f=(x<0 or x>w-1 or y<0 or y>h-1)
    f=(f or maplis[y][x]=="#")
    f=(f or [x,y] in used)
    if not f:
        que.append([x,y,c+1])

f=-1
while que:
    x,y,c=que.pop(0)
    if x==w-1 and y==h-1:
        f=c
    used.append([x,y])
    check(x-1,y,c)
    check(x+1,y,c)
    check(x,y-1,c)
    check(x,y+1,c)
print(f if f==-1 else(h*w-f-bcount))


### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
maplis=[input() for i in range(h)]

que=deque([(0,0,1)])
used={(0,0)}
bcount =sum(s.count("#") for s in maplis)


def check(x,y,c):
    if x<0 or x>w-1 or y<0 or y>h-1:
        return
    if maplis[y][x]=="#":
        return
    if  (x,y) in used:
        return
    que.append((x,y,c+1))
    used.add((x,y))

f=-1
while que:
    x,y,c=que.popleft()
    if x==w-1 and y==h-1:
        f=c
        break
    check(x-1,y,c)
    check(x+1,y,c)
    check(x,y-1,c)
    check(x,y+1,c)
print(f if f==-1 else(h*w-f-bcount))
### BUGGY CODE ###

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

coins = [10000, 5000, 1000]

ans = []
def dfs(sum_v, now, i):
    if len(ans) != 0:
        return

    if len(now) == 3:
        if sum_v == Y:
            ans.append(now)
        return

    used = sum(now)
    if i == 2:
        ne = now + [N - used]
        dfs(sum_v + coins[i] * (N - used), ne, i + 1)
    else:
        for j in range(N - used + 1):
            ne = now + [j]
            dfs(sum_v + coins[i] * j, ne, i + 1)

dfs(0, [], 0)
if len(ans) == 0:
    print("-1 -1 -1")
else:
    print(" ".join(map(str, ans[0])))


### FIXED CODE ###

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

coins = [10000, 5000, 1000]

ans = []
def dfs(sum_v, now, i):
    if len(ans) != 0:
        return

    used = sum(now)

    if len(now) == 3:
        if sum_v == Y:
            ans.append(now)
        return

    if sum_v + coins[i] * (N - used) < Y:
        return

    if sum_v > Y:
        return

    if i == 2:
        ne = now + [N - used]
        dfs(sum_v + coins[i] * (N - used), ne, i + 1)
    else:
        for j in range(N - used + 1):
            ne = now + [j]
            dfs(sum_v + coins[i] * j, ne, i + 1)

dfs(0, [], 0)
if len(ans) == 0:
    print("-1 -1 -1")
else:
    print(" ".join(map(str, ans[0])))
### BUGGY CODE ###

import numpy as np

h, w = map(int, input().split())
grid = [[False for j in range(w)] for i in range(h)]

for i in range(h):
    s = input()
    for j in range(w):
        if s[j] == '.':
            grid[i][j] = 1
        else:
            grid[i][j] = 0

grid = np.array(grid)

L = np.zeros((h, w), dtype=int)
R = np.zeros((h, w), dtype=int)
U = np.zeros((h, w), dtype=int)
D = np.zeros((h, w), dtype=int)

for j in range(w):
    if j == 0:
        L[:, j] = grid[:, j]
    else:
        L[:, j] = (L[:, j - 1] + 1) * grid[:, j]


for j in range(w - 1, -1, -1):
    if j >= w - 1:
        R[:, j] = grid[:, j]
    else:
        R[:, j] = (R[:, j + 1] + 1) * grid[:, j]

for i in range(h):
    if i <= 0:
        U[i, :] = grid[i, :]
    else:
        U[i, :] = (U[i - 1, :] + 1) * grid[i, :]


for i in range(h - 1, -1, -1):
    if i >= h - 1:
        D[i, :] = grid[i, :]
    else:
        D[i, :] = (D[i + 1, :] + 1) * grid[i, :]


nums = []
for i in range(h):
    for j in range(w):
        nums.append(L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)

print(np.max(L + R + U + D - 3))


### FIXED CODE ###

import numpy as np

h, w = map(int, input().split())
grid = [[False for j in range(w)] for i in range(h)]

for i in range(h):
    s = input()
    for j in range(w):
        if s[j] == '.':
            grid[i][j] = 1
        else:
            grid[i][j] = 0

grid = np.array(grid)

L = np.zeros((h, w), dtype=int)
R = np.zeros((h, w), dtype=int)
U = np.zeros((h, w), dtype=int)
D = np.zeros((h, w), dtype=int)

for j in range(w):
    if j == 0:
        L[:, j] = grid[:, j]
    else:
        L[:, j] = (L[:, j - 1] + 1) * grid[:, j]


for j in range(w - 1, -1, -1):
    if j >= w - 1:
        R[:, j] = grid[:, j]
    else:
        R[:, j] = (R[:, j + 1] + 1) * grid[:, j]

for i in range(h):
    if i <= 0:
        U[i, :] = grid[i, :]
    else:
        U[i, :] = (U[i - 1, :] + 1) * grid[i, :]


for i in range(h - 1, -1, -1):
    if i >= h - 1:
        D[i, :] = grid[i, :]
    else:
        D[i, :] = (D[i + 1, :] + 1) * grid[i, :]

print(np.max(L + R + U + D - 3))
### BUGGY CODE ###

import numpy as np
N = int(input())
An = list(map(int, input().split()))
ans = 0
ng = set()
a_An = np.array(An)
for i, a in enumerate(An):
    temp = a_An / a
    check = np.where(temp%1 == 0)
    check = np.delete(check, np.where(check==i))
    check = check[check != i]
    if len(check) > 0:
        ng = ng | set(check)
print(N-len(ng))



### FIXED CODE ###

N = int(input())
An = list(map(int, input().split()))
An.sort()
max_n = max(An)
dp = [0] * (max_n + 1)
for i in range(N):
    if dp[An[i]] != 0:
        dp[An[i]] = 2
        continue
    for j in range(1, max_n//An[i] + 1):
        dp[An[i]*j] += 1
ans = 0
for a in An:
    if dp[a] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, p: "List[float]"):
    dp = []
    for _ in range(0, N + 1):
        L = [0.0] * (N + 1)
        dp.append(L)
    
    dp[1][0] = 1 - p[0]
    dp[1][1] = p[0]

    for i in range(2, N + 1):
        for j in range(0, i + 1):
            if j == 0:
                dp[i][j] = dp[i - 1][j] * (1 - p[i - 1])
            else:
                dp[i][j] = dp[i - 1][j - 1] * p[i - 1] + dp[i - 1][j] * (1 - p[i - 1])

    res = 0
    for j in range(0, N + 1):
        if j < N / 2:
            continue
        res += dp[N][j]
    print(res)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    p = [float(next(tokens)) for _ in range(N)]  # type: "List[float]"
    solve(N, p)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, p: "List[float]"):
    dp = []
    for _ in range(0, N + 1):
        L = [0.0] * (N + 1)
        dp.append(L)
    
    dp[1][0] = 1 - p[0]
    dp[1][1] = p[0]

    for i in range(2, N + 1):
        for j in range(0, i + 1):
            if j == 0:
                dp[i][j] = dp[i - 1][j] * (1 - p[i - 1])
            else:
                dp[i][j] = dp[i - 1][j - 1] * p[i - 1] + dp[i - 1][j] * (1 - p[i - 1])

    res = 0
    for j in range(0, N + 1):
        if j < N / 2:
            continue
        res += dp[N][j]
    print(res)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    p = [float(next(tokens)) for _ in range(N)]  # type: "List[float]"
    solve(N, p)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

INF = 1000000000

while True:
  try:
    n,k = list(map(int,input().split()))
    if n == 0 and k == 0:
      break
    vlst = [[INF if i != j else 0 for i in range(n)] for j in range(n)]
    for i in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        if vlst[lst[1] - 1][lst[2] - 1] >= INF:
          print(-1)
        else:
          print(vlst[lst[1] - 1][lst[2] - 1])
      elif lst[0] == 1:
        for i in range(n):
          for j in range(n):
            vlst[i][j] = min(vlst[i][j],vlst[i][lst[1] - 1] + lst[3] + vlst[lst[2] - 1][j])
            vlst[j][i] = vlst[i][j]
  except EOFError:
    break


### FIXED CODE ###

from heapq import heappush,heappop

def dij(s,g,E):
  h = []
  U = []
  heappush(h,(0,s))
  while h:
    v = heappop(h)
    if v[1] == g:
      if v[0] >= INF:print(-1)
      else:print(v[0])
      break
    U.append(v[1])
    for e in E[v[1]]:
      if not e[0] in U:
        heappush(h,(v[0] + e[1],e[0]))
  else:print(-1)
INF = 100000000
while True:
  try:
    n,k = map(int,input().split())
    if n == 0 and k == 0: break
    E = [[] for i in range(n)]
    for _ in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        dij(lst[1] - 1, lst[2] - 1, E)
      else:
        E[lst[1] - 1].append([lst[2] - 1, lst[3]])
        E[lst[2] - 1].append([lst[1] - 1, lst[3]])

  except EOFError:
    break