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

h,w=map(int,input().split())
m=[[None for j in range(w)] for i in range(h)]
c=[[-1 for j in range(w)] for i in range(h)]
for i in range(h):
    s=input()
    for j in range(w):
        if s[j]==".":
            m[i][j]=0
        else:
            m[i][j]=1

for i in range(h):
    j=0
    start=-1
    while(j<w):
        if start==-1:
            if m[i][j]==0:
                start=j
                count=1
        else:
            if m[i][j]==1:
                for k in range(start,j):
                    c[i][k]+=count
                start=-1
            else:
                count+=1
        j+=1
    if start!=-1:
        for k in range(start,w):
            c[i][k]+=count
for j in range(w):
    i=0
    start=-1
    while(i<h):
        if start==-1:
            if m[i][j]==0:
                start=i
                count=1
        else:
            if m[i][j]==1:
                for k in range(start,i):
                    c[k][j]+=count
                start=-1
            else:
                count+=1
        i+=1
    if start!=-1:
        for k in range(start,h):
            c[k][j]+=count
result=0
for i in range(h):
    for j in range(w):
        result=max(result,c[i][j])
print(result)

### FIXED CODE ###

h,w=map(int,input().split())
m=[[None for j in range(w)] for i in range(h)]
c=[[-1 for j in range(w)] for i in range(h)]
for i in range(h):
    s=input()
    for j in range(w):
        if s[j]==".":
            m[i][j]=0
        else:
            m[i][j]=1

for i in range(h):
    j=0
    start=-1
    while(j<w):
        if start==-1:
            if m[i][j]==0:
                start=j
                count=1
        else:
            if m[i][j]==1:
                for k in range(start,j):
                    c[i][k]+=count
                start=-1
            else:
                count+=1
        j+=1
    if start!=-1:
        for k in range(start,w):
            c[i][k]+=count
for j in range(w):
    i=0
    start=-1
    while(i<h):
        if start==-1:
            if m[i][j]==0:
                start=i
                count=1
        else:
            if m[i][j]==1:
                for k in range(start,i):
                    c[k][j]+=count
                start=-1
            else:
                count+=1
        i+=1
    if start!=-1:
        for k in range(start,h):
            c[k][j]+=count
result=0
for i in range(h):
    for j in range(w):
        result=max(result,c[i][j])
print(result)
### BUGGY CODE ###

N = int(input())
texts = []
for i in range(N):
    texts.append((input()))
    
import collections

counters = []
count_dict = {}
count = 0
for text in texts:
    text_list = list(text)
    text_list.sort()
    text = "".join(text_list) 
    
    c = collections.Counter(text)
    name = str(c)
    if c in counters:
        count_dict[name] += 1
        
        
    else:
        count_dict[name] = 1
        counters.append(c)

anss = []
for v in count_dict.values():
    ans = v * (v-1) / 2
    anss.append(ans)
    
print(int(sum(anss)))

### FIXED CODE ###

N = int(input())
texts = []
for i in range(N):
    texts.append((input()))

import collections
counters = []
count = 0
for text in texts:
    text_list = list(text)
    text_list.sort()
    text = "".join(text_list) 
    c = collections.Counter(text)
    counters.append(c)



ccccc = []
anss = []
for ccc in counters:
    ccc = str(ccc)
    ccccc.append(ccc)
    

dd = collections.Counter(ccccc)
for v in dd.values():
    ans = v * (v-1) / 2
    anss.append(ans)
    
print(int(sum(anss)))
### BUGGY CODE ###

N = input()
A = {int(x) for x in input().split()}

while True:
    if len(A) == 1:
        break
    mn = min(A)
    A = {x for x in A if x % mn != 0 or x == mn}

print(A.pop())

### FIXED CODE ###

N = input()
A = {int(x) for x in input().split()}

while True:
    if len(A) == 1:
        break
    tmp = list(A)
    mn = min(tmp)
    for idx in range(len(tmp)):
        if tmp[idx] != mn:
            tmp[idx] = tmp[idx] % mn if tmp[idx] % mn != 0 else mn
    A = set(tmp)

print(A.pop())
### BUGGY CODE ###

