CodeEff/ECCO huggingface dataset:
# Original solution
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

H, W, *AB = list(map(int, read().split()))
AB_list = [(-1,-1)]
for i in range(H):
    a, b = AB[2*i], AB[2*i+1]
    AB_list.append((a,b))

min_list = [INF] * (H+3)
MAP = [[INF] * (W + 2) for _ in range(H + 3)]

def bfs(start):
    queue = deque([(start + (0,))])
    while queue:
        ci,cj, count = queue.popleft()
        if min_list[ci] > count:
            min_list[ci] = count

        if ci == H+1:break
        a, b = AB_list[ci]

        if a <= cj <= b:
            if b + 1 <= W:
                queue.append((ci+1, b + 1, count + b- cj + 2))

        elif ci + 1 <= H+1:
            queue.append((ci+1, cj, count + 1))


def run():
    a1, b1 = AB_list[1]
    for j in range(1, W+1):
        if a1 <= j <= b1:continue
        bfs((1, j))

    for v in min_list[2:-1]:
        if v == INF:
            print((-1))
        else:
            print(v)

    #for m in MAP:
    #    print(m)




if __name__ == "__main__":
    run()

# Optimized solution
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

H, W, *AB = list(map(int, read().split()))
AB_list = [(-1,-1)]
for i in range(H):
    a, b = AB[2*i], AB[2*i+1]
    AB_list.append((a,b))

min_list = [INF] * (H+3)
MAP = [[INF] * (W + 2) for _ in range(H + 3)]

def bfs(start):
    queue = deque([(start + (0,))])
    while queue:
        ci,cj, count = queue.popleft()
        if MAP[ci][cj] > count:
            MAP[ci][cj] = count
            if min_list[ci] > count:
                min_list[ci] = count
        else:
            continue



        if ci == H+1:break
        a, b = AB_list[ci]

        if a <= cj <= b:
            if b + 1 <= W:
                queue.append((ci+1, b + 1, count + b- cj + 2))

        elif ci + 1 <= H+1:
            queue.append((ci+1, cj, count + 1))


def run():
    a1, b1 = AB_list[1]
    for j in range(1, W+1):
        if a1 <= j <= b1:continue
        bfs((1, j))

    for v in min_list[2:-1]:
        if v == INF:
            print((-1))
        else:
            print(v)

    #for m in MAP:
    #    print(m)




if __name__ == "__main__":
    run()
# Original solution
def collatz(n):
	c = 0
	while n > 1:
		if n%2:	n = 3*n+1
		else: n /= 2
		c += 1
	return c
	
while True:
	n = int(input())
	if n == 0: break
	print(collatz(n))

# Optimized solution
def f(n):
	c=0
	while n>1:
		if n%2:n=3*n+1
		else:n /= 2
		c += 1
	print(c)
	
while 1:
	n=eval(input())
	if n==0:break
	f(n)
# Original solution
import sys
for line in sys.stdin:
	l = [int(i) for i in line.split(' ')]
	print(len(str(l[0] + l[1])))

# Optimized solution
import sys

for s in sys.stdin:
	a,b = list(map(int,s.split()))
	print(len(str(a+b)))
# Original solution
import math
while True:
    try:
        line = input().split(" ")
        a = int(line[0])
        b = int(line[1])
        print((int(math.log10(a+b))+1))
    except:
        break

# Optimized solution
import math

while True:
    try:
        line = input().split(" ")
        print((int(math.log10(int(line[0])+int(line[1])))+1))
    except:
        break
# Original solution
while True:
    try:
        print((len(str(sum(map(int, input().split()))))))
    except EOFError:
        break

# Optimized solution
import sys
 
[print(len(str(y[0] + y[1]))) for y in [[int(z) for z in x.split()] for x in sys.stdin]]
# Original solution
import sys
from math import log10

for line in sys.stdin:
	a, b = list(map(int, line.split()))
	digitNumber = int(log10((a + b))) + 1
	print(digitNumber)

# Optimized solution
import sys

for line in sys.stdin:
	a, b = list(map(int, line.split()))
	digitNumber = len(str(a + b))
	print(digitNumber)
