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

N, Q =  map(int, (input().split(' ')))
S = str(input())
lr = [tuple(map(int, input().split(' '))) for _ in range(Q)]
save = ''
i = 0
#while i < len(S):
#    if S[i] == "A":
#        if S[i+1] == "C":
#            save += 't'
#        else:
#            save += 'f'
#        i += 1
#    elif S[i] == "C":
#        i += 1
#        save += 'f'
#    else:
#        save += 'f'
#        i += 1

for left, right in lr:
    print(S[left-1: right].count('AC'))
    #save[left-1: right-1].count('t')
    #save[left-1: right-1]





### FIXED CODE ###

N, Q =  map(int, (input().split(' ')))
S = ' '+str(input())
lr = [tuple(map(int, input().split(' '))) for _ in range(Q)]
save = ''
#i = 0
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, h, x):
        while h <= self.size:
            self.tree[h] += x
            h += h & -h

bit = Bit(N)     # 要素数を与えてインスタンス化
i = 1
while i < len(S)-1:
    if S[i] == "A":
        if S[i+1] == "C":
            bit.add(i, 1)    # a2に10を加える
        else:
            pass
    i += 1

for left, right in lr:
    print(bit.sum(right-1) - bit.sum(left-1)) # a1～a6の合計を返す => 9
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
[print(A.count(i)) for i in range(1,N+1)]

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = [0] * (N+1)
for i in A:
    ans[i] += 1
for a in ans[1:]:
    print(a)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
H, W = map(int, input().split())
map = [list(input()) for i in range(H)]
cost_map = [[None]*W for i in range(H)]
starts = list()
for x in range(H):
    for y in range(W):
        if map[x][y]=="#":
            for nx, ny in [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]:
                if 0<=nx<H and 0<=ny<W:
                    if map[nx][ny]==".":
                        break
            else:
                continue
            starts.append([x, y])
for sx, sy in starts:
    queue = [[sx, sy]]
    cost_map[sx][sy] = 0
    while queue:
        x, y = queue.pop(0)
        current = cost_map[x][y]
        for nx, ny in [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]:
            if 0<=nx<H and 0<=ny<W:
                if cost_map[nx][ny] is None:
                    cost_map[nx][ny] = current + 1
                    queue.append([nx, ny])
                elif current+1 < cost_map[nx][ny]:
                    cost_map[nx][ny] = current + 1
                    queue.append([nx, ny])
if cost_map[0][0] is None:
    print(0)
    exit()
result = 0
for i in range(H):
    for j in range(W):
        if cost_map[i][j]>result:
            result = cost_map[i][j]
print(result)


### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import deque
H, W = map(int, input().split())
map = [list(input()) for i in range(H)]
checked = list()
queue = deque()
for x in range(H):
    checked.append(list())
    for y in range(W):
        if map[x][y]=="#":
            checked[x].append(True)
            queue.append((x, y, 0))
        else:
            checked[x].append(False)
neighbors = [(1,0), (0,1), (-1,0), (0,-1)]
while queue:
    x, y, res = queue.popleft()
    for dx, dy in neighbors:
        nx, ny = x+dx, y+dy
        if 0<=nx<H and 0<=ny<W:
            if not checked[nx][ny]:
                queue.append((nx, ny, res+1))
                checked[nx][ny] = True
print(res)
### BUGGY CODE ###

def main():
    n, t = map(int, input().split())
    f = [list(map(int, input().split())) for _ in range(n)]
    dp = [0 for i in range(t)]
    ls = [[] for i in range(t)]
    for i in range(n):
        for j in range(t - 1, -1, -1):
            if j - f[i][0] >= 0 and dp[j - f[i][0]] + f[i][1] > dp[j]:
                dp[j] = dp[j - f[i][0]] + f[i][1]
                ls[j] = ls[j - f[i][0]][:]
                ls[j].append(i)
    res = dp[t - 1]
    ll = ls[t - 1]
    fff = [0 for _ in range(n)]
    for sll in ll:
        fff[sll] = 1
    ff = [f[i][1] for i in range(n) if fff[i] == 0]
    if ff:
        return res + max(ff)
    else:
        return res


print(main())


### FIXED CODE ###



