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

from collections import deque
n, q = map(int, input().split())
g = [[] for i in range(n)]
k = []
for i in range(n-1):
  a,b = map(int, input().split())
  g[a-1].append(b-1)
  g[b-1].append(a-1)
for i in range(q):
  a,b = map(int, input().split())
  k.append([a-1,b])
m = [-1]*n
m[0] = 0
q = deque()
q.append(0)
while len(q):
  d = q.popleft()
  for i in g[d]:
    if m[i] == -1:
      m[i] = m[d]+1
      q.append(i)
ans = [0]*n
for i,j in k:
  t = m[i]
  for x,y in enumerate(m):
    if i == x or t < y:
      ans[x]+=j
print(' '.join(map(str,ans)))


### FIXED CODE ###

from collections import deque
n, q = map(int, input().split())
g = [[] for i in range(n)]
k = []
for i in range(n-1):
  a,b = map(int, input().split())
  g[a-1].append(b-1)
  g[b-1].append(a-1)
for i in range(q):
  a,b = map(int, input().split())
  k.append([a-1,b])
m = [-1]*n
m[0] = 0
m1 = [-1]*n
m1[0] = 0
q = deque()
q.append(0)
while len(q):
  d = q.popleft()
  for i in g[d]:
    if m[i] == -1:
      m[i] = m[d]+1
    if m1[i] == -1:
      m1[i] = d
      q.append(i)
kyori = [[] for i in range(max(m)+1)]
for i,j in enumerate(m):
  kyori[j].append(i)
ans= [0]*n
for i,j in k:
  ans[i]+=j
for i in kyori[1:]:
  for j in i:
    ans[j] = ans[j] + ans[m1[j]]
print(' '.join(map(str,ans)))
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
INF = 10**12

