Harryxun/stf_run huggingface dataset:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    if q<0 or q>=n or len(a)!=n:
        b=1
        while True:
            b+=1

    while p<n and a[q]+a[p]<=md:
        p+=1

    if p==n: break
    cnt+=n-p
    ans+=a[q]*(n-p)*2


ans+=(m-cnt)*md
print(ans)


### FIXED CODE ###

import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2
md=(r+l)//2
while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and a[q]+a[p]<=md:
            p+=1
    except:
        b=1
        while True:
            b+=1

    if p==n: break
    cnt+=n-p
    ans+=a[q]*(n-p)*2


ans+=(m-cnt)*md
print(ans)
def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    cnt, nega, posi = 0, 0, []
    for x, y in zip(a, b):
        if x < y:
            nega += y - x
            cnt += 1
        else:
            posi.append(x - y)
    posi.sort(reverse=True)
    i = 0
    while nega > 0:
        nega -= posi[i]
        cnt += 1
        i += 1
    print(cnt)

if __name__ == "__main__":
    main()

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
cnt, nega, posi = 0, 0, []
for x, y in zip(a, b):
    if x < y:
        nega += y - x
        cnt += 1
    else:
        posi.append(x - y)
if nega > 0:
    posi.sort(reverse=True)
    for i, x in enumerate(posi):
        nega -= x
        if nega <= 0:
            cnt += i + 1
            break
    else:
        cnt = -1
print(cnt)
# PROBLEM A
s = input()
letters = set(s)
perm_abc = len(letters) == 3 and all(c in letters for c in 'abc')
if perm_abc:
    print 'Yes'
else:
    print 'No'

### FIXED CODE ###

# PROBLEM A
s = input()
letters = set(s)
perm_abc = len(letters) == 3 and all(c in letters for c in 'abc')
if perm_abc:
    print('Yes')
else:
    print('No')
N,K = map(int,input().split())

def nCr(n, r, mod=10**9+7):
    r = min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n+1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod

for i in range(1,K+1):
    if N-K+1 < i:
        print(0)
        continue
    else:
        print((nCr(N-K+1,i)*nCr(K-1,i-1))%M)


### FIXED CODE ###

N,K = map(int,input().split())
M = 10**9+7
def nCr(n, r, mod=10**9+7):
    r = min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n+1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod

for i in range(1,K+1):
    if N-K+1 < i:
        print(0)
        continue
    else:
        print((nCr(N-K+1,i)*nCr(K-1,i-1))%M)
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
import sys
gcd = math.gcd
co = collections.Counter()
n = ni()
mod=10**9+7
for i in range(n):
    a,b = ma()
    d = gcd(a,b)
    a//=d
    b//=d
    co[(a,b)]+=1
d = collections.defaultdict(lambda:False)
ans=1
for t,cnt in co.items():
    a,b = t
    if t==(0,0) or d[t]:
        continue
    d[(a,b)]=True;d[(-a,-b)]=True;d[(b,-a)]=True;d[(-b,a)]=True
    l1 = co[(a,b)]+co[(-a,-b)]
    l2 = co[(b,-a)]+co[(-b,a)]
    ans=ans*(pow(2,l1,mod)+pow(2,l2,mod) -1)%mod
    ans%=mod
print((ans-1)%mod)


### FIXED CODE ###

ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
import sys
gcd = math.gcd
co = collections.Counter()
n = ni()
mod=10**9+7
for i in range(n):
    a,b = ma()
    d = gcd(a,b)
    if d!=0:
        a//=d
        b//=d
    elif abs(a)>0 or abs(b)>0:
        l = max(abs(a), abs(b))
        a//=l
        b//=l
    co[(a,b)]+=1
d = collections.defaultdict(lambda:False)
ans=1
for t,cnt in co.items():
    a,b = t
    if t==(0,0) or d[t]:
        continue
    d[(a,b)]=True;d[(-a,-b)]=True;d[(b,-a)]=True;d[(-b,a)]=True
    l1 = co[(a,b)]+co[(-a,-b)]
    l2 = co[(b,-a)]+co[(-b,a)]
    ans=ans*(pow(2,l1,mod)+pow(2,l2,mod) -1)%mod
    ans%=mod
