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

h, w = map(int, input().split())
hw = [input() for _ in range(h)]
ans = h+w
pvs = None

def dfs(x, y, cnt, pvs):
    global ans
    if hw[x][y] == "#" and pvs != "#":
        cnt += 1
        pvs = "#"
    elif hw[x][y] == "#" and pvs == "#":
        pass
    elif hw[x][y] == ".":
        pvs = "."
    if x == h-1 and y == w-1:
        ans = min(ans, cnt)
        return ans
    if x < h-1 and y == w-1:
        dfs(x+1, y, cnt, pvs)
    if x == h-1 and y < w-1:
        dfs(x, y+1, cnt, pvs)
    if x < h-1 and y < w-1:
        dfs(x+1, y, cnt, pvs)
        dfs(x, y+1, cnt, pvs)

dfs(0, 0, 0, pvs)
print(ans)

### FIXED CODE ###

h, w = map(int, input().split())
hw = [input() for _ in range(h)]
dp = [[1000]*w for _ in range(h)]
if hw[0][0] == "#":
    dp[0][0] = 1
else:
    dp[0][0] = 0

for i in range(h):
    for j in range(w):
        if i > 0:
            if hw[i][j] == "#" and hw[i-1][j] == ".":
                dp[i][j] = min(dp[i][j], dp[i-1][j] + 1)
            else:
                dp[i][j] = min(dp[i][j], dp[i-1][j])
        if j > 0:
            if hw[i][j] == "#" and hw[i][j-1] == ".":
                dp[i][j] = min(dp[i][j], dp[i][j-1] + 1)
            else:
                dp[i][j] = min(dp[i][j], dp[i][j-1])

print(dp[h-1][w-1])
### BUGGY CODE ###

# s1 = input()
# len_s = len(s1)
# s2 = s1
# while True:
#     len_1 = len(s2)
#     s2 = s2.replace("01", "").replace("10", "")
#     len_2 = len(s2)
#     if len_1 == len_2:
#         break
#
# print(len_s - len(s2))

s = input()
s2 = s
# for i in range(len(s) // 2, 0, -1):
#     # print("i", i)
#     # print("s2", s2)
#     m1 = "1" * i + "0" * i
#     m2 = "0" * i + "1" * i
#     s2 = s2.replace(m1, "").replace(m2, "")

while True:
    len_1 = len(s2)

    a1 = "000111"
    a2 = "111000"
    if a1 in s2:
        s2 = s2.replace(a1, "")
    if a2 in s2:
        s2 = s2.replace(a2, "")

    a5 = "01"
    a6 = "10"
    if a5 in s2:
        s2 = s2.replace(a5, "")
    if a6 in s2:
        s2 = s2.replace(a6, "")

    a3 = "0011"
    a4 = "1100"
    if a3 in s2:
        s2 = s2.replace(a3, "")
    if a4 in s2:
        s2 = s2.replace(a4, "")

    len_2 = len(s2)
    if len_1 == len_2:
        break

print(len(s) - len_2)


### FIXED CODE ###

s = input()
ans = min(s.count('0'), s.count('1'))
print(ans * 2)
### BUGGY CODE ###

n,m=[int(i) for i in input().split()]
c={}
for _ in range(n):
  a,b=[int(i) for i in input().split()]
  if a in c:
    c[a].append(b)
  else:
    c[a]=[b]
k=0
l=[]
for i in range(m+1):
  if i in c:
    j=list(reversed(sorted(c[i])))
    if l:
      if j[0]>l[0]:
        k+=j[0]
        if len(j)>1:
          l=list(reversed(sorted(l+j[1:])))
      else:
        k+=l[0]
        l=list(reversed(sorted(l[1:]+j)))
    else:
      k+=j[0]
      l=j[1:]
  else:
    if l:
      k+=l[0]
      l=l[1:]
print(k)

### FIXED CODE ###

import heapq
n, m = [int(i) for i in input().split()]
ab = []
for _ in range(n):
    a, b = [int(i) for i in input().split()]
    ab.append([a, -b])