class Rmin():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1 << (size.bit_length())
		self.node = [INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)>>1
			self.node[x] = min(self.node[(x<<1)+1], self.node[(x<<1)+2])
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = INF
		while L<R:
			if R & 1:
				R -= 1
				s = min(s, self.node[R-1])
			if L & 1:
				s = min(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

n, q, a, b, *qs = map(int, read().split())
dp_l, dp_r = Rmin(n+1), Rmin(n+1)
dp_l.Update(b, -b)
dp_r.Update(b, b)

total_diff = 0
x = a
for y in qs:
	diff = abs(y - x)
	l_min = dp_l.Get(1, y)
	r_min = dp_r.Get(y, n+1)
	res = min(l_min + y, r_min - y)
	dp_l.Update(x, res - diff - x)
	dp_r.Update(x, res - diff + x)
	total_diff += diff
	x = y

N = dp_l.n
print(total_diff + min((l+r)>>1 for l, r in zip(dp_l.node[N:], dp_r.node[N:])))

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
INF = 10**12

class Rmin():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1 << (size.bit_length())
		self.node = [INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)>>1
			self.node[x] = min(self.node[(x<<1)+1], self.node[(x<<1)+2])
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = INF
		while L<R:
			if R & 1:
				R -= 1
				s = min(s, self.node[R-1])
			if L & 1:
				s = min(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

n, q, a, b, *qs = map(int, read().split())
dp_l, dp_r = Rmin(n+1), Rmin(n+1)
dp_l.Update(b, -b)
dp_r.Update(b, b)

total_diff = 0
x = a
for y in qs:
	diff = abs(y - x)
	l_min = dp_l.Get(1, y)
	r_min = dp_r.Get(y, n+1)
	res = min(l_min + y, r_min - y)
	dp_l.Update(x, res - diff - x)
	dp_r.Update(x, res - diff + x)
	total_diff += diff
	x = y

N = dp_l.n
print(total_diff + min((l+r)>>1 for l, r in zip(dp_l.node[N:], dp_r.node[N:])))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    N = int(input())
    S = input().rstrip()
    tmp = set()
    second = list()
    ans = 0
    for index, i in enumerate(range(N-2)):
        for j in range(index+1, N-1):
            if S[i] + S[j] not in tmp:
                tmp.add(S[i] + S[j])
                second.append(int(j))

    for k in second:
        ans += len(set(list(S[k+1:])))
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    N = int(input())
    S = input().rstrip()
    ans = 0
    for i in range(1000):
        i = str(i).zfill(3)
        prev = -1
        for s in i:
            pos = S.find(s, prev + 1)
            if pos > prev:
                prev = pos
            else:
                break
        else:
            ans += 1
    print(ans)


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

from collections import defaultdict
n=int(input())
dic=defaultdict(int)
for i in range(n):
    dic[input()]+=1
max_kv_list=[k for k,v in dic.items() if v==max(dic.values())]
max_kv_list.sort()
for i in range(len(max_kv_list)):
    print(max_kv_list[i])


### FIXED CODE ###

from collections import defaultdict
import sys

def main():
    input = sys.stdin.readline
    n=int(input())
    dic=defaultdict(int)
    st=set([])
    for i in range(n):
        s=input().strip('\n')
        st.add(s)
        dic[s]+=1
    maxv=max(dic.values())
    l=sorted(st)
    for i in range(len(l)):
        if dic[l[i]]==maxv:
            print(l[i])
        
    

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

def main():
    import sys 
    input = sys.stdin.readline
    from heapq import heappop,heappush

    def prim():
        used = [True]*n
        edgelist = []
        for e in edge[0]:
            heappush(edgelist,e)
        used[0] = False
        res = 0
        while len(edgelist) != 0:
            short_edge = heappop(edgelist)
            if not used[short_edge[1]]:
                continue
            v = short_edge[1]
            used[v] = False
            for e in edge[v]:
                if used[e[1]]:
                    heappush(edgelist,e)
            res += short_edge[0]
        return res

    n = int(input())
    A = [list(map(int,input().split()))+[i] for i in range(n)]
    A.append([-10**12,-10**12,-1])
    A.append([10**12,10**12,-1])
    X = sorted(A)
    Y = sorted(A,key = lambda x:x[1])
    d = []
    for i in range(1,n+1):
        sx = X[i-1][0]
        sy = Y[i-1][1]
        mx = X[i][0]
        my = Y[i][1]
        lx = X[i+1][0]
        ly = Y[i+1][1]
        nsx = X[i-1][2]
        nsy = Y[i-1][2]
        nmx = X[i][2]
        nmy = Y[i][2]
        nlx = X[i+1][2]
        nly = Y[i+1][2]
        i -= 1
        d.append((nsx,nmx,mx-sx))
        d.append((nmx,nlx,lx-mx))
        d.append((nsy,nmy,my-sy))
        d.append((nmy,nly,ly-my))

    edge = [[] for i in range(n)]
    for x,y,z in d:
        if x==-1 or y==-1:
            continue
        edge[x].append([z,y])
        edge[y].append([z,x])

    print(prim())

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys 
    input = sys.stdin.readline
    from heapq import heappop,heappush
    from operator import itemgetter
    
    def prim():
        used = [True]*n
        edgelist = []
        for e in edge[0]:
            heappush(edgelist,e)
        used[0] = False
        res = 0
        while len(edgelist) != 0:
            short_edge = heappop(edgelist)
            if not used[short_edge[1]]:
                continue
            v = short_edge[1]
            used[v] = False
            for e in edge[v]:
                if used[e[1]]:
                    heappush(edgelist,e)
            res += short_edge[0]
        return res

    n = int(input())
    A = [list(map(int,input().split()))+[i] for i in range(n)]
    A.append([-10**12,-10**12,-1])
    A.append([10**12,10**12,-1])
    X = sorted(A)
    Y = sorted(A,key = itemgetter(1))
    edge = [[] for i in range(n)]
    for i in range(1,n+1):
        sx = X[i-1][0]
        sy = Y[i-1][1]
        mx = X[i][0]
        my = Y[i][1]
        lx = X[i+1][0]
        ly = Y[i+1][1]
        nsx = X[i-1][2]
        nsy = Y[i-1][2]
        nmx = X[i][2]
        nmy = Y[i][2]
        nlx = X[i+1][2]
        nly = Y[i+1][2]
        edge[nsx].append((mx-sx,nmx))
        edge[nmx].append((mx-sx,nsx))
        edge[nlx].append((lx-mx,nmx))
        edge[nmx].append((lx-mx,nlx))
        edge[nsy].append((my-sy,nmy))
        edge[nmy].append((my-sy,nsy))
        edge[nly].append((ly-my,nmy))
        edge[nmy].append((ly-my,nly))

    print(prim()) 

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

from collections import deque
from copy import deepcopy

N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[set() for _ in range(N)]
d=[set() for _ in range(N)] # 隣接リスト
e=[-1 for _ in range(N)] #訪問ずみかどうか
g=[[ 0 for _ in range(N)] for _ in range(N)]

for i in range(N-1):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1].add(b[i]-1)
    d[b[i]-1].add(a[i]-1)
f=deepcopy(d)
#print(f)

#x=0としてBFSする
v=deque([0])
e[0]=0

maxi=0
while len(v)>0:
  k=v.popleft()
  maxi=max(maxi,len(d[k]))
  all=set(i+1 for i in range(len(d[k])))
  pos=deepcopy(all)
  pos -= c[k]
  for item in d[k]:
    if e[item]==-1:
      s=min(pos)
      c[k].add(s)
      c[item].add(s)
      pos.remove(s)
      e[item] = e[k]+1
      v.append(item)
      g[k][item]=s
      g[item][k]=s
      
print(maxi)
for i in range(N-1):
  print( g[a[i]-1][b[i]-1] )


### FIXED CODE ###

from collections import deque

N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[set() for _ in range(N)] # 使用している色
d=[set() for _ in range(N)] # 隣接リスト
e=[ False for _ in range(N)] #訪問ずみかどうか
f=[0]*N  #答え
for i in range(N-1):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1].add(b[i]-1)
    d[b[i]-1].add(a[i]-1)

