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

import bisect

n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
for i in range(m):
  t=a[-1]
  t//=2
  a.pop()
  bisect.insort_left(a,t)
  #print(i,a)
print(sum(a))


### FIXED CODE ###

import bisect

n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
for i in range(m):
  t=a[-1]
  t//=2
  a.pop()
  bisect.insort_left(a,t)
  #print(i,a)
print(sum(a))
### BUGGY CODE ###

import numpy as np
from collections import deque

N,M,X = [int(i) for i in input().split()]
A = np.array([[int(i) for i in input().split()]])
for _ in range(N-1):
    B = np.array([int(i) for i in input().split()])
    A = np.vstack([A, B])

m = min([np.sum(A[:,i:i+1]) for i in range(1,M+1)])
if m < X:
    print(-1)
    exit()

ans = np.sum(A[:,0:1])
q = deque([[i] for i in range(N)])
while len(q) != 0:
    L = q.pop()
    L.sort(reverse=True)
    B = A.copy()
    for i in L:
        B = np.delete(B, i, 0)
    m = min([np.sum(B[:,i:i+1]) for i in range(1,M+1)])
    if m < X:
        continue
    ans = min([ans,np.sum(B[:,0:1])])
    for i in range(N):
        L1 = L.copy()
        L1.append(i)
        L1set = set(L1)
        if len(L) < len(L1set):
            q.append(L1)

print(ans)

### FIXED CODE ###

N,M,X = [int(i) for i in input().split()]
A = []
for _ in range(N):
    A.append([int(i) for i in input().split()])
ans = float("inf")

for i in range(1,2**N):
    a = 0
    e = [0]*M
    bi = "0"*N + bin(i)[2:]
    bi = list(bi[len(bi)-N:])
    for j in range(N):
        if bi[j] == "1":
            a += A[j][0]
            for k in range(M):
                e[k] += A[j][k+1]
    c = True
    for i in range(M):
        c &= e[i] >= X
    if c:
        ans = min(ans,a)
if ans > 10**7:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

N = int(input())
K = list(input())
a = collections.Counter(K)
ans = 0
R = list(itertools.accumulate([1 if K[i] == "R" else 0 for i in range(N)])) + [0]
G = list(itertools.accumulate([1 if i == "G" else 0 for i in K])) + [0]
B = list(itertools.accumulate([1 if i == "B" else 0 for i in K])) + [0]
for i in range(N):
    if K[i] == "R":
        ans += G[i - 1] * B[i - 1]
    elif K[i] == "G":
        ans += R[i - 1] * B[i - 1]
    else:
        ans += R[i - 1] * G[i - 1]
for k in range(2, N):
    for i in range(0, k):
        j = (k + i) / 2
        if j == (k + i) // 2 and j > i:
            j = int(j)
            if K[k] != K[i] and K[k] != K[j] and K[i] != K[j]:
                ans -= 1
print(ans)


### FIXED CODE ###

#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

N = int(input())
K = list(input())
a = collections.Counter(K)
ans = 0
R = list(itertools.accumulate([1 if K[i] == "R" else 0 for i in range(N)])) + [0]
G = list(itertools.accumulate([1 if i == "G" else 0 for i in K])) + [0]
B = list(itertools.accumulate([1 if i == "B" else 0 for i in K])) + [0]
for i in range(N):
    if K[i] == "R":
        ans += G[i - 1] * B[i - 1]
    elif K[i] == "G":
        ans += R[i - 1] * B[i - 1]
    else:
        ans += R[i - 1] * G[i - 1]
for k in range(2, N):
    for i in range(0, k):
        j = (k + i) / 2
        if j == (k + i) // 2 and j > i:
            j = int(j)
            if K[k] != K[i] and K[k] != K[j] and K[i] != K[j]:
                ans -= 1
print(ans)
### BUGGY CODE ###

import sys


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


sys.setrecursionlimit(20000000)
MOD = 10 ** 9 + 7


def main():
    L = list(input())

    pow = [0] * (len(L) + 1)
    pow[0] = 1
    for i in range(1, len(L) + 1):
        pow[i] = pow[i - 1] * 3 % MOD

    def cnt(s):
        if len(s) == 1:
            if s[0] == "1":
                return 3
            else:
                return 1
        if s[0] == "0":
            return cnt(s[1:]) % MOD
        else:
            return (cnt(s[1:]) * 2) % MOD + pow[len(s) - 1]

    answer = cnt(L) % MOD

    print(answer)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import queue


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