ab.sort()
j = 0
ans=0
h = []
for i in range(1, m + 1):
    while j<n and ab[j][0] <= i:
        heapq.heappush(h, ab[j][1])
        j += 1
    if h:
        ans += heapq.heappop(h)
print(-ans)
### BUGGY CODE ###

import heapq
#listから複数index削除するやつ
dellist = lambda items, indexes: [item for index, item in enumerate(items) if index not in indexes]

[N,M]=[int(x) for x in input().split()]
work=[[int(x) for x in input().split()] for _ in range(N)]

work.sort() #日付の短い順にsortしておく　これいる？いる！！！！
tank=[] #候補を入れる
res=0 #回答
indexlist=[] #バイトは重複不可なので決定済の労働をindexで管理

for i in range(M+1): #日付を後ろから見ていく
  for n,item in enumerate(work): #（日付的に働けるかをみて）候補たりうるものを探しheapqに突っ込む
    if item[0]<=i:
      heapq.heappush(tank,-item[1])
      indexlist.append(n)
      
    work=dellist(work,indexlist)
    indexlist=[]
    
  #print("tank1:",tank)
  
  if len(tank)==0: #候補がなければ次の日へ
    #print("continue.")
    continue

  else: #候補があればもっとも良いのを回答に足す
    res -= heapq.heappop(tank)
    #print("res=",res)
    
  #print("tank2:",tank)
    
print(res)

### FIXED CODE ###

import heapq
#listから複数index削除するやつ
dellist = lambda items, indexes: [item for index, item in enumerate(items) if index not in indexes]

[N,M]=[int(x) for x in input().split()]
work=[[int(x) for x in input().split()] for _ in range(N)]

work.sort() #日付の短い順にsortしておく　これいる？いる！！！！
tank=[] #候補を入れる
res=0 #回答
j=0

for i in range(M+1): #日付を後ろから見ていく
  while j<=N-1 and work[j][0]<=i: #forじゃないのはheapqに入れた分はずっと候補なのでもうみなくていいため
    heapq.heappush(tank,-work[j][1])
    j+=1
  #print("tank1:",tank)
  
  if len(tank)==0: #候補がなければ次の日へ
    #print("continue.")
    continue

  else: #候補があればもっとも良いのを回答に足す
    res -= heapq.heappop(tank)
    #print("res=",res)
    
  #print("tank2:",tank)
    
print(res)
### BUGGY CODE ###

R,C,K = map(int,input().split())
board = [[0 for _ in range(C)] for __ in range(R)]
for _ in range(K):
  r,c,v = map(int,input().split())
  board[r-1][c-1] = v

dp = [[[0 for _ in range(C)] for __ in range(R)] for ___ in range(4)]

for i in range(R):
  for j in range(C):
    dp[1][i][j] = max(dp[1][i][j],dp[0][i][j]+board[i][j])
    for k in range(4):
      if j>0:
        dp[k][i][j] = max(dp[k][i][j],dp[k][i][j-1])
      if j>0 and k>0:
        dp[k][i][j] = max(dp[k][i][j],dp[k-1][i][j-1]+board[i][j])
      if i>0:
        dp[0][i][j] = max(dp[0][i][j],dp[k][i-1][j])
        dp[1][i][j] = max(dp[1][i][j],dp[k][i-1][j]+board[i][j])
#print(*board,sep='\n')
#print(*dp,sep='\n')
print(max(max(dpij) for dpi in dp for dpij in dpi))

### FIXED CODE ###

R,C,K = map(int,input().split())
board = [[0 for _ in range(C)] for __ in range(R)]
for _ in range(K):
  r,c,v = map(int,input().split())
  board[r-1][c-1] = v

dp0 = [[0]*C for _ in range(R)]
dp1 = [[0]*C for _ in range(R)]
dp2 = [[0]*C for _ in range(R)]
dp3 = [[0]*C for _ in range(R)]