# Original solution
import sys
strs = sys.stdin.readlines()
for s in strs:
    a, b = list(map(int, s.split()))
    print((len(str(a + b))))

# Optimized solution
import sys
for line in sys.stdin:
    a, b = list(map(int, line.split()))
    print((len(str(a + b))))
# Original solution
import sys
a=[map(int,i.split()) for i in sys.stdin]
[print(len(str(b+c))) for b,c in a]


# Optimized solution
import sys
for a in sys.stdin:
    b,c=list(map(int,a.split()))
    d=len(str(b+c))
    print(d)
# Original solution
import sys
for a in sys.stdin:
    b,c=list(map(int,a.split()))
    d=len(str(b+c))
    print(d)

# Optimized solution
import sys
a=[map(int,i.split())for i in sys.stdin]
[print(len(str(b+c)))for b,c in a]
# Original solution
import sys

for line in sys.stdin:
  x, y = list(map(int, line.split()))
  print((len(str(x+y))))

# Optimized solution
import sys
[print(len(str(sum(map(int, line.split()))))) for line in sys.stdin]
# Original solution
import sys
for s in sys.stdin:
    print(len(str(sum(map(int,s.split())))))

# Optimized solution
import sys
for s in sys.stdin:
    x=len(str(sum(map(int,s.split())))) 
    print(x)
# Original solution

while 1:
    try:
        a, b = list(map(int, input().split()))
        c = str(a + b)

        print((len(c)))
    except:
        break

# Optimized solution
import sys

def solve():
    while True:
        try:
            a, b = list(map(int, sys.stdin.readline().split()))
            c = a + b

            if c == 0:
                print((1))
            else:
                ans = 0

                while c > 0:
                    ans += 1
                    c //= 10

                print(ans)

        except:
            return

if __name__ == '__main__':
    solve()
# Original solution
from collections import defaultdict

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

DP = [defaultdict(int)]
DP[0][0] = 2
DP[0][A[0]] = 1
DP2 = [defaultdict(int)]  # R=G=S/2, B=0
DP2[0][0] = 1
DP2[0][A[0]] = 1
for i in range(1, N):
    curr = defaultdict(int)
    curr2 = defaultdict(int)
    for (key, val) in list(DP[-1].items()):
        curr[key] += val*2  # B,G
        curr[key+A[i]] += val  # R
    for (key, val) in list(DP2[-1].items()):
        curr2[key] += val  # G
        curr2[key+A[i]] += val  # R
    DP.append(curr)
    DP2.append(curr2)
# print(DP)
# print(DP2)

ans = 3**N
for (key, val) in list(DP[-1].items()):
    if key >= S/2:
        ans -= 3*val