maxi=max([len(d[i]) for i in range(N-1)])
print(maxi)
#print("c:",c)
#print("d",d)
#print("e",e)

#x=0としてBFSする

v=deque([0])
e[0]=True
color=1

while v:
  p = v.popleft()
  for q in d[p]:
    if e[q]==False:
      while color in c[p]:
        color +=1
        if color>maxi:
          color=1
      c[p].add(color)
      c[q].add(color)
      f[q]=color
      e[q]=True
      v.append(q)
      
for i in range(N-1):
  print( f[b[i]-1])
### BUGGY CODE ###

n,y = map(int,input().split())
p = 0
for i in range(n+1):
    for j in range(n+1):
        for k in range(n+1):
            if 1000*i+5000*j+10000*k == y:
                if i+j+k == n:
                    print(k,j,i)
                    p += 1
                    break
    if p == 1:
        break
            
    
if p == 0:
    print("-1 -1 -1")
    

### FIXED CODE ###

n,y = map(int,input().split())
p = 0
for i in range(n+1):
    for j in range(n+1):
        k = (n-i-j)
        if k < 0:
            k = 0
        if 1000*i+5000*j+10000*k == y:
            if i+j+k == n:
                print(k,j,i)
                p += 1
                break       
    if p == 1:
        break
            
    
if p == 0:
    print("-1 -1 -1")
### BUGGY CODE ###

N, M, K = map( int, input().split() )
friends = [ set() for _ in range( N + 1 ) ]

for i in range( M ):
  a, b = map( int, input().split())
  friends[ a ].add( b )
  friends[ b ].add( a )

friends_chain = []

sets = set( range( 1, N + 1) )

while sets != set():
  i = sets.pop()
  lists = [ i ]
  chain = { i }
  while lists != []:
    j = lists.pop()
    lists += list( friends[ j ] - chain )
    chain |=  friends[ j ]
  friends_chain.append( chain )
  sets -= chain

block = [ set() for _ in range( N + 1 )]
for i in range( K ):
  c, d = map( int, input().split() )
  block[ c ].add( d )
  block[ d ].add( c )