ans = 0
for i in range(R):
  for j in range(C):
    if dp1[i][j] < dp0[i][j]+board[i][j]:
      dp1[i][j] = dp0[i][j]+board[i][j]
    if j>0:
      if dp0[i][j] < dp0[i][j-1]:
        dp0[i][j] = dp0[i][j-1]
      if dp1[i][j] < dp1[i][j-1]:
        dp1[i][j] = dp1[i][j-1]
      if dp2[i][j] < dp2[i][j-1]:
        dp2[i][j] = dp2[i][j-1]
      if dp3[i][j] < dp3[i][j-1]:
        dp3[i][j] = dp3[i][j-1]
      if dp1[i][j] < dp0[i][j-1]+board[i][j]:
        dp1[i][j] = dp0[i][j-1]+board[i][j]
      if dp2[i][j] < dp1[i][j-1]+board[i][j]:
        dp2[i][j] = dp1[i][j-1]+board[i][j]
      if dp3[i][j] < dp2[i][j-1]+board[i][j]:
        dp3[i][j] = dp2[i][j-1]+board[i][j]
    if i>0:
      if dp0[i][j] < dp0[i-1][j]:
        dp0[i][j] = dp0[i-1][j]
      if dp0[i][j] < dp1[i-1][j]:
        dp0[i][j] = dp1[i-1][j]
      if dp0[i][j] < dp2[i-1][j]:
        dp0[i][j] = dp2[i-1][j]
      if dp0[i][j] < dp3[i-1][j]:
        dp0[i][j] = dp3[i-1][j]
      if dp1[i][j] < dp0[i-1][j]+board[i][j]:
        dp1[i][j] = dp0[i-1][j]+board[i][j]
      if dp1[i][j] < dp1[i-1][j]+board[i][j]:
        dp1[i][j] = dp1[i-1][j]+board[i][j]
      if dp1[i][j] < dp2[i-1][j]+board[i][j]:
        dp1[i][j] = dp2[i-1][j]+board[i][j]
      if dp1[i][j] < dp3[i-1][j]+board[i][j]:
        dp1[i][j] = dp3[i-1][j]+board[i][j]
print(max(dp0[-1][-1],dp1[-1][-1],dp2[-1][-1],dp3[-1][-1]))
### BUGGY CODE ###

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

def imosu(x,k):
  data = [0]*k
  for i in range(k):
    first = i-x[i]
    last = i+x[i]
    if first < 0:
      first = 0
    data[first] += 1
    if last+1 < k:
      data[last+1] +=-1
  ruiseki = [0]*k
  ruiseki[0] = data[0]
  for i in range(k-1):
    ruiseki[i+1] = ruiseki[i] + data[i+1]
  return ruiseki

for i in range(K):
  Flag = False
  List = imosu(List,N)
  if List.count(N) == N:
      Flag = True
  if Flag:
    break
print(*List)

### FIXED CODE ###

N,K=map(int,input().split())
List = list(map(int, input().split()))
 
def imosu(x,k):
  data = [0]*k
  for i in range(k):
    first = i-x[i]
    last = i+x[i]
    if first < 0:
      first = 0
    data[first] += 1
    if last+1 < k:
      data[last+1] +=-1
  ruiseki = [0]*k
  ruiseki[0] = data[0]
  for i in range(k-1):
    ruiseki[i+1] = ruiseki[i] + data[i+1]
  return ruiseki
 
for i in range(K):
  List = imosu(List,N)
  if List.count(N) == N:
    break
print(*List)
### BUGGY CODE ###

s=input()
l=[]
prev='R'
cnt=0
for i in range(len(s)):
    if s[i]==prev:
        cnt+=1
        continue
    else:
        if prev=='R':
            prev='L'
        else:
            prev='R'
        l.append(cnt)
        cnt=1
