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

# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq

n = int(input())
a = []
b = []
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a.append([i,xy[0]])
    b.append([i,xy[1]])

a.sort(key=lambda x: x[1])
b.sort(key=lambda x: x[1])
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for i, [j, x] in enumerate(a[:-1]):
    adj[j].append([a[i+1][1]-x, a[i+1][0]])
    adj[a[i+1][0]].append([a[i+1][1]-x, j])
for i, [j, y] in enumerate(b[:-1]):
    adj[j].append([b[i+1][1]-y, b[i+1][0]])
    adj[b[i+1][0]].append([b[i+1][1]-y, j])

#print(adj)
    
# Prim's algorithm
d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
while h:
    cost, node = heapq.heappop(h)
    if visited[node] != True and cost < d[node]:
    #if visited[node] != True:        
        d[node] = cost
        visited[node] = True
        cnt += 1
        if cnt == n:
            break
        for edge in adj[node]:
            if visited[edge[1]] == True:
                continue
            heapq.heappush(h, edge)
            
#print(d)
print(sum(d))
        


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq
import sys
input = sys.stdin.readline

n = int(input())
a = [[] for _ in range(n)]
b = [[] for _ in range(n)]
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a[i]=[xy[0],i]
    b[i]=[xy[1],i]

a.sort()
b.sort()
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for [x0, j0], [x1, j1]  in zip(a, a[1:]):
    adj[j0].append([x1-x0, j1])
    adj[j1].append([x1-x0, j0])
for [y0, j0], [y1, j1] in zip(b, b[1:]):
    adj[j0].append([y1-y0, j1])
    adj[j1].append([y1-y0, j0])

#print(adj)
    
# Prim's algorithm
#d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
totalcost = 0 
while h:
    cost, node = heapq.heappop(h)
    #if visited[node] != True and cost < d[node]:
    if visited[node] != True:        
        #d[node] = cost
        visited[node] = True
        totalcost += cost
        cnt += 1
        if cnt == n:
            break
        for edge in adj[node]:
            if visited[edge[1]]:
                continue
            heapq.heappush(h, edge)
            
#print(d)
print(totalcost)
### BUGGY CODE ###

r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
f=[1]
for i in range(2*10**6+7):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod
def F(r,c):
  ans=0
  for i in range(r+c+1):
    ans+=2**i
    ans%=mod
  #print(ans)
  d=0
  s=0
  for i in range(r-1,-1,-1):
    s+=comb((r-i-1)+c,c)
    d+=2**i*s
    s%=mod
    d%=mod
  #print(d)
  ans=(ans+(mod-d))%mod
  d=0
  s=0
  for i in range(c-1,-1,-1):
    s+=comb((c-i-1)+r,r)
    d+=2**i*s
    s%=mod
    d%=mod
  #print(d)
  ans=(ans+(mod-d))%mod
  return ans
"""
"""
ans=F(r2,c2)
ans=(ans+(mod-F(r2,c1-1)))%mod
ans=(ans+(mod-F(r1-1,c2)))%mod
ans+=F(r1-1,c1-1)
print(ans%mod)
"""
print(F(4,3))
"""

### FIXED CODE ###

r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
f=[1]
for i in range(2*10**6+7):f+=[f[-1]*(i+1)%mod]
ans=0
for i in range(c1,c2+1):
  d=((r2+1)*f[i+r2+1]%mod)*f[r1]
  d%=mod
  d=(d+(mod-((r1*f[r2+1]%mod)*f[i+r1])%mod))%mod
  d*=pow((((i+1)*f[i]%mod)*f[r1]%mod)*f[r2+1]%mod,mod-2,mod)
  d%=mod
  ans+=d
  ans%=mod
print(ans)
### BUGGY CODE ###

a,b,k = map(int, input().split())
for i in range(k):
  if a>=1:
    a-=1
  elif b>=1:
    b-=1
  if a == 0 and b == 0:
    print(0,0)
    exit()
print(a,b)

### FIXED CODE ###

a,b,k = map(int, input().split())
if a>=k:
  print(a-k,b)