def main():
    n, t = map(int, input().split())
    f = [list(map(int, input().split())) for _ in range(n)]
    dp1 = [[0 for i in range(t)]for j in range(n+1)]
    dp2 = [[0 for i in range(t)]for j in range(n+1)]
    for i in range(n):
        for j in range(t - 1, -1, -1):
            if j - f[i][0] >= 0:
                dp1[i+1][j] = max(dp1[i][j - f[i][0]] + f[i][1],dp1[i][j])
            else:
                dp1[i+1][j] = dp1[i][j]
    for i in range(n):
        for j in range(t - 1, -1, -1):
            if j - f[n-1-i][0] >= 0:
                dp2[i+1][j] = max(dp2[i][j - f[n-1-i][0]] + f[n-1-i][1],dp2[i][j])
            else:
                dp2[i+1][j] = dp2[i][j]

    res = 0
    for i in range(n):
        for j in range(t):
            res = max(res,dp1[i][j]+f[i][1]+dp2[n-1-i][t-1-j])

    return res




print(main())
### BUGGY CODE ###

def inpl(): return input().split()

n = int(input())
a = sorted(list(map(int, inpl())))

p = 10 ** 9 + 7

ans = 1
i = (n - 1) % 2
j = 0
while (i + j) < n:
    cnt = a.count(i + j)
    if (j % 2 == 0):
        if cnt != 2:
            if not((cnt == 1) and (((i + j) == 0) or ((i + j) == (n - 1)))):
                ans = 0
                break
        else:
            if ((i + j) == 0):
                ans = 0
                break
            else:
                ans *= cnt
                if ans > p:
                    ans %= p
    else:
        if cnt != 0:
            ans = 0
            break
    j += 1
print(ans)

### FIXED CODE ###

def inpl(): return input().split()

n = int(input())
a = sorted(list(map(int, inpl())))
p = 10 ** 9 + 7

if a[0] == 0:
    st = 1
    next_value = 2
else:
    st = 0
    next_value = 1

ans = 1
found = False
for i in range(st, n):    
    if (next_value == a[i]):
        if found:
            next_value += 2
            found = False
            ans *= 2
            if ans > p:
                ans %= p
        else:
            found = True
    else:
        ans = 0
        break
print(ans)
### BUGGY CODE ###

a, b, x = map(int, input().split())
num_list = [i for i in range(a, b + 1) if i % x == 0]
print(len(num_list))

### FIXED CODE ###

a, b, x = map(int, input().split())


def func(n, x):
    if n == -1:
        return 0
    return n//x + 1


print(func(b, x) - func(a-1, x))
### BUGGY CODE ###

N = int(input())
L = []
for i in range(N):
	A = input()
	if L.count(A) == 0:
		L.append(A)
	else:
		L.remove(A)

print(len(L))

### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
	A.append(int(input()))

A = sorted(A)

x = A[0]
s = 0
c = 0
for i in range(N):
	if A[i] == x:
		c += 1
	else:
		x = A[i]
		if c % 2 == 1:
			s += 1
		c = 1

if c % 2 == 1:
	s += 1

print(s)
### BUGGY CODE ###

N, M, L = map(int, input().split())
dist = [[float('inf')] * N for _ in range(N)]
for i in range(N):
    dist[i][i] = 0
    
for _ in range(M):
    a, b, c = map(int, input().split())
    dist[a-1][b-1] = dist[b-1][a-1] = c

for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

old_dist = [row[:] for row in dist]
for i in range(N):
    for j in range(N):
        if old_dist[i][j] <= L:
            dist[i][j] = 1
        else:
            dist[i][j] = float('inf')
        if i == j:
            dist[i][j] = 0
            
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Q = int(input())
for _ in range(Q):
    start, end= map(int, input().split())
    if dist[start-1][end-1] != float('inf'):
    	print(dist[start-1][end-1] - 1)
    else:
        print(-1)

### FIXED CODE ###

N, M, L = map(int, input().split())
dist = [[10**12] * N for _ in range(N)]
for i in range(N):
    dist[i][i] = 0
    
for _ in range(M):
    a, b, c = map(int, input().split())
    if c <= L:
    	dist[a-1][b-1] = dist[b-1][a-1] = c

for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

old_dist = [row[:] for row in dist]
for i in range(N):
    for j in range(N):
        if old_dist[i][j] <= L:
            dist[i][j] = 1
            
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Q = int(input())
for _ in range(Q):
    start, end= map(int, input().split())
    if dist[start-1][end-1] < 10**12:
    	print(dist[start-1][end-1] - 1)
    else:
        print(-1)