N,C = map(int,input().split())
d = [list(map(int,input().split())) for _ in range(C)]
c = [list(map(int,input().split())) for _ in range(N)]
ans = 1e9
for c_1 in range(C):
    for c_2 in range(C):
        for c_3 in range(C):
            if c_1==c_2 or c_1==c_3 or c_2==c_3:
                continue
            c_list = [c_1,c_2,c_3]
            k = 0
            for i in range(N):
                for j in range(N):
                    if not c[i][j]==c_list[(i+j)%3]:
                        k += d[c[i][j]-1][c_list[(i+j)%3]-1]
            ans = min(ans,k)
print(ans)

### FIXED CODE ###

N,C = map(int,input().split())
d = [list(map(int,input().split())) for _ in range(C)]
c = [list(map(int,input().split())) for _ in range(N)]
c_set = [[0]*C for _ in range(3)]
for i in range(N):
    for j in range(N):
        c_set[(i+j)%3][c[i][j]-1] += 1
ans = 1e9
for c_1 in range(C):
    for c_2 in range(C):
        for c_3 in range(C):
            if c_1==c_2 or c_1==c_3 or c_2==c_3:
                continue
            c_list = [c_1,c_2,c_3]
            k = 0
            for i in range(C):
                for j in range(3):
                    k += d[i][c_list[j]-1]*c_set[j][i]
            ans = min(ans,k)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    k, s = map(int, input().split())
    ans = 0
    for x in range(k+1):
        if x > s:
            break
        for y in range(k+1):
            if x + y > s:
                break
            for z in range(k+1):
                if x + y + z > s:
                    break
                if x + y + z == s:
                    ans += 1
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    k, s = map(int, input().split())
    ans = 0
    for x in range(k+1):
        if x > s:
            break
        for y in range(k+1):
            if x + y > s:
                break
            if s - (x + y) <= k:
                ans += 1

    print(ans)

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

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

N, K = map(int, input().split())
P = [[] for i in range(N)]

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


dic = {}


def Perm(n, k):
    if (n, k) in dic:
        return dic[(n, k)]
    ans = 1
    for i in range(n - k + 1, n + 1):
        ans *= i
    dic[(n, k)] = ans
    return ans % MOD


def dfs(g, p):
    ans = Perm(K - 2, len(P[p]) - 1) % MOD
    for c in P[p]:
        if not c == g:
            ans *= dfs(p, c) % MOD
    return ans % MOD


ans = Perm(K, len(P[0]) + 1)
for c in P[0]:
    ans *= dfs(0, c) % MOD

print(ans % MOD)


### FIXED CODE ###

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

N, K = map(int, input().split())
P = [[] for i in range(N)]

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


dic = {}


def Perm(n, k):
    if (n, k) in dic:
        return dic[(n, k)]
    ans = 1
    for i in range(n - k + 1, n + 1):
        ans *= i
        ans %= MOD
    dic[(n, k)] = ans
    return ans


def dfs(g, p):
    ans = Perm(K - 2, len(P[p]) - 1)
    for c in P[p]:
        if not c == g:
            ans *= dfs(p, c)
            ans %= MOD
    return ans


ans = Perm(K, len(P[0]) + 1)
for c in P[0]:
    ans *= dfs(0, c)
    ans %= MOD

print(ans)
### BUGGY CODE ###

S=input()
count=S.count("BW")
end=0
def sigma(i):
    ans=0
    while i!=0:
        ans+=i
        i-=1
    return ans
place=[]
while "BW" in S:
    i=S.find("BW") + 1
    place.append(i)
    S=S.replace("BW","BB",1)

count=sum(place)-sigma(count-1)
print(count)

### FIXED CODE ###

S=input()
count=0
def sigma(i):
    a=[b for b in range(0,i+1)]
    return sum(a)
place=0
flag=0
start=0
for i in range(len(S)):
    if S[i]=="B":
        flag=1
    elif S[i]=="W":
        if flag == 1:
            count += 1
            place += i - start
        else:
            start+=1
ans=place-sigma(count-1)
print(ans)
### BUGGY CODE ###

s = input()
t = input()
S = len(s)
T = len(t)
dp = [[0]*(T+1) for _ in range(S+1)]

for i in range(S):
    for j in range(T):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

ans = ""
while S and T:
    if dp[S][T] == dp[S-1][T]:
        S -= 1
    elif dp[S][T] == dp[S][T-1]:
        T -= 1
    else:
        ans = s[S-1]+ans
        S -= 1
        T -= 1
print(ans)