sys.setrecursionlimit(20000000)
MOD = 10 ** 9 + 7


def main():
    L = list(input())

    pow = [0] * (len(L) + 1)
    pow[0] = 1
    for i in range(1, len(L) + 1):
        pow[i] = pow[i - 1] * 3 % MOD
    N = len(L)
    if L[-1] == "0":
        answer = 1
    else:
        answer = 3
    for i in range(1, N):
        if L[N - i - 1] == "1":
            answer = answer * 2 + pow[i]
            answer %= MOD
        else:
            continue
    print(answer)


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

#!/usr/bin/env python3

from collections import defaultdict


class Graph(object):
    """ Graph data structure, undirected by default. """

    def __init__(self, connections, directed=False):
        self._graph = defaultdict(set)
        self._directed = directed
        self.add_connections(connections)

    def add_connections(self, connections):
        """ Add connections (list of tuple pairs) to graph """

        for u, v in connections:
            self.add(u, v)

    def add(self, u, v):
        """ Add connection between node u and node v """

        self._graph[u].add(v)
        if not self._directed:
            self._graph[v].add(u)

    def get_adj(self, v):
        """ Get adjacency list of node v """
        return self._graph[v]

    def __str__(self):
        return '{}({})'.format(self.__class__.__name__, dict(self._graph))


# -----
N, Q = map(int, input().split())
connections = []
for _ in range(N - 1):
    a, b = map(int, input().split())
    connections.append((a, b))
query = []
for _ in range(Q):
    p, x = map(int, input().split())
    query.append([p, x])
# print(N, Q)
# print(connections, query)

keys = [v for v in range(1, N + 1)]
values = [0 for _ in range(N)]
counter = dict(zip(keys, values))
# print(counter)
for p, x in query:
    counter[p] += x


def dfs(v, parent):
    for v_next in g.get_adj(v):
        if v_next != parent:
            counter[v_next] += counter.get(v)
            dfs(v_next, v)


g = Graph(connections)
# print(g)

root = 1
dfs(root, None)

for c in counter.values():
    print(c, end=" ")


### FIXED CODE ###

#!/usr/bin/env python3

import sys

input = sys.stdin.buffer.readline

sys.setrecursionlimit(10 ** 6)

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

edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

query = []
for _ in range(Q):
    p, x = map(int, input().split())
    query.append([p, x])

counter = [0 for _ in range(N)]
for p, x in query:
    counter[p - 1] += x


def dfs(v, parent):
    for v_next in edges[v]:
        if v_next != parent:
            counter[v_next] += counter[v]
            dfs(v_next, v)


root = 0
dfs(root, None)

print(*counter)
### BUGGY CODE ###

n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))
escape = min(a) - 1
for i in range(len(a)):
    compare = list(a)
    compare[i] = escape
    print(max(compare))

### FIXED CODE ###

n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))
firstMax = max(a)
minVal = min(a)
secondMax = max(map(lambda x:x if x != firstMax else minVal, a)) if len(str(a).split(str(firstMax))) == 2 else firstMax
for i in range(len(a)):
    if a[i] < firstMax:
        print(firstMax)
    else:
        print(secondMax)
### BUGGY CODE ###

import sys
N = input()
AList = list(map(int, input().split()))

mode = 1
L = []
p = 0
for i in range(-1, 2):
    for j in range(1,int(N)+1):
        p += abs(AList[j-1] -(i + j))
    L.append(p)        
    p = 0

if L[1] == min(L):
    print(L[1])
    sys.exit()
elif L[0] == min(L):
    pre = L[0]
    mode = -1
else:
    pre = L[2]
    mode = 1    
    
for i in range(2 * mode,1000000000 * mode ,mode):
    for j in range(1,int(N)+1):
        p += abs(AList[j-1] -(i + j))
    if pre < p:
        print(pre)
        sys.exit()
    else:
        pre = p
    p = 0

### FIXED CODE ###

from statistics import median
N = int(input())
AList = list(map(int, input().split()))
 
L = []
m = 0
for j in range(1, N+1):
    L.append(AList[j-1] - j)
m = median(L)
 
p = 0
for j in range(1, N+1):
    p += abs(AList[j-1] - j - m)
 
print(int(p))
### BUGGY CODE ###

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

if n == 2:
   print(abs(a[0]-a[1]))
   exit()