print((ans-1 +co[(0,0)])%mod)
def main():
    a, b = map(int, input().split())
    # 1 + R * (A - 1) >= B
    print((b - 1 + a - 2) // (a - 1))


if __name__ == "__main__":
    main()


### FIXED CODE ###

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

print(1 / sum([1 / a for a in A_list]))
n, input_k = map(int, input().split())
a = list(map(int, input().split()))

MAX = 40

k = [0 for _ in range(MAX)]
c = [0 for _ in range(MAX)]
b = [0 for _ in range(MAX)]
v = [[0 for _ in range(MAX)] for _ in range(2)]

K = input_k
d = 0
while K > 0:
    if K % 2 == 1:
        k[d] = 1
    d += 1
    K //= 2

for p in a:
    counter = 0
    while p > 0:
        if p % 2 == 1:
            c[counter] += 1
        counter += 1
        p //= 2

temp = 1
for i in range(MAX):
    if c[i] > n - c[i]:
        b[i] = 0
    else:
        b[i] = 1
    v[0][i] = temp * c[i]
    v[1][i] = temp * (n - c[i])
    temp *= 2

if input_k == 0:
    print(sum(v[0]))
    exit()

ans = 0
for i in range(d, -1, -1):
    if k[i] == 0:
        continue

    temp_ans = 0
    for j in range(i+1, MAX):
        temp_ans += v[k[j]][j]

    temp_ans += v[0][i]

    for j in range(i):
        temp_ans += v[b[j]][j]

    ans = max(ans, temp_ans)

print(ans)


### FIXED CODE ###

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

MAX = 41

k = [0 for _ in range(MAX)]
c = [0 for _ in range(MAX)]
b = [0 for _ in range(MAX)]
v = [[0 for _ in range(MAX)] for _ in range(2)]

K = input_k + 1
d = 0
while K > 0:
    if K % 2 == 1:
        k[d] = 1
    d += 1
    K //= 2

for p in a:
    counter = 0
    while p > 0:
        if p % 2 == 1:
            c[counter] += 1
        counter += 1
        p //= 2

temp = 1
for i in range(MAX):
    if c[i] > n - c[i]:
        b[i] = 0
    else:
        b[i] = 1
    v[0][i] = temp * c[i]
    v[1][i] = temp * (n - c[i])
    temp *= 2

if input_k == 0:
    print(sum(v[0]))
    exit()

ans = 0
for i in range(MAX - 1, -1, -1):
    if k[i] == 0:
        continue

    temp_ans = 0
    for j in range(i+1, MAX):
        temp_ans += v[k[j]][j]

    temp_ans += v[0][i]

    for j in range(i):
        temp_ans += v[b[j]][j]

    #print(i, temp_ans)
    ans = max(ans, temp_ans)

print(ans)
from datetime import datetime,timedelta

a=[int(input()) for _ in range(5)]

t1=datetime(2000,1,1,a[0],a[1],0)
t2=datetime(2000,1,1,a[2],a[3],0)

delta=t2-t1
total_seconds=delta.seconds

ans=(total_seconds-a[4]*60)/60
print(ans)


### FIXED CODE ###

from datetime import datetime,timedelta

a=input().split()
a=[int(_) for _ in a]

t1=datetime(2000,1,1,a[0],a[1],0)
t2=datetime(2000,1,1,a[2],a[3],0)

delta=t2-t1
total_seconds=delta.seconds

ans=(total_seconds-a[4]*60)/60
print(int(ans))
import  numpy as np

arr = np.array([])
N = int(input())
for _ in range(N):
  arr = np.append(arr,input())
  
print(len(np.unique(arr)))

### FIXED CODE ###


N = int(input())
ss = []
for i in range(N):
  ss.append(input())
  
print(len(set(ss)))
s=str(input())

for i in range(len(s)):
  if s.index(s[i]) % 2 == 0:
    del s[i]
print(s)

### FIXED CODE ###

s=str(input())
ans=str('')
for i in range(0,len(s),2):
  ans+=s[i]
print(ans)
a = list(map(int,input().split()))
a.sort()
print(sum(a[0:1])

### FIXED CODE ###

a = list(map(int,input().split()))
a.sort()
print(sum(a[0:2]))
a=map(int,input().split())
flg=0
for i in range(9):
  if a % (9-i) == 0 and a / (9-i) < 10:
    print("YES")
    flg=1
    break

if flg==0:
  print("NO")
    

### FIXED CODE ###

am=input()
a = int(am)
flg=0
for i in range(9):
  if a % (9-i) == 0 and a / (9-i) < 10:
    print("Yes")
    flg=1
    break
 
if flg==0:
  print("No")
from fractions import gcd

n=int(input())
t=[int(input()) for i in range(n)]

for i in range(1,n):
    lcm=(t[i]*t[i-1]//gcd(t[i],t[i-1]))
    t[i]=lcm
print(lcm)

### FIXED CODE ###

from fractions import gcd

n=int(input())
t=[int(input()) for i in range(n)]

lcm=t[0]
for i in range(n-1):
    lcm=(t[i]*t[i+1]//gcd(t[i],t[i+1]))
    t[i+1]=lcm
print(lcm)
import math

a, b, c, d = map(int, input().split())

g = int(c * d / math.gcd(c, d))

b_c = b // c
b_d = b // d
b_g = b // g
a_c = (a-1) // c
a_d = (a-1) // d
a_g = (a-1) // g

ans = (b - b_c - b_d + b_g) - ((a-1) - a_c - a_d + a_g)
print(ans)


### FIXED CODE ###

from fractions import gcd

a, b, c, d = map(int, input().split())
g = int(c * d / gcd(c, d))
print((b - b // c - b // d + b // g) - ((a-1) - (a-1) // c - (a-1) // d + (a-1) // g))
L, R= map(int, input().split())
ans = []
for i in range(L, R):
    for j in range(i+1, R+1):
        if (i*j)%2019 == 0:
            print(0)
            sys.exit()
        else:
            ans.append((i*j)%2019)
print(min(ans))

### FIXED CODE ###

import sys
L, R= map(int, input().split())
ans = []
for i in range(L, R):
    for j in range(i+1, R+1):
        if (i*j)%2019 == 0:
            print(0)
            sys.exit()
        else:
            ans.append((i*j)%2019)
print(min(ans))
from fractions import gcd
from functools import reduce

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

def lcm(x, y):
    return int(x*y/gcd(x, y))

B = [1 for i in range(N)]
global_lcm = reduce(lambda a, b : lcm(a, b), A)
for i in range(N):
    B[i] = int(global_lcm/A[i])
ans = 0
for i, b in enumerate(B):
    ans += b % MOD
    ans %= MOD

print(ans)

### FIXED CODE ###

from fractions import gcd
from functools import reduce, lru_cache

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

def lcm(x, y):
    return int(x*y)//int(gcd(x, y))

B = [1 for i in range(N)]
global_lcm = reduce(lcm, A) % MOD
ans = 0
for i in range(N):
    ans += (global_lcm*pow(A[i], MOD-2, MOD)) % MOD
    ans %= MOD

print(ans)
sx,sy,tx,ty=map(int,input().split())
ans=[[] for _ in range(4)]

x=sx
y=sy

while y!=ty or x!=tx:
    if y<ty:
        y+=1
        ans[0].append("U")
        ans[1].append("D")
    elif x<tx:
        x+=1
        ans[0].append("R")
        ans[1].append("L")
       
x=sx-1
y=sy
ans[2].append("L")
ans[3].append("R")

while 1:
    if y<ty+1:
        y+=1
        ans[2].append("U")
        ans[3].append("D")
    elif x<tx:
        x+=1
        ans[2].append("R")
        ans[3].append("L")
    else:
        ans[2].append("D")
        ans[3].append("U")
        break


print(*ans[0],*ans[1],*ans[2],*ans[3],sep="")

### FIXED CODE ###

sx,sy,tx,ty=map(int,input().split())
ans=[[] for _ in range(4)]

x=sx
y=sy

while y!=ty or x!=tx:
    if y<ty:
        y+=1
        ans[0].append("U")
        ans[1].append("D")
    elif x<tx:
        x+=1
        ans[0].append("R")
        ans[1].append("L")
       
x=sx-1
y=sy
ans[2].append("L")
ans[3].append("R")

while 1:
    if y<ty+1:
        y+=1
        ans[2].append("U")
        ans[3].append("D")
    elif x<tx:
        x+=1
        ans[2].append("R")
        ans[3].append("L")
    else:
        ans[2].append("D")
        ans[3].append("U")
        break

li=[]

for i in range(4):
    for j in ans[i]:
        li.append(j)

print(''.join(li))

#print(*ans[0],*ans[1],*ans[2],*ans[3],sep="")
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
 
# 遅延評価で加えてあげるだけ
 
N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
 
value = [0] * (N+1)
for p,x in px:
    value[p] += x
    
q = [(1,0)]
while q:
    x,parent = q.pop()
    value[x] += value[parent]
    for y in graph[x]:
        if y == parent:
            continue
        q.append((y,x))
 
answer = ' '.join(map(str,value[1:]))
print(answer)

### FIXED CODE ###

N,Q = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(N-1)]
px = [list(map(int,input().split())) for i in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)

value = [0] * (N+1)
for p,x in px:
    value[p] += x

from collections import deque
todo = deque([(1,0)])
while len(todo) > 0:
    x,parent = todo.pop()
    value[x] += value[parent]
    for y in graph[x]:
        if y == parent:
            continue
        todo.append((y,x))

answer = ' '.join(map(str,value[1:]))
print(answer)
h, a = int(input())

n = 0
while h > 0:
    h -= a
    n += 1
print(n)

### FIXED CODE ###

h, a = map(int, input().split())

n = 0
while h > 0:
    h -= a
    n += 1
print(n)
N,K = map(int, input().split())

S = input()
S_bef = int(S[:2])
S_aft = int(S[-2:])

is_bef_yy = False
is_bef_mm = False
is_aft_yy = False
is_aft_mm = False

if S_bef >= 1 and S_bef <= 12:
    is_bef_mm = True
if S_bef >= 0:
    is_bef_yy = True
if S_aft >= 1 and S_aft <= 12:
    is_aft_mm = True
if S_aft >= 0:
    is_aft_yy = True

if is_bef_yy and is_bef_mm and is_aft_yy and is_aft_mm:
    print('AMBIGUOUS')
elif is_bef_yy and is_aft_mm:
    print('YYMM')
elif is_aft_yy and is_bef_mm:
    print('MMYY')
else:
    print('NA')



### FIXED CODE ###

S = input()
S_bef = int(S[:2])
S_aft = int(S[-2:])

is_bef_yy = False
is_bef_mm = False
is_aft_yy = False
is_aft_mm = False

if S_bef >= 1 and S_bef <= 12:
    is_bef_mm = True
if S_bef >= 0:
    is_bef_yy = True
if S_aft >= 1 and S_aft <= 12:
    is_aft_mm = True
if S_aft >= 0:
    is_aft_yy = True

if is_bef_yy and is_bef_mm and is_aft_yy and is_aft_mm:
    print('AMBIGUOUS')
elif is_bef_yy and is_aft_mm:
    print('YYMM')
elif is_aft_yy and is_bef_mm:
    print('MMYY')
else:
    print('NA')
#他人のコードです
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
 
N = int(readline())
A = np.array(read().split(), np.int64)
I = np.argsort(A)[::-1].tolist()
A = A[I].tolist()
 
dp = np.zeros(1, np.int64)
 
for n, (i, x) in enumerate(zip(I, A)):
    newdp = np.zeros(len(dp) + 1, np.int64)
    left_ind = np.arange(len(dp))
    right_ind = N - 1 - n + left_ind
    left_cost = x * np.abs(left_ind - i)
    right_cost = x * np.abs(right_ind - i)
    np.maximum(newdp[:-1], dp + right_cost, out=newdp[:-1])
    np.maximum(newdp[1:], dp + left_cost, out=newdp[1:])
    dp = newdp
 
print(dp.max())

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=[]
for k in range(N):
    B.append([A[k],k+1])
B.sort(key=lambda x: x[0], reverse=True)
dp=[[0 for k in range(N+1)]for k in range(N+1)]
dp[1][0]=dp[0][0]+B[0][0]*(B[0][1]-1)
dp[0][1]=dp[0][0]+B[0][0]*(N-B[0][1])
for k in range(1,N):
    #j=0
    dp[0][k+1]=dp[0][k]+B[k][0]*(N-k-B[k][1])
    dp[1][k]=max(dp[0][k]+B[k][0]*(B[k][1]-1), dp[1][k-1]+B[k][0]*(N-k+1-B[k][1]))
    #j=k
    dp[k+1][0]=dp[k][0]+B[k][0]*(B[k][1]-k-1)
    dp[k][1]=max(dp[k-1][+1]+B[k][0]*(B[k][1]-k), dp[k][0]+B[k][0]*(N-B[k][1]))
    for j in range(1,k):
        dp[j+1][k-j]=max(dp[j][k-j]+B[k][0]*(B[k][1]-j-1), dp[j+1][k-j-1]+B[k][0]*(N-k+j+1-B[k][1]))
        dp[j][k-j+1]=max(dp[j-1][k-j+1]+B[k][0]*(B[k][1]-j), dp[j][k-j]+B[k][0]*(N-k+j-B[k][1]))
ans=[]
for k in range(N+1):
    ans.append(dp[k][N-k])
print(max(ans))
N, M = map(int, input().split(" "))
AB = [list(map(int, input().split(" "))) for _ in range(M)]


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.per = list(range(n))
        self.point = n*(n-1) // 2
        self.counts = [1]*n

    def root(self, x):
        if self.per[x] == x:
            return x
        return self.root(self.per[x])

    def union(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return False
        self.per[rx] = ry
        self.point -= self.counts[ry] * self.counts[rx]
        self.counts[ry] += self.counts[rx]
        self.counts[rx] = 0

    def is_same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry


u = UnionFind(N)
results = []
for a, b in AB[::-1]:
    x, y = a-1, b-1
    u.union(x, y)
    results.append(u.point)

for r in results[::-1]:
    print(r)


### FIXED CODE ###

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


class UnionFind:
    def __init__(self, n):
        self.par = [-1]*n
        self.size = [1]*n
        self.point = n*(n-1) // 2

    def root(self, x):
        if self.par[x] < 0:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return False
        if self.size[rx] < self.size[ry]:
            rx, ry = ry, rx
        self.point -= self.size[rx]*self.size[ry]
        self.size[rx] += self.size[ry]
        self.par[ry] = rx
        return True

    def is_same(self, x, y):
        rx, ry = self.root(x), self.root(y)
        return rx == ry

    def get_size(self, x):
        return self.size[self.root(x)]


uf = UnionFind(N)
results = []
for a, b in AB[::-1]:
    results.append(uf.point)
    x, y = a-1, b-1
    uf.unite(x, y)

print(*results[::-1], sep="\n")
a, b, c, d, e, f = [int(i) for i in input().split()]
max_density = 0
for i_1 in range(f//(a*100)+1):
    for i_2 in range((f-100*a)//(b*100)+1):
        for i_3 in range(((i_1*a+i_2*b)*e)//c+1):
            i_4 = (((i_1*a+i_2*b)*e)-i_3*c)//d
            if i_1 == 0 and i_2 == 0:
                break
            if i_1*100*a+i_2*100*b+i_3*c + i_4*d > f:
                continue
            if (i_3*c + i_4*d)/(i_1*100*a+i_2*100*b+i_3*c + i_4*d) > max_density:
                max_density = (i_3*c + i_4*d)/(i_1*100*a+i_2*100*b+i_3*c + i_4*d)
                water = i_1*100*a+i_2*100*b
                sugar = i_3*c + i_4*d
print(water+sugar, sugar)

### FIXED CODE ###

a, b, c, d, e, f = [int(i) for i in input().split()]
max_density = 0.0
water = 0
sugar = 0
for i_1 in range(f//(a*100)+1):
    for i_2 in range((f-100*a*i_1)//(b*100)+1):
        for i_3 in range(min(((i_1*a+i_2*b)*e)//c , (f-(i_1*100*a+i_2*100*b))//c)+1):
            i_4 = min((((i_1*a+i_2*b)*e)-i_3*c)//d , (f-(i_1*100*a+i_2*100*b+i_3*c))//d)
            if i_1 == 0 and i_2 == 0:
                break
            if (i_3*c + i_4*d)/(i_1*100*a+i_2*100*b+i_3*c + i_4*d) >= max_density:
                max_density = (i_3*c + i_4*d)/(i_1*100*a+i_2*100*b+i_3*c + i_4*d)
                water = i_1*100*a+i_2*100*b
                sugar = i_3*c + i_4*d
print(water+sugar, sugar)
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
import numpy as np




def main():
    num = int(input())
    data = [int(input()) for i in range(num)]
    sum_num = sum(data)
    mod = 998244353

    dp = np.zeros(sum_num + 1, dtype=np.int64)
    dp[0] = 1
    for i in range(num):
        now_num = data[i]
        prev = dp
        dp = 2 * prev
        dp[now_num:] += prev[:-now_num]
        dp %= mod

    dp2 = np.zeros(sum_num + 1, dtype=np.int64)
    dp2[0] = 1
    for i in range(num):
        now_num = data[i]
        prev = dp2
        dp2[now_num:] += prev[:-now_num]
        dp2 %= mod

    ans = pow(3, num, mod)
    hikukazu = 0
    for i in range(math.ceil(sum_num / 2), sum_num + 1):
        hikukazu += dp[i]
    if sum_num % 2 == 0:
        hikukazu -= dp2[sum_num // 2]
    ans -= hikukazu * 3
    ans %= mod
    print(ans)
    # print(dp)


if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
MOD = 998244353

N = int(input())
A = [int(input()) for _ in range(N)]
S = sum(A)

# 赤の和がS/2以上となるものを求めて3倍
# 和に対して何通りあるのか

dp = np.zeros(S+1, dtype=np.int64)
dp[0] = 1
for a in A:
    prev = dp
    dp = prev * 2 # 赤以外を採用
    dp[a:] += prev[:-a] # 赤
    dp %= MOD

answer = pow(3,N,MOD) - dp[(1+S)//2:].sum() * 3
# 2色が反例となる場合を引きすぎている
if S % 2 == 0:
    dp = np.zeros(S+1, dtype=np.int64)
    dp[0] = 1
    for a in A:
        dp[a:] += dp.copy()[:-a]
        dp %= MOD
    answer += dp[S//2] * 3
answer %= MOD
print(answer)
n,k=map(int,input().split())
xs=[0]+list(map(int,input().split()))
from itertools import accumulate
As=list(accumulate(xs))
r = 0
for i in range(k+1):
    for j in range(i, k+1):
        x = i, j-i, k-j
        m1 = As[i] + As[n] - As[n-j+i]
        m = m1 - sum(sorted(z for z in (xs[:i]+xs[n-j+i+1:]) if z < 0)[:k-j])
#        if m > r:
#            print(x, m, m1)
        r = max(r, m)
print(r)


### FIXED CODE ###

n,k=map(int,input().split())
xs=[0]+list(map(int,input().split()))
from itertools import accumulate
As=list(accumulate(xs))
r = 0
for i in range(k+1):
    for j in range(i, k+1):
        x = i, j-i, k-j
        if j > n:
            continue
        m1 = As[i] + As[n] - As[n-j+i]
        m = m1 - sum(sorted(z for z in (xs[:i]+xs[n-j+i+1:]) if z < 0)[:k-j])
#        if m > r:
#            print(x, m, m1)
        r = max(r, m)
print(r)
s = input()
l = set(s)
if len(l) == 2 and l.count(s[0]) == 2:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

s = input()
l = set(s)
if len(l) == 2 and s.count(s[0]) == 2:
    print('Yes')
else:
    print('No')
A, B = map(long, raw_input().split())
ans = B
for i in range(A, B):
    ans = ans ^ i

print(ans)

### FIXED CODE ###

def xor(_x) :
    if _x % 4 == 0:
        return _x
    elif _x % 4 == 1:
        return 1
    elif _x % 4 == 2:
        return 1 ^ _x
    else:
        return 0


A, B = map(long, raw_input().split())
print(xor(A - 1) ^ xor(B))
n=int(input())
if n===1:print(1)
else:print((n+1)//2/n)

### FIXED CODE ###

n=int(input())
if n==1:print(1)
else:print((n+1)//2/n)
A, B, M = list(map(int,input().split()))
list_a = list(map(int,input().split()))
list_b = list(map(int,input().split()))
for i in range(M):
    x, y, c = list(map(int,input().split()))
buy = []
buy.append(min(list_a) + min(list_b))
buy.append(list_a[x] + list_b[y] - c)
answer = min(buy)
print(answer)


### FIXED CODE ###

A, B, M = list(map(int,input().split()))
list_a = list(map(int,input().split()))
list_b = list(map(int,input().split()))
buy = []
buy.append(min(list_a) + min(list_b))
for i in range(M):
    x, y, c = list(map(int,input().split()))
    buy.append(list_a[x-1] + list_b[y-1] - c)
answer = min(buy)
print(answer)
s=input()

for i in range(3):
        if s[i] == s[j+1]:
                print("Bad")
                exit()
print("Good")

### FIXED CODE ###

s=input()

for i in range(3):
        if s[i] == s[i+1]:
                print("Bad")
                exit()
print("Good")
import math
import sys

x,y=[int(i) for i in input().split()]

if x > y:
    print("GREATER")
elif x == y:
    print("EQUAL")
else:
    print("LESS")


### FIXED CODE ###

import math
import sys

s = input().split()

print(s[0][0].upper() + s[1][0].upper() + s[2][0].upper())
W, H, x, y = map(int, input().split())
B=1 if 2*x == W and 2*y = H else B=0
print(W*H/2, B)

### FIXED CODE ###

W, H, x, y = map(int, input().split())
if 2*x == W and 2*y == H:
    B=1
else: 
    B=0
print(W*H/2, B)
a = int(input())
b = int(input())
print(a*b)

### FIXED CODE ###

a, b = map(int,input().split())
print(a*b)