### FIXED CODE ###

s = input()
t = input()
S = len(s)
T = len(t)
dp = [[0]*(T+1) for _ in range(S+1)]

for i in range(S):
    for j in range(T):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

ans = ""
while S and T:
    if dp[S][T] == dp[S-1][T]:
        S -= 1
    elif dp[S][T] == dp[S][T-1]:
        T -= 1
    else:
        ans = s[S-1]+ans
        S -= 1
        T -= 1
print(ans)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
S = input()
Q = int(input())
for i in range(Q):
    q = list(input().split())
    if q[0] == '1':
        S = S[::-1]
    else:
        if q[1] == '1':
            S = q[2] + S
        else:
            S += q[2]
print(S)

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
S = input()
Q = int(input())
flag = True
f = ''
b = ''
for i in range(Q):
    q = list(input().split())
    if q[0] == '1':
        flag = not flag
    else:
        if flag:
            if q[1] == '1':
                f = q[2] + f
            else:
                b += q[2]
        else:
            if q[1] == '1':
                b += q[2]
            else:
                f = q[2] + f
S = f + S + b
if not flag:
    S = S[::-1]
print(S)
### BUGGY CODE ###

from collections import defaultdict

n, q = map(int, input().strip().split())
edges = [list(map(int, input().strip().split())) for _ in range(n - 1)]
values = [list(map(int, input().strip().split())) for _ in range(q)]


edge_dict = defaultdict(list)
value_dict = defaultdict(int)
total_value_dict = defaultdict(int)
visited = [False] * n

for a, b in edges:
    edge_dict[a].append(b)
    edge_dict[b].append(a)

for p, x in values:
    value_dict[p] += x

queue = [1]
total_value_dict[1] = value_dict[1]
visited[0] = True

while len(queue) > 0:
    node = queue.pop(0)
    next_nodes = filter(lambda m: not visited[m - 1], edge_dict[node])
    for m in next_nodes:
        total_value_dict[m] = total_value_dict[node] + value_dict[m]
        visited[m - 1] = True
        queue.append(m)

print(' '.join([str(total_value_dict[i]) for i in range(1, n + 1)]))


### FIXED CODE ###

from collections import defaultdict
from collections import deque
import time
import sys

input = sys.stdin.readline

# start = time.time()
n, q = map(int, input().strip().split())
edges = [list(map(int, input().strip().split())) for _ in range(n - 1)]
values = [list(map(int, input().strip().split())) for _ in range(q)]

# elapsed = time.time() - start
# print("elapsed_time:{0}".format(elapsed) + "[sec]")

edge_dict = defaultdict(list)
value_dict = defaultdict(int)
total_value_dict = defaultdict(int)
visited = [False] * n

for a, b in edges:
    edge_dict[a].append(b)
    edge_dict[b].append(a)

for p, x in values:
    value_dict[p] += x


qu = deque([1])
total_value_dict[1] = value_dict[1]
visited[0] = True

while len(qu) > 0:
    node = qu.popleft()
    next_nodes = [m for m in edge_dict[node] if not visited[m - 1]]
    for m in next_nodes:
        total_value_dict[m] = total_value_dict[node] + value_dict[m]
        visited[m - 1] = True
        qu.append(m)

print(' '.join([str(total_value_dict[i]) for i in range(1, n + 1)]))
### BUGGY CODE ###

from itertools import groupby 

N = int(input())

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

def solve(N):
    if (N % 2 == 1): return 0
    
    ans = 0
    for i in range(2, N + 2, 2):
        if (i % 5 == 0):
            ans += prime_factors(i).count(5)
    return ans

print(solve(N))


### FIXED CODE ###

from itertools import groupby 

N = int(input())

def solve(N):
    if (N % 2 == 1):
        return 0
    
    d = N // 10
    ans = d
    while d:
        d //= 5
        ans += d
    return ans

print(solve(N))
### BUGGY CODE ###

N,K,Q = map(int,input().split())
A = [int(input()) for i in range(Q)]
point = [K]*N
def calc(num):
  return num-1
for a in A:
  for index,p in enumerate(point):
    if index+1 != a:
      point[index] -= 1
     

for po in point:
  if po > 0:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

N,K,Q = map(int,input().split())
A = [int(input()) for i in range(Q)]
num = K-Q
point = [num]*N