ans = 10**10
for i in range(1, n-1):
   tmp = abs(sum(a[:i]) - sum(a[i:]))
   ans = min(tmp, ans)
print(ans)


### FIXED CODE ###

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

x = a[0]
y = sum(a[1:])
ans = abs(x - y)
for i in range(1, n-1):
   x += a[i]
   y -= a[i]
   ans = min(abs(x-y), ans)
print(ans)
### BUGGY CODE ###

N = int(input())
T = list(map(int,input().split()))
A = list(map(int,input().split()))
count = 0
Tmax = 0
Amax = 0
T2 = []
A2 = []

for i in range(N):
    if T[i] > Tmax:
        T2.append([T[i]])
        Tmax = T[i]
    else:
        T2.append([j for j in range(1,Tmax+1)])
    if A[N-1-i] > Amax:
        A2.append([A[N-1-i]])
        Amax = A[N-1-i]
    else:
        A2.append([j for j in range(1,Amax+1)])

s = 1

for i in range(N):
    count = 0
    for j in T2[i]:
        for z in A2[N-1-i]:
            if j == z:
                count += 1
    if count == 0:
        break
    else:
        s = s * count
        s = s % (10**9+7)

if count == 0:
    print('0')
else:
    print(s)

### FIXED CODE ###

N = int(input())
T = list(map(int,input().split()))
A = list(map(int,input().split()))
A.append(1)
count = 0
Tmax = 1
Amax = 1
T2 = [0] * N
A2 = [0] * N
ans = 1

for i in range(N):
    if T[i] > Tmax and A[i] > A[i+1] and T[i] != A[i]:
        ans = 0
        break
    elif T[i] > Tmax and A[i] == A[i+1] and T[i] > A[i]:
        ans = 0
        break
    elif A[i] > A[i+1] and T[i] == Tmax and A[i] > T[i]:
        ans = 0
        break
    elif T[i] > Tmax and A[i] > A[i+1] and T[i] == A[i]:
        count = 1
        Tmax = T[i]
        Amax = A[i+1]
    elif T[i] > Tmax and A[i] == A[i+1] and T[i] <= A[i]:
        count = 1
        Tmax = T[i]
    elif A[i] > A[i+1] and T[i] == Tmax and A[i] <= Tmax:
        count = 1
        Amax = A[i+1]
    else:
        count = min(A[i],T[i])
    ans *= count
    ans = ans % (10**9+7)
print(ans)
### BUGGY CODE ###

N,X,Y = map(int,input().split())
matrix = [[0 for n in range(0,N)] for nn in range(0,N)]
for n in range(N):
    for i in range(n+1,N):
        s = i+1
        d = n+1
        p1 = abs(s-d)
        p2 = abs(s-X)+abs(d-Y)+1
        p3 = abs(s-Y)+abs(d-X)+1
        matrix[n][i] = min(p1,p2,p3)
matrix_flatten = sum(matrix,[])
for n in range(1,N):
    print(matrix_flatten.count(n))

### FIXED CODE ###

N,X,Y = map(int,input().split())
from collections import defaultdict as ddict
ans = ddict(int)
for n in range(N):
    for i in range(n+1,N):
        s = i+1
        d = n+1
        p1 = abs(s-d)
        p2 = abs(s-X)+abs(d-Y)+1
        p3 = abs(s-Y)+abs(d-X)+1
        ans[min(p1,p2,p3)] += 1
for n in range(1,N):
    print(ans[n])
### BUGGY CODE ###

N,M = map(int,input().split())
H_list = [int(i) for i in input().split()]
not_good_list = []
AB_list = []
for i in range(M) :
    AB_list.append([int(i) for i in input().split()])

AB_list = list(set(list(map(tuple,AB_list))))

# for i in range(M) :
for t in AB_list :
    A = t[0]
    B = t[1]

    if (A in not_good_list) :
        continue

    if (H_list[A-1] <= H_list[B-1]) :
        not_good_list.append(A)
        continue

for t in AB_list :
    A = t[1]
    B = t[0]

    if (A in not_good_list) :
        continue

    if (H_list[A-1] <= H_list[B-1]) :
        not_good_list.append(A)
        continue

print(N - len(not_good_list))

### FIXED CODE ###

N,M = map(int,input().split())
H_list = [int(i) for i in input().split()]
# not_good_list = []
not_good_set = set()
not_good_count = 0
AB_list = []
for i in range(M) :
    AB_list.append([int(i) for i in input().split()])