elif k>=a+b:
  print(0,0)
else:
  print(0,str(b-k+a))
### BUGGY CODE ###

from collections import Counter
N = int(input())
S = input()
c = Counter(S)
ans = c['R']*c['G']*c['B']
for i in range(N):
  for j in range(i+1,N):
    k = j-i+j
    if k>N-1:
      continue
    if S[i]!=S[j] and S[j]!=S[k] and S[i]!= S[k]:
      ans -= 1
print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
S = input()
c = Counter(S)
ans = c['R']*c['G']*c['B']
for i in range(N):
  for j in range(i+1,N):
    k = j-i+j
    if k>N-1:
      continue
    if S[i]!=S[j] and S[j]!=S[k] and S[i]!= S[k]:
      ans -= 1
print(ans)
### BUGGY CODE ###

s = input()
K = int(input())

l = len(s)
lst = [[s[i], i] for i in range(l)]
lst.sort()
substr = []
i = 0
init_c = lst[i][0]

while len(substr) < K:
    while True:
        j = lst[i][1]
        for k in range(j, l):
            substr.append(s[j:k+1])
        i += 1
        init_c_ = init_c
        if i == l: break
        init_c = lst[i][0]
        if init_c != init_c_: break
    substr = list(set(substr))

substr.sort()
print(substr[K-1])


### FIXED CODE ###

s = input()
K = int(input())

l = len(s)
substr = []

for i in range(l):
    for k in range(K):
        substr.append(s[i:i+k+1])
        if i+k+1 >= l: break

substr = list(set(substr))
substr.sort()
print(substr[K-1])
### BUGGY CODE ###

import sys

H, W = map(int, sys.stdin.readline().split())
s = [list(sys.stdin.readline().rstrip()) for _ in range(H)]

ans = float("inf")


def dfs(x, y, tmp=0):
    if s[x][y] == "#":
        tmp = tmp + 1
    global ans
    if tmp > ans:
        return
    if x == H - 1 and y == W - 1:
        ans = tmp
        return ans
    else:
        if x == H - 1:
            dfs(x, y + 1, tmp)
        elif y == W - 1:
            dfs(x + 1, y, tmp)
        else:
            dfs(x, y + 1, tmp)
            dfs(x + 1, y, tmp)


def main():
    dfs(0, 0)
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys


def main():
    dp = [[0] * W for _ in range(H)]

    for y in range(H):
        for x in range(W):
            if x == 0 and y == 0:
                if s[0][0] == "#":
                    dp[0][0] = 1
            elif x == 0:
                if s[y][x] == "#" and s[y - 1][x] == ".":
                    dp[y][x] = dp[y - 1][x] + 1
                else:
                    dp[y][x] = dp[y - 1][x]
            elif y == 0:
                if s[y][x] == "#" and s[y][x - 1] == ".":
                    dp[y][x] = dp[y][x - 1] + 1
                else:
                    dp[y][x] = dp[y][x - 1]
            else:
                if s[y][x] == "#" and s[y][x - 1] == "." and s[y - 1][x] == ".":
                    dp[y][x] = min(dp[y][x - 1], dp[y - 1][x]) + 1
                elif s[y][x] == "#" and s[y][x - 1] == ".":
                    dp[y][x] = min(dp[y][x - 1] + 1, dp[y - 1][x])
                elif s[y][x] == "#" and s[y - 1][x] == ".":
                    dp[y][x] = min(dp[y][x - 1], dp[y - 1][x] + 1)
                else:
                    dp[y][x] = min(dp[y][x - 1], dp[y - 1][x])

    print(dp[-1][-1])


if __name__ == "__main__":
    H, W = map(int, sys.stdin.readline().split())
    s = [list(sys.stdin.readline().rstrip()) for _ in range(H)]
    main()
### BUGGY CODE ###

##from scipy.sparse.csgraph import csgraph_from_dense,floyd_warshall
import numpy as np
from itertools import permutations
N,M,R = map(int,input().split())
r = list(map(int,input().split()))