ans=""
for i in range( 1, N + 1 ):
    for u in friends_chain:
        if i in u:
            ans += str( len( u - friends[i] - block[i] - { i } ))
            break
    if i != N:
      ans += " "
print( ans )
    

### FIXED CODE ###

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

class UnionFind():
    def __init__( self, n ):
        self.n = n
        self.parents = [ - 1 ] * n
        
    def find( self, x ):
        if self.parents[ x ] < 0:
            return x
        else:
            self.parents[ x ] = self.find( self.parents[ x ] )
            return self.parents[ x ]

    def union( self, x, y ):
        x = self.find( x )
        y = self.find( y )
        if x == y:
            return
        if self.parents[ x ] > self.parents[ y ]:
            x, y = y, x
        self.parents[ x ] += self.parents[ y ]
        self.parents[ y ] = x
        
    def size( self, x ):
      return -self.parents[ self.find( x ) ]
        
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def same( self, x, y ):
      return self.find( x ) == self.find( y )

uf = UnionFind( N + 1 )
not_use = [ 0 ] * ( N + 1 )
for i in range( M ):
  a, b = map( int, input().split() )
  uf.union( a, b )
  not_use[ a ] += 1
  not_use[ b ] += 1

block = [ [] for _ in range( N + 1 ) ]
for i in range( K ):
  c, d = map( int, input().split() )
  if uf.same( c, d ):
    not_use[ c ] += 1
    not_use[ d ] += 1

ans = str( uf.size( 1 ) - not_use[ 1 ] - 1 )
for i in range( 2, N + 1 ):
  ans += " " + str( uf.size( i ) - not_use[ i ] - 1 )
print( ans )
### BUGGY CODE ###

a,b,x = map(int,input().split())
ans = 0
while a <= b:
  if a%x == 0:
    ans += 1
  a+= 1
print(ans)

### FIXED CODE ###

a,b,x = map(int,input().split())
d = b//x
if a%x == 0:
  e = a//x
else:
  e = a//x + 1
print(d-e+1)
### BUGGY CODE ###

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

Z = [j for j, s in enumerate(S) if (j > 0 and s == 0 and S[j] != S[j-1]) or (j == 0 and s == 0)] + [N]
Y = [j for j, s in enumerate(S) if (j > 0 and s == 1 and S[j] != S[j-1]) or (j == 0 and s == 1)] + [N]
result = 0
if len(Z) <= K:
    print(N)
else:
    for i in range(len(Z)-K):
        if i == 0:
            result = Z[i+K]
        else:
            result = max(result, Z[i+K] - max([y for y in Y if y <= Z[i]]))
    print(result)

### FIXED CODE ###

N, K = map(int, input().split())
S = list(map(int, input()))
 
Z = [j for j, s in enumerate(S) if (j > 0 and s == 0 and S[j] != S[j-1]) or (j == 0 and s == 0)] + [N]
Y = [j for j, s in enumerate(S) if (j > 0 and s == 1 and S[j] != S[j-1]) or (j == 0 and s == 1)]
result = 0
if len(Z) <= K:
    print(N)
else:
    for i in range(len(Z)-K):
        if i == 0:
            result = Z[i+K]
        else:
            result = max(result, Z[i+K] - Y[i if Y[0] < Z[0] else i-1])
    print(result)
### BUGGY CODE ###

k = int(input())
s = input()
len_s = len(s)
MOD = 1000000007

pow26_i = pow(26, k, MOD)
inv_26 = pow(26, -1, MOD)
pow25_i = 1
comb_i = 1

a = 0
for i in range(k + 1):  
  a += (comb_i  * pow26_i* pow25_i ) % MOD
  a %= MOD
  
  pow26_i = (pow26_i * inv_26) % MOD
  pow25_i = (pow25_i * 25) % MOD
  comb_i = (comb_i * (len_s + i) * pow(i + 1, -1, MOD)) % MOD


print(a)

### FIXED CODE ###

k = int(input())
s = input()
len_s = len(s)
MOD = 1000000007

x_i = pow(26, k, MOD)
r = (25 * pow(26, -1, MOD)) % MOD
comb_i = 1