### BUGGY CODE ###

n, k = map(int, input().split())
lst = []
for i in range(n):
    a, b = map(int, input().split())
    for j in range(b):
        lst.extend([a])
lst.sort()
print(lst[k-1])

### FIXED CODE ###

n, k = map(int, input().split())
dic = {}
lst = []
ans = 0
for i in range(n):
    a, b = map(int, input().split())
    if (a in dic)==False:
        dic[a] = b
        lst.append(a)
    else:
        dic[a] += b
lst.sort()

for i in range(len(dic)):
    if k > (dic[lst[i]] + ans):
        ans += dic[lst[i]]
    else:
        ans = lst[i]
        break
print(ans)
### BUGGY CODE ###

N = int(input())
TT=0
AA=0
for k in range(N):
    T,A = map(int,input().split())
    k=min(TT//T,AA//A)
    for k in range(100000000000000000):
        k+=1
        if T*k>=TT and A*k>=AA:
            TT=T*k 
            AA=A*k
            break
print(TT+AA)

### FIXED CODE ###

N = int(input())
TT,AA= map(int,input().split())
for k in range(1,N):
    T,A = map(int,input().split())
    j = max((TT-1+T)//T,(AA-1+A)//A)
    TT = T*j 
    AA = A*j
        
print(TT + AA)
### BUGGY CODE ###

for _ in range(int(input())):
    X = input()
    Y = input()
    dp = [[0 for y in range(len(Y)+1)] for x in range(len(X)+1)]
    for x in range(1, len(X) + 1):
        for y in range(1, len(Y) + 1):
            if X[x-1] == Y[y-1]:
                dp[x][y] = dp[x-1][y-1] + 1
            else:
                dp[x][y] = max(dp[x-1][y], dp[x][y-1])
    print(dp[-1][-1])


### FIXED CODE ###

def ser(X, Y):
    dp = [[0] * (len(Y)+1) for x in range(len(X)+1)]
    for i, x in enumerate(X, 1):
        tmp = dp[i]
        pre = dp[i-1]
        for j, y in enumerate(Y, 1):
            if x == y:
                tmp[j] = pre[j-1] + 1
            elif pre[j] < tmp[j-1]:
                tmp[j] = tmp[j-1]
            else:
                tmp[j] = pre[j]
    return(dp[-1][-1])

for _ in range(int(input())):
    X, Y = input(), input()
    print(ser(X, Y))
### BUGGY CODE ###

n = int(input())
s = input()

r = [0] * n
g = [0] * n
b = [0] * n
ri = gi = bi = 0
for i, c in enumerate(s):
  if c == "R":
    ri += 1
  elif c == "G":
    gi += 1
  if c == "B":
    bi += 1
  r[i] = ri
  g[i] = gi
  b[i] = bi

 
ans = 0

for k in range(2, n):
  for j in range(1, k):
    if s[k] == s[j]:
      continue
    i = 2 * j - k
    x = None
    c = None
    if s[k] != "R" and s[j] != "R":
      x = r
      c = "R"
    elif s[k] != "G" and s[j] != "G":
      x = g
      c = "G"
    elif s[k] != "B" and s[j] != "B":
      x = b
      c = "B"
    ans += x[j - 1]
    if i >= 0 and s[i] == c:
      ans -= 1


print(ans)

### FIXED CODE ###

n = int(input())
s = input()

r = [0] * n
g = [0] * n
b = [0] * n
ri = gi = bi = 0
for i, c in enumerate(s):
  if c == "R":
    ri += 1
  elif c == "G":
    gi += 1
  if c == "B":
    bi += 1
  r[i] = ri
  g[i] = gi
  b[i] = bi

 
ans = r[-1] * g[-1] * b[-1]

for k in range(2, n):
  for j in range(1, k):
    if s[k] == s[j]:
      continue
    i = 2 * j - k
    if i < 0 :
      continue
    if s[k] != s[i] and s[j] != s[i]:
      ans -= 1

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

# 接続最大クラスタのサイズが答え？
from networkx import Graph, connected_components

N, M = [int(x) for x in input().split(' ')]

list_ab = [None] * M
for i in range(M):
    a, b = [int(x) for x in input().split(' ')]
    list_ab[i] = (a, b)


G = Graph()
G.add_nodes_from(range(N))
G.add_edges_from(list_ab)

# get max connected component
max_size = 0
for component in connected_components(G):
    max_size = max(max_size, len(component))
    #     if len(component) > max_size:
    #             max_cluster = component
    #             max_size = len(max_cluster)
print(max_size)

### FIXED CODE ###

# 接続最大クラスタのサイズが答え？

N, M = [int(x) for x in input().split(' ')]

# from collections import defaultdict
# d = defaultdict(set)

# for i in range(M):
#     a, b = [int(x) for x in input().split(' ')]
#     d[a].add(b)
#     d[b].add(a)

class UF:
    def __init__(self):
        self.r = [-1] * N

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

    def union(self, i, j):
        i -= 1
        j -= 1
        ri = self.root(i)
        rj = self.root(j)
        if ri == rj:
            return
        else:
            if not self.r[ri] < self.r[rj]:
                ri, rj = rj, ri
            self.r[ri] += self.r[rj]
            self.r[rj] = ri
            return

    def max_size(self):
        return -min(self.r)

uf = UF()
for i in range(M):
    uf.union(*[int(x) for x in input().split(' ')])
print(uf.max_size())
### BUGGY CODE ###

name = set()
n = int(input())
s = input()

for x in range(n - 2):
    for y in range(x + 1, n - 1):
        for z in range(y + 1, n):
            name.add(int(s[x] + s[y] + s[z]))

print(len(name))


### FIXED CODE ###

ans = 0
n = int(input())
s = input()

for x in range(10):
    if s.find(str(x)) > -1:
        tmp = s[s.find(str(x)) + 1:]
        for y in range(10):
            if tmp.find(str(y)) > -1:
                tmp2 = tmp[tmp.find(str(y)) + 1:]
                for z in range(10):
                    if tmp2.find(str(z)) > -1:
                        ans += 1

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

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = sorted(list(map(int, input().split())), reverse = True)

list = []
for i in range(x):
    for j in range(y):
        list.append(a[i]+b[j])
list = sorted(list, reverse = True)[:k]

list1 = []
for i in range(len(list)):
    for j in range(z):
        list1.append(list[i]+c[j])
list1 = sorted(list1, reverse = True)[:k]

for i in range(k):
    print(list1[i])

### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse = True)
b = sorted(list(map(int, input().split())), reverse = True)
c = sorted(list(map(int, input().split())), reverse = True)

list = []
for aa in a:
    for bb in b:
        list.append(aa+bb)
list.sort(reverse = True)
list = list[:k]

list1 = []
for ab in list:
    for cc in c:
        list1.append(ab+cc)
list1.sort(reverse = True)
list1 = list1[:k]

for i in range(k):
    print(list1[i])
### BUGGY CODE ###

H, N = map(int, input().split())
AB = sorted([list(map(int, input().split())) for _ in range(N)], key = lambda x: x[0])

dp = [0] + [float("inf")]*(H + AB[-1][0])
for j in range(H+1):
    for i in range(N):
        if dp[j] < float("inf"):
            try:
                dp[j + AB[i][0]] = min(dp[j + AB[i][0]], dp[j] + AB[i][1])
            except IndexError:
                pass

print(min(dp[H:]))

### FIXED CODE ###

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

dp = [float("inf")]*H + [0]
ans = float("inf")
for j in reversed(range(H+1)):
    for i in range(N):
        if dp[j] < float("inf"):
            if j - AB[i][0] >= 0:
                dp[j - AB[i][0]] = min(dp[j - AB[i][0]], dp[j] + AB[i][1])
            else:
                ans = min(ans, dp[j] + AB[i][1])

print(min(dp[0], ans))
### BUGGY CODE ###

def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

s = input()
t = input()
n = len(s)
m = len(t)

pre = [[0]*(m+1) for _ in range(n+1)]
dp = [[0]*(m+1) for _ in range(n+1)]

for si in range(n):
    for ti in range(m):
        if s[si]==t[ti]:
            dp[si+1][ti+1] = dp[si][ti]+1
        else:
            dp[si+1][ti+1] = max(dp[si+1][ti],dp[si][ti+1])

ans = ""
x = dp[-1][-1]
for i in range(n,-1,-1):
    for j in range(m,-1,-1):
        if dp[i][j]==x:
            if (dp[i-1][j]==x-1) and (dp[i][j-1]==x-1):
                ans = s[i-1]+ans
                x-=1
                break
print(ans)


### FIXED CODE ###

def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

s = input()
t = input()
n = len(s)
m = len(t)

pre = [[0]*(m+1) for _ in range(n+1)]
dp = [[0]*(m+1) for _ in range(n+1)]

for si in range(n):
    for ti in range(m):
        if s[si]==t[ti]:
            dp[si+1][ti+1] = dp[si][ti]+1
        else:
            dp[si+1][ti+1] = max(dp[si+1][ti],dp[si][ti+1])

ans = ""
x = dp[-1][-1]
for i in range(n,-1,-1):
    for j in range(m,-1,-1):
        if dp[i][j]==x:
            if (dp[i-1][j]==x-1) and (dp[i][j-1]==x-1):
                ans = s[i-1]+ans
                x-=1
                break
print(ans)
### BUGGY CODE ###

N,M= map(int,input().split())
A = list(map(int,input().split()))
if len(A) > 1:
    ind = A.index(max(A))
    top = A.pop(ind)
    sec = max(A)
    for i in range(M):
        top = top/2
        if top < sec:
            A.append(top)
            top = A.pop(A.index(max(A)))
            sec = max(A)
    A.append(top)
    A =list(map(int,A))
    print(sum(A))
else:
    print(int(A[0]/(2**M)))
    # ind = A.index(max(A))
    # A[ind] = A[ind]/2
    # print(A)

### FIXED CODE ###

from heapq import heappush,heappop,heapify
N,M= map(int,input().split())
A = list(map(int,input().split()))
a = [-x for x in A]
heapify(a)
for i in range(M):
    item = -1*heappop(a)
    item = item//2
    heappush(a,-1*item)
print(-sum(a))
### BUGGY CODE ###

n, m = map(int, input().split())
data = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int,input().split())
    data[a - 1].append(b - 1)
    data[b - 1].append(a - 1)

ans = [0] * (n - 1)

def bfs(i, queue, p):
    while len(queue) > 0:
        x = queue.pop(0)
        pre = p.pop(0)
        for j in range(len(x)):
            if ans[x[j] - 1] == 0 and x[j] != 0:
                ans[x[j] - 1] = pre + 1
                queue.append(data[x[j]])
                p.append(x[j])

queue = []
pre = [0]
queue.append(data[0])
bfs(0, queue, pre)

if 0 not in ans:
    print("Yes")
    for i in range(len(ans)):
        print(ans[i])
else:
    print("No")

### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
data = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int,input().split())
    data[a - 1].append(b - 1)
    data[b - 1].append(a - 1)

