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

# 再帰関数使用時は再帰上限を十分にとること
import sys
sys.setrecursionlimit(10 ** 8)

# グローバル変数定義
INF = 10 ** 13
N, W = map(int, input().split())

# knopsock[n][0] = w    :   n = 品物の位置 , w = 重さ
# knopsock[n][1] = v    :   n = 品物の位置 , v = 価値
knapsack = [list(map(int, input().split())) for _ in range(N)]

# db[n][w] = v          :   w = 現在の重さ, n = 見てきた品物の数, v = 現在の価値
db = [[INF] * W for _ in range(N)]


def dfs(n, w):
    """
    品物に対する深さ優先探索による全探索（メモ化再帰）。

    Args:
        n (int) : 見てきた品物の数
        w (int) : ここまでの重さの総和

    Returns:
        v (int) : 価値の総和の最大値
    """

    # 終了条件：現在の個数が全ての品物の個数を越える
    if n >= N:
        return 0

    if w + knapsack[n][0] > W:
        # １つ前までの重さ + 今回の品物の重さが重さの最大値を越えていたら今回の品物は選べない
        return dfs(n + 1, w)
    else:
        # 今回の品物を選ぶか選ばないかで全探索
        return max([dfs(n + 1, w), dfs(n + 1, w + knapsack[n][0]) + knapsack[n][1]])


def main():
    out = dfs(0, 0)
    print(out)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
readline = sys.stdin.readline


def chmax(a, b):
    """
    2値の大きい値を返す

    Args:
        a   (int)   : 値１
        b   (int)   : 値２
    Return:
        a   (int)   : aまたはbの大きい値
    """
    if a < b:
        a = b
    return a


def main():

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

    # knopsock[n][0] = w    :   n = 品物の位置 , w = 重さ
    # knopsock[n][1] = v    :   n = 品物の位置 , v = 価値
    knapsack = [list(map(int, readline().split())) for _ in range(N)]

    # db[n][w] = v          :   w = 現在の重さ, n = 見てきた品物の数, v = 現在の価値
    dp = [[0] * (W + 1) for _ in range(N + 1)]

    for n in range(1, N + 1):
        for w in range(W + 1):
            if w - knapsack[n - 1][0] < 0:
                dp[n][w] = dp[n - 1][w]
            else:
                dp[n][w] = chmax(dp[n - 1][w], dp[n - 1]
                                 [w - knapsack[n - 1][0]] + knapsack[n - 1][1])

    print(dp[N][W])


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

from collections import deque
H,W = map(int,input().split())
A = [input().strip() for _ in range(H)]
B = [[0 for _ in range(W)] for _ in range(H)]
que = deque([])
for i in range(H):
    for j in range(W):
        if A[i][j]=="#":
            que.append((i,j,0))
            B[i][j] = 1
dmax = 0
while que:
    i,j,d = que.popleft()
    if j+1<W and B[i][j+1]==0:
        B[i][j+1]=d+1
        dmax = max(dmax,d+1)
        que.append((i,j+1,d+1))
    if i-1>=0 and B[i-1][j]==0:
        B[i-1][j]=d+1
        dmax = max(dmax,d+1)
        que.append((i-1,j,d+1))
    if j-1>=0 and B[i][j-1]==0:
        B[i][j-1]=d+1
        dmax = max(dmax,d+1)
        que.append((i,j-1,d+1))
    if i+1<H and B[i+1][j]==0:
        B[i+1][j]=d+1
        dmax = max(dmax,d+1)
        que.append((i+1,j,d+1))
print(dmax)

### FIXED CODE ###

from collections import deque
H,W = map(int,input().split())
A = [list(input().strip()) for _ in range(H)]
que = deque([])
for i in range(H):
    for j in range(W):
        if A[i][j]=="#":
            que.append((i,j,0))
tot = 0
while que:
    i,j,cnt = que.popleft()
    if j+1<W and A[i][j+1]==".":
        A[i][j+1]="#"
        que.append((i,j+1,cnt+1))
        tot = cnt+1
    if j-1>-1 and A[i][j-1]==".":
        A[i][j-1]="#"
        que.append((i,j-1,cnt+1))
        tot = cnt+1
    if i+1<H and A[i+1][j]==".":
        A[i+1][j]="#"
        que.append((i+1,j,cnt+1))
        tot = cnt+1
    if i-1>-1 and A[i-1][j]==".":
        A[i-1][j]="#"
        que.append((i-1,j,cnt+1))
        tot = cnt+1