for a in A:
  point[a-1] += 1

for po in point:
  if po > 0:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

h=0
a=list(input())
for i in range(1,len(a)):
  if int(a[i-1])==int(a[i]):
    if int(a[i])==0:
      b=1
    else:
      b=0
    a.pop(i)
    a.insert(i,b)
    h+=1
print(h)

### FIXED CODE ###

a = list(input())
s = a[0]
count = 0
if s == "0":
    for i in range(1, len(a)):
        if int(a[i]) != i % 2:
            count += 1
elif s == "1":
    for i in range(1, len(a)):
        if int(a[i]) != (i + 1) % 2:
            count += 1
print(count)
### BUGGY CODE ###

from collections import defaultdict

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

friend_list = defaultdict(list)
for _ in range(M):
    a, b = map(int, input().split(' '))
    a, b = a - 1, b - 1
    friend_list[a].append(b)
    friend_list[b].append(a)

block_list = defaultdict(list)
for _ in range(K):
    c, d = map(int, input().split(' '))
    c, d = c - 1, d - 1
    block_list[c].append(d)
    block_list[d].append(c)


def dfs(s, adj_list):
    cand_list = [s]
    vis_list = []

    while len(cand_list) > 0:
        vis = cand_list.pop(-1)
        vis_list.append(vis)
        pre_cand_list = adj_list[vis]
        for cand in pre_cand_list:
            if cand in vis_list:
                continue
            if cand in cand_list:
                continue
            cand_list.append(cand)

    return vis_list


num_friend_candidate_array = [0, ] * N
visited_user_list = []

for i in range(N):
    if i in visited_user_list:
        continue

    connected_components = dfs(i, friend_list)
    visited_user_list += connected_components

    for j in connected_components:
        friend_candidates = set(connected_components) - \
            set(friend_list[j]) - set(block_list[j]) - {j}
        num_friend_candidate_array[j] = max(len(friend_candidates), 0)

print(*num_friend_candidate_array)


### FIXED CODE ###

from collections import defaultdict


