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

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)] # #.のグリッドの場合
#print(a)

from collections import deque
step = [(0,1), (0,-1), (1,0), (-1,0)]
que = deque()

seen = [[-1] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            que.append((i, j))
            seen[i][j] = 0
ans = 0
import numpy as np
#print(np.array(seen))
while len(que) > 0:
    x, y = que.popleft()
    for tx, ty in step:
        xi, yi = x + tx, y + ty
        if xi < 0 or yi < 0 or xi >= h or yi >= w:
            continue
        if a[xi][yi] == '#':
            continue
        if a[xi][yi] == '.':
            seen[xi][yi] = seen[x][y] + 1
            ans = max(ans, seen[xi][yi])
            a[xi][yi] = '#'
            que.append((xi, yi))
    #print(np.array(seen))
print(ans)




### FIXED CODE ###

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)] # #.のグリッドの場合
#print(a)

from collections import deque
step = [(0,1), (0,-1), (1,0), (-1,0)]
que = deque()

seen = [[-1] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            que.append((i, j))
            seen[i][j] = 0
ans = 0
#import numpy as np
#print(np.array(seen))
while len(que) > 0:
    x, y = que.popleft()
    for tx, ty in step:
        xi, yi = x + tx, y + ty
        if xi < 0 or yi < 0 or xi >= h or yi >= w:
            continue
        if a[xi][yi] == '#':
            continue
        if a[xi][yi] == '.':
            seen[xi][yi] = seen[x][y] + 1
            ans = max(ans, seen[xi][yi])
            a[xi][yi] = '#'
            que.append((xi, yi))
    #print(np.array(seen))
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
for i in range(m):
  a[a.index(max(a))]//=2
print(sum(a))

### FIXED CODE ###

from heapq import *
n,m = map(int,input().split())
a = list(map(lambda x:-int(x),input().split()))
heapify(a)
for i in range(m):
  heappush(a,-(-heappop(a)//2))
print(-sum(a))
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
L.sort()
ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            if L[k] < L[i] + L[j]:
                ans += 1
            else:
                break
print(ans)

### FIXED CODE ###

N = int(input())
L = list(map(int,input().split()))
L.sort()
ans = 0
x = []
for i in range(N-2):
    check = 0
    for j in range(i+1,N-1):
        for k in range(j+1+check,N):
            if L[k] < L[i]+L[j]:
                check += 1
            else:
                break
        ans += check
        check -= 1
print(ans)
### BUGGY CODE ###

x,y,z,N =(int(i) for i in input().split())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]

answer=[]
for i in range(len(a)):
  for j in range(len(b)):
    for k in range(len(c)):
      answer.append(a[i]+b[j]+c[k])
sortedAnswer=sorted(answer)
for i in range(x*y*z-1,x*y*z-N-1,-1):
  print(sortedAnswer[i])

### FIXED CODE ###

#解答を見た後


x,y,z,N =(int(i) for i in input().split())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]

sa=sorted(a,reverse=True)
sb=sorted(b,reverse=True)
sc=sorted(c,reverse=True)
answer=[]

for i in range(len(sa)):
  for j in range(len(sb)):
    if (i+1)*(j+1)>N:break
    for k in range(len(sb)):
      if (i+1)*(j+1)*(k+1)>N:break 
      answer.append(sa[i]+sb[j]+sc[k])
answer=sorted(answer,reverse=True)
for i in range(0,N):
  print(answer[i])
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())

ans = 0
for a in range(1, K+1):
  for b in range(1, K+1):
    for c in range(1, K+1):
      ans += gcd(a, b, c)

print(ans)

### FIXED CODE ###

import math

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())

ans = 0
for a in range(1, K+1):
  for b in range(1, K+1):
    for c in range(1, K+1):
      ans += math.gcd(math.gcd(a, b), c)

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

s = input()
n = int(input())
li = [input().split() for i in range(n)]

for x in li:
    if x[0] == "1":
        s = s[::-1]
    else:
        if x[1] == "1":
            s = x[2] + s
        else:
            s = s + x[2]

print(s)

### FIXED CODE ###