print(tot)
### BUGGY CODE ###

N = int(input())
S_list = [[_ for _ in input()] for i in range(N)]

gift = []
for i_s in S_list:
    if not i_s in gift:
        gift.append(i_s)

print(len(gift))

### FIXED CODE ###

N = int(input())
S_list = [input() for i in range(N)]

S_set = set(S_list)
print(len(S_set))
### BUGGY CODE ###

import sys


def input(): return sys.stdin.readline().strip()


N, M = (list)(map(int, input().split()))
edge = []

for _ in range(M):
    edge.append((list)(map(int, input().split())))


inf = 10**15

d = [inf]*(N+1)
d[1] = 0
ans = inf
for i in range(N-1):
    for a, b, c in edge:
        c = -c
        new_d = d[a]+c
        if d[a] != inf and d[b] > new_d:
            d[b] = new_d

neg = [False]*(N+1)
for i in range(N):
    for a, b, c in edge:
        c = -c
        new_d = d[a]+c
        if d[a] != inf and d[b] > new_d:
            d[b] = new_d
            neg[b] = True
        if neg[a]:
            neg[b] = True

if neg[-1]:
    print('inf')
else:
    print(-d[-1])


### FIXED CODE ###

import sys


def input(): return sys.stdin.readline().strip()


N, M = (list)(map(int, input().split()))
edge = []

for _ in range(M):
    edge.append((list)(map(int, input().split())))


inf = 10**15

d = [inf]*(N+1)
d[1] = 0
ans = inf
for i in range(N):
    update = False
    for a, b, c in edge:
        c = -c
        new_d = d[a]+c
        if d[a] != inf and d[b] > new_d:
            d[b] = new_d
            update = True

    if not update:
        break

neg = [False]*(N+1)
for i in range(N):
    for a, b, c in edge:
        c = -c
        new_d = d[a]+c
        if d[a] != inf and d[b] > new_d:
            d[b] = new_d
            neg[b] = True
        if neg[a]:
            neg[b] = True

if neg[-1]:
    print('inf')
else:
    print(-d[-1])
### BUGGY CODE ###

def main():
  s=list(input())
  n=len(s)
  dp=[0]*13
  mod=pow(10,9)+7
  if s[-1]=='?':
    dp=[1]*10+[0]*3
  else:
    dp[int(s[-1])]=1
  p_dp=[0]*13
  for i in range(2,n+1):
    if s[-i]=='?':
      for j in range(10):
        a=(j*pow(10,i-1,13))%13
        for k in range(13):
          p_dp[(a+k)%13]+=dp[k]
    else:
      j=int(s[-i])
      a=(j*pow(10,i-1,13))%13
      for k in range(13):
        p_dp[(a+k)%13]+=dp[k]
    
    for k in range(13):
      p_dp[k]%=mod
    dp=p_dp.copy()
    p_dp=[0]*13
  print(dp[5])

if __name__=='__main__':
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())


### FIXED CODE ###

def main():
  s=list(input())
  n=len(s)
  dp=[0]*13
  mod=pow(10,9)+7
  if s[-1]=='?':
    dp=[1]*10+[0]*3
  else:
    dp[int(s[-1])]=1
  p_dp=[0]*13
  for i in range(2,n+1):
    if s[-i]=='?':
      for j in range(10):
        a=(j*pow(10,i-1,13))%13
        for k in range(13):
          p_dp[(a+k)%13]+=dp[k]
    else:
      j=int(s[-i])
      a=(j*pow(10,i-1,13))%13
      for k in range(13):
        p_dp[(a+k)%13]+=dp[k]
    
    for k in range(13):
      p_dp[k]%=mod
    dp=[k for k in p_dp]
    p_dp=[0]*13
  print(dp[5])

if __name__=='__main__':
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())
### BUGGY CODE ###

#frog1からジャンプの回数が変数kになった
n,k=map(int,input().split())
h=list(map(int,input().split()))
INF=float('INF')
dp=[INF]*n
dp[0]=0
for i in range(1,n):
    for j in range(1,k+1):
        if i-j<0:#out of indexを防ぐ
            continue
        dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))#dp[i]と大小を比較する
print(dp[n-1])

### FIXED CODE ###

#b
n,k=map(int,input().split())
h=list(map(int,input().split()))