ans = [0] * (n - 1)

def bfs(i, queue, p):
    while len(queue) > 0:
        x = queue.popleft()
        pre = p.popleft()
        for j in range(len(x)):
            if ans[x[j] - 1] == 0 and x[j] != 0:
                ans[x[j] - 1] = pre + 1
                queue.append(data[x[j]])
                p.append(x[j])

queue = deque()
pre = deque()
pre.append(0)
queue.append(data[0])
bfs(0, queue, pre)

if 0 not in ans:
    print("Yes")
    for i in range(len(ans)):
        print(ans[i])
else:
    print("No")
### BUGGY CODE ###

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

for i in range(k):
    b = [0] * (n+1)
    c = list(b)
    for j in range(n):
        l = max(0, j-a[j])
        r = min(n, j+a[j]+1)
        b[l] += 1
        b[r] -= 1
    for j in range(1, n):
        b[j] += b[j-1]
    a = b
    if b == c:
        for j in range(n):
            print(a[j], end=' ')
        exit()
for i in range(n):
    print(a[i], end=' ')


### FIXED CODE ###

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


for i in range(k):
    b = [0] * (n+1)
    for j in range(n):
        l = max(0, j-a[j])
        r = min(n, j+a[j]+1)
        b[l] += 1
        b[r] -= 1
    for j in range(n):
        b[j+1] += b[j]
    b.pop()
    if a == b:
        break
    a = b