"""
https://juppy.hatenablog.com/entry/2018/11/01/%E8%9F%BB%E6%9C%AC_python_%E5%85%A8%E7%82%B9%E5%AF%BE%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%E6%B3%95%EF%BC%88%E3%83%AF%E3%83%BC%E3%82%B7%E3%83%A3%E3%83%AB%E3%83%95%E3%83%AD%E3%82%A4%E3%83%89%E6%B3%95
"""

def warshall_floyd(d):
    n = len(d)
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

graph = [[float("inf") for i in range(N)] for j in range(N)] 
for i in range(M):
    A,B,C = map(int,input().split())
    graph[A-1][B-1] = C
    graph[B-1][A-1] = C

dist = warshall_floyd(graph)

ans = 1e10
for i in permutations(r):
    flag = True
    way = list(i)
    tmp = 0
    for i in range(len(way)-1):
        if dist[way[i]-1][way[i+1]-1] < 0:
            flag = False
            break
        tmp += dist[way[i]-1][way[i+1]-1]
    if flag:
        ans = min(tmp,ans)

print(ans)

### FIXED CODE ###

##from scipy.sparse.csgraph import csgraph_from_dense,floyd_warshall
##import numpy as np
from itertools import permutations
N,M,R = map(int,input().split())
r = list(map(int,input().split()))

"""
https://juppy.hatenablog.com/entry/2018/11/01/%E8%9F%BB%E6%9C%AC_python_%E5%85%A8%E7%82%B9%E5%AF%BE%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%E6%B3%95%EF%BC%88%E3%83%AF%E3%83%BC%E3%82%B7%E3%83%A3%E3%83%AB%E3%83%95%E3%83%AD%E3%82%A4%E3%83%89%E6%B3%95
"""

def warshall_floyd(d):
    n = len(d)
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

graph = [[float("inf") for i in range(N)] for j in range(N)] 
for i in range(M):
    A,B,C = map(int,input().split())
    graph[A-1][B-1] = C
    graph[B-1][A-1] = C

dist = warshall_floyd(graph)

ans = 1e10
for i in permutations(r):
    flag = True
    way = list(i)
    tmp = 0
    for i in range(len(way)-1):
        if dist[way[i]-1][way[i+1]-1] < 0:
            flag = False
            break
        tmp += dist[way[i]-1][way[i+1]-1]
    if flag:
        ans = min(tmp,ans)

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

import sys
sys.setrecursionlimit(10 ** 9)
n, q = map(int, input().split())
edges = [[] for i in range(n)]
counter = [0] * n
for i in range(n - 1):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
for i in range(q):
    p, x = map(int, input().split())
    counter[p - 1] += x
def dfs(now, prev):
    for next in edges[now]:
        if next == prev:
            continue
        counter[next] += counter[now]
        dfs(next, now)
dfs(0, -1)
print(*counter)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
n, q = map(int, input().split())
edges = [[] for i in range(n)]
counter = [0] * n
for i in range(n - 1):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
for i in range(q):
    p, x = map(int, input().split())
    counter[p - 1] += x
def dfs(now, prev):
    for next in edges[now]:
        if next == prev:
            continue
        counter[next] += counter[now]
        dfs(next, now)
dfs(0, -1)
print(*counter)
### BUGGY CODE ###

import math
import collections
N = int(input())
s = []
for i in range(N):
    ss = input()
    s.append(ss)
t= []
for i in range(N):
    tt= sorted(s[i])
    t.append(tt)
#s.sort()
#print(t)

count = 0
for i in range(N):
    start = t[i]
    for j in range(i+1,N):
#        print("i,j1=",i,j)
        if start == t[j]:
#            print("i,j=",i,j)
            count = count +1
print(count)

### FIXED CODE ###

import collections as cl
import itertools as it
N = int(input())
s = []
for i in range(N):
    ss = input()
    s.append(ss)
#print(s)
t = sorted(s)
t= []
for i in range(N):
    tt= sorted(s[i])
    ts = ",".join(tt)
    t.append(ts)