N=100010
INF=float('INF')
dp=[INF]*N
dp[0]=0

for i in range(1,n):
    for j in range(1,k+1):
        if i-j>=0:
            dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))

print(dp[n-1])
### BUGGY CODE ###

import sys
n,k=map(int,input().split())
a=[int(x) for x in input().split()]
vis=[0]
now=0
for i in range(1,k+1):
  now=a[now]-1
  if now in vis:
    bgn=vis.index(now)
    print(vis[bgn+((k-bgn)%(len(vis)-bgn))]+1)
    sys.exit()
  else:
    vis.append(now)
print(vis[-1]+1)


### FIXED CODE ###

import sys
n,k=map(int,input().split())
a=[int(x) for x in input().split()]
vis_ti=[-1]*n
vis_at=[0]
now=0
for i in range(1,k+1):
  now=a[now]-1
  if vis_ti[now]>=0:
    bgn=vis_ti[now]
    print(vis_at[bgn+(k-bgn)%(i-bgn)]+1)
    sys.exit()
  vis_ti[now]=i
  vis_at.append(now)
print(vis_at[-1]+1)
### BUGGY CODE ###

def expect(p, i, j):
    sum=0
    for l in range(j-i+1):
        sum += (1 + p[i + l]) / 2
    return sum

n,k = map(int, input().split())
p=list(map(int, input().split()))
max = 0

for j in range(n-k+1):
    tmp = expect(p, j, k+j-1)
    if max < tmp: max = tmp
print(max)

### FIXED CODE ###

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

for i in range(len(p)):
    p[i] = (1+p[i]) / 2
    
max = 0

for i in range(k):
    max += p[i]
tmp = max

for i in range(n-k):
    tmp = tmp - p[i] + p[i+k]
    if max < tmp: max = tmp
print(max)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000)

N, W = map(int, input().split())
wv = [[int(i) for i in input().split()] for _ in range(N)]

def knapsack(i, w) :
    if i == N :
        return 0
        
    if w + wv[i][0] <= W :
        return max(knapsack(i+1, w+wv[i][0])+wv[i][1], knapsack(i+1, w))
    else :
        return knapsack(i+1, w)
        
print(knapsack(0, 0))

### FIXED CODE ###

N, W = map(int, input().split())
wv = [[int(i) for i in input().split()] for _ in range(N)]
V = max([wv[i][1] for i in range(N)]) * N