for t in AB_list :
    A = t[0]
    B = t[1]

    if (A not in not_good_set) :
        if (H_list[A-1] <= H_list[B-1]) :
            not_good_set.add(A)
            not_good_count += 1

    if (B not in not_good_set) :
        if (H_list[B-1] <= H_list[A-1]) :
            not_good_set.add(B)
            not_good_count += 1
            continue

print(N - not_good_count)
### BUGGY CODE ###

print(sum(range(int(input()))))


### FIXED CODE ###

n = int(input())
print((n - 1) * n // 2)
### BUGGY CODE ###

from sys import setrecursionlimit

def read_key():
    a, _ = map(int, input().split())
    m = 0
    for c in map(int, input().split()):
        m |= 1 << (c - 1)
    return (a, m)

def solve(keys, amount, cm, dp):
  if cm == (1 << N) - 1:
    return amount
  if len(keys) == 0:
    return INF
  a, m = keys[0]
  if dp[cm | m] < amount + a:
    return solve(keys[1:], amount, cm, dp)
  else:
    dp[cm | m] = amount + a
    return min(solve(keys[1:], amount, cm, dp), solve(keys[1:], amount + a, cm | m, dp))

setrecursionlimit(1000000)
INF = float('inf')

N, M = map(int, input().split())
keys = [read_key() for _ in range(M)]

dp = [INF] * (1 << N)
t = solve(keys, 0, 0, dp)
if t == INF:
  print(-1)
else:
  print(t)


### FIXED CODE ###

def read_key():
    a, _ = map(int, input().split())
    m = 0
    for c in map(int, input().split()):
        m |= 1 << (c - 1)
    return (a, m)


def main():
    INF = float('inf')

    N, M = map(int, input().split())
    keys = [read_key() for _ in range(M)]

    dp = [[INF] * (1 << N) for _ in range(M + 1)]

    dp[0][0] = 0
    for i in range(M):
        a, m = keys[i]
        dpi = dp[i]
        dpi1 = dp[i + 1]
        for j in range(1 << N):
            if dpi[j] == INF:
                continue
            if dpi[j] + a < dpi1[j | m]:
                dpi1[j | m] = dpi[j] + a
            if dpi[j] < dpi1[j]:
                dpi1[j] = dpi[j]

    if dp[M][(1 << N) - 1] == INF:
        print(-1)
    else:
        print(dp[M][(1 << N) - 1])


main()
### BUGGY CODE ###

N, K = map(int, input().split())
MOD = 998244353
P = []
for _ in range(K):
    l, r = map(int, input().split())
    for i in range(l, r+1):
        P.append(i)
dp = [0]*(N+1)
dp[0]=1
for i in range(N):
    for p in P:
        dp[min(i+p,N)] += dp[i]
        dp[min(i + p, N)]%=MOD
print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
MOD = 998244353
D = []
for _ in range(K):
    l, r = map(int, input().split())
    D.append((l,r))
imos = [0]*(N+2)
dp = [0]*(N+1)
imos[0]=1
imos[1]=-1
for i in range(N):
    dp[i] = dp[i-1] + imos[i]
    dp[i] %= MOD
    for a, b in D:
        imos[min(i+a,N+1)] += dp[i]
        imos[min(i+b+1,N+1)] -= dp[i]

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

S=raw_input()
l=len(S)

dp=[ 0 for j in range(13) ]
dp[0]=1

mod=10**9+7


for i in range(1,l+1):
	dp2=[ 0 for _ in range(13) ]
	for j in range(13):
		if dp[j]!=0:
			if S[i-1]=="?":
				for k in range(10):
					dp2[ (k*pow(10,l-i,13)+j)%13 ]+=dp[j]
					dp2[ (k*pow(10,l-i,13)+j)%13 ]%=mod
			else:
				k=int(S[i-1])
				dp2[ (k*pow(10,l-i,13)+j)%13 ]+=dp[j]
				dp2[ (k*pow(10,l-i,13)+j)%13 ]%=mod
	dp=dp2

print dp[5]


### FIXED CODE ###

S=raw_input()
S=S[::-1]
l=len(S)

dp=[ 0 for j in range(13) ]
dp[0]=1

mod=10**9+7

dp2=[ 0 for _ in range(13) ]

keta=1

for i in range(1,l+1):
	dp2=[0]*13
	for j in range(13):
		if dp[j]!=0:
			if S[i-1]=="?":
				for k in range(10):
					next=(k*keta+j)%13 
					dp2[next]+=dp[j]
					dp2[next]%=mod
			else:
				k=int(S[i-1])
				next=(k*keta+j)%13
				dp2[next]+=dp[j]
				dp2[next]%=mod

	dp=dp2
	keta=(keta*10)%13

print dp[5]
### BUGGY CODE ###

n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))
value = sum(a)
used = []
import math
for i in range(m):
  if value == 0:
    break
  
  if used != []:
    if a != []:
      if max(used) < a[-1]:
        value -= math.ceil(a[-1]/2)
        used.append(math.floor(a[-1]/2))
        a = a[:-1]
      else:
        use = max(used)
        value -= math.ceil(use/2)
        used[used.index(use)] //= 2
    else:
      use = max(used)
      value -= math.ceil(use/2)
      used[used.index(use)] //= 2
  else:
    value -= math.ceil(a[-1]/2)
    used.append(math.floor(a[-1]/2))
    a = a[:-1]