#    print(ts)
#print(t)
l = cl.Counter(t)
#print(l)
count = 0
for v in l.values():
    if v > 1:
        count = count + v*(v-1)/2
#    print(v)
print(int(count))
### BUGGY CODE ###

def my_index(l, x, default=False):
    return l.index(x) if x in l else default


def main():
    n,m = map(int, input().split())
    PY = [list(map(int, input().split())) for _ in range(m)]
    P = [x[0] for x in PY]
    Y = [x[1] for x in PY]

    PY = sorted(PY, key=lambda x:(x[0],x[1]))
    P_sorted = [x[0] for x in PY]
    Y_sorted = [x[1] for x in PY]
    for i in range(m):
        x = my_index(Y_sorted, Y[i])+1 - my_index(P_sorted,P[i])
        print(str(P[i]).rjust(6,'0')+str(x).rjust(6,'0'))


if __name__ == '__main__':
    main()
    # test()


### FIXED CODE ###

def main():
    n,m = map(int, input().split())
    PY = [list(map(int, input().split()+[i])) for i in range(m)]
    PY = sorted(PY, key=lambda x:(x[0],x[1]))

    tmp = 0
    for i in range(m):
        if tmp == PY[i][0]:
            count += 1
        else:
            count = 1
            tmp = PY[i][0]
        PY[i].append(count)

    PY = sorted(PY, key=lambda x:x[2])

    for i in range(m):
        print(str(PY[i][0]).rjust(6,'0')+str(PY[i][3]).rjust(6,'0'))


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

n,k=map(int,input().split())
a=list(map(int,input().split()))
l=[sum(a[x:x+k]) for x in range(n-k+1)]
print((max(l)+k)/2)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
s=sum(a[:k])
l=[s]
for x in range(n-k):
    s=s-a[x]+a[x+k]
    l.append(s)
print((max(l)+k)/2)
### BUGGY CODE ###

N,M = list(map(int,input().strip().split()))
num = N
i = 0

while True:
    if M%(N+i) == 0:
        ans = M//(N+i)
        break
    else:
        i += 1

print(ans)

### FIXED CODE ###

import math

N,M = list(map(int,input().strip().split()))
ans = 1
i = 0

def is_prime(num):
    if num < 2:
        return False
    if num == 2 or num == 3 or num == 5:
        return True
    if num % 2 == 0 or num % 3 == 0 or num % 5 == 0:
        return False

    prime = 7
    step = 4
    num_sqrt = math.sqrt(num)
    while prime <= num_sqrt:
        if num % prime == 0:
            return False
        prime += step
        step = 6 - step

    return True

if is_prime(M) == False:
    while M//2 >= N+i:
        if M%(N+i) == 0:
            ans = M//(N+i)
            break
        else:
            i += 1

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

class UnionFind():
    n=1
    par=[0]
    rnk=[0]
    def __init__(self,size):
        self.n=size
        self.par=[i for i in range(self.n)]
        self.rnk=[0 for i in range(self.n)]
    def find(self,vertex1):
        if self.par[vertex1]==vertex1:
            return vertex1
        else:
            self.par[vertex1]=self.find(self.par[vertex1])
            return self.par[vertex1]
    def unite(self,vertex1,vertex2):
        vertex1=self.find(vertex1)
        vertex2=self.find(vertex2)
        if vertex1==vertex2:
            return
        if (self.rnk[vertex1]<self.rnk[vertex2]):
            self.par[vertex1]=vertex2
        else:
            self.par[vertex2]=vertex1
            if(self.rnk[vertex1]==self.rnk[vertex2]):
                self.rnk[vertex1]+=1
    def same(self,vetrex1,vertex2):
        return self.find(vetrex1)==self.find(vertex2)

N,M=map(int,input().split())
A=[0 for i in range(M)]
B=[0 for i in range(M)]
for i in range(M):
    A[i],B[i]=map(int,input().split())
    A[i]-=1;B[i]-=1
G=UnionFind(N)
D=dict()
for i in range(N):
    D[i]=1
