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

rflag = 0
s = [i for i in input()]
q = int(input())

for i in range(q):
    x = input().split()
    
    if(x[0] == '1'):
        rflag = rflag + 1
        # s = s[::-1]
    else:
        if((rflag % 2) == 0):
            rflag = 0
        else:
            s = s[::-1]
            rflag = 0
            
        s.insert(0,x[2]) if(x[1]=='1') else s.append(x[2])

s = s if((rflag % 2) == 0) else s[::-1]

print(''.join(s))


### FIXED CODE ###

from collections import deque

revFlag = False

s = deque(input())
q = int(input())

for i in range(q):
    a,b,c, *_ = input().split() + [None, None]
    
    if(a == '1'):
        revFlag = not revFlag
        
    else:
        b = int(b)
        if(revFlag):
            b = (int(b)%2)+1
        
        if(b == 1):
            s.appendleft(c)
        else:
            s.append(c)
            
    #print(_,*s, sep="")

if(revFlag):
    s.reverse()
    
print(*s, sep='')
### BUGGY CODE ###

H, N = map(int, input().split())

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

A, B = zip(*AB)

dp = [-1 for _ in range(H+max(A))]
dp[0] = 0

for i in range(H):
    if dp[i] == -1:
        continue
    for j in range(N):
        k = min(i+A[j], H)
        if dp[k] == -1:
            dp[k] = dp[i]+B[j]
        else:
            dp[k] = min(dp[k], dp[i]+B[j])

print(dp[H])

### FIXED CODE ###

H, N = map(int, input().split())

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

A, B = zip(*AB)

dp = [-1 for _ in range(H+max(A))]
dp[0] = 0

for i in range(H):
    if dp[i] == -1:
        continue
    for j in range(N):
        k = min(i+A[j], H)
        if dp[k] == -1:
            dp[k] = dp[i]+B[j]
        else:
            dp[k] = min(dp[k], dp[i]+B[j])

print(dp[H])
### BUGGY CODE ###

h, w = map(int, input().split())
ls = [input().strip() for _ in range(h)]
lrs = []
tbs = []

for y in range(h):
    left = 0
    while left < w:
        if ls[y][left] == '#':
            left += 1
            continue
        right = left
        while right < w:
            right += 1
            if right == w or ls[y][right] == '#':
                lrs.append([y, left, right, right - left])
                break
        left = right

for x in range(w):
    top = 0
    while top < h:
        if ls[top][x] == '#':
            top += 1
            continue
        bottom = top
        while bottom < h:
            bottom += 1
            if bottom == h or ls[bottom][x] == '#':
                tbs.append([x, top, bottom, bottom - top])
                break
        top = bottom
lrs.sort(key=lambda x: x[3], reverse=True)
tbs.sort(key=lambda x: x[3], reverse=True)

res = 0
for y, left, right, lh in lrs:
    for x, top, bottom, lv in tbs:
        if top <= y <= bottom and left <= x <= right:
            res = max(res, lh + lv - 1)
            break
print(res)

### FIXED CODE ###

h, w = map(int, input().split())
ls = [input().strip() for _ in range(h)]
counts = [[[-1] * w for _ in range(h)] for _ in range(4)]

for y in range(h):
    for x in range(w):
        if ls[y][x] == '#':
            counts[0][y][x] = 0
        else:
            if x == 0:
                counts[0][y][x] = 1
            else:
                counts[0][y][x] = counts[0][y][x - 1] + 1
        yy = h - 1 - y
        xx = w - 1 - x
        if ls[yy][xx] == '#':
            counts[1][yy][xx] = 0
        else:
            if x == 0:
                counts[1][yy][xx] = 1
            else:
                counts[1][yy][xx] = counts[1][yy][xx + 1] + 1

        if ls[y][x] == '#':
            counts[2][y][x] = 0
        else:
            if y == 0:
                counts[2][y][x] = 1
            else:
                counts[2][y][x] = counts[2][y - 1][x] + 1
        yy = h - 1 - y
        xx = w - 1 - x
        if ls[yy][xx] == '#':
            counts[3][yy][xx] = 0
        else:
            if y == 0:
                counts[3][yy][xx] = 1
            else:
                counts[3][yy][xx] = counts[3][yy + 1][xx] + 1