print(value)

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(lambda x: -int(x), input().split()))
import heapq
import math
value = -sum(a)
heapq.heapify(a)

for i in range(m):
  use = heapq.heappop(a)
  value += math.floor(use/2)
  heapq.heappush(a, math.ceil(use/2))
  
print(value)
### BUGGY CODE ###

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
 
    if temp!=1:
        arr.append([temp, 1])
 
    if arr==[]:
        arr.append([n, 1])
 
    return arr
X = int(input())
A = []
for i in factorization(X):
  for j in range(1,i[1]+1):
    a = i[0]**j
    b = X//a
    if(a<b):
      A.append([a,b])
    else:
      A.append([b,a])
 
A = list(map(list, set(map(tuple, A))))
flag = 0
for i in A:
  r = list(range(0,1000000+1))
  for a in r:
    b = a - i[0]
    if a**4 + a**3 * b + a**2 * b**2 + a * b**3 + b**4 == i[1]:
      print(a,b)
      flag = 1
      break
  if flag==1:
    break
  r = list(range(0,1000000+1))
  for a in r:
    b = a - i[1]
    if a**4 + a**3 * b + a**2 * b**2 + a * b**3 + b**4 == i[0]:
      print(a,b)
      flag = 1
      break
  if flag==1:
    break

### FIXED CODE ###


X = int(input())
flag = 0
for i in range(-150,150):
  for j in range(-150,150):
    if(i**5 - j**5 == X):
      print(i,j)
      flag = 1
      break
  if(flag==1):
    break
### BUGGY CODE ###

N = int(input())
S = input()
ans = S.count('R') * S.count('G') * S.count('B')
for i in range(N):
  for j in range(i, N):
    k = 2*j - i
    if k >= N:
      break
    if len(set([S[i], S[j],S[k]])) ==3:
      ans -= 1
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
ans = S.count("R") * S.count("G") * S.count("B")
for i in range(N):
    for j in range(i + 1, N):
        k = j - i + j
        if k < N:
            if {S[i], S[j], S[k]} == {"R", "G", "B"}:
                ans -= 1
print(ans)
### BUGGY CODE ###

A =input()
S = list(A)
Q = int(input())
Qlist = []
for i in range(Q):
    Qlist.append(list((map(str,input().split()))))
for i in range(Q):
    op = Qlist[i]
    if len(op) ==1:
        S.reverse()
    else:
        if op[1] =='1':
            S.reverse()
            S.append(op[2])
            S.reverse()
        else:
            S.append(op[2])
A = S[0]
for i in range(1,len(S)):
    A += S[i]
print(A)

### FIXED CODE ###

from collections import deque
S= deque(input())
Q = int(input())
ba = 1
for i in range(Q):
    Query =list(map(str,input().split()))
    Query0 = Query[0]
    if Query[0] == '1':
        ba *= -1
    else:
        if Query[1] == '1' and ba ==1:
            S.appendleft(Query[2])
        elif Query[1] == '1' and ba ==-1:
            S.append(Query[2])
        elif Query[1] == '2' and ba ==1:
            S.append(Query[2])
        elif Query[1] == '2' and ba ==-1:
            S.appendleft(Query[2])
if ba == -1:
    S.reverse()
mojieru = ''.join(S)
print(mojieru)
### BUGGY CODE ###

import numpy as np
N, K = map(int, input().split())
c = []
for _ in range(N):
    a, b= map(int, input().split())
    for i in range(b):
        c.append(a)