a = 0
for i in range(k + 1):  
  a += (comb_i  * x_i  ) % MOD
  a %= MOD
  
  x_i  = (x_i  * r) % MOD
  comb_i = (comb_i * (len_s + i) * pow(i + 1, -1, MOD)) % MOD


print(a)
### BUGGY CODE ###

# coding: utf-8
s = list(input())
c = 0
b = 100
flag = 1
while flag == 1:
    flag = 0
    for i, n in enumerate(s):
        if (b == "0" and n == "1") or (b == "1" and n == "0"):
            c += 2
            b = 2
            flag = 1
            break
        else:
            b = n
    if flag == 1:
        for j in range(2):
            del s[i-1]
print(c)

### FIXED CODE ###

# coding: utf-8
s = list(input())
zero = s.count("0")
one = s.count("1")
print(min(zero,one)*2)
### BUGGY CODE ###

A,B,N= map(int,input().split())


floor_num=[]
   
for x in range(0,N+1):

    floor_num.append(int(A*x/B)-A*int(x/B))

if N >=B:
    floor_num.append(int(A*(B-1)/B))

print(max(floor_num))


### FIXED CODE ###

A,B,N= map(int,input().split())


floor_num=[]

if N >=B:
    floor_num.append(int(A*(B-1)/B))
else:  

        floor_num.append(int(A*N/B))


print(max(floor_num))
### BUGGY CODE ###

root=[]
n,k = map(int,input().split())
for i in range(k):
    x,y = map(int,input().split())
    root.append([x,y])

toori=[0]*(2*10**5)+[0]*n+[0]*(2*10**5)
toori[2*10**5]=1
cum=[0]*k
for a,i in enumerate (root):
    s=0
    for j in range (i[0],i[1]+1):
        s+=toori[2*10**5+1-j]
    cum[a]=s
aaa=sum(cum)
toori[2*10**5+1]+=aaa


for now in range(2,n):#nowが今の場所
    hueru=0
    for a,i in enumerate (root):
        hueru+=(toori[2*10**5+now-i[0]] - toori[2*10**5+now-1-i[1]])
    aaa+=hueru
    toori[2*10**5+now]+=aaa
    toori[2*10**5+n-1]%=998244353
    


print(toori[2*10**5+n-1]%998244353)

### FIXED CODE ###

root=[]
n,k = map(int,input().split())
for i in range(k):
    x,y = map(int,input().split())
    root.append([x,y])

toori=[0]*(2*10**5)+[0]*n+[0]*(2*10**5)
toori[2*10**5]=1
cum=[0]*k
for a,i in enumerate (root):
    s=0
    for j in range (i[0],i[1]+1):
        s+=toori[2*10**5+1-j]
    cum[a]=s
aaa=sum(cum)%998244353
toori[2*10**5+1]+=aaa


for now in range(2,n):#nowが今の場所
    hueru=0
    for a,i in enumerate (root):
        hueru+=(toori[2*10**5+now-i[0]] - toori[2*10**5+now-1-i[1]])
    aaa+=hueru
    aaa%=998244353
    toori[2*10**5+now]+=aaa
    toori[2*10**5+now]%=998244353
    


print(toori[2*10**5+n-1]%998244353)
### BUGGY CODE ###

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

ans_lst = [float("inf")]*(N)
for i in range(0,N):
    ans_lst[i] = S[:i].count("W") + S[i+1:].count("E")
ans = min(ans_lst)
print(ans)

### FIXED CODE ###

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

lst = [0]*N
Re = S.count("E")
Lw = 0

for i in range(N):
    if S[i] == "E":
        Re -= 1
        lst[i] = Re + Lw
    else:
        Lw += 1
        lst[i] = Re + Lw - 1

ans = min(lst)
print(ans)
### BUGGY CODE ###

from collections import deque
INF = int(1e9) + 7
h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
d = [[INF] * w for i in range(h)]
dx = [1,0]
dy = [0,1]
if s[0][0] == '#':
    d[0][0] = 1
else:
    d[0][0] = 0
que = deque([(0, 0)])