res = 0
for y in range(h):
    for x in range(w):
        val = -3
        for i in range(4):
            val += counts[i][y][x]
        res = max(res, val)

print(res)
### BUGGY CODE ###

N = int(input())
ans = 0

if N == 1:
  print(ans)
  exit()

for i in range(N-1):
  ans = ans + i + 1

print(ans)

### FIXED CODE ###

N = int(input())
ans = 0

ans = (N*(N-1))//2

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

# D - Decayed Bridges
from collections import deque

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

graph = [[] for _ in range(N)]
AB = deque()
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    AB.append([a, b])
    graph[a].append(b)
    graph[b].append(a)

def isDivided(a, b, graph):
    d = deque()
    d.append(a)
    done = [0] * N
    while len(d)>0:
        now = d.popleft()
        done[now] = 1
        for i in graph[now]:
            if i==b:
                return 0
            elif done[i]==0:
                d.append(i)
    return sum(done)

ans = 0
for i in range(M):
    a, b = AB.popleft()
    graph[a].remove(b)
    graph[b].remove(a)
    tmpa = isDivided(a, b, graph)
    tmpb = isDivided(b, a, graph)
    if tmpa!=0:
        ans += tmpa*tmpb
        print(ans)
    else:
        print(ans)



### FIXED CODE ###

# Decayed Bridges
from collections import deque

class UnionFind():
    def __init__(self, x):
        self.parent = [-1] * x

    def Find(self, x):
        if self.parent[x]<0:
            return x
        else:
            self.parent[x] = self.Find(self.parent[x])
            return self.parent[x]
    
    def Union(self, x, y):
        x = self.Find(x)
        y = self.Find(y)
        if x==y:
            return False
        if x>y:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        return True

    def isSameGroup(self, x, y):
        return self.Find(x)==self.Find(y)

    def Size(self, x):
        return self.parent[self.Find(x)]*-1

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

uf = UnionFind(N)

ans = deque()
tmp = N*(N-1)//2
ans.append(tmp)
for i in range(M-1):
    a, b = AB.pop()
    if uf.isSameGroup(a, b):
        ans.append(tmp)
    else:
        tmp -= uf.Size(a) * uf.Size(b)
        ans.append(tmp)
        uf.Union(a, b)

for i in range(M):
    print(ans.pop())
### BUGGY CODE ###

N, Q = map(int, input().split())
S =  input()
qlist = [list(map(int, input().split())) for i in range(Q)]
AC = 'AC'

for i in qlist:
    tmp = S[i[0]-1:i[1]]
    print(tmp.count(AC))

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
point = [list(map(int,input().split())) for i in range(Q)]
ac_list = [0]*(N+1)
 
for i in range(N):
  if S[i:i+2] == 'AC':
    ac_list[i+1] = ac_list[i] + 1
  else:
    ac_list[i+1] = ac_list[i]
 
 
for i in range(Q):
  print(ac_list[point[i][1]-1] - ac_list[point[i][0]-1])
### BUGGY CODE ###

from numba import jit
from collections import deque
import numpy as np