l.append(cnt)
x=[0 for _ in range(len(s))]
b=0
f=True
for a in l:
    if f:
        x[b+a-1]=x[b+a-1]+(a-a//2)
        x[b+a]=x[b+a]+a//2
        b+=a
        f=False
    else:
        x[b]=x[b]+(a-a//2)
        x[b-1]=x[b-1]+a//2
        b+=a
        f=True

p=''
for a in x:
    p+=str(a)+' '
print(p[:-1])

### FIXED CODE ###

import numpy as np
s=input()
prev='R'
a=0
x=np.zeros(len(s)).astype(np.uint32)
b=0
for i in range(len(s)):
    if s[i]==prev:
        a+=1
        continue
    else:
        if prev=='R':
            prev='L'
            x[b+a-1]+=(a-a//2)
            x[b+a]+=a//2
            b+=a
        else:
            prev='R'
            x[b]+=(a-a//2)
            x[b-1]+=a//2
            b+=a 
        a=1
x[b]+=(a-a//2)
x[b-1]+=a//2
p=''
for i in range(len(s)):
    p+=str(x[i])+' '
print(p[:-1])
### BUGGY CODE ###

K, S = map(int, input().split())

cnt = 0

for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i + j + k == S:
                cnt += 1
                
print(cnt)

### FIXED CODE ###

K, S = map(int, input().split())

cnt = 0

for i in range(K+1):
    for j in range(K+1):
        z = S - i - j
        if z >= 0 and z <= K:
            cnt += 1
                
print(cnt)
### BUGGY CODE ###

from copy import deepcopy
import numpy as np
def factor(N):
    ans = []
    for i in range(1,int(np.sqrt(N))+1):
        if N%i == 0:
            ans.append(i)
            if N//i != i:
                ans.append(i)
    return ans

def check(K,N):
    while 1:
        if N%K == 0:
            N = N//K
        else:
            break
    if N%K == 1:
        return True
    else:
        return False

N = int(input())
ans = len(factor(N-1)[1:])
for K in factor(N)[1:]:
    if check(K,N):
        ans += 1

print(ans)   

### FIXED CODE ###

import numpy as np
def factor(N):
    ans = []
    for i in range(1,int(np.sqrt(N))+1):
        if N%i == 0:
            ans.append(i)
            if N//i != i:
                ans.append(N//i)
    return ans

def check(K,N):
    while N >= K:
        if N%K == 0:
            N //= K
        else:
            N %= K
    if N%K == 1:
        return True
    else:
        return False

N = int(input())
ans = len(factor(N-1))-1

for K in factor(N)[1:]:
    if check(K,N):
        ans += 1

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

n, x, y = map(int,input().split())

ans = []
for i in range(1,n+1):
    for j in range(i+1,n+1):
        ans.append(min(j-i,abs(x-i)+1+abs(y-j)))
for k in range(1,n):
    print(ans.count(k))


### FIXED CODE ###

n, x, y = map(int,input().split())

ans = [0]*(n-1)
for i in range(1,n+1):
    for j in range(i+1,n+1):
        ans[min(j-i,abs(x-i)+1+abs(y-j))-1] += 1
        #ans.append(min(j-i,abs(x-i)+1+abs(y-j)))
for k in range(n-1):
    print(ans[k])
### BUGGY CODE ###

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


for q in range(Q):
  l,r = map(int, input().split())
  
  cnt = 0
  
  for i in range(l-1,r-1):
    if s[i:i+2] == 'AC':
      
      cnt += 1
  
  print(cnt)
  




### FIXED CODE ###

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

cnt = 0
n = [0]
for i in range(N-1):
    if s[i]+s[i+1] == 'AC':
        cnt += 1
    n.append(cnt)


for i in range(Q):
    l,r = map(int,input().split())
    print(n[r-1]-n[l-1])
### BUGGY CODE ###

def sort_with_three(a):
    changed = True
    while True:
        if not changed:
            break
        changed = False
        for i in range(1, N+1-2):
            if a[i] > a[i+2]:
                a[i], a[i+2] = a[i+2], a[i]
                changed = True
    return a

def sort_once(a):
    for i in range(1, N):
        if a[i] > a[i+1]:
            a[i], a[i+1] = a[i+1], a[i]
            break
    return a

N = int(input())
A = [0] * (N+1)

for i in range(1, N+1):
    A[i] = int(input())

sorted_A = sorted(A)

ans = 0
while True:
    A = sort_with_three(A)
    if A == sorted_A:
        break
    ans += 1
    A = sort_once(A)

print(ans)


### FIXED CODE ###

N = int(input())
A = [0] * (N+1)

for i in range(1, N+1):
    A[i] = int(input())

sorted_A = sorted(A)
sorted_dict_A = { sorted_A[i]: i for i in range(1, N+1) }

cnt = 0
for i in range(1, N+1):
    ind = sorted_dict_A[A[i]]
    if ind % 2 != i % 2:
        cnt += 1

print(cnt // 2)
### BUGGY CODE ###

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

i=1
gcd=1
if(n==1):
    print(p)
else:
    while((i**n)<=p):
        if(p%(i**n)==0):
            gcd=i
        i+=1
        
    print(gcd)

### FIXED CODE ###

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

i=2
gcd=1
if(n>40):
    print(1)
elif(n==1):
    print(p)
else:
    while((i**n)<=p):
        if(p%(i**n)==0):
            #print(i)
            gcd*=i
            p/=(i**n)
            i-=1
        i+=1
        
    print(gcd)
### BUGGY CODE ###

#!/usr/bin/env python3

import numpy as np


def next_line():
    return input()


def next_int():
    return int(input())


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


def next_int_array_multi_lines(size):
    return [int(input()) for _ in range(size)]


def next_str_array(size):
    return [input() for _ in range(size)]


def main():
    r, c, k = map(int, input().split())
    dp = np.full((r+1, c+1, 4), 0)
    v = np.full((r+1, c+1), 0)
    for i in range(k):
        row, col, val = map(int, input().split())
        v[row][col] = val

    for row in range(1, r + 1):
        for col in range(1, c + 1):
            for num in range(0, 4):
                if num == 0:
                    dp[row][col][num] = dp[row-1][col][3]  # simple down
                else:
                    dp[row][col][num] = max(dp[row][col][num-1],  # str
                                            dp[row][col-1][num],  # right x
                                            dp[row-1][col][3] + \
                                            v[row][col],  # down o
                                            dp[row][col-1][num-1] + \
                                            v[row][col],  # right o
                                            )
    # print(v)
    # print(dp)
    print(dp[r][c][3])


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3


def next_line():
    return input()


def next_int():
    return int(input())


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


def next_int_array_multi_lines(size):
    return [int(input()) for _ in range(size)]


def next_str_array(size):
    return [input() for _ in range(size)]


def main():
    r, c, k = map(int, input().split())
    dp = [[[0] * (c+1) for i in range(r+1)] for i in range(4)]
    v = [[0] * (c+1) for i in range(r+1)]
    for i in range(k):
        row, col, val = map(int, input().split())
        v[row][col] = val

    for row in range(1, r + 1):
        for col in range(1, c + 1):
            for num in range(0, 4):
                if num == 0:
                    dp[num][row][col] = dp[3][row-1][col]  # simple down
                else:
                    
                    dp[num][row][col] = max(dp[num-1][row][col],  # str
                                            dp[num][row][col-1],  # right x
                                            dp[3][row-1][col] + \
                                            v[row][col],  # down o
                                            dp[num-1][row][col-1] + \
                                            v[row][col],  # right o
                                            )
    print(dp[3][r][c])


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

n,m = map(int,input().split())
a = list(map(int,input().split()))
bcl = [list(map(int,input().split())) for nesya in range(m)]
for bc in bcl:
  a += [bc[1]]*bc[0]
a.sort(reverse=True)
print(sum(a[:n]))

### FIXED CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
bcl = [list(map(int,input().split())) for nesya in range(m)]
bcl.sort(reverse=True,key=lambda x:x[1])
t = 0
for bc in bcl:
  t += bc[0]
  a += [bc[1]]*bc[0]
  if t > n:
    break
a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

n, m = map(int, input().split())
a = []
b = []
ans = 0
for i in range(n):
    a_next, b_next = map(int, input().split())
    a.append(a_next)
    b.append(b_next)

for i in range(1000000):
    min_index = a.index(min(a))
    if m - b[min_index] <=0:
        break
    m = m - b[min_index]
    ans += a[min_index]*b[min_index]
    del a[min_index]
    del b[min_index]

ans += m * a[min_index]
print(ans)

### FIXED CODE ###

import numpy as np
n, m = map(int, input().split())
a = []
b = []
ans = 0
for i in range(n):
    a_next, b_next = map(int, input().split())
    a.append(a_next)
    b.append(b_next)

a_sorted_index = np.argsort(a)

for i in range(1000000):
    min_index = a_sorted_index[i]
    if m - b[min_index] <=0:
        break
    m = m - b[min_index]
    ans += a[min_index]*b[min_index]

ans += m * a[min_index]
print(ans)
### BUGGY CODE ###

#import re

i = int(input().split()[1])
s = input()
result = []

for k in range(i):
    ft, et = map(int, input().split())
    result.append(s[ft - 1:et].count("AC"))
    #result.append(len(re.findall("AC", s[ft - 1:et])))

for kekka in result:
    print(kekka)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n, q = map(int, input().split())
s = input()

count = [0]
for i in range(1, n):
    count.append(count[i-1])
    if(s[i-1:i+1] == "AC"):
        count[i] += 1

# print(count)

for _ in range(q):
    l, r = map(int, input().split())
    print(count[r-1]-count[l-1])
### BUGGY CODE ###

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

#A = [input() for _ in range(H)]

data = []

for y in range(H):
    for x, v in enumerate(input()):
        if v == '#':
            data.append([y, x, [], 0])

inf = H * W + 10
ans = [[inf for _ in range(W)] for __ in range(H)]

for v in data:
    ans[v[0]][v[1]] = 0

def check(destination, origin):
    return [destination[0], destination[1]] not in origin[2]

def cnt_update(ans, v):
    ans[v[0], v[1]] = v[3] + 1
"""
BFSまとめ
0. 現在位置、履歴、アクション数の3要素が必要
1. 更新する, アクション数を加算する
2. 条件を一致しているか、履歴に入っていないかを確認
3. popをループ
"""


while len(data):
    v = data.pop()
    v[2].append([v[0], v[1]])

    if v[1] - 1 >= 0 and ans[v[0]][v[1] - 1] > v[3] + 1:
        v_left = [v[0], v[1] - 1, v[2], v[3] + 1]
        if check(v_left, v):
            ans[v_left[0]][v_left[1]] = v_left[3]
            data.append(v_left)
    if v[1] + 1 <= W - 1 and ans[v[0]][v[1] + 1] > v[3] + 1:
        v_right = [v[0], v[1] + 1, v[2], v[3] + 1]
        if check(v_right, v):
            ans[v_right[0]][v_right[1]] = v_right[3]
            data.append(v_right)
    if v[0] - 1 >= 0 and ans[v[0] - 1][v[1]] > v[3] + 1:
        v_up = [v[0] - 1, v[1], v[2], v[3] + 1]
        if check(v_up, v):
            ans[v_up[0]][v_up[1]] = v_up[3]
            data.append(v_up)
    if v[0] + 1 <= H - 1 and ans[v[0] + 1][v[1]] > v[3] + 1:
        v_down = [v[0] + 1, v[1], v[2], v[3] + 1]
        if check(v_down, v):
            ans[v_down[0]][v_down[1]] = v_down[3]
            data.append(v_down)

print(max([a for aa in ans for a in aa]))

### FIXED CODE ###

from collections import deque

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

for y in range(H):
    for x, v in enumerate(input()):
        if v == '#':
            data.append((y, x))

ans = [[-1 for _ in range(W)] for __ in range(H)]

for v in data:
    ans[v[0]][v[1]] = 0

"""
BFSまとめ

0. 
現在位置、履歴、アクション数の3要素が必要.
処理をLIFOでなく、FIFOでやる
そのため、collection.dequeを使う
更にソートしつつ、FIFOしたい場合は、heapqを使う

1. 
更新する, アクション数を加算する

2. 
条件を一致しているか、履歴に入っていないかを確認

3. 
popをループ
"""

d = 0
while len(data):
    y, x = data.popleft()
    d = ans[y][x]

    for i, j in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        new_y = y + i
        new_x = x + j
        if new_y < 0 or H <= new_y or new_x < 0 or W <= new_x:
            continue
        if ans[new_y][new_x] == -1:
            ans[new_y][new_x] = d + 1
            data.append((new_y, new_x))

print(max([a for aa in ans for a in aa]))
### BUGGY CODE ###

s = input()
K = int(input())

s_set = set()
for i in range(len(s) + 1):
    for j in range(i + 1, len(s) + 1):
        s_set.add(s[i:j])
s_list = list(s_set)
s_list.sort()
print(s_list[K - 1])


### FIXED CODE ###

s = input()
K = int(input())

s_set = set()
for i in range(len(s)):
    for j in range(i + 1, i + K + 1):
        if j > len(s) + 1:
            break
        s_set.add(s[i:j])
s_list = list(s_set)
s_list.sort()
print(s_list[K - 1])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
for i in range(n):
    ans *= a[i]
if ans > 10**18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
if a.count(0) > 0:
    print(0)
    exit()
for i in range(n):
    ans *= a[i]
    if ans > 10**18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

def main():
    from itertools import permutations

    n, m, r, *x = map(int, open(0).read().split())
    to = x[:r]

    dis = [[float("Inf")] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        dis[i][i] = 0

    for a, b, c in zip(*[iter(x[r:])] * 3):
        dis[a][b] = c
        dis[b][a] = c

    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])

    ans = float("Inf")
    for p in permutations(to):
        tmp = 0
        for i, j in zip(p, p[1:]):
            tmp += dis[i][j]
        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.read
from itertools import permutations
def main():
    def warshall_floyd(d):
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        return d
 
    n, m, r = map(int, input().split())
    rs = tuple(map(int, input().split()))
    d = [[10**9] * n for _ in range(n)]
    m = map(int, read().split())
    mmm = zip(m, m, m)
    for s, t, dis in mmm:
        s -= 1
        t -= 1
        d[t][s] = d[s][t] = dis
    for j1 in range(n):
        d[j1][j1] = 0
    res = warshall_floyd(d)
    rsp = tuple(permutations(rs))
    result = float('inf')
    for rspe in rsp:
        res_t = 0
        for i1 in range(r - 1):
            res_t += res[rspe[i1]-1][rspe[i1+1]-1]
        result = min(result, res_t)
    print(result)
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import math
import numpy as np

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

a = np.array(a)
ans = []
while a.min() != 9999999:
    min_index = a.argmin()
    ans.append(min_index+1)
    a[min_index] = 9999999

print(' '.join([str(_) for _ in ans]))


### FIXED CODE ###

import math
import numpy as np

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

# a = np.array(a)
# ans = []
# while a.min() != 9999999:
#     min_index = a.argmin()
#     ans.append(min_index+1)
#     a[min_index] = 9999999

# print(' '.join([str(_) for _ in ans]))

l = []
for i in range(n):
    l.append([i+1, a[i]])

sl = sorted(l, key=lambda x: x[1])
sl0 = [r[0] for r in sl]
print(' '.join([str(_) for _ in sl0]))
### BUGGY CODE ###

from functools import reduce


def main():
    n = int(input())
    a_list = map(int, input().split())

    result = reduce(lambda a1, a2: a1*a2, a_list)

    if result > 10**18:
        result = -1
    
    print(result)
    

if __name__ == "__main__":
    main()


### FIXED CODE ###


def main():
    n = int(input())
    a_list = list(map(int, input().split()))

    a_list = list(filter((1).__ne__, a_list))

    if 0 in a_list:
        print('0')
        return

    result = 1

    for a in a_list:
        result = result * a

        if result > 10**18:
            print('-1')
            return

    print(result)


if __name__ == "__main__":
    main()