print(' '.join(map(str, a)))
### BUGGY CODE ###

A, B = map(int, input().split())

x = 0

for n in range(A, B + 1):
	#print("{:010b}".format(x))
	x ^= n

#print(x, "{:b}".format(x))
print(x)


### FIXED CODE ###

A, B = map(int, input().split())

r = 0
def F(n):
	ec = (n + 1) // 2
	r = ec % 2
	if not n % 2:
		r ^= n
	return r
"""
def F2(n):
	r = 0
	for i in range(n + 1):
		r ^= i
	return r
"""
#print("{:04b}".format(F2(4)))
print(F(A - 1) ^ F(B))
### BUGGY CODE ###

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

index = [i for i in range(N)]

dict_value = {key: val for key, val in zip(index, P)}

ac = [dict_value[i] for i in range(N) if dict_value[i] <= min([v for k, v in dict_value.items() if k <= i])]

print(len(ac))


### FIXED CODE ###

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

value = 10 ** 9
ans = 0
for v in P:
    if v < value:
        ans += 1
        value = v
print(ans)
### BUGGY CODE ###

S = input()
rem = [0]*2019

n = ""
for s in S[::-1]:
    n = s + n
    tmp = int(n)%2019
    rem[tmp] += 1
    
ans = 0
for i in rem:
    ans += ((i*(i-1))//2)

print(ans+rem[0])

### FIXED CODE ###

S = input()[::-1]
rem = [0]*2019

n = 0
d = 1

for s in S:
    n = n%2019 + (int(s)*d)%2019
    tmp = n%2019
    rem[tmp] += 1
    d *= 10
    d %= 2019
    
ans = 0
for i in rem:
    ans += ((i*(i-1))//2)

print(ans+rem[0])
### BUGGY CODE ###

def main():
    h, w = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(h)]
    b = [list(map(int, input().split())) for _ in range(h)]
    n = 2000
    m = n//2
    dp = [[[False]*n for j in range(w)] for i in range(h)]
    dp[0][0][m+abs(a[0][0] - b[0][0])] = True
    dp[0][0][m-abs(a[0][0] - b[0][0])] = True
    for i in range(h):
        for j in range(w):
            x = abs(a[i][j] - b[i][j])
            if 0 < i and 0 < h:
                for k in range(x, n-x):
                    if dp[i-1][j][k] or dp[i][j-1][k]:
                        dp[i][j][k-x] = True
                        dp[i][j][k+x] = True
            elif 0 < i:
                for k in range(x, n-x):
                    if dp[i-1][j][k]:
                        dp[i][j][k-x] = True
                        dp[i][j][k+x] = True
            elif 0 < j:
                for k in range(x, n-x):
                    if dp[i][j-1][k]:
                        dp[i][j][k-x] = True
                        dp[i][j][k+x] = True
    ans = float("inf")
    for i in range(n):
        if dp[h-1][w-1][i]:
            ans = min(ans, abs(m-i))
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import numpy as np
def main():
    h, w = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(h)]
    b = [list(map(int, input().split())) for _ in range(h)]
    n = 80*(80+80) + 10
    m = n//2
    dp = [[None]*w for i in range(h)]
    for i in range(h):
        for j in range(w):
            dp[i][j] = np.zeros(n, np.bool)
    dp[0][0][m+abs(a[0][0] - b[0][0])] = True
    dp[0][0][m-abs(a[0][0] - b[0][0])] = True
    for i in range(h):
        for j in range(w):
            x = abs(a[i][j] - b[i][j])
            if 0 < i and 0 < h:
                dp[i][j][x:] |= dp[i-1][j][:n-x]
                dp[i][j][:n-x] |= dp[i-1][j][x:]
                dp[i][j][x:] |= dp[i][j-1][:n-x]
                dp[i][j][:n-x] |= dp[i][j-1][x:]
            elif 0 < i:
                dp[i][j][x:] |= dp[i-1][j][:n-x]
                dp[i][j][:n-x] |= dp[i-1][j][x:]
            elif 0 < j:
                dp[i][j][x:] |= dp[i][j-1][:n-x]
                dp[i][j][:n-x] |= dp[i][j-1][x:]
    ans = float("inf")
    for i in range(m-80-1, m+80+2):
        if dp[h-1][w-1][i]:
            ans = min(ans, abs(m-i))
    print(ans)

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

from operator import mul
from functools import reduce

N = int(input())
A = list(map(int,input().split()))
anser = reduce(mul, A)
if anser > 10 ** 18:
    print("-1")
else:
    print(anser)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
anser = 1
if 0 in A:
    print("0")
    exit()
for i in A:
    anser *= i
    if anser > 10 ** 18:
        print("-1")
        exit()
print(anser)