def main():
  N=int(input())
  S=list(map(int,input().split()))
  count=0
  P=np.ones((N*N+1))
  d=np.zeros((N*N+1))
  que=deque()
  for i in range(N*N):
    player=S[i]
    P[player]=0
    que.clear()
    que.append((player,0))
    d[player]=i+1

    while que:
      kouho,j=que.popleft()
      if kouho%N==0:
        break
      if kouho%N==1:
        break
      if kouho+N>N*N:
        break
      if kouho<N:
        break

      if d[kouho+N]<i+1:
        if P[kouho+N]==1:
          que.append((kouho+N,j+1))
          d[kouho+N]=i+1
        else:
          que.appendleft((kouho+N,j))
          d[kouho+N]=i+1

      if d[kouho-N]<i+1:
        if P[kouho-N]==1:
          que.append((kouho-N,j+1))
          d[kouho-N]=i+1
        else:
          que.appendleft((kouho-N,j))
          d[kouho-N]=i+1

      if d[kouho+1]<i+1:
        if P[kouho+1]==1:
          que.append((kouho+1,j+1))
          d[kouho+1]=i+1
        else:
          que.appendleft((kouho+1,j))
          d[kouho+1]=i+1

      if d[kouho-1]<i+1:
        if P[kouho-1]==1:
          que.append((kouho-1,j+1))
          d[kouho-1]=i+1
        else:
          que.appendleft((kouho-1,j))
          d[kouho-1]=i+1
    count+=j

  print(count)

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main')(main)
    cc.compile()

main()


### FIXED CODE ###

from numba import njit
import numpy as np