if S % 2 == 0:
    ans += 3*DP2[-1][S//2]

print((ans % 998244353))


# Optimized solution
from collections import defaultdict

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

DP = [[0]*(S+1) for _ in range(2)]
DP[0][0] = 2
DP[0][A[0]] = 1

# R=G=S/2, B=0
DP2 = [[0]*(S+1) for _ in range(2)]
DP2[0][0] = 1
DP2[0][A[0]] = 1


max_A = A[0]
for i in range(1, N):
    a = A[i]
    max_A += a
    curr_dp = DP[i % 2]
    prev_dp = DP[(i+1) % 2]
    curr_dp2 = DP2[i % 2]
    prev_dp2 = DP2[(i+1) % 2]
    for r in range(max_A+1):
        if r >= a:
            curr_dp[r] = prev_dp[r]*2 + prev_dp[r-a]
            curr_dp2[r] = prev_dp2[r] + prev_dp2[r-a]
        else:
            curr_dp[r] = prev_dp[r]*2
            curr_dp2[r] = prev_dp2[r]
#print(DP)
#print(DP2)

half_S = (S+1)//2
ans = (3**N) - 3*sum(DP[(N-1) % 2][half_S:])
if S % 2 == 0:
    ans += 3*DP2[(N-1) % 2][S//2]

print((ans % 998244353))
# Original solution
from collections import defaultdict

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

DP = [[0]*(S+1) for _ in range(2)]
DP[0][0] = 2
DP[0][A[0]] = 1

# R=G=S/2, B=0
DP2 = [[0]*(S+1) for _ in range(2)]
DP2[0][0] = 1
DP2[0][A[0]] = 1


max_A = A[0]
for i in range(1, N):
    a = A[i]
    max_A += a
    curr_dp = DP[i % 2]
    prev_dp = DP[(i+1) % 2]
    curr_dp2 = DP2[i % 2]
    prev_dp2 = DP2[(i+1) % 2]
    for r in range(max_A+1):
        if r >= a:
            curr_dp[r] = prev_dp[r]*2 + prev_dp[r-a]
            curr_dp2[r] = prev_dp2[r] + prev_dp2[r-a]
        else:
            curr_dp[r] = prev_dp[r]*2
            curr_dp2[r] = prev_dp2[r]
#print(DP)
#print(DP2)

half_S = (S+1)//2
ans = (3**N) - 3*sum(DP[(N-1) % 2][half_S:])
if S % 2 == 0:
    ans += 3*DP2[(N-1) % 2][S//2]

print((ans % 998244353))


# Optimized solution
from collections import defaultdict

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

DP = [[0]*(S+1) for _ in range(2)]
DP[0][0] = 2
DP[0][A[0]] = 1

# R=G=S/2, B=0
DP2 = [[0]*(S+1) for _ in range(2)]
DP2[0][0] = 1
DP2[0][A[0]] = 1


max_A = A[0]
for i in range(1, N):
    a = A[i]
    max_A += a
    curr_dp = DP[i % 2]
    prev_dp = DP[(i+1) % 2]
    curr_dp2 = DP2[i % 2]
    prev_dp2 = DP2[(i+1) % 2]
    for r in range(max_A+1):
        if r >= a:
            curr_dp[r] = prev_dp[r]*2 + prev_dp[r-a]
            curr_dp2[r] = prev_dp2[r] + prev_dp2[r-a]
        else:
            curr_dp[r] = prev_dp[r]*2
            curr_dp2[r] = prev_dp2[r]
        curr_dp[r] %= 998244353
        curr_dp2[r] %= 998244353
# print(DP)
# print(DP2)

half_S = (S+1)//2
ans = pow(3, N, 998244353)
ans -= 3*sum(DP[(N-1) % 2][half_S:])
if S % 2 == 0:
    ans += 3*DP2[(N-1) % 2][S//2]

print((ans % 998244353))
# Original solution
from collections import defaultdict

MOD = 998244353


def main():
    N = int(eval(input()))
    A = [int(eval(input())) for _ in range(N)]
    total = sum(A)
    half = -(-total//2)
    dp1 = [defaultdict(lambda: 0) for _ in range(N+1)]
    dp1[0][0] = 1
    dp2 = [defaultdict(lambda: 0) for _ in range(N+1)]
    dp2[0][0] = 1
    for i in range(N):
        for j in dp1[i]:
            nj = min(j+A[i], half+1)
            dp1[i+1][j] = (dp1[i+1][j] + dp1[i][j] * 2) % MOD
            dp1[i+1][nj] = (dp1[i+1][nj] + dp1[i][j]) % MOD
            dp2[i+1][j] = (dp2[i+1][j] + dp2[i][j]) % MOD
            dp2[i+1][nj] = (dp2[i+1][nj] + dp2[i][j]) % MOD
    ans = (3**N) % MOD
    for t in dp1[N]:
        if t >= -(-total//2):
            ans = (ans - dp1[N][t] * 3) % MOD
            if total % 2 == 0 and t == total // 2:
                ans = (ans + dp2[N][t] * 3) % MOD
    print(ans)


if __name__ == "__main__":
    main()


# Optimized solution
from collections import defaultdict

MOD = 998244353


def main():
    N = int(eval(input()))
    A = [int(eval(input())) for _ in range(N)]
    total = sum(A)
    half = -(-total//2)
    dp1 = [defaultdict(lambda: 0) for _ in range(2)]
    dp1[0][0] = 1
    dp2 = [defaultdict(lambda: 0) for _ in range(2)]
    dp2[0][0] = 1
    for i in range(N):
        dp1[(i+1) & 1] = defaultdict(lambda: 0)
        dp2[(i+1) & 1] = defaultdict(lambda: 0)
        for j in dp1[i & 1]:
            nj = min(j+A[i], half+1)
            dp1[(i+1) & 1][j] = (dp1[(i+1) & 1][j] + dp1[i & 1][j] * 2) % MOD
            dp1[(i+1) & 1][nj] = (dp1[(i+1) & 1][nj] + dp1[i & 1][j]) % MOD
            dp2[(i+1) & 1][j] = (dp2[(i+1) & 1][j] + dp2[i & 1][j]) % MOD
            dp2[(i+1) & 1][nj] = (dp2[(i+1) & 1][nj] + dp2[i & 1][j]) % MOD
    ans = (3**N) % MOD
    for t in dp1[N & 1]:
        if t >= -(-total//2):
            ans = (ans - dp1[N & 1][t] * 3) % MOD
            if total % 2 == 0 and t == total // 2:
                ans = (ans + dp2[N & 1][t] * 3) % MOD
    print(ans)


if __name__ == "__main__":
    main()
# Original solution
N, *A = list(map(int, open(0).read().split()))
MOD = 998244353

S = sum(A)
dp0 = [0]*(S+1)
dp0[0] = 1
dp1 = [0]*(S+1)
dp1[0] = 1
for a in A:
    for i in range(S, a-1, -1):
        dp0[i] = (dp0[i] + dp0[i-a]*2) % MOD
        dp1[i] = (dp1[i] + dp1[i-a]) % MOD

ans = pow(3, N, MOD)
for L in range(0, S+1):
    if L <= S-L:
        ans = (ans - dp0[L]*3) % MOD
if S % 2 == 0:
    ans = (ans + dp1[S//2]*3) % MOD
print(ans)

# Optimized solution
N, *A = list(map(int, open(0).read().split()))
MOD = 998244353

S = sum(A)
dp0 = [0]*(S+1)
dp0[0] = 1
for a in A:
    for i in range(S, a-1, -1):
        dp0[i] = (dp0[i] + dp0[i-a]*2) % MOD
dp1 = [0]*(S+1)
dp1[0] = 1
for a in A:
    for i in range(S, a-1, -1):
        dp1[i] = (dp1[i] + dp1[i-a]) % MOD

ans = pow(3, N, MOD)
for L in range(0, S//2+1):
    ans = (ans - dp0[L]*3) % MOD
if S % 2 == 0:
    ans = (ans + dp1[S//2]*3) % MOD
print(ans)
# Original solution
M=998244353
N,*A=open(0)
d=[0]*90001
d[0]=1
e=[0]*90001
e[0]=1
z=1
s=0
for a in A:
	i=s;a=int(a);s+=a;z*=3
	while~i:d[i+a]+=d[i]%M;d[i]*=2;e[i+a]+=e[i]%M;i-=1
i=s
while i*2>=s:z=(z-d[i]*3)%M;i-=1
print(([(z+e[s//2]*3)%M,z][s%2]))

# Optimized solution
M=998244353
N,*A=open(0)
d=[0]*90001
d[0]=1
e=[0]*90001
e[0]=1
z=1
s=0
for a in A:
	i=s;a=int(a);s+=a;z*=3
	while~i:d[i+a]+=d[i]%M;d[i]*=2;e[i+a]+=e[i]%M;i-=1
i=s
while i*2>=s:z=(z-d[i]*3)%M;i-=1
if~s%2:z+=e[s//2]*3
print((z%M))
# Original solution
M=998244353
N,*A=open(0)
d=[0]*90301
d[0]=1
e=[0]*90301
e[0]=1
z=1
s=0
for a in A:
	a=int(a);s+=a;i=s;z*=3
	while~i:d[i]=d[i]*2+d[i-a]%M;e[i]+=e[i-a]%M;i-=1
i=s
while i*2>=s:z=(z-d[i]*3)%M;i-=1
z+=~s%2*e[s//2]*3
print((z%M))

# Optimized solution
M=998244353
N,*A=open(0)
d=[0]*90301
d[0]=1
e=[0]*90301
e[0]=1
z=1
s=0
for a in A:
	a=int(a);s+=a;i=s;z*=3
	while~i:d[i]+=d[i]+d[i-a]%M;e[i]+=e[i-a]%M;i-=1
i=s
while i*2>=s:z=(z-d[i]*3)%M;i-=1
z+=~s%2*e[s//2]*3
print((z%M))
# Original solution
M=998244353
N,*A=open(0)
d=[1]+[0]*7**6
e=[1]+[0]*7**6
z=1
s=0
for a in A:
	a=int(a);s+=a;i=s;z*=3
	while~i:d[i]+=d[i]+d[i-a]%M;e[i]+=e[i-a]%M;i-=1
i=s
while i*2>=s:z=(z-d[i]*3)%M;i-=1
z+=~s%2*e[s//2]*3
print((z%M))

# Optimized solution
M=998244353
N,*A=open(0)
d=[1]+[0]*7**6
e=[1]+[0]*7**6
z=1
s=0
for a in A:
	a=int(a);s+=a;i=s;z*=3
	while~i:d[i]+=d[i]+d[i-a]%M;e[i]+=e[i-a]%M;i-=1
i=s
while i*2>=s:z=(z-d[i]*3)%M;i-=1
print(((z+~s%2*e[s//2]*3)%M))
# Original solution
M=998244353
N,*A=open(0)
d=[1]+[0]*7**6
e=[1]+[0]*7**6
z=1
s=0
for a in A:
	a=int(a);s+=a;i=s;z*=3
	while~i:d[i]+=d[i]+d[i-a]%M;e[i]+=e[i-a]%M;i-=1
i=s
while i*2>=s:z=(z-d[i]*3)%M;i-=1
print(((z+~s%2*e[s//2]*3)%M))

# Optimized solution
M,z,s=998244353,1,0
d=[1]+[0]*7**6
e=[1]+[0]*7**6
for _ in'_'*eval(input()):
 a=eval(input());s+=a;i=s;z*=3
 while~i:d[i]+=d[i]+d[i-a]%M;e[i]+=e[i-a]%M;i-=1
i=s
while i*2>=s:z=(z-d[i]*3)%M;i-=1
print((z+~s%2*e[s//2]*3)%M)
# Original solution
import sys
input = sys.stdin.readline

n = int(eval(input()))
a = [int(eval(input())) for i in range(n)]
w = sum(a)
mod =998244353

dp = [[0]*(w+1) for i in range(n)]

cnt = a[0]
dp[0][a[0]] = 1
dp[0][0] = 2
for i in range(1,n):
    cnt += a[i]
    for j in range(cnt+1):
        dp[i][j] = dp[i-1][j]*2
        if j >= a[i]:
            dp[i][j] += dp[i-1][j-a[i]]
        


#sより大きいのはブー
s = w//2+1
if w %2 == 0:
    d = [[0]*(s+1) for i in range(n)]
    d[0][0] = 1
    d[0][a[0]] = 1
    cnt = a[0]

    for i in range(1,n):
        cnt += a[i]
        for j in range(min(cnt+1,s+1)):
            d[i][j] = d[i-1][j]
            if j >= a[i]:
                d[i][j] += d[i-1][j-a[i]]
            d[i][j] = d[i][j]%mod
    mns = d[-1][w//2]
if w%2 == 0:
    s -= 1
cnt = 0
for i in range(s,w+1):
    cnt += dp[-1][i]
    cnt = cnt%mod

res = (pow(3,n,mod)-cnt*3)%mod

if w % 2 == 0:
    res = (res+mns*3)%mod
print(res)

# Optimized solution
import sys
input = sys.stdin.readline

n = int(eval(input()))
a = [int(eval(input())) for i in range(n)]
w = sum(a)
mod =998244353

dp = [[0]*(w+1) for i in range(n)]

cnt = a[0]
dp[0][a[0]] = 1
dp[0][0] = 2
for i in range(1,n):
    cnt += a[i]
    for j in range(cnt+1):
        dp[i][j] = dp[i-1][j]*2
        if j >= a[i]:
            dp[i][j] += dp[i-1][j-a[i]]
        
        dp[i][j] = dp[i][j]%mod

#sより大きいのはブー
s = w//2+1
if w %2 == 0:
    d = [[0]*(s+1) for i in range(n)]
    d[0][0] = 1
    d[0][a[0]] = 1
    cnt = a[0]

    for i in range(1,n):
        cnt += a[i]
        for j in range(min(cnt+1,s+1)):
            d[i][j] = d[i-1][j]
            if j >= a[i]:
                d[i][j] += d[i-1][j-a[i]]
            d[i][j] = d[i][j]%mod
    mns = d[-1][w//2]
if w%2 == 0:
    s -= 1
cnt = 0
for i in range(s,w+1):
    cnt += dp[-1][i]
    cnt = cnt%mod

res = (pow(3,n,mod)-cnt*3)%mod

if w % 2 == 0:
    res = (res+mns*3)%mod
print(res)
# Original solution
N = int(eval(input()))
A = [int(eval(input())) for _ in range(N)]

sum_A = sum(A)
MOD = 998244353

dp1 = [0] * (sum_A + 1)
dp2 = [0] * (sum_A + 1)
dp1[0] = dp2[0] = 1


for a in A:
    dp1_ = [0] * (sum_A + 1)
    dp2_ = [0] * (sum_A + 1)
    for i in range(sum_A + 1):
        if i - a >= 0:
            # R に塗れる場合
            dp1_[i] = (dp1[i - a] + dp1[i] * 2) % MOD
            dp2_[i] = (dp2[i - a] + dp2[i]) % MOD
        else:
            dp1_[i] = (dp1[i] * 2) % MOD
            dp2_[i] = dp2[i]
    dp1, dp2 = dp1_, dp2_


ans = pow(3, N, MOD)
for i in range(sum_A + 1):
    if i * 2 >= sum_A:
        ans = (ans - dp1[i] * 3 + MOD * 3) % MOD
    if i * 2 == sum_A:
        ans = (ans + dp2[i] * 3) % MOD
print(ans)


# Optimized solution
N = int(eval(input()))
A = [int(eval(input())) for _ in range(N)]

sum_A = sum(A)
MOD = 998244353

dp1 = [0] * (sum_A + 1)
dp2 = [0] * (sum_A + 1)
dp1[0] = dp2[0] = 1


for a in A:
    for i in reversed(list(range(sum_A + 1))):
        if i - a >= 0:
            # R に塗れる場合
            dp1[i] = (dp1[i - a] + dp1[i] * 2) % MOD
            dp2[i] = (dp2[i - a] + dp2[i]) % MOD
        else:
            dp1[i] = (dp1[i] * 2) % MOD
            dp2[i] = dp2[i]


ans = pow(3, N, MOD)
for i in range(sum_A + 1):
    if i * 2 >= sum_A:
        ans = (ans - dp1[i] * 3 + MOD * 3) % MOD
    if i * 2 == sum_A:
        ans = (ans + dp2[i] * 3) % MOD
print(ans)
# Original solution
N = int(eval(input()))
A = [int(eval(input())) for _ in range(N)]

sum_A = sum(A)
MOD = 998244353

dp1 = [0] * (sum_A + 1)
dp2 = [0] * (sum_A + 1)
dp1[0] = dp2[0] = 1


for a in A:
    for i in reversed(list(range(sum_A + 1))):
        if i - a >= 0:
            # R に塗れる場合
            dp1[i] = (dp1[i - a] + dp1[i] * 2) % MOD
            dp2[i] = (dp2[i - a] + dp2[i]) % MOD
        else:
            dp1[i] = (dp1[i] * 2) % MOD
            dp2[i] = dp2[i]


ans = pow(3, N, MOD)
for i in range(sum_A + 1):
    if i * 2 >= sum_A:
        ans = (ans - dp1[i] * 3 + MOD * 3) % MOD
    if i * 2 == sum_A:
        ans = (ans + dp2[i] * 3) % MOD
print(ans)


# Optimized solution
N = int(eval(input()))
A = [int(eval(input())) for _ in range(N)]

sum_A = sum(A)
MOD = 998244353

dp1 = [0] * (sum_A + 1)
dp2 = [0] * (sum_A + 1)
dp1[0] = dp2[0] = 1
tmp_sum = 0

for a in A:
    tmp_sum += a
    for i in reversed(list(range(tmp_sum + 1))):
        if i - a >= 0:
            # R に塗れる場合
            dp1[i] = (dp1[i - a] + dp1[i] * 2) % MOD
            dp2[i] = (dp2[i - a] + dp2[i]) % MOD
        else:
            dp1[i] = (dp1[i] * 2) % MOD
            dp2[i] = dp2[i]


ans = pow(3, N, MOD)
for i in range(sum_A + 1):
    if i * 2 >= sum_A:
        ans = (ans - dp1[i] * 3 + MOD * 3) % MOD
    if i * 2 == sum_A:
        ans = (ans + dp2[i] * 3) % MOD
print(ans)
# Original solution
MOD = 998244353

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

total = sum(a)
sup = (total - 1) // 2

# total > 2 * max(R,G,B)
# を満たすR,G,Bの場合の数
# (total - 1) // 2 >= max(R,G,B)

dp = [[[0 for _ in range(total + 1)] for _ in range(total + 1)] for _ in range(N + 1)]
dp[0][0][0] = 1
# dp[i][R][G]:=i番目まででRGとなる総数

# 枝刈り
# sup = (total - 1) // 2
# sup >= max(R,G,B)
# supを超えるRGBはdp遷移時にカット

for i in range(N):
    # a[i]はRGBのいずれかに加算
    for s in range(2 * sup + 1):
        for r in range(a[i], min(s, sup) + 1):
            g = s - r
            dp[i + 1][r][g] += dp[i][r - a[i]][g]
            dp[i + 1][r][g] %= MOD
        for g in range(a[i], min(s, sup) + 1):
            r = s - g
            dp[i + 1][r][g] += dp[i][r][g - a[i]]
            dp[i + 1][r][g] %= MOD
        for r in range(min(s, sup) + 1):
            g = s - r
            dp[i + 1][r][g] += dp[i][r][g]
            dp[i + 1][r][g] %= MOD
            # Bに対応

ans = sum(dp[N][r][g] for r in range(sup + 1) for g in range(sup + 1) if total - r - g <= sup)
ans %= MOD
print(ans)


# Optimized solution
# https://atcoder.jp/contests/tenka1-2019/submissions/5065329

import sys

input = sys.stdin.readline

N = int(eval(input()))
a = [int(eval(input())) for _ in range(N)]
total = sum(a)
MOD = 998244353

'''(1)全体'''
U = pow(3, N, MOD)  # 三角形を構成できない場合を含むRGBの組み合わせ総数

'''(2)単円'''
dp = [[0] * (total + 1) for _ in range(N + 1)]
dp[0][0] = 1
# dp[i][R]:=i番目まででRとなる場合の数

for i in range(N):
    for r in range(total + 1):
        if r - a[i] >= 0:
            dp[i + 1][r] += dp[i][r - a[i]]
        dp[i + 1][r] += 2 * dp[i][r]
        # g, bに加算する分で、2回起こる
# print(dp)

single_circle = 0
for r in range(total + 1):
    if r >= (total / 2):
        single_circle += dp[N][r]
# print(single_circle)

'''(3)２円の積集合'''
if total % 2 == 0:
    dp2 = [[0] * (total + 1) for _ in range(N + 1)]
    dp2[0][0] = 1
    # dp[i][R]:=i番目まででRとなる場合の数

    for i in range(N):
        for r in range(int(total / 2) + 1):
            if r - a[i] >= 0:
                dp2[i + 1][r] += dp2[i][r - a[i]]
            dp2[i + 1][r] += dp2[i][r]
    # print(dp2)

two_circle_intersect = dp2[N][int(total / 2)] if total % 2 == 0 else 0

'''(3)３円の積集合'''
three_circle_intersect = 0

'''(4)解答'''
ans = 0

ans += U
ans %= MOD

ans -= 3 * single_circle
ans %= MOD

ans += 3 * two_circle_intersect
ans %= MOD

ans -= three_circle_intersect
ans %= MOD

print(ans)