print(sorted(c)[K-1])

### FIXED CODE ###

N, K = map(int, input().split())
num = [0]*(10**5+1)
for i in range(N):
    a, b= map(int, input().split())
    num[a] += b
for i in range(1, 10**5+1):
    if K <= num[i]:
        print(i)
        exit()
    K -= num[i]
### BUGGY CODE ###

n,m=map(int, input().split())
s=list(map(int, input().split()))
t=list(map(int, input().split()))
dp=[[0]*(n+1) for _ in range(m+1)]
for i in range(m+1):
    dp[i][0]=1
for i in range(n+1):
    dp[0][i]=1
for i in range(m):
    for j in range(n):
        if s[j]==t[i]:
            dp[i+1][j+1]=(dp[i][j+1]+dp[i+1][j])%(10**9+7)
        else:
            dp[i+1][j+1]=dp[i][j+1]+dp[i+1][j]-dp[i][j]
print(dp[-1][-1]%(10**9+7))

### FIXED CODE ###

n,m=map(int, input().split())
s=list(map(int, input().split()))
t=list(map(int, input().split()))
dp=[[0]*(n+1) for _ in range(m+1)]
for i in range(m+1):
    dp[i][0]=1
for i in range(n+1):
    dp[0][i]=1
for i in range(m):
    for j in range(n):
        if s[j]==t[i]:
            dp[i+1][j+1]=(dp[i][j+1]+dp[i+1][j])%(10**9+7)
        else:
            dp[i+1][j+1]=dp[i][j+1]+dp[i+1][j]-dp[i][j]
print(dp[-1][-1]%(10**9+7))
### BUGGY CODE ###

import sys
n = int(input())
l = list(map(int,input().split()))
count = 1
for i in l:
    count= count*i
    if i == 0:
        print("0")
        sys.exit()
if count > 10**18:
    print("-1")
    sys.exit()
print(count)

### FIXED CODE ###

import sys
n = int(input())
l = list(map(int,input().split()))
l.sort()
count = 1
for i in l:
    count= count*i
    if count == 0:
        print("0")
        sys.exit()
    elif count > 10**18:
        print("-1")
        sys.exit()
if count > 10**18:
    print("-1")
    sys.exit()
print(count)
### BUGGY CODE ###

n,a,b,k=[int(i) for i in input().split()]
c=a+b
mod=998244353
ans=0

g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  #逆元テーブル
inverse = [0, 1]  #逆元テーブル計算用テーブル

for i in range(2,300003):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

#以下のcom関数を用いて組み合わせを計算
def com(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

for i in range(n+1):
    if (k-b*i)%a==0 and k-b*i>=0:
        n_a=(k-b*i)//a
        n_b=i
        n_c=min(n_a,n_b)
        n_a, n_b=n_a-min(n_a,n_b), n_b-min(n_a,n_b)
        count=0
        while n_a + n_b + n_c <=n and n_c>=0 and n_b>=0 and n_a>=0:
            ans+=com(n, n_c, mod) * com(n-n_c, n_b, mod) * com(n-n_c-n_b, n_a, mod)

            n_c-=1
            n_b+=1
            n_a+=1

print(ans%mod)

### FIXED CODE ###

n,a,b,k=[int(i) for i in input().split()]
c=a+b
mod=998244353
ans=0

g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  #逆元テーブル
inverse = [0, 1]  #逆元テーブル計算用テーブル

for i in range(2,300003):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

#以下のcom関数を用いて組み合わせを計算
def com(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

for i in range(n+1):
    if (k-b*i)%a==0 and k-b*i>=0:
        n_a=(k-b*i)//a
        n_b=i
        if  max(n_a, n_b) <=n:
            ans+=com(n, n_a, mod) * com(n, n_b, mod)  %mod

print(ans%mod)
### BUGGY CODE ###

N,M=map(int,input().split())
x=[int(x) for x in range(1,N+1)]
l=[]
a=0
for i in range(M):
    L,R=map(int,input().split())
    y=[int(x) for x in range(L,R+1)]
    l+=y
for j in range(1,N+1):
    if l.count(x[j-1])==M:
        a+=1
print(a)

### FIXED CODE ###

N,M=map(int,input().split())
l=[]
r=[]
for i in range(M):
    L,R=map(int,input().split())
    l.append(L)
    r.append(R)
a=max(l)
b=min(r)
x=list(range(a,b+1))
print(len(x))