while len(que) != 0:
    val = que.popleft()

    for i in range(2):
        nx = val[0] + dx[i]
        ny = (val[1] + dy[i])
        if nx < h and ny < w:

            que.append((nx, ny))
            if (s[nx][ny] == '#') and (d[nx][ny] > d[val[0]][val[1]]):
                d[nx][ny] = d[val[0]][val[1]] + 1
            elif s[nx][ny] != '#' and d[nx][ny] < d[val[0]][val[1]]:
                d[nx][ny] = d[nx][ny]

            else:
                d[nx][ny] = d[val[0]][val[1]]
print(d[h-1][w-1])


### FIXED CODE ###

INF = int(1e9) + 7
h, w = map(int, input().split())
s = []
for i in range(h):
    s.append(list(input()))

dp = [[INF] * w for i in range(h)]
if s[0][0] == '#':
    dp[0][0] = 1
else:
    dp[0][0] = 0
#print(dp)

for i in range(h):
    for j in range(w):
        if i == 0 and j == 0:
            continue
        val1 = dp[i-1][j]
        if s[i][j] == '#' and s[i-1][j] == '.':
            val1 += 1
        val2 = dp[i][j-1]
        if s[i][j] == '#' and s[i][j-1] == '.':
            val2 += 1
        dp[i][j] = min(val1, val2)
        #print(i, j,val1, val2)
print(dp[h-1][w-1])
#print(dp)
### BUGGY CODE ###


def dp_table(*counts):  # dp[x][y]を作りたかったら dp_table(xのサイズ,yのサイズ)
    if counts:
        return [dp_table(*counts[1:]) for _ in range(counts[0])]
    else:
        return 0