dp = [[float('inf')] * (V + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N) :
    for j in range(V+1) :
        if j >= wv[i][1] :
            dp[i+1][j] = min(dp[i][j-wv[i][1]] + wv[i][0], dp[i][j])
        else :
            dp[i+1][j] = dp[i][j]

for i in range(V, -1, -1) :
    if dp[N][i] <= W :
        print(i)
        break
### BUGGY CODE ###

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

### FIXED CODE ###

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

import sys

INF = float('inf')

input = sys.stdin.readline


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


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

# DP配列を初期化
dp = [INF] * N

# 初期条件を入力
dp[0] = 0

# テーブルを更新 もらうDP
for i in range(1, N):
    j = i - K
    x = 0
    if 0 <= j:
        x = j
    else:
        x = 0
    dp[i] = min([dp_ + abs(h[i] - h_) for dp_, h_ in zip(dp[x:i], h[x:i])])

print(dp[N - 1])

### FIXED CODE ###

import sys

INF = float('inf')

input = sys.stdin.readline


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


N, K = LIST()
h = LIST()

# DP配列を初期化
dp = [INF] * N

# 初期条件を入力
dp[0] = 0

# テーブルを更新 もらうDP
for i in range(1, N):
    x = max(0, i - K)
    dp[i] = min([dp_ + abs(h[i] - h_) for dp_, h_ in zip(dp[x:i], h[x:i])])

print(dp[N - 1])
### BUGGY CODE ###

import math
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


INF = float('inf')


def f(m):
    ans = 0
    r_m = math.sqrt(m)
    for i in range(1, int(r_m) + 1):
        for j in range(1, int(r_m) + 1):
            for k in range(1, int(r_m) + 1):
                # print(
                # f'{(i, j, k)=}, {i ** 2 + j ** 2 + k ** 2 + i * j + j * k + k * i}')
                if i ** 2 + j ** 2 + k ** 2 + i * j + j * k + k * i == m:
                    ans += 1
    return ans


n = I()
for i in range(1, n + 1):
    # print(f'{i=}')
    print(f(i))


### FIXED CODE ###

import math
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


INF = float('inf')


def f(m):
    res = 0
    r_m = math.sqrt(m)
    for i in range(1, int(r_m) + 1):
        for j in range(1, int(r_m) + 1):
            for k in range(1, int(r_m) + 1):
                if i ** 2 + j ** 2 + k ** 2 + i * j + j * k + k * i == m:
                    print(f'{(m, i, j, k)=}')
                    res += 1
    return res


n = I()
cnt = [0] * 10001
r_n = int(math.sqrt(n)) + 1
for x in range(1, r_n):
    for y in range(1, r_n):
        for z in range(1, r_n):
            v = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if v <= n:
                cnt[v] += 1

for i in range(1, n + 1):
    print(cnt[i])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = [int(x) for x in input().split()]

m = max(a)
primes = list(range(m+1))
primes[1] = 0
for i in range(2, m+1, 2): primes[i] = 2

for i in range(3, int(m ** 0.5)+1):
    for j in range(i, m+1, i):
        if primes[j] > i: primes[j] = i

b = [0] * (m + 1)
def factorization(n):
    temp = n
    lst = []
    while temp != 1:
        lst.append(primes[temp])
        temp = temp // primes[temp]

    aset = set(lst)
    for i in aset:
        b[i] += 1

for aa in a:
    factorization(aa)
maxb = max(b)
if maxb <= 1: print('pairwise coprime')
elif maxb < n: print('setwise coprime')
else: print('not coprime')

### FIXED CODE ###

import sys, math
input = sys.stdin.readline
n = int(input())
a = [int(x) for x in input().split()]

m = max(a)
primes = list(range(m+1))
primes[1] = 0
for i in range(2, m+1, 2): primes[i] = 2

for i in range(3, int(m ** 0.5)+1):
    for j in range(i, m+1, i):
        if primes[j] > i: primes[j] = i

b = [0] * (m + 1)
jdg_p = True
for aa in a:
    aset = set()
    while aa != 1:
        aset.add(primes[aa])
        aa //= primes[aa]
    for aaset in aset:
        b[aaset] += 1
        if b[aaset] >= 2:
            jdg_p = False
            break
        else:
            b[aaset] += 1
    if not jdg_p: break

x = a[0]
jdg_s = True
for aa in a[1:]:
    x = math.gcd(x, aa)
if x != 1: 
    jdg_s = False

if jdg_p: print('pairwise coprime')
elif jdg_s: print('setwise coprime')
else: print('not coprime')
### BUGGY CODE ###

N = int(input())
k = []
x = []
for i in range(0, N):
    a = input()
    k.append(a)
for i in k:
    if i not in x:
        x.append(i)
print (len(x))

### FIXED CODE ###

N = int(input())
k = set()
for _ in range(N):
    k.add(input())
print (len(k))
### BUGGY CODE ###

import math

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)

### FIXED CODE ###

from math import gcd

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(gcd(a,b), c)
print(ans)
### BUGGY CODE ###

N=int(input())
t=1
for i in range(1,N+1):
    t*=i

print(int(t%(10**9+7)))


### FIXED CODE ###

import math
N=int(input())

print(int(math.factorial(N)%(10**9+7)))
### BUGGY CODE ###

N=int(input())

cnt=0

for i in range(1,N+1):
  for j in range(1,N+1):
    buf=N-i*j
    if buf>0:
      cnt+=1
    else:
      break

print(cnt)


### FIXED CODE ###

N=int(input())

cnt=0

for i in range(1,N+1):
  for j in range(1,i+1):
    buf=N-i*j
    if buf>0:
      if i==j:
        cnt+=1
      else:
        cnt+=2
    else:
      break
  

print(cnt)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7

from collections import Counter
def factorize(n):
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m += 1
    if n > 1:
        d[n] += 1
    return d

factors = [None] * N

lcms = Counter()
for i,a in enumerate(A):
    factors[i] = factorize(a)
    for k,v in factors[i].items():
        if k in lcms:
            lcms[k] = max(lcms[k], v)
        else:
            lcms[k] = v

ans = 0
for fs in factors:
    a = 1
    for k,v in lcms.items():
        a *= pow(k, v - fs[k], MOD)
        a %= MOD
    ans += a
    ans %= MOD
print(ans)

### FIXED CODE ###

from fractions import gcd
N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7

lcm = 1
for a in A:
    lcm = lcm // gcd(lcm,a) * a