ans = input()
q = int(input())
top = 0
first = str()
last = str()

for i in range(q):
    li =input().split()
    if li[0] =="1":
        top = (top+1)%2
    else:
        if li[1] == "1":
            if top ==0:
                first += li[2]
            else:
                last += li[2]
        else:
            if top ==1:
                first += li[2]
            else:
                last += li[2]

if top == 0:
    ans = first[::-1] + ans + last
else:
    ans = last[::-1] + ans[::-1] + first

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

import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    S = input()

    cnt = [0]*2019
    cnt[0] = 1

    # Sの右側から1ずつ左に伸ばして、cntの対応するところに加算
    rmd = 0
    L = len(S)
    for i in range(L):
        rmd = (int(S[L-i-1])*10**i + rmd) % 2019
        cnt[rmd] += 1

    ans = sum([i*(i-1)//2 for i in cnt])
    print(ans)

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    S = input()

    cnt = [0]*2019
    cnt[0] = 1

    # Sの右側から1ずつ左に伸ばして、cntの対応するところに加算
    rmd = 0
    num_rate = 1
    L = len(S)
    for i in range(L):
        rmd = (int(S[L-i-1])*num_rate + rmd) % 2019
        num_rate = num_rate*10%2019
        cnt[rmd] += 1

    ans = sum([i*(i-1)//2 for i in cnt])
    print(ans)

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

def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N,K = map(int, input().split())
    S = input()
  else:
    # For Test
    # N = 5
    # K = 1
    # S = "00010"
    N = 14
    K = 2
    S = "11101010110011"
    # N = 1
    # K = 1
    # S = "1"
    
  SC = []
  i = 0
  if S[0] == "0":SC.append(0)
  while i < N :
    if S[i] == "0":
      j = S.find("1",i)
    else:
      j = S.find("0",i)
    if j == -1: j = N 
    cnt = j - i
    i = j
    SC.append(cnt)
    
  if 'get_ipython' in globals(): print(SC)
    
  i = 0
  lenSC = len(SC) - 1
  ans = 0
  while i <= lenSC:
    cnt = 0
    k = i + K * 2
    if k > lenSC:
      k = lenSC
    for j in range(i,k + 1):
      cnt += SC[j]
    if ans < cnt:
      ans = cnt
    i += 2

  print(ans)

main()

### FIXED CODE ###

import sys
def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N,K = map(int, input().split())
    S = sys.stdin.readline()
  else:
    # For Test
    # N = 5
    # K = 1
    # S = "00010"
    # N = 14
    # K = 2
    # S = "11101010110011"
    # N = 1
    # K = 1
    # S = "1"
    N = 5
    K = 1
    S = "11111"
    
  SC = []
  i = 0
  if S[0] == "0":SC.append(0)
  while i < N :
    if S[i] == "0":
      j = S.find("1",i)
    else:
      j = S.find("0",i)
    if j == -1: j = N 
    cnt = j - i
    i = j
    SC.append(cnt)
    
  if 'get_ipython' in globals(): print(SC)
    
  SH = []
  cnt = 0
  for i in range(len(SC)):
    cnt += SC[i]
    SH.append(cnt)
  
  if 'get_ipython' in globals(): print(SH)
  
  lenSC = len(SC) - 1
  ans = 0
  for i in range(0,lenSC+1,2):
    k = i + K * 2
    if k > lenSC:
      k = lenSC
    if i != 0:
      cnt = SH[k] - SH[i-1]
    elif k == i:
      cnt = SH[k]
    else:
      cnt = SH[k] - SH[i]
    if ans < cnt: ans = cnt

  print(ans)

main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1] * (n + 1)
        self.rnk = [0] * (n + 1)

    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def size(self, x):
        return -self.root[self.find_root(x)]


# adj: [[weight, u, v] * num_edge], V: number of vertices
def kruskal(adj, V):
    adj.sort()
    uf = UnionFind(V)
    ans = 0
    for edge in adj:
        weight, u, v = edge
        if not uf.isSameGroup(u, v):
            ans += weight
            uf.unite(u, v)
    return ans


N = int(input())
x_list = []
y_list = []
for i in range(N):
    x, y = map(int, input().split())
    x_list.append([x, i])
    y_list.append([y, i])

x_list.sort()
y_list.sort()
adj = []
for i in range(N-1):
    adj.append([x_list[i + 1][0] - x_list[i][0], x_list[i + 1][1], x_list[i][1]])
    adj.append([y_list[i + 1][0] - y_list[i][0], y_list[i + 1][1], y_list[i][1]])

print(kruskal(adj, N))


### FIXED CODE ###

# 6199094

import array
import sys
input = sys.stdin.readline

class UnionFind():
    def __init__(self,n):
        self.parent = [-1 for _ in range(n)]

    def size(self,x):
        return -self.parent[self.find(x)]

    def find(self,x):
        if(self.parent[x]<0):
            return x
        else:
            self.parent[x]=self.find(self.parent[x])
            return self.parent[x]

    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return False
        if(self.size(x)<self.size(y)):
            self.parent[y]+=self.parent[x]
            self.parent[x]=y
        else:
            self.parent[x]+=self.parent[y]
            self.parent[y]=x
        return True

    def same(self,x,y):
        return self.find(x)==self.find(y)

def main():
    N = int(input())
    xli = []
    yli = []
    x_app = xli.append
    y_app = yli.append


    for i in range(N):
        x,y = (int(x) for x in input().split())
        x_app([x-1,i])
        y_app([y-1,i])
    xli.sort()
    yli.sort()

    edges = []
    edges_app = edges.append
    for i in range(N-1):
        edges_app((xli[i][1],xli[i+1][1],xli[i+1][0]-xli[i][0]))
        edges_app((yli[i][1],yli[i+1][1],yli[i+1][0]-yli[i][0]))


    edges.sort(key=lambda edge: edge[2])
    uf = UnionFind(N)
    weight = 0

    for edge in edges:
        if not uf.same(edge[0], edge[1]):
            uf.unite(edge[0], edge[1])
            weight+=edge[2]
    print(weight)

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

import numpy as np

k = int(input())
out = 0
for i in range(k):
    a = i + 1
    for j in range(k):
        b = j + 1
        gcd2 = np.gcd(a, b)
        for m in range(k):
            c = m + 1
            out = out + np.gcd(c, gcd2)


print(out)

### FIXED CODE ###

from math import  gcd

k = int(input())
out = 0

# 3つとも同じ数字のとき
out = out + (1 + k) * k / 2

#2つが同じ数字の時
for i in range(k):
    a = i + 1
    b = i + 1
    for j in range(a - 1):
        c = j + 1
        out = out + gcd(a, c) * 6

#3つとも違うとき
for m in range(k):
    a = m + 1
    for n in range(a - 1):
        b = n + 1
        gcd2 = gcd(a, b)
        for o in range(b - 1):
            c = o + 1
            out = out + gcd(gcd2, c) * 6


print(int(out))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
B = []
ans = 0
for i in A:
    B.append(list(bin(i)[2:]))
for i in range (len(B)):
    for l in range(len(B[i])):
        B[i][l] = int(B[i][l])
C = [0 for i in range(60)]
for i in B:
    for l in range(len(i)):
        if i[-(l+1)] == 1:
            C[l] += 1
for i in range(60):
    ans = (ans + C[i]*(N-C[i])*(2**i))%(10**9+7)
print(ans)

### FIXED CODE ###

import sys
mod = 10**9+7
N = int(sys.stdin.readline())
A = tuple(map(int, sys.stdin.readline().split()))
B = []
ans = 0
C = [0 for i in range(60)]
for i in A:
    for l in range(60):
        if ((i >> l) & 1) == 1:
            C[l] += 1
for i in range(60):
    t = C[i]
    ans = (ans + t*(N-t)*(2**i)) % mod
print(ans)
### BUGGY CODE ###

import itertools as itr

n, wmax = list(map(int, input().split()))
w = [0]*(n+1)
v = [0]*(n+1)

for i in range(1, n+1):
    wi, vi = list(map(int, input().split()))
    w[i] = wi
    v[i] = vi
vmax = sum(v)
    
dp = [[10**9+7]*(vmax+1) for _ in range(n+1)]
for i in range(n+1):
    dp[i][0]=0

for i, j in itr.product(range(1, n+1), range(1, vmax+1)):
    if j-v[i] >= 0:
        dp[i][j] = min(dp[i-1][j], dp[i-1][j-v[i]]+w[i])
        #print((i,j), dp[i][j])
    else:
        dp[i][j] = dp[i-1][j]

ans = [j for j in range(vmax+1) if dp[n][j] <= wmax]       
print(ans[-1])

### FIXED CODE ###

import itertools as itr

n, wmax = list(map(int, input().split()))
w = [0]*(n+1)
v = [0]*(n+1)

for i in range(1, n+1):
    wi, vi = list(map(int, input().split()))
    w[i] = wi
    v[i] = vi
vmax = sum(v)
    
dp = [[10**9+7]*(vmax+1) for _ in range(n+1)]
for i in range(n+1):
    dp[i][0]=0

for i, j in itr.product(range(1, n+1), range(1, vmax+1)):
    if j-v[i] >= 0:
        dp[i][j] = min(dp[i-1][j], dp[i-1][j-v[i]]+w[i])
        #print((i,j), dp[i][j])
    else:
        dp[i][j] = dp[i-1][j]

ans = [j for j in range(vmax+1) if dp[n][j] <= wmax]       
print(ans[-1])
### BUGGY CODE ###

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

a.sort()
count = 0


def binary_search(numbers, target_number):
    # 最小値を仮決め
    low = 0
    # 範囲内の最大値
    high = len(numbers)


    # 目的地を探し出すまでループ
    while low <= high:
        if low == high:
            return low
        # 中央値を求める（index）
        middle = (low + high) // 2
        # 中央値のnumbersの値とtarget_numberが等しい場合
        if numbers[middle] == target_number:
            return middle
        # 中央値のnumbersの値がtarget_numberより小さい場合
        elif numbers[middle] < target_number:
            low = middle + 1
        # 中央値のnumbersの値がtarget_numberより大きい場合
        else:
            high = middle - 1
    return max(low, high)


for i in range(n-2):
    for j in range(i+1, n-1):
        if a[i] + a[j] > max(a):
            count += n - (j+1)
            continue
        elif a[i] + a[j] == max(a):
            count += n - (j+1) - 1
            continue
        index = binary_search(a, (a[i]+a[j]))
        if a[i] + a[j] == a[index] or a[i] + a[j] < a[index]:
            count += (index-(j+1))
        else:
            count += (index - j)


print(count)




### FIXED CODE ###

from bisect import bisect_left

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


a.sort()
count = 0

for i in range(n-2):
    for j in range(i+1, n-1):
        x = bisect_left(a, a[i] + a[j])
        count += x - (j+1)

print(count)
### BUGGY CODE ###

N, K = map(int, input().split())
As = list(map(int, input().split()))
ts = []

t = 0
for i in range(N):
    ts.append(t)
    t = As[t]-1
    if t in ts:
        break

d = ts.index(t)
p = i - d + 1

if K > d:
    idx = (K - d) % p + d
else:
    idx = K

print(ts[idx]+1)


### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
 
t = 1
tl = [1]
ts = {1}
for i in range(len(a)):
 
    t = a[t-1]
    if t in ts:
        break
    else:
        tl.append(t)
        ts.add(t)
 
tl2 = tl[tl.index(t):len(tl)]
 
 
if k < len(tl):
    ans = tl[k]
else:
    k = k - (len(tl) - len(tl2))
    j = k % len(tl2)
    ans = tl2[j]
 
print(ans)
### BUGGY CODE ###

import queue

H,W = map(int, input().split())
grid = [0]*(H*W)
black = queue.Queue()
for i in range(H):
  A_i = input()
  for j in range(W):
    grid[W*i + j] = 0 if A_i[j] == '#' else -1
    if A_i[j] == '#':
      black.put(W*i + j)

ans = 0
while True:
  black_new = queue.Queue()
  while not black.empty():
    i = black.get()
    if i - W >= 0:
      if grid[i - W] == -1:
        grid[i - W] = ans + 1
        black_new.put(i-W)
    if i - 1 >= 0 and i%W != 0:
      if grid[i - 1] == -1:
        grid[i - 1] = ans + 1
        black_new.put(i-1)
    if i + 1 <= H*W-1 and i%W != W-1:
      if grid[i + 1] == -1:
        grid[i + 1] = ans + 1
        black_new.put(i+1)
    if i + W <= H*W-1:
      if grid[i + W] == -1:
        grid[i + W] = ans + 1
        black_new.put(i+W)
  black = black_new
  if black.empty():
    print(ans)
    break
  ans += 1

### FIXED CODE ###

import collections

H,W = map(int, input().split())
grid = [0]*(H*W)
black = collections.deque()
for i in range(H):
  A_i = input()
  for j in range(W):
    grid[W*i + j] = 0 if A_i[j] == '#' else -1
    if A_i[j] == '#':
      black.append(W*i + j)

ans = 0
while True:
  black_new = collections.deque()
  while len(black) > 0:
    i = black.pop()
    if i - W >= 0:
      if grid[i - W] == -1:
        grid[i - W] = ans + 1
        black_new.append(i-W)
    if i - 1 >= 0 and i%W != 0:
      if grid[i - 1] == -1:
        grid[i - 1] = ans + 1
        black_new.append(i-1)
    if i + 1 <= H*W-1 and i%W != W-1:
      if grid[i + 1] == -1:
        grid[i + 1] = ans + 1
        black_new.append(i+1)
    if i + W <= H*W-1:
      if grid[i + W] == -1:
        grid[i + W] = ans + 1
        black_new.append(i+W)
  black = black_new
  if len(black) == 0:
    print(ans)
    break
  ans += 1
### BUGGY CODE ###

import sys
from bisect import bisect

n = int(sys.stdin.buffer.readline())
a = list(map(int, sys.stdin.buffer.readline().split()))
b = list(map(int, sys.stdin.buffer.readline().split()))
c = list(map(int, sys.stdin.buffer.readline().split()))
a.sort()
b.sort()
c.sort()
ans = 0
for i in a:
    for j in range(bisect(b, i), n):
        ans += n - bisect(c, b[j])
print(ans)

### FIXED CODE ###

import sys
from bisect import bisect_left, bisect_right

n = int(sys.stdin.buffer.readline())
a = list(map(int, sys.stdin.buffer.readline().split()))
b = list(map(int, sys.stdin.buffer.readline().split()))
c = list(map(int, sys.stdin.buffer.readline().split()))
a.sort()
b.sort()
c.sort()
ans = 0
for j in b:
    ans += (n - bisect_right(c, j))*bisect_left(a, j)
print(ans)
### BUGGY CODE ###

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

total = 1

if 0 in li:
    total = 0
    print(total)
else:
    for a in li:
        total *= a
        if 10 ** 18 < total:
            total = -1
    print(total)

### FIXED CODE ###

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

total = 1
li.sort()
for a in li:
    if a == 0:
        total = 0
        break
    total *= a
    if 10 ** 18 < total:
        total = -1
        break
print(total)
### BUGGY CODE ###

s = input()

count = 0

while True:
    cnt = s.count("BW")
    if cnt > 0:
        s = s.replace("BW", "WB")
        count += cnt
    else:
        break

print(count)


### FIXED CODE ###

s = list(input())

count = 0
w_cnt = 0

for index in range(len(s))[::-1]:
    if s[index] == "W":
        w_cnt += 1
    else:
        count += w_cnt

print(count)
### BUGGY CODE ###

n = int(input())
l = [list(map(int,input().split())) for i in range(n)]

xcal = [[0]*n for i in range(1<<n)]
ycal = [[0]*n for i in range(1<<n)]

for i in range(1<<n):
    for j in range(n):
        xcal[i][j] = abs(l[j][0])
        ycal[i][j] = abs(l[j][1])
        for k in range(n):
            if (i>>k) & 1:
                xcal[i][j] = min(xcal[i][j],abs(l[j][0]-l[k][0]))
                ycal[i][j] = min(ycal[i][j],abs(l[j][1]-l[k][1]))
        xcal[i][j] *= l[j][2]
        ycal[i][j] *= l[j][2]
ans = [float("INF")]*(n+1)

for _ in range(3**n):
    count = 0
    state = _
    x = 0
    y = 0
    for i in range(n):
        if state%3 == 1:
            count += 1
            x += 1<<i
        elif state%3 == 2:
            count += 1
            y += 1<<i
        state //= 3
    z = x|y
    
    cost = 0
    for i in range(n):
        if not (z>>i & 1):
            cost += min(xcal[x][i],ycal[y][i])
        if cost >= ans[count]:
            break
    ans[count] = min(ans[count],cost)

for i in ans:
    print(i)


### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    n = int(input())
    l = [list(map(int,input().split())) for i in range(n)]

    xcal = [[0]*n for i in range(1<<n)]
    ycal = [[0]*n for i in range(1<<n)]

    for i in range(1<<n):
        for j in range(n):
            xcal[i][j] = abs(l[j][0])
            ycal[i][j] = abs(l[j][1])
            for k in range(n):
                if (i>>k) & 1:
                    xcal[i][j] = min(xcal[i][j],abs(l[j][0]-l[k][0]))
                    ycal[i][j] = min(ycal[i][j],abs(l[j][1]-l[k][1]))
            xcal[i][j] *= l[j][2]
            ycal[i][j] *= l[j][2]
    ans = [float("INF")]*(n+1)

    for i in range(1<<n):
        count = 0
        for j in range(n):
            if i >> j & 1:
                count += 1
        j = i
        while j >= 0:
            j &= i
            cost = 0
            for k in range(n):
                if not (i>>k & 1):
                    cost += min(xcal[j][k],ycal[i-j][k])
                if cost > ans[count]:
                    break
            ans[count] = min(ans[count],cost)
            j -= 1

    for i in ans:
        print(i)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n = int(input())
list = input().split(" ")
x = 1
for i in list:
  x = x * int(i)
if x <= 10**18:
  print(x)
else:
  print(-1)


### FIXED CODE ###

n = int(input())
al = list(map(int, input().split()))
al.sort()
ans = 1
for a in al:
    ans *= a
    if ans > 10**18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

class UnionFind(object):
    def __init__(self, n):
        self.par = [-1] * n
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return False
        else:
            if self.par[x] > self.par[y]:
                x, y = y, x
            self.par[x] += self.par[y]
            self.par[y] = x
            return True

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.par[self.find(x)]

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.par) if x < 0]

    def group_count(self):
        return len(self.roots())

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

# 最後は全部つながってない
# うしろから順番につなぐ
edges = []
for _ in range(M):
    ai, bi = map(int, input().split())
    ai, bi = ai - 1, bi - 1
    edges.append((ai, bi))
edges.reverse()

ans = [N * (N - 1) // 2]
for (ai, bi) in edges:
    u1 = uf.group_count()
    if not uf.same(ai, bi):
        ans.append(ans[-1] - uf.size(ai) * uf.size(bi))
    else:
        ans.append(ans[-1])
    uf.unite(ai, bi)

for a in ans[::-1][1:]:
    print(a)

### FIXED CODE ###

# https://atcoder.jp/contests/abc120/tasks/abc120_d

######### Union Find ########
class UnionFind(object):
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def find(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return 
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    def is_same(self, x, y):
        return self.find(x) == self.find(y)

    def count(self, x):
        return -self.root[self.find(x)]


if __name__ == '__main__':
    n, m = map(int, input().split())
    ab = []
    for _ in range(m):
        ai, bi = map(int, input().split())
        ab.append((ai - 1, bi - 1))
    all_n = n * (n - 1) // 2
    ans = [all_n]
    uf = UnionFind(n)

    # 後ろから
    for i in range(m - 1):
        ai, bi = ab[-1 - i]
        # print(ai, bi)

        if not uf.is_same(ai, bi):
            all_n -= uf.count(ai) * uf.count(bi)
        uf.unite(ai, bi)
        ans.append(all_n)

    for v in ans[::-1]:
        print(v)