class UnionFind:
    def __init__(self, n=0):
        self.d = {i: -1 for i in range(n)}

    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.d[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if (x == y):
            return False
        if (self.d[x] > self.d[y]):
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.d[self.find(x)]


N, M, K = map(int, input().split(' '))
deg = defaultdict(int)
to = defaultdict(list)
uf = UnionFind(N)

for _ in range(M):
    a, b = map(int, input().split(' '))
    a -= 1
    b -= 1
    deg[a] += 1
    deg[b] += 1
    uf.unite(a, b)

for _ in range(K):
    c, d = map(int, input().split(' '))
    c -= 1
    d -= 1
    to[c].append(d)
    to[d].append(c)

for i in range(N):
    ans = uf.size(i) - 1 - deg[i]
    for u in to[i]:
        if uf.same(i, u):
            ans -= 1
    print(ans, end=' ' if i != (N - 1) else '\n')
### BUGGY CODE ###

from scipy.spatial import distance

N, D = map(int, input().split())
xy = [list(map(int, input().split())) for xy in range(N)]
o = [0, 0]
count = 0

for i in range(N):
    if xy[i][0] > D or xy[i][1] >D:
        pass
    else:
        if distance.euclidean(xy[i], o) <= D:
            count += 1
        else:
            pass

print(count)


### FIXED CODE ###

import numpy as np

N, D = map(int, input().split())
xy = np.array([list(map(int, input().split())) for xy in range(N)])
o = np.array([0, 0])
count = 0

for i in range(N):
    if np.linalg.norm(xy[i] - o) <= D:
        count += 1
    else:
        pass

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

import bisect

n, m = map(int, input().split())

nums = list(map(int, input().split()))

nums.sort()

ops = []
for i in range(m):
    b, c = map(int, input().split())
    ops.append([b, c])

total = 0
for b, c in sorted(ops, key=lambda x:x[1], reverse=True):
    if c < nums[0]:
        break
    if total > n:
        break

    index = bisect.bisect_left(nums, c)
    if index > 0:
        temp = nums[0:index]
        temp.extend([c]*b)
        temp.extend(nums[index:])
        nums = temp[-n:]
    total = total + b
print(sum(nums))

### FIXED CODE ###

n, m = map(int, input().split())

nums = list(map(int, input().split()))

ops = []
for i in nums:
    ops.append([1, i])
    
for i in range(m):
    b, c = map(int, input().split())
    ops.append([b, c])

total = 0
sums = []
for b, c in sorted(ops, key=lambda x:x[1], reverse=True):
    if total > n:
        break
    sums.extend([c]*b)
    total = total + b
print(sum(sums[:n]))
### BUGGY CODE ###

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

sums=[0]*(len(a)+1)
for i in range(len(a)):
  sums[i+1]=sums[i]+a[i]
  
cnt=0
for i in range(len(sums)-1):
  for j in range(i+1,len(sums)):
    if sums[j]-sums[i]==0:
      cnt+=1
      
print(cnt)

### FIXED CODE ###

import collections

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

sums=[0]*(len(a)+1)
for i in range(len(a)):
  sums[i+1]=sums[i]+a[i]
  
counter=collections.Counter(sums)
cnt=0
for val in counter.values():
  if val>1:
    cnt+=(val*(val-1))//2

print(cnt)
### BUGGY CODE ###

N = int(input())
ans = 10**10
for i in range(1,1+int(N)):
    if N % i == 0:
        tmp = i
        s = max(len(str(N // tmp)),len(str(tmp)))
        ans = min(ans,s)
print(ans)

### FIXED CODE ###

N = int(input())
for i in range(1,1+int(N**(1/2))):
    if N % i == 0:
        tmp = i
print(max(len(str(N // tmp)),len(str(tmp))))
### BUGGY CODE ###

S = input()
cnt1 = 0
cnt2 = 0
while True:
    before = S
    S = before.replace("01", "", 1)
    if before != S:
        cnt1 += 1
    else:
        break

while True:
    before = S
    S = before.replace("10", "", 1)
    if before != S:
        cnt2 += 1
    else:
        break

print(2 * (cnt1 + cnt2))


### FIXED CODE ###

S = input()
print(2 * min(S.count("1"), S.count("0")))
### BUGGY CODE ###

n = int(input())
xyd = [input().split() for _ in range(n)]
def reg(a):
    a.sort()
    if len(a) > 2:
        a = [a[0], a[-1]]
    return a
xr = reg([int(v[0]) for v in xyd if v[2] == 'R'])
xl = reg([int(v[0]) for v in xyd if v[2] == 'L'])
xs = reg([int(v[0]) for v in xyd if v[2] == 'U' or v[2] == 'D'])
yu = reg([int(v[1]) for v in xyd if v[2] == 'U'])
yd = reg([int(v[1]) for v in xyd if v[2] == 'D'])
ys = reg([int(v[1]) for v in xyd if v[2] == 'R' or v[2] == 'L'])
xd = [(x, 1) for x in xr] + [(x, -1) for x in xl] + [(x, 0) for x in xs]
yd = [(y, 1) for y in yu] + [(y, -1) for y in yd] + [(y, 0) for y in ys]
def calc(mid):
    xmin = min(x + mid * d for x, d in xd)
    xmax = max(x + mid * d for x, d in xd)
    ymin = min(y + mid * d for y, d in yd)
    ymax = max(y + mid * d for y, d in yd)
    return (xmax - xmin) * (ymax - ymin)
lo = 0.0
hi = 1e200
while hi - lo > 1e-15 and hi - lo > lo * 1e-19:
    mid1 = (lo * 2 + hi) / 3
    mid2 = (lo + hi * 2) / 3
    if calc(mid1) > calc(mid2):
        lo = mid1
    else:
        hi = mid2
print(calc((lo + hi) / 2))

### FIXED CODE ###

n = int(input())
m = {}
for _ in range(n):
    x, y, d = input().split()
    x, y = int(x) * 2, int(y) * 2
    if d not in m:
        m[d] = [1000000000, -1000000000, 1000000000, -1000000000]
    m[d][0] = min(m[d][0], x)
    m[d][1] = max(m[d][1], x)
    m[d][2] = min(m[d][2], y)
    m[d][3] = max(m[d][3], y)

dx = {'L': -1, 'R': 1, 'U': 0, 'D': 0}
dy = {'L': 0, 'R': 0, 'U': 1, 'D': -1}

px = []
py = []
for d in 'LRUD':
    if d in m:
        px.append((m[d][0], dx[d]))
        px.append((m[d][1], dx[d]))
        py.append((m[d][2], dy[d]))
        py.append((m[d][3], dy[d]))

times = [0]
def append(pa, pb):
    (a, da) = pa
    (b, db) = pb
    if db != da:
        t = (a - b) // (db - da)
        if t >= 0:
            times.append(t)

for i in range(len(px)):
    for j in range(i + 1, len(px)):
        append(px[i], px[j])

for i in range(len(py)):
    for j in range(i + 1, len(py)):
        append(py[i], py[j])

ret = 1000000000000000000
for t in times:
    bb = [1000000000, -1000000000, 1000000000, -1000000000]
    for d in 'LRUD':
        if d in m:
            bb[0] = min(bb[0], m[d][0] + dx[d] * t)
            bb[1] = max(bb[1], m[d][1] + dx[d] * t)
            bb[2] = min(bb[2], m[d][2] + dy[d] * t)
            bb[3] = max(bb[3], m[d][3] + dy[d] * t)
    ret = min(ret, (bb[1] - bb[0]) * (bb[3] - bb[2]))

print(ret / 4.0)
### BUGGY CODE ###

import bisect
N=int(input())
l = list(map(int,input().split()))
l.sort()
ans = 0
for i in range(1,N-1):
  for j in range(i+1,N):
    a=l[i]
    b=l[j]
    ans+=i-bisect.bisect_right(l[:i],b-a)
print(ans)

### FIXED CODE ###

import bisect
N=int(input())
l = list(map(int,input().split()))
l.sort()
ans = 0
for i in range(1,N-1):
  for j in range(i+1,N):
    m=bisect.bisect_right(l,l[j]-l[i])
    if i>m:
      ans+=i-m
print(ans)
### BUGGY CODE ###

import sys

import numpy as np

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]

n = readInt()
aa = []
for i in range(n):
    aa.append(readInt())

memo = {}
def dfs(a, b, c, i):
    if i == len(aa):
        return 1 if c < a + b else 0
    if (a, b, c) in memo:
        return memo[(a, b, c)]

    ret = 0
    v0 = sorted([a + aa[i], b, c])
    ret = (ret + dfs(v0[0], v0[1], v0[2], i + 1)) % 998244353

    v1 = sorted([a, b + aa[i], c])
    ret = (ret + dfs(v1[0], v1[1], v1[2], i + 1)) % 998244353

    v2 = sorted([a, b, c + aa[i]])
    ret = (ret + dfs(v2[0], v2[1], v2[2], i + 1)) % 998244353

    memo[(a, b, c)] = ret
    return ret

print(dfs(0, 0, 0, 0))

### FIXED CODE ###

import sys

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]

total = 0
ret = 1
n = readInt()
aa = []
for i in range(n):
    v = readInt()
    aa.append(v)
    total += v
    ret *= 3


L = (n * max(aa) + 1)
memo = [-1] * ((n+1) * L * 2)
def dfs(i, c):
    key = (i * L * 2) + 2 * c
    if 0 <= memo[key]:
        return memo[key: key+2]

    if i == n:
        memo[key + 0] = 3 if total <= (2 * c) else 0
        memo[key + 1] = 3 if total == (2 * c) else 0
        return memo[key: key + 2]

    v0 = dfs(i + 1, c)
    v1 = dfs(i + 1, c + aa[i])

    memo[key + 0] = (2 * v0[0] + v1[0]) % 998244353
    memo[key + 1] = (v0[1] + v1[1]) % 998244353
    return memo[key: key + 2]

a, b = dfs(0, 0)
ret = (ret - a + b) % 998244353
print(ret)
### BUGGY CODE ###

def trycand(first, second, nextcand):
    rest = nextcand.copy()
    rest.remove(second)
    n1 = first
    n2 = second
    while rest:
        try:
            n3 = n1 ^ n2
            rest.remove(n3)
            n1 = n2
            n2 = n3
        except ValueError:
            return False
    return True


n = input()

a = list(map(lambda x: int(x), input().split()))
first = a[0]
#print(first)
nextcand = a[1:]
#print(nextcand)

for second in nextcand:
    if trycand(first, second, nextcand):
        print("Yes")
        exit()

print("No")
exit()


### FIXED CODE ###

n = input()

a = list(map(lambda x: int(x), input().split()))

xor = 0

for i in a:
    xor = xor ^ i

if xor == 0:
    print("Yes")
else:
    print("No")