ans = 0
for a in A:
    ans += lcm // a
ans %= MOD
print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
a = list(map(int,input().split()))
a = sorted(a,reverse=True)
for m in range(M):
  if len(a)>1:
    max_=max(a[:2])
    a.remove(max_)
    flag=1
    for n in range(N-1):
      if max_//2<a[n]:
        continue
      else:
        a.insert(n,max_//2)
        flag=0
        break
    if flag:
      a.append(max_//2)
  else:
    a[0]=a[0]//2
print(sum(a))

### FIXED CODE ###

from heapq import heapify,heappush,heappop

N,M = map(int,input().split())
a = list(map(int,input().split()))
a = [(-x, x) for x in a]

heapify(a)

for m in range(M):
  max_ = heappop(a)
  a_ = max_[1]//2
  heappush(a,(-a_,a_))

ans=0
for a_ in a:
  ans+=a_[1]
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline

def main():
    H,W = map(int, input().split())
    
    S = []
    for _ in range(H):
        S.append(input().strip()+"#") # 末尾に壁を足すと後が楽になる
    S.append("#"*W) # 同上

    # グリッド y,x を含む横方向の "." の最大長
    grid_x = [[0]*(W+1) for _ in range(H)]
    for y in range(H):
        l = r = 0
        for x in range(W+1):
            if S[y][x] == "#":
                r = x
                for i in range(l,r):
                    grid_x[y][i] = r-l
                grid_x[y][x] = 0
                l = x+1

    # グリッド y,x を含む縦方向の "." の最大長
    grid_y = [[0]*W for _ in range(H+1)]
    for x in range(W):
        u = d = 0
        for y in range(H+1):
            if S[y][x] == "#":
                d = y
                for i in range(u,d):
                    grid_y[i][x] = d-u
                grid_y[y][x] = 0
                u = y+1

    ans = 0
    for y in range(H):
        for x in range(W):
            ans = max(ans, grid_x[y][x]+grid_y[y][x]-1)
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline

def main():
    H,W = map(int, input().split())
    
    S = []
    for _ in range(H):
        S.append(input().strip())
 
    u = [[0]*W for _ in range(H)]
    d = [[0]*W for _ in range(H)]
    l = [[0]*W for _ in range(H)]
    r = [[0]*W for _ in range(H)]
    for y in range(H):
        for x in range(W):
            if S[y][x] == "#":
                u[y][x] = l[y][x] = 0
            else:
                u[y][x] = 1 if y == 0 else u[y-1][x] + 1
                l[y][x] = 1 if x == 0 else l[y][x-1] + 1
    for y in range(H-1,-1,-1):
        for x in range(W-1,-1,-1):
            if S[y][x] == "#":
                d[y][x] = r[y][x] = 0
            else:
                d[y][x] = 1 if y == H-1 else d[y+1][x] + 1
                r[y][x] = 1 if x == W-1 else r[y][x+1] + 1
 
    ans = 0
    for y in range(H):
        for x in range(W):
            ans = max(ans, u[y][x] + d[y][x] + l[y][x] + r[y][x] - 3)
            
    print(ans)

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

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

A_div = [0 for _ in range(N)]
for i in range(N):
    if A_div[i] == 0:
        for j in range(i + 1, N):
            if A[i] % A[j] == 0:
                A_div[i] += 1
            if A[j] % A[i] == 0:
                A_div[j] += 1

print(A_div.count(0))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
A_div = [0] * (10 ** 6 + 1)

for a in A:
    A_div[a] += 1
    if A_div[a] == 1:
        for j in range(2 * a, 10 ** 6 + 1, a):
            A_div[j] += 100

print(A_div.count(1))
### BUGGY CODE ###

from heapq import heapify, heappush, heappop

class Rail:
  def __init__(self, f, t, y, s, c=0):
    self.from_city = f
    self.to_city = t
    self.yen = y
    self.sunuke = s
    self.cost = c

  def __lt__(self, other):
    return self.cost < other.cost

  def __str__(self):
    return str(self.cost)


N, M, Start, Goal = map(int, input().split())
Start -= 1
Goal -= 1
adj_list = [[] for _ in range(N)]
for i in range(M):
  u, v, yen, sunuke = map(int, input().split())
  u -= 1
  v -= 1
  adj_list[u].append(Rail(u, v, yen, sunuke))
  adj_list[v].append(Rail(v, u, yen, sunuke))

def dijkstra(start, changed):
  res = {}
  r = Rail(start, start, 0, 0)
  q = [r]
  heapify(q)
  visited = {}

  while len(q)>0:
    r = heappop(q)
    now_city = r.to_city
    if visited.get(now_city, False):
      continue
    visited[now_city] = True
    res[now_city] = r.cost

    #print([now_city+1, r.cost])

    for rr in adj_list[now_city]:
      if changed:
        rr.cost = r.cost + rr.sunuke
      else:
        rr.cost = r.cost + rr.yen
        
      heappush(q, rr)

  return res


min_yen_path = dijkstra(Start, False)
min_sunuke_path = dijkstra(Goal, True)

res = []
max_sunuke = 0
for i in reversed(range(N)):
  s = 10**15-min_yen_path[i]-min_sunuke_path[i]
  max_sunuke = max([s, max_sunuke]) 
  res.append(max_sunuke)
  
for i in reversed(res):
  print(i)


### FIXED CODE ###

from heapq import heappush, heappop

N, M, Start, Goal = map(int, input().split())
Start -= 1
Goal -= 1
adj_list = [[] for _ in range(N)]
for i in range(M):
  u, v, yen, sunuke = map(int, input().split())
  u -= 1
  v -= 1
  adj_list[u].append([u, v, yen, sunuke])
  adj_list[v].append([v, u, yen, sunuke])

def dijkstra(start, changed):
  res = [ -1 for _ in range(N) ]
  q = [[0, start]]
  visited = {}

  while len(q)>0:
    money, city = heappop(q)
    if res[city]>=0:
      continue
    res[city] = money

    for from_city, to_city, yen, sunuke  in adj_list[city]:
      if res[to_city]<0:
        cost = sunuke if changed else yen
        heappush(q, [money+[yen, sunuke][changed], to_city])
        

  return res


min_yen_path = dijkstra(Start, 0)
min_sunuke_path = dijkstra(Goal, 1)

res = []
max_sunuke = 0
for i in reversed(range(N)):
  s = 10**15-min_yen_path[i]-min_sunuke_path[i]
  max_sunuke = max([s, max_sunuke]) 
  res.append(max_sunuke)
  
for i in reversed(res):
  print(i)
### BUGGY CODE ###

n = int(input())

ans = 1

for e in map(int, input().split()):
    ans *= e

if ans > 10**18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

n = int(input())

a = [*map(int, input().split())]
for e in a:
    if e == 0:
        print(0)
        exit(0)

ans = 1
for e in a:
    ans *= e
    if ans > 10**18:
        print(-1)
        exit(0)

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

from math import factorial
def comb_mod(n, k, mod):
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    a = factorial(n)
    b = factorial(k)
    c = factorial(n-k)
    return (a*pow(b, mod-2, mod)*pow(c, mod-2, mod)) % mod

def main():
    import sys
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    N, K = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    minus = 0
    plus = 0
    for i in range(N-K+1):
        comb = comb_mod(N-i-1, K-1, mod)
        minus += (A[i] * comb)
        plus += (A[-i-1] * comb)
    print((plus - minus) % mod)
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
mod = 10 ** 9 + 7
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
minus = 0
plus = 0
fact = [0] * (N+1)
fact[0] = 1
pow_fact = [0] * (N+1)
pow_fact[0] = 1
fa = 1
for i in range(1, N+1):
    fa *= i
    fa %= mod
    fact[i] = fa
    pow_fact[i] = pow(fa, mod-2, mod)
b = pow_fact[K-1]
for i in range(N-K+1):
    a = fact[N-i-1]
    c = pow_fact[N-i-K]
    comb = (a*b*c) % mod
    minus += (A[i] * comb) % mod
    plus += (A[-i-1] * comb) % mod
print((plus - minus) % mod)
### BUGGY CODE ###

n,q=map(int, input().split())
s=input()
a=[0]*q
b=[0]*q
for i in range(q):
    a[i], b[i] = map(int, input().split())

for i in range(q):
    print(s.count("AC",a[i]-1,b[i]))

### FIXED CODE ###

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

lst=[0]
for i in range(1,n):
    if s[i-1]=="A" and s[i]=="C":
        lst.append(lst[i-1]+1)
    else:
        lst.append(lst[i-1])

for i in range(q):
    l,r=map(int,input().split())
    print(lst[r-1]-lst[l-1])