def main():

    N = int(input())
    A = [int(input()) for i in range(N)]
    mod = 998244353
    ans = pow(3, N, mod)
    sum_A = sum(A)
    dp = dp_table(N, sum_A + 1)
    # dp[i][j]: i番目までの中から辺をいくつか選んで、長さがjになるパターン数

    # init
    dp[0][A[0]] = 1
    dp[0][0] = 2  # 他の色のうちどちらに入れるかで2通り

    # init2
    dp2 = dp_table(N, sum_A+1)  # ある二色でsum_Aを等分するパターンを数える
    dp2[0][A[0]] = 1
    dp2[0][0] = 1  # 今度は片方に集中したパターン

    # dp
    for i in range(1, N):
        for length in range(0, sum_A + 1):
            # A[i]を追加しないのなら他の２食のうちどちらに入れるかで2倍選択肢がある
            if length >= A[i]:
                dp[i][length] = dp[i - 1][length - A[i]] + dp[i - 1][length] * 2
            else:
                dp[i][length] = dp[i-1][length]*2
            dp[i][length] %= mod
        for length in range(sum_A//2+1):
            if length >= A[i]:
                dp2[i][length] = dp2[i - 1][length - A[i]] + dp2[i - 1][length]
            else:
                dp2[i][length] = dp2[i-1][length]
            dp2[i][length] %= mod
    # print(sum(dp[N-1][sum_A//2]))
    # print(dp)
    ans -= 3*sum(dp[N-1][(sum_A+1)//2:])
    if sum_A % 2 == 0:
        ans += 3*dp2[N-1][sum_A//2]
    print(ans % mod)


if __name__ == '__main__':
    main()


### FIXED CODE ###


def dp_table(*counts):  # dp[x][y]を作りたかったら dp_table(xのサイズ,yのサイズ)
    if counts:
        return [dp_table(*counts[1:]) for _ in range(counts[0])]
    else:
        return 0


def main():

    N = int(input())
    A = [int(input()) for _ in range(N)]
    mod = 998244353
    ans = pow(3, N, mod)
    sum_A = sum(A)
    dp = [[0] * (sum_A+1) for i in range(N)]
    # dp[i][j]: i番目までの中から辺をいくつか選んで、長さがjになるパターン数

    # init
    dp[0][A[0]] = 1
    dp[0][0] = 2  # 他の色のうちどちらに入れるかで2通り

    # init2
    dp2 = [[0] * (sum_A+1) for i in range(N)]  # ある二色でsum_Aを等分するパターンを数える
    dp2[0][A[0]] = 1
    dp2[0][0] = 1  # 今度は片方に集中したパターン

    # dp
    sum_now = A[0]
    for i in range(1, N):
        a = A[i]
        sum_now += a
        for length in range(sum_now+1):
            # A[i]を追加しないのなら他の２食のうちどちらに入れるかで2倍選択肢がある
            if length >= a:
                dp[i][length] = dp[i - 1][length - a] + \
                    (dp[i - 1][length] << 1)
            else:
                dp[i][length] = dp[i-1][length] << 1
            dp[i][length] %= mod

        for length in range(min(sum_now + 1, sum_A // 2 + 1)):
            if length >= a:
                dp2[i][length] = dp2[i - 1][length - a] + dp2[i - 1][length]
            else:
                dp2[i][length] = dp2[i-1][length]
            dp2[i][length] %= mod
    # print(sum(dp[N-1][sum_A//2]))
    # print(dp)
    ans -= 3*sum(dp[N-1][(sum_A+1)//2:])
    if sum_A % 2 == 0:
        ans += 3*dp2[N-1][sum_A//2]
    print(ans % mod)


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

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

ans = 0
for i in range(N):
    for j in range(i+1, N+1):
#         print(a[i:j])
        if sum(a[i:j]) >= 0:
            ans += 1
            
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
a = []
for _ in range(N):
    a.append(int(input())-K)
    
su = 0
v = [(0, 0)]
for i in range(N):
    su += a[i]
    v.append((su, i+1))
v = sorted(v)

data = [0]*(N+5)

def sumation(i):
    s = 0
    while i > 0:
        s += data[i]
        i -= i & -i
    return s
    
def add(i, x):
    while i <= N+2:
        data[i] += x
        i += i & -i
ans = 0
for e, i in v:
    ans += sumation(i+1)
    add(i+1, 1)
    
print(ans)
### BUGGY CODE ###

s=str(input())
n=len(s)
k=[0]*(n+1)
for i in range (1,n+1):
    k[i]=int(s[i-1])
t=[0]*(n+1)
t[0]=0  
for i in range(1,n+1):
    t[i]=(10*t[i-1]+k[i])%2019

p=1
q=[0]*200000
for z in range(0,200000):
    q[z]=p%2019
    p=10*q[z]

d=0    
for j in range(n+1):
    for l in range (j):
        f=j-l
        if (t[l]*q[f]-t[j])%2019==0:
            d+=1
            
print(d)


### FIXED CODE ###

s=str(input())
n=len(s)
k=[0]*(n+1)
for i in range (1,n+1):
    k[i]=int(s[i-1])
t=[0]*(n+1)
t[0]=0  
for i in range(1,n+1):
    t[i]=(10*t[i-1]+k[i])%2019

p=1
q=[0]*448
for z in range(0,448):
    q[z]=p%2019
    p=10*q[z]

d=[0]*n   
for j in range(1,n+1):
    f=(n-j)%448
    d[j-1]=q[f]*t[j]%2019
ds=sorted(d)
ct=0
ans=0
if ds[0]==0:
    ct=1
    ans=1
for i in range(n-1):
    if ds[i+1]==ds[i]:
        ct+=1
        ans+=ct
    else:
        ct=0
print(ans)
### BUGGY CODE ###

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

ans = 0

for i in range(N-2):
    for j in range(i+1, N-1):
        if len(set([S[i], S[j]])) == 2:
            sk = list({"R", "G", "B"} - set([S[i], S[j]]))[0]
            if 2*j - i < N and S[2*j - i] == sk:
                ans += S[j+1:].count(sk) - 1
            else:
                ans += S[j+1:].count(sk)

print(ans)


### FIXED CODE ###

N = int(input())
S = input()
ans = S.count("R") * S.count("G") * S.count("B")

for i in range(N-2):
    for d in range(1, (N-i-1)//2+1):
        if {S[i], S[i+d], S[i+2*d]} == {"R", "G", "B"}:
            ans -= 1

print(ans)