@njit
def main(N, P):
    lista = [1, -1, N, -N]
    d = np.zeros((N, N), dtype=np.int32)
    d = d.ravel()
    sit = np.ones_like(d)
    stack = np.empty_like(d)
    count = 0
    for i in range(N*N):
        d[i] = min(i % N, (N-1-i) % N, i//N, N-1-i//N)
    for player in P:
        sit[player-1] = 0
        count += d[player-1]
        stack[0] = player
        num = 0
        while num >= 0:
            p = stack[num]
            num -= 1
            a = d[p-1]+sit[p-1]
            for i in lista:
                if p+i < 1 or p + i > N*N:
                    continue
                if d[p+i-1] > a:
                    d[p+i-1] = a
                    num += 1
                    stack[num] = p+i
    print(count)

N = int(input())
P = np.array(input().split(), np.int32)

main(N, P)
### BUGGY CODE ###

N = int(input())
a = [list() for i in range(N+1)]
for i in range(N):
    b = int(input())
    a[i+1].append(b)

ans = 0
check = []
tmp = 1
check.append(tmp)
flag = False
while(1):
    tmp = a[tmp][0]
    ans += 1
    if tmp==2:
        flag = True
        break
    if tmp in check:
        break
    check.append(tmp)
if flag:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

N = int(input())
a = []
for i in range(N):
    b = int(input())
    a.append(b)
ans = 0
tmp = 1
flag = False
while(1):
    tmp = a[tmp-1]
    ans += 1
    if tmp==2:
        flag = True
        break
    if ans > N:
        break
if flag:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

class SegmentTree():
    def __init__(self, S):
        # S:英小文字からなる配列
        # tmp = len(S)
        # cnt = 0
        # while tmp // 2 > 0:
        #     tmp //= 2
        #     cnt += 1
        self.size = 19
        # sizeはSの長さ<=2**nをみたす最小のn
        self.array = [set()] * (2**(self.size + 1) - 1)
        for i, c in enumerate(S):
            self.array[i + 2**self.size - 1] = {c}
        for i in range(2**self.size - 1)[::-1]:
            self.array[i] = self.array[2 * i + 1] | self.array[2 * i + 2]

    def subquery(self, l, r, k, i, j):
        # 区間[i,j)の中で区間[l,r)の文字列の集合を返す
        if j <= l or r <= i:
            return set()
        elif l <= i and j <= r:
            return self.array[k]
        else:
            l_set = self.subquery(l, r, 2 * k + 1, i, (i + j) // 2)
            r_set = self.subquery(l, r, 2 * k + 2, (i + j) // 2, j)
            return l_set | r_set

    def query(self, l, r):
        # [l,r)に含まれる文字の種類数
        return len(self.subquery(l, r, 0, 0, 2**self.size))

    def update(self, i, c):
        tmp = i + 2**self.size - 1
        self.array[tmp] = {c}
        while tmp > 0:
            tmp = (tmp - 1) // 2
            self.array[tmp] = self.array[2 * tmp + 1] | self.array[2 * tmp + 2]


N = int(input())
S = list(input())
Q = int(input())
tree = SegmentTree(S)
for q in range(Q):
    t, i, c = input().split()
    if t == '1':
        i = int(i) - 1
        tree.update(i, c)
    else:
        l, r = int(i) - 1, int(c)
        print(tree.query(l, r))
# S = ['a', 'b', 'c', 'd', 'b', 'b', 'd']
# tree = SegmentTree(S)
# print(tree.query(2, 6))


### FIXED CODE ###

import sys
input = sys.stdin.readline


class SegmentTree():
    def __init__(self, S):
        self.size = 19
        self.array = [set()] * (2**(self.size + 1) - 1)
        for i, c in enumerate(S):
            self.array[i + 2**self.size - 1] = {c}
        for i in range(2**self.size - 1)[::-1]:
            self.array[i] = self.array[2 * i + 1] | self.array[2 * i + 2]

    def subquery(self, l, r, k, i, j):
        # 区間[i,j)の中で区間[l,r)の文字列の集合を返す
        if j <= l or r <= i:
            return set()
        elif l <= i and j <= r:
            return self.array[k]
        else:
            l_set = self.subquery(l, r, 2 * k + 1, i, (i + j) // 2)
            r_set = self.subquery(l, r, 2 * k + 2, (i + j) // 2, j)
            return l_set | r_set

    def query(self, l, r):
        # [l,r)に含まれる文字の種類数
        return len(self.subquery(l, r, 0, 0, 2**self.size))

    def update(self, i, c):
        tmp = i + 2**self.size - 1
        self.array[tmp] = {c}
        while tmp > 0:
            tmp = (tmp - 1) // 2
            self.array[tmp] = self.array[2 * tmp + 1] | self.array[2 * tmp + 2]


def main():
    N = int(input())
    S = [ord(_) - 97 for _ in list(input())]
    Q = int(input())
    tree = SegmentTree(S)
    for q in range(Q):
        t, i, c = input().split()
        if t == '1':
            i = int(i) - 1
            tree.update(i, ord(c) - 97)
        else:
            l, r = int(i) - 1, int(c)
            print(tree.query(l, r))


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

S = input()
Q = int(input())
st = S
for i in range(1, Q+1):
    query = input()
    if len(query) == 1:
        st = st[::-1]
    else:
        n, F, C = query.split()
        # n = int(n)
        # F = int(F)
        if F == '1':
            st = C + st
        else:
            st = st + C
print(st)

### FIXED CODE ###

from collections import deque
S = list(input())
Q = int(input())

d = deque()
d.extend(S)
cnt = 0
for i in range(1, Q+1):
    query = input()
    if len(query) == 1:
        cnt += 1
    else:
        n, F, C = query.split()
        if cnt % 2 == 0:  # 反転cntが偶数,F=1で末尾
            if F == '1':
                d.appendleft(C)
            else:
                d.append(C)
        else:  # 反転cntが偶数,F=1で先頭
            if F == '1':
                d.append(C)
            else:
                d.appendleft(C)

if cnt % 2 == 1:  # cnt奇数の場合、反転
    d.reverse()
else:
    pass

l = list(d)
S = ''.join(l)
print(S)
### BUGGY CODE ###

a=1
n=input()
for i in input().split():
  a*=int(i)
if a>10**18:
  print(-1)
else:
  print(a)

### FIXED CODE ###

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

count=0
if 0 in s:
  print(0)
  count=1
else:
  a=1
  for i in s:
    a*=i
    if a>10**18:
      print(-1)
      break
if a<=10**18 and count!=1:
  print(a)
### BUGGY CODE ###

N=int(input())
P=list(map(int,input().split()))
ans=1
for i in range(1,N):
    if min(P[:i])==min(P):
        break
    if min(P[:i])>P[i]:
        ans+=1
print(ans)

### FIXED CODE ###

N=int(input())
P=list(map(int,input().split()))
x=N+1
cnt=0

for i in range(N):
    if P[i]<x:
        cnt+=1
        x=P[i]
print(cnt)
### BUGGY CODE ###

n, k=[int(x) for x in input().split()]
a=input().split()
s=set(a)
d=[]
for i in s:
  d.append(a.count(i))
p=len(s)-k
if p<=0:
  print("0")
  exit()
d=sorted(d)
print(sum(d[:p]))


### FIXED CODE ###

n, k=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]
d={i:0 for i in set(a)}
for i in a: d[i]+=1
print(n-sum([t[1] for t in sorted(d.items(), key=lambda x:-x[1])][:k]))
### BUGGY CODE ###

import  fractions
from functools import reduce
import sys
input = sys.stdin.readline
def main():
    n=int(input())
    a=list(map(int,input().split()))
    tmp = lcm(*a)
    mod=10**9 + 7
    m=0
    ans=0
    for i,v in enumerate(a):
        m=tmp//v
        ans+=m%mod
    ans = ans % mod
    print(ans)

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


if __name__=='__main__':
    main()


### FIXED CODE ###

import  fractions
from functools import reduce
import sys
input = sys.stdin.readline
def main():
    n=int(input())
    a=list(map(int,input().split()))
    # tmp = lcm(*a)
    mod=pow(10,9) + 7
    m=0
    ans=0
    tmp = a[0]
    for i in range(1,len(a)):
        tmp = (tmp*a[i]) // fractions.gcd(tmp,a[i])
    
    for i,v in enumerate(a):
        m=tmp//v
        ans+=m
    ans = ans % mod
    print(ans)


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

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

A.sort()
A_acc = list(accumulate(A))
upper_len = len("{:b}".format(max(A)))

upper = 10**6  # 必要そうな階乗の限界を入れる
factorial = [1]
for i in range(1, upper):
    factorial.append(factorial[i-1] * i % mod)

def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % mod
    elif y % 2 == 0:
        return power(x, int(y/2)) ** 2 % mod
    else:
        return power(x, int((y-1)/2)) ** 2 * x % mod

def C(n, r):
    return (((factorial[n] * x_inv[r]) % mod) * x_inv[n-r]) % mod
x_inv = [0] * (upper)
x_inv[-1] = power(factorial[-1], mod-2)
for i in range(upper-2, -1, -1):
    x_inv[i] = x_inv[i+1] * (i+1) % mod

cnt = [defaultdict(int) for _ in range(upper_len)]
for i in range(N):
	num = "{:b}".format(A[i]).zfill(upper_len)
	for j in range(len(num)):
		cnt[upper_len-j-1][num[j]] += 1

ans = 0
for i in range(upper_len):
	ans = (ans + (2**i)*cnt[i]["0"]*cnt[i]["1"])%mod
print(ans)


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	N = INT()
	A = LIST()

	upper_len = len("{:b}".format(max(A)))

	cnt = [defaultdict(int) for _ in range(upper_len)]
	for i in range(N):
		num = "{:b}".format(A[i]).zfill(upper_len)
		for j in range(len(num)):
			cnt[upper_len-j-1][num[j]] += 1

	ans = 0
	for i in range(upper_len):
		ans = (ans + (1<<i)*cnt[i]["0"]*cnt[i]["1"])%mod
	print(ans)

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

#!usr/bin/env python3


import sys


def I(): return int(sys.stdin.readline())


def solve():
    n = I()
    sli = [input() for i in range(n)]
    setli = set(sli)
    rank = {}
    for i in setli:
        j = sli.count(i)
        rank[i] = j
    print(
        '\n'.join(sorted([k for k, v in rank.items() if v == max(rank.values())])))


# Solve
if __name__ == "__main__":
    solve()


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def LS(): return [list(x) for x in sys.stdin.readline().split()]


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


def LIR(n):
    return [LI() for i in range(n)]


def SR(n):
    return [S() for i in range(n)]


def LSR(n):
    return [LS() for i in range(n)]


sys.setrecursionlimit(1000000)
mod = 1000000007


def solve():
    n = I()
    sli = [input() for i in range(n)]
    rank = defaultdict(lambda: 0)
    for i in sli:
        rank[i] += 1
    rank = list(rank.items())
    rank.sort(key=lambda x: (-x[1], x[0]))
    for i, j in rank:
        if j == rank[0][1]:
            print(i)


# Solve
if __name__ == "__main__":
    solve()
### BUGGY CODE ###

from itertools import accumulate
from collections import defaultdict


def main():
    n = int(input())
    prime_counter = defaultdict(int)  # key ^ value
    acc = tuple(accumulate(range(1, 42)))  # because 10^12 < 2^39

    def facs(n):
        yield 2
        for x in range(3, int(pow(n, 0.5)) + 1, 2):
            yield x
        yield n

    for fac in facs(n):
        while n % fac == 0:
            n //= fac
            prime_counter[fac] += 1
            # ここで if fac * fac > n: braek を入れると，
            # 計算量の少ないケースでは早く，多いケースでは遅くなる。
    if n != 1:
        prime_counter[n] += 1

    ans = 0
    for c in prime_counter.values():
        for i, x in enumerate(acc):
            if c < x:
                tmp = i
                break
        ans += tmp
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import Counter
from itertools import accumulate


def prime_factorize(n):
    """素因数分解し，ユニークな素因数のsetを返す。"""
    ans = []
    ans_add = ans.append
    while n % 2 == 0:
        ans_add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            ans_add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        ans_add(n)
    return ans


def main():
    n = int(input())
    primes = prime_factorize(n)
    acc = tuple(accumulate(range(1, 42)))
    counted = Counter(primes)
    ans = 0

    for c in counted.values():
        for i, x in enumerate(acc):
            if c >= x:
                tmp = i + 1
            else:
                break
        ans += tmp

    print(ans)


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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, s = map(int, readline().split())
a = list(map(int, readline().split()))
dp = [[0] * (s + 2) for _ in range(n + 1)]
dp[0][0] = 1
mod = 998244353
for i, aa in enumerate(a):
    for j in range(s + 1):
        ss = j + aa
        dp[i + 1][min(j + aa, s + 1)] += dp[i][j]
        dp[i + 1][j] += dp[i][j] * 2
        dp[i + 1][j] %= mod
print(dp[-1][-2])


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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

from heapq import heappush, heappop
min2 = lambda x,y: x if x < y else y
H,N = map(int,input().split())

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

AB.sort(key=lambda x: -x[1])

cost = [float('inf')]*(H+1)
last = [None]*(H+1)

q = [(0, 0)]

while q:
    c, t = heappop(q)
    if cost[t] <= c:
        continue
    cost[t] = c
    if t == H:
        break
    if last[t] is None:
        for i,(a,b) in enumerate(AB):
            d = min2(H,t+a)
            if cost[d] > c+b:
                last[d] = i
                heappush(q, (c+b, d))
            if cost[d] == c+b:
                last[d] = min2(last[d], i)
    else:
        for i,(a,b) in enumerate(AB[last[t]:]):
            d = min2(H,t+a)
            if cost[d] > c+b:
                last[d] = i
                heappush(q, (c+b, d))
            if cost[d] == c+b:
                last[d] = min2(last[d], i)

print(cost[H])


### FIXED CODE ###

min2 = lambda x,y: x if x < y else y
H,N = map(int,input().split())


dp = [float('inf')]*(H+1)
dp[0] = 0

for _ in range(N):
    a,b = map(int,input().split())
    for i,v in enumerate(dp):
        j = min2(H,i+a)
        dp[j] = min2(dp[j],v+b)

print(dp[-1])