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

import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
#

def join(s):
    return ''.join(s)

#iterate macro
def piter(n,m):
    return itertools.permutations(n,m)
def citer(n,m):
    return itertools.combinations(n,m)

#modulo macro
def modc(a,b,m):
    c = 1
    for i in xrange(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = gcd(a, m)
    return inv % m

#bisect macro
def index(a, x):
    #Locate the leftmost value exactly equal to x
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

#memoize macro
def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper

@memoize
def nck(a,b,m):
    b = min([a-b,b])
    if (b>a or b<0 or a<0):
        return 0
    elif a == 0:
        return 1
    return (nck(a-1,b-1,m)+nck(a-1,b,m)) % m

nh=zip([1,0,-1,0],[0,1,0,-1])

###########

n,x=ii()
a=ii()

@memoize
def dp(j,k):
    if k!=0:
        return min(dp(j,k-1),a[(j-k)%n])
    else:
        return a[j]
s=[0]*n
for k in range(n):
    s[k]=sum([dp(j,k) for j in range(n)])+k*x

print min(s)


### FIXED CODE ###

n,x=map(int,raw_input().split(" "))
a=map(int,raw_input().split(" "))
t=[i for i in a]
s=10**15
for m in range(n):
    t=[min(t[j],a[(j-m)%n]) for j in range(n)]
    s=min(x*m+sum(t),s)
print s
### BUGGY CODE ###

from functools import reduce  
n = int(input())
l = list(map(int, input().split()))
res = reduce((lambda x, y: x * y), l) 
if(res > 10**18):
    print(-1)
else:
    print(res)


### FIXED CODE ###

def multiplyList(myList) : 
      
    # Multiply elements one by one 
    result = 1
    for x in myList: 
        result = result * x
        if result == 0:
             return 0 
        if result > 10**18:
             return -1
    return result
 
n = int(input())
l = list(map(int, input().split()))
l.sort()
res = multiplyList(l)
print(res)
### BUGGY CODE ###

from collections import Counter
import math

def c(n, r):
    if n >= r:
        return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
    return 0

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

d = Counter(A)

sum_c = 0
for v in d.values():
    if v >= 2:
        sum_c += c(v, 2)

for a in A:
    x = sum_c - c(d[a], 2) + c(d[a]-1, 2)
    print(x)

### FIXED CODE ###

from collections import Counter
from scipy.special import comb

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

d = Counter(A)

sum_c = 0
for v in d.values():
    if v >= 2:
        sum_c += comb(v, 2, exact=True)

for a in A:
    x = sum_c - comb(d[a], 2, exact=True) + comb(d[a]-1, 2, exact=True)
    print(x)
### BUGGY CODE ###

import math

#input = sys.stdin.readline
#def main():

#---------------------------------------------------------

def make_prime_list_2(num):
    if num < 2:
        return []

    # 0のものは素数じゃないとする
    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0 # 1は素数ではない
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break

        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0

    return [prime for prime in prime_list if prime != 0]
    
def search_divisor_num_1(num):
    if num < 0:
        return None
    elif num == 1:
        return 1
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list_2(num_sqrt)

        divisor_num = 1
        for prime in prime_list:
            count = 1
            while num % prime == 0:
                num //= prime
                count += 1
            divisor_num *= count

        if num != 1:
            divisor_num *= 2

        return divisor_num

n = int(input())

ans = 0

for i in range(1,n+1):
    ans += i * search_divisor_num_1(i)

print(ans)

### FIXED CODE ###

N = int(input())
ans = 0
for i in range(1, N + 1):
    n = N // i  # 項数n
    cnt = (n * (2 * i + (n - 1) * i)) // 2  # 初項i, 項数n の等差数列の和の公式
    ans += cnt
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
a_ = sorted(a)
if len(a)==2:
    print(a_[1],a_[0])
    exit()
a = a_[::-1]
import bisect
import math
def combinations_count(n,r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))
ret = 0
for i in range(n//2):
    k = bisect.bisect_left(a_,a[i]//2)
    if a[i]//2-a_[k]>a_[k+1]-a[i]//2:
        k += 1
    cmb = combinations_count(a[i],a_[k])
    if ret<cmb:
        ans = [a[i],a_[k]]
        ret = cmb
print(ans[0],ans[1])

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a_ = sorted(a)
if len(a)==2:
    print(a_[1],a_[0])
    exit()
a = a_[::-1]
k = 10**9
for i in range(1,n):
    if k>abs(a[0]/2-a[i]):
        k=abs(a[0]/2-a[i])
        ans = [a[0],a[i]]
print(ans[0],ans[1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

def zenbu(m, B):
    if m == 1:
        return B[0]
    elif m == 2:
        return max(B[0],B[1])
    elif m == 3:
        return max(B[0],B[1],B[2])
    elif m%2 == 0: #偶数の場合
        temp = 0
        for i in range(m//2-1):
            temp += B[i*2]
        return max(temp+ max(B[m-2],B[m-1]), zenbu(m-2, B[:-2])+ B[m-1])
    else:#奇数の場合
        temp = 0
        for i in range((m-1)//2):
            temp += B[i*2]
        return max(temp, zenbu(m-2,B[:-2])+ B[m-1], zenbu(m-3,B[:-3])+ max(B[m-2],B[m-1]))

ans = zenbu(n,A)

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
if N%2 == 0:
  dp = [[0]*2 for _ in range(N)] #0index
  dp[0][0] = A[0]
  dp[1][1] = A[1]
  for i in range(2,N):
    dp[i][0] = dp[i-2][0]+A[i]
    if i-3>=0:
      dp[i][1] = max(dp[i-2][1],dp[i-3][0])+A[i]
    else:
      dp[i][1] = max(dp[i-2][1],0)+A[i]
  ans = max(dp[-2][0],dp[-1][1])
  print(ans)
#i個目を使ってj(0-2)回多く飛んでいる。
else: #N%2 == 1:
  dp = [[0]*3 for _ in range(N)] #0index
  dp[0][0] = A[0]
  dp[1][1] = A[1]
  dp[2][2] = A[2]
  dp[2][0] = A[0]+A[2]
  #print(dp)
  for i in range(3,N):
    dp[i][0] = dp[i-2][0]+A[i]
    if i-3 >= 0:
      dp[i][1] = max(dp[i-2][1],dp[i-3][0])+A[i]
    else:
      dp[i][1] = max(dp[i-2][1],0)+A[i]
    if i-4 >= 0:
      dp[i][2] = max(dp[i-2][2],dp[i-3][1],dp[i-4][0])+A[i]
    elif i-3 >= 0:
      dp[i][2] = max(dp[i-2][2],dp[i-3][1],0)+A[i]
  #else:
  #  dp[i][2] = max(dp[i-2][2],0,0)+A[i]
  #print(dp[-1],dp[-2],dp[-3])

  ans = max(dp[-3][0],dp[-2][1],dp[-1][2])
  print(ans)
  exit()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
n,m=mii()

from fractions import gcd
from functools import reduce

#list
def gcd_list(numbers):
    return reduce(gcd, numbers)
ans=0
for i in range(1,m//n+1):
    p=gcd_list([i,m-i*n])

    ans=max(ans,p)
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
n,m=mii()

def mdiv(n):
    divisors=[]
    for i in range(1,int(n**0.5)+1):
        if n%i==0:

            divisors.append(i)
            if i!=n//i:

                divisors.append(n//i)
    return divisors
#print(mdiv(m))

ans=0
for i in mdiv(m):
    if i<=m//n:
        ans=max(i,ans)
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
B=[0]*M
C=[0]*M
D=0
for i in range(M):
    B[i], C[i] = map(int, input().split())
    D +=B[i]
    A += [C[i]]*B[i]

a=sorted(A)
print(sum(a[D:]))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]
BC.sort(key=lambda x: x[1], reverse=True)
D = []
sum_B=0
for B, C in BC:
    D += [C] * B
    sum_B += B
    if sum_B>N:
        break

A+=D
A.sort(reverse = True)
print(sum(A[:N]))
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

N = int(input())
S = input()

from collections import defaultdict
d = defaultdict(int)

for i in range(N):
    s = S[i]
    d[s] += 1
cnt = 0
for i in range(N-2):
    for j in range(i,N-1):
        k = 2*j - i
        if k <= N-1 and (S[i] != S[j] and S[j] != S[k] and S[k] != S[i]):
            cnt += 1
if d["R"] and d["G"] and d["B"]:
    ans = d["R"] * d["G"] * d["B"] - cnt
    print(ans)
else:
    print(0)

### FIXED CODE ###

N = int(input())
S = input()

R = [0] * N
G = [0] * N
B = [0] * N
SR = [0] * N
SG = [0] * N
SB = [0] * N
pr = 0
pg = 0
pb = 0
for i in range(N):
    if S[i] == "R":
        pr += 1
        SR[i] = pr
        R[i] = 1
    elif S[i] == "G":
        pg += 1
        SG[i] = pg
        G[i] = 1
    elif S[i] == "B":
        pb += 1
        SB[i] = pb
        B[i] = 1
        
ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        if R[i]:
            if G[j]:
                if j+(j-i) <= N-1 and B[j + (j-i)] == 1:
                    ans += SB[N-1] - SB[j] - 1
                else:
                    ans += SB[N-1] - SB[j]
            if B[j]:
                if j+(j-i) <= N-1 and G[j + (j-i)] == 1:
                    ans += SG[N-1] - SG[j] - 1
                else:
                    ans += SG[N-1] - SG[j]
        if G[i]:
            if B[j]:
                if j+(j-i) <= N-1 and R[j + (j-i)] == 1:
                    ans += SR[N-1] - SR[j] - 1
                else:
                    ans += SR[N-1] - SR[j]
            if R[j]:
                if j+(j-i) <= N-1 and B[j + (j-i)] == 1:
                    ans += SB[N-1] - SB[j] - 1
                else:
                    ans += SB[N-1] - SB[j]
        if B[i]:
            if G[j]:
                if j+(j-i) <= N-1 and R[j + (j-i)] == 1:
                    ans += SR[N-1] - SR[j] - 1
                else:
                    ans += SR[N-1] - SR[j]
            if R[j]:
                if j+(j-i) <= N-1 and G[j + (j-i)] == 1:
                    ans += SG[N-1] - SG[j] - 1
                else:
                    ans += SG[N-1] - SG[j]
print(ans)
### 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)

while True:
    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 ###

N,W=map(int,input().split())
WV=[[int(x) for x in input().split()] for y in range(N)]

dp=[[0 for x in range(W+1)] for y in range(N+1)]
for i in range(N-1,-1,-1):
    for j in range(W+1):
        if j < WV[i][0]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j],dp[i+1][j-WV[i][0]]+WV[i][1])

print(dp[0][W])

### FIXED CODE ###

N,W=map(int,input().split())
WV=[[int(x) for x in input().split()] for y in range(N)]

dp=[[0 for x in range(W+1)] for y in range(N+1)]
for i in range(N-1,-1,-1):
    for j in range(W+1):
        if j < WV[i][0]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j],dp[i+1][j-WV[i][0]]+WV[i][1])

print(dp[0][W])
### BUGGY CODE ###

import sys

count = 0

number = int(input())

for line in sys.stdin:
    n = int(line)
    if n == 2:
        count += 1
        continue

    if n % 2 == 0:
        continue

    jdg = True
    for i in range(3, n, 2):
        if n % i == 0:
            jdg = False
            break
    if jdg:
        count += 1

print(count)



### FIXED CODE ###

import sys

count = 0

number = int(input())

for line in sys.stdin:
    n = int(line)
    if n == 2:
        count += 1
        continue

    if n % 2 == 0:
        continue

    jdg = True
    for i in range(3, int(n ** 0.5) + 1, 2):
        if n % i == 0:
            jdg = False
            break
    if jdg:
        count += 1

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

K = int(input())


import math
from functools import reduce

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

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 ###

K = int(input())


import math
from functools import reduce

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

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)
### BUGGY CODE ###

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


def read_list():
    return list(read_values())


def g(a, b):
    if a > b:
        a, b = b, a
    while b % a:
        a, b = b % a, a
    return a


def l(a, b):
    return a * b // g(a, b)


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()

    B = 1
    for a in A:
        B = l(a, B)
    
    print(sum(B // a for a in A) % mod)


if __name__ == "__main__":
    main()



### FIXED CODE ###

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


def read_list():
    return list(read_values())


def g(a, b):
    if a > b:
        a, b = b, a
    while b % a:
        a, b = b % a, a
    return a


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()

    B = 1
    for a in A:
        B *= a // g(B, a)
    
    print(sum(B // a for a in A) % mod)


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

import functools
import operator
Π = functools.partial(functools.reduce, operator.mul)

N  = int(input())
A  = [int(x) for x in input().split()]
AM = Π(A)
if AM > pow(10,18):
    print('-1')
else:
    print(str(AM))

### FIXED CODE ###

import numpy as np
N    = int(input())
A    = input().split()
Pro  = 1
PrF  = 1
PrFF = 1

if '0' in A:
    print(0)
    PrF = 0
    
if PrF:
    for T in range(0,len(A)):
        if int(A[T]) == pow(10,18):
            PrFF = 0
            print('-1')
            break
        else:
            Pro = Pro*int(A[T])
            if Pro > pow(10,18):
                PrFF = 0
                print('-1')
                break

if PrF & PrFF:
    print(Pro)
### BUGGY CODE ###

n,k=map(int,input().split())
cst=list(map(int,input().split()))
arr=[0]*10**5
arr[0]=0
arr[1]=abs(cst[1]-cst[0])
if n==2:
    print(arr[1])
else:
    for i in range(2, n):
        #arr[i] = min(abs(cst[i - 1] - cst[i]) + arr[i - 1], abs(cst[i - 2] - cst[i]) + arr[i - 2])
        #t=cst.index(min(cst[max(i-k,0):i]))
        arr[i]=min(abs(cst[max(i-j,0)]-cst[i])+arr[i-j] for j in range(1,k+1))
    print(arr[n-1])

#print(arr)

### FIXED CODE ###

import sys

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

def main():
    n, k = map(int, input().split())
    cst = list(map(int, input().split()))
    arr = [0] * n
    arr[1] = abs(cst[1] - cst[0])
    for i in range(2, n):
        arr[i] = min(abs(cst[j] - cst[i]) + arr[j] for j in range(max(i - k, 0), i))
    print(arr[n - 1])
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n,k = list(map(int, input().split()))
step_array = list(map(int, input().split()))
score_array = [0 for _ in range(n)]
for i in range(0, n+1):
	for j in range(1, k+1):
		if i+j > n-1:
			break
		cost = abs(step_array[i] - step_array[i+j]) + score_array[i]
		if( score_array[i+j] == 0 or score_array[i+j]>cost):
			score_array[i+j] = cost
print(score_array[n-1])

### FIXED CODE ###

n,k = list(map(int, input().strip().split()))
step_array = list(map(int, input().strip().split()))
score_array = [0]
for i in range(0, n+1):
	for j in range(1, k+1):
		if i+j > n-1:
			break
		cost = abs(step_array[i] - step_array[i+j]) + score_array[i]
		if len(score_array) <= i+j:
			score_array.append(cost)
		elif(score_array[i+j]>cost):
			score_array[i+j] = cost
print(score_array[n-1])
### BUGGY CODE ###

n=int(input())
res=1
for i in range(1,n+1):
  res*=i
print(res%(10**9+7))

### FIXED CODE ###

n = int(input())

pw = 1
num = 1
for i in range(n):
  pw = pw*num % (10**9+7)
  num += 1
  
print(pw)
### BUGGY CODE ###

#どっちで出すか注意, rstrip注意
#提出前に見返すこと！
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    for _ in range(m):
        b,c = map(int, input().split())
        i = bisect_left(a, c)
        if b >= i:
            a = [c]*i + a[i:]
        else:
            a = a[b:i] + [c]*b +a[i:]
    print(sum(a))


if __name__ == '__main__':
    main()


### FIXED CODE ###

#どっちで出すか注意, rstrip注意
#提出前に見返すこと！
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    a = list(map(int, input().split()))
    bc = [list(map(int, input().split())) for _ in range(m)]
    bc.sort(key=lambda a: a[1])
    a.sort()
    res = 0
    cnt = 0
    while cnt<n:
        if not bc:
            res += sum(a[cnt-n:])
            break
        if a[-1] >= bc[-1][1]:
            res += a.pop()
            cnt += 1
        else:
            d, e = bc.pop()
            if n-cnt >= d:
                res += d*e
                cnt += d
            else:
                res += (n-cnt)*e
                break

    print(res)


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

S=input()
Q=int(input())

for i in range(Q):
    q=list(input().split())
    if q[0]=="1":
        S=S[::-1]
    elif q[1]=="1":
        S=q[2]+S
    elif q[1]=="2":
        S=S+q[2]
print(S)

### FIXED CODE ###

from collections import deque
S=input()
Q=int(input())
r_count=0
top=[1,2]
tail=[2,1]
S=deque(list(S))

for i in range(Q):
    q=list(input().split())
    if q[0]=="1":
        r_count+=1
    else:
        q[1]=int(q[1])
        if q[1]==1:
            q[1]=top[r_count%2]
        else:
            q[1]=tail[r_count%2]
        
        if q[1]==1:
            S.appendleft(q[2])
        else:
            S.append(q[2])
S=list(S)
if r_count%2==1:
    S.reverse()
print(''.join(S))
### BUGGY CODE ###

n, m = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(n)]
num = []
sum = 0
for i in range(n):
    for _ in range(l[i][1]):
        num.append(l[i][0])
num = sorted(num)
for i in range(m):
    sum += num[i]
print(sum)

### FIXED CODE ###

n, m = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(n)]
l.sort(key=lambda x: x[0])
num = 0
ansum = 0
for i in range(n):
    if num + l[i][1] < m:
        ansum += l[i][0] * l[i][1]
        num += l[i][1]
    else:
        ansum += l[i][0] * (m - num)
        break
print(ansum)
### BUGGY CODE ###

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

A_list = list(map(int, input().split()))
A_list = [A - 1 for A in A_list]

path = [0]
town = 0
k = K
j = 0
while k > 0:
  town = A_list[town]
                     
  if town in path:
    #print("town is {}".format(town))
    #print("path is {}".format(path))
    first_visit = path.index(town)
    loop_size = j - first_visit + 1
    #print("loop_size is {}".format(loop_size))
    #print("k is {}".format(k))
    k = (k-1) % loop_size 
    #print("k is now {}".format(k))
    town = path[first_visit + k]
    break
    
  path.append(town)
    
  k = k - 1
  j = j + 1

print(town+1)

### FIXED CODE ###

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

A_list = list(map(int, input().split()))
A_list = [A - 1 for A in A_list]

path = [0]
town = 0
k = K
j = 0

while k > 0:
  town = A_list[town]
   
  if k % 10000 == 0:
    if town in path:
      #print("town is {}".format(town))
      #print("path is {}".format(path))
      first_visit = path.index(town)
      loop_size = j - first_visit + 1
      #print("loop_size is {}".format(loop_size))
      #print("k is {}".format(k))
      k = (k-1) % loop_size 
      #print("k is now {}".format(k))
      town = path[first_visit + k]
      break
    
  path.append(town)
    
  k = k - 1
  j = j + 1

print(town+1)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans =1;
iszero = False

for i in range(N):
  if(A[i]==0):
    iszero = True

for i in range(N):
  if(iszero):
    ans = 0
    break
    
  ans *= A[i]
  
  if(ans>10**18):
    ans = -1

print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans =1;
iszero = False

if 0 in A:
  iszero = True
for i in range(N):
  if(iszero):
    ans = 0
    break
  ans *= A[i] 
  if ans>10**18:
    ans = -1
    break

print(ans)