ans=[(N*(N-1))//2]
for i in range(M)[::-1]:
    #この行があるとTLEになるはず
    tmp=[G.find(i) for i in range(N)]
    #この上の行のせいでO(NM)になって通らない
    a=G.find(A[i])
    b=G.find(B[i])
    G.unite(A[i],B[i])
    x=G.find(A[i])
    if a!=b:
        ans.append(ans[-1]-D[a]*D[b])
        if x==a:
            D[a],D[b]=D[a]+D[b],0
        else:
            D[a],D[b]=0,D[a]+D[b]
    else:
        ans.append(ans[-1])
for line in ans[:-1][::-1]:
    print(line)


### FIXED CODE ###

class UnionFind():
    n=1
    par=[0]
    rnk=[0]
    def __init__(self,size):
        self.n=size
        self.par=[i for i in range(self.n)]
        self.rnk=[0 for i in range(self.n)]
    def find(self,vertex1):
        if self.par[vertex1]==vertex1:
            return vertex1
        else:
            self.par[vertex1]=self.find(self.par[vertex1])
            return self.par[vertex1]
    def unite(self,vertex1,vertex2):
        vertex1=self.find(vertex1)
        vertex2=self.find(vertex2)
        if vertex1==vertex2:
            return
        if (self.rnk[vertex1]<self.rnk[vertex2]):
            self.par[vertex1]=vertex2
        else:
            self.par[vertex2]=vertex1
            if(self.rnk[vertex1]==self.rnk[vertex2]):
                self.rnk[vertex1]+=1
    def same(self,vetrex1,vertex2):
        return self.find(vetrex1)==self.find(vertex2)

N,M=map(int,input().split())
A=[0 for i in range(M)]
B=[0 for i in range(M)]
for i in range(M):
    A[i],B[i]=map(int,input().split())
    A[i]-=1;B[i]-=1
G=UnionFind(N)
D=dict()
for i in range(N):
    D[i]=1
ans=[(N*(N-1))//2]
for i in range(M)[::-1]:
    #print([G.find(i) for i in range(N)],A[i],B[i],D,ans[-1])
    a=G.find(A[i])
    b=G.find(B[i])
    G.unite(A[i],B[i])
    x=G.find(A[i])
    if a!=b:
        ans.append(ans[-1]-D[a]*D[b])
        if x==a:
            D[a],D[b]=D[a]+D[b],0
        else:
            D[a],D[b]=0,D[a]+D[b]
    else:
        ans.append(ans[-1])
for line in ans[:-1][::-1]:
    print(line)
### BUGGY CODE ###

S = input()
Q = int(input())
for _ in range(Q):
    T = input()
  
    if len(T)==1:
        S = S[::-1]
    else:
        if T[2]=="1":
            S = T[4]+S
        else:
              S = S+T[4]
print(S)


### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())

t = deque(S)
reverse = False
for _ in range(Q):
    query = input()
    if query[0] == '1':
        reverse = not reverse
    elif query[0] == '2':
        _, F, C = query.split()
        if F == '1':
            if reverse:
                t.append(C)
            else:
                t.appendleft(C)
        elif F == '2':
            if reverse:
                t.appendleft(C)
            else:
                t.append(C)
result = ''.join(t)
if reverse:
    result = result[::-1]
print(result)
### BUGGY CODE ###

from collections import deque

X = int(input())

queue = deque()
queue.appendleft((0, 0))

while queue:
    now = queue.pop()
    pos = now[0]
    time = now[1]

    if pos == X:
        print(time)
        exit()

    queue.appendleft((pos + time+1, time+1))
    queue.appendleft((pos, time+1))
    queue.appendleft((pos - (time+1), time+1))


### FIXED CODE ###

X = int(input())

time = 0
pos = 0
while pos < X:
    time += 1
    pos += time

print(time)
### BUGGY CODE ###

n,s,*a=map(int,open(0).read().split())
mod=998244353
dp=[[0]*(s+1) for _ in range(n+1)]
dp[0][0]=pow(2,n,mod)
for i in range(n):
  for j in range(s+1):
    dp[i+1][j]+=dp[i][j]
    dp[i+1][j]%=mod
    if j+a[i]<=s:
      dp[i+1][j+a[i]]+=dp[i][j]*(mod+1)//2
      dp[i+1][j+a[i]]%=mod
print(dp[n][s])

### FIXED CODE ###

n,s,*a=map(int,open(0).read().split())
mod=998244353
dp=[[0]*(s+1) for _ in range(n+1)]
dp[0][0]=pow(2,n,mod)
for i in range(n):
  for j in range(s+1):
    dp[i+1][j]+=dp[i][j]
    dp[i+1][j]%=mod
    if j+a[i]<=s:
      dp[i+1][j+a[i]]+=dp[i][j]*(mod+1)//2
      dp[i+1][j+a[i]]%=mod
print(dp[n][s])
### BUGGY CODE ###

N,K= map(int,input().split())
A=list(map(int,input().split()))
count=1
now=A[0]
while  now != 1 and count<K:
    now=A[now-1]
    count+=1
if now ==1:
    x=K%count
    for i in range(x):
        now=A[now-1]
print(now)

### FIXED CODE ###

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

s = [True] * n #訪れているかを判定するlist
c = [1] #訪ずれた順番を記録するlist
now = 0 #現在地
while s[now]:
    s[now] = False #訪ずれた地点を記録
    now = a[now] - 1
    c.append(now+1)

start_cycle = c.index(c[-1]) #ループに入る点
loop = c[start_cycle:-1] #ループのlist
cycle = len(loop)

if k < start_cycle: #ループまで到達できないK
    print(c[k])
else:
    k -= start_cycle
    k %= cycle
    print(loop[k])
### BUGGY CODE ###

s = str(input())
q = int(input())
flip = -1
strs_f = []
strs_b = []

for i in range(q):
    query = list(map(str, input().split()))
    if query[0] == '1':
        flip = flip * -1
    else:
        if query[1] == '1':
            if flip == -1:
                strs_f.insert(0,query[2])
            else:
                strs_b.append(query[2])
        else:
            if flip == -1:
                strs_b.append(query[2])
            else:
                strs_f.insert(0,query[2])
 
strs_f = ''.join(strs_f)
strs_b = ''.join(strs_b)
ans = strs_f + s + strs_b

if flip == 1:
    ans = ans[::-1]
print(ans)

### FIXED CODE ###

from collections import deque

s = str(input())
q = int(input())
flip = -1
strf = deque()
strb = deque()

for i in range(q):
    query = list(map(str, input().split()))
    if query[0] == '1':
        flip = flip * -1
    elif query[0] == '2':
        if query[1] == '1':
            if flip == -1:
                strf.appendleft(query[2])
            else:
                strb.append(query[2])
        elif query[1] == '2':
            if flip == -1:
                strb.append(query[2])
            else:
                strf.appendleft(query[2])

# print(strf)
# print(strb)
ans = ''.join(strf) + s + ''.join(strb)
if flip == 1:
    ans = ans[::-1]
print(ans)

# s = str(input())
# q = int(input())
# flip = -1
# strs = '/'
 
# for i in range(q):
#     query = list(map(str, input().split()))
#     if query[0] == '1':
#         flip = flip * -1
#     elif query[0] == '2':
#         if query[1] == '1':
#             if flip == -1:
#                 strs = query[2] + strs
#             else:
#                 strs = strs + query[2]
#         else:
#             if flip == -1:
#                 strs = strs + query[2]
#             else:
#                 strs = query[2] + strs
 
# if flip == -1:
#     ans = strs.replace('/', s)
# else:
#     ans = strs[::-1].replace('/', s[::-1])
 
# print(ans)
### BUGGY CODE ###

MOD=998244353
N=int(input())
A=[int(input()) for _ in range(N)]

TOTAL=pow(3,N,MOD)
ASum=sum(A)
AMax=max(A)

dp=[[0 for _ in range(ASum+1)] for _ in range(2)]

dp[0][0] = 2
dp[0][A[0]] = 1

prev=0
current=1
curMax=A[0]
for n in range(1,N):
	curMax += A[n]
	current = n % 2
	prev = (n+1) % 2
	for e in range(curMax+1):
		dp[current][e] = dp[prev][e]*2
		if A[n] <= e:
			dp[current][e] += dp[prev][e-A[n]]
		dp[current][e] %= MOD
sumStart = 0
plus = 0

if ASum % 2 == 0:
	# 合計が偶数
	sumStart=ASum//2
	dpOther=[0 for _ in range(ASum+1)]
	dpOther[0] = 1
	for n in range(N):
		for e in range(ASum//2,A[n]-1,-1):
			dpOther[e] = dpOther[e] + dpOther[e-A[n]]
			dpOther[e] %= MOD
	plus = (dpOther[ASum//2]*3) % MOD
else:
	# 合計が奇数の場合、ceil
	sumStart=ASum//2+1

exceptCnt=0
for s in range(sumStart,ASum+1):
	exceptCnt = (exceptCnt + dp[current][s]*3) % MOD

exceptCnt -= plus

print((TOTAL - exceptCnt) % MOD )



### FIXED CODE ###

import numpy as np

MOD=998244353
N=int(input())
A=np.array([int(input()) for _ in range(N)])
TOTAL=pow(3,N,MOD)
ASum=sum(A)
sumEnd=0
sumEnd=ASum//2+1

dp=np.array([0 for _ in range(sumEnd)],dtype=np.int64)
dp[0] = 1

for n in range(N):
	dp[A[n]:] += dp[:-A[n]]*2 % MOD

plus = 0
if ASum % 2 == 0:
	# 合計が偶数
	dpOther=np.array([0 for _ in range(sumEnd+1)],dtype=np.int64)
	dpOther[0] = 1
	for n in range(N):
		dpOther[A[n]:] += dpOther[:-A[n]] % MOD
	plus = (dpOther[ASum//2]*3) % MOD

exceptCnt=0
for s in range(0,sumEnd):
	exceptCnt = (exceptCnt + dp[s]*3) % MOD

exceptCnt -= plus
print((TOTAL - exceptCnt) % MOD )
### BUGGY CODE ###

from collections import Counter
N = int(input())
S = []
ans = 0
for i in range(N):
  s = list(input())
#  c = Counter(s)
  c = sorted(s)
  S.append(c)
for i in range(N-1):
  for j in range(i+1,N):
    if S[i] == S[j]:
      ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
memo = {}
ans = 0
for i in range(N):
  s = list(input())
  s.sort()
  s = str(s)
  if s in memo.keys():
    memo[s] += 1
  else:
    memo[s] = 1
for v in memo.values():
  if v >= 2:
    ans += v*(v-1)//2
print(ans)
### BUGGY CODE ###

mod = 10**9+7
n, m = map(int, input().split())
stairs = [0]*(n+1)
broken = []
stairs[0] = 1

for i in range(m):
    broken.append(int(input()))

for i in range(n+1):
    if i in broken:
        continue
    if i >= 2:
        stairs[i] = stairs[i-1] + stairs[i-2]
    elif i == 1:
        stairs[i] = stairs[i-1]

print(stairs[-1]%mod)




### FIXED CODE ###

mod = 10**9+7
n, m = map(int, input().split())
stairs = [0]*(n+1)
broken = []
stairs[0] = 1

def binSearch(broken, e):
    l, r = 0, m-1

    while l <= r:
        mid = (l+r)//2

        if broken[mid] > e:
            r = mid - 1
        elif broken[mid] < e:
            l = mid + 1
        else:
            return True
    return False


for i in range(m):
    b = int(input())
    if broken and b-1 == broken[-1]:
        print(0)
        exit(0)
    broken.append(b)

for i in range(n+1):
    if binSearch(broken, i):
        continue
    if i >= 2:
        stairs[i] = stairs[i-1] + stairs[i-2]
    elif i == 1:
        stairs[i] = stairs[i-1]

print(stairs[-1]%mod)