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

import bisect
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
inf = 10**6


N = int(input())
VW = [(inf, inf)] + [list(map(int, input().split())) for _ in range(N)]
Q = int(input())
d = {i + 1: [] for i in range(N)}


def rec(i):
    if len(d[i]) > 0:
        return d[i]
    if i == 1:
        vi, wi = VW[i]
        d[i] = [(0, 0), (wi, vi)]
        return d[i]
    tmp = []
    vi, wi = VW[i]
    for w, v in rec(i // 2):
        tmp.append((w, v))
        tmp.append((w + wi, v + vi))
    tmp.sort()

    m = 1
    for j in range(1, len(tmp)):
        if tmp[m - 1][1] < tmp[j][1]:
            tmp[m] = tmp[j]
            m += 1
    d[i].extend(tmp[:m])
    return d[i]


ans = [-1] * Q
for q in range(Q):
    n, L = map(int, input().split())
    wei, val = zip(*rec(n))
    i = bisect.bisect_right(wei, L) - 1
    ans[q] = val[i]

print(*ans, sep="\n")

### FIXED CODE ###

import sys
import bisect
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


def merge(a, b):
    res = []
    i, j = 0, 0
    while i < len(a) or j < len(b):
        if j >= len(b) or (i < len(a) and a[i][0] < b[j][0]):
            w, v = a[i]
            i += 1
        else:
            w, v = b[j]
            j += 1
        if not res or (res[-1][1]) < v:
            res.append((w, v))
        elif res[-1][0] == w and res[-1][1] <= v:
            res.pop()
            res.append((w, v))
    return res


def best(L, a, b):
    res = 0
    i = 0
    j = len(b) - 1
    while i < len(a):
        w, v = a[i]
        if j < 0:
            break
        if b[j][0] + w > L:
            j -= 1
            continue
        res = max(res, v + b[j][1])
        i += 1
    return res


def main():
    N = int(input())
    VW = [(-1, -1)] + [list(map(int, input().split())) for _ in range(N)]
    Q = int(input())
    query = tuple(tuple(map(int, input().split())) for _ in range(Q))

    dp = [[] for _ in range(2048)]
    dp[0] = [(0, 0)]
    for i in range(1, min(N + 1, 2048)):
        vi, wi = VW[i]
        a1 = dp[i // 2]
        a2 = [(w + wi, v + vi) for w, v in a1]
        dp[i] = merge(a1, a2)

    for n, L in query:
        if n < 2048:
            w, v = zip(*dp[n])
            i = bisect.bisect_right(w, L) - 1
            print(v[i])
        else:
            a = [(0, 0)]
            while n >= 2048:
                vi, wi = VW[n]
                b = [(w + wi, v + vi) for w, v in a]
                a = merge(a, b)
                n //= 2
            print(best(L, a, dp[n]))


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

a=list(map(int,input().split()))
a.sort()
mid=1
ans=10**9
for i in range(2):
  mid*=a[i]
  
for i in range(1,a[-1]+1):
  b=mid*i
  c=mid*(a[-1]-i)
  sa=abs(b-c)
  if ans>sa:
    ans=sa
print(ans)

### FIXED CODE ###

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

for i in range(3):
  if a[i]%2==0:
    print(0)
    exit()

a.sort()
ma=a[0]*a[1]
print(ma*(a[2]//2+1)-ma*(a[2]//2))
### BUGGY CODE ###

N,K = [int(e) for e in input().split()]
asiba = [int(e) for e in input().split()]
dp =[0] *N

#初期化
dp[0]=0
dp[1]=abs(asiba[1]-asiba[0])

for i in range(2,N):
    dp[i] = min(abs(asiba[i] - asiba[j]) + dp[j] for j in range(max(0, i - K), i))
    
print(dp[N-1])


### FIXED CODE ###

def main():
  n, k = [int(e) for e in input().split()]
  h = [int(e) for e in input().split()]
  cost = [0] * n
  for i in range(1, n):
    cost[i] = min(abs(h[i] - h[j]) + cost[j] for j in range(max(0, i - k), i))
  print(cost[n - 1])
main()
### BUGGY CODE ###

s = list(input())

minLength = 4
maxLength = len(s)

cnt = 0

for length in range(minLength,maxLength+1):
    for position in range(maxLength - length + 1):
        num = int(''.join(s[position:position+length]))
        if num % 2019 == 0:
            cnt += 1

print(cnt)

### FIXED CODE ###

s = list(input())
mods = [0]*(len(s))
countRemainder = [0] * 2019
cnt = 0


m = 1
mod = 0
for i in range(len(s)):
    mod += int(s[len(s) - i - 1]) * m

    mod %= 2019
    m *= 10
    m %= 2019

    countRemainder[mod] += 1

countRemainder[0] += 1

for i in range(2019):
    cnt += int(countRemainder[i] * (countRemainder[i] - 1) / 2)

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

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

a.sort()
def Eratosthenes(x):
    cnt = 0
    nmax = x[-1]
    is_prime = [True] * (nmax+1)
    for i in x:
        if not is_prime[i]:
            continue
        if not x.count(i) > 1:
            cnt += 1
        for j in range(i*2, nmax+1, i):
            is_prime[j] = False
    print(cnt)

Eratosthenes(a)

### FIXED CODE ###

from collections import Counter

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

a.sort()
cnt = 0
nmax = a[-1]
table = [True] * (nmax+1)
c = Counter(a)

duplicate = []
for i in c.keys():
    if c[i] > 1:
        duplicate.append(i)
for i in a:
    if not table[i]:
        continue
    if not i in duplicate:
        cnt += 1
    for j in range(i*2, nmax+1, i):
        table[j] = False
print(cnt)
### BUGGY CODE ###

def main():
  from fractions import gcd
  mod = 10**9 + 7
  N = int(input())
  A = list(map(int, input().split()))

  lcm = A[0]
  for i in range(1, N):
    lcm = (lcm*A[i]) // gcd(lcm, A[i])

  ans = 0
  for i in range(N):
    ans += lcm // A[i]
    ans %= mod
  print(ans)
main()

### FIXED CODE ###

from fractions import gcd

def lcm(c,d):
    return c//gcd(c,d)*d
mod=10**9+7
n=int(input())
a=[int(i) for i in input().split()]
l=a[0]
for i in range(1,n):
    l=lcm(l,a[i])
ans=0
for i in range(n):
    ans+=l//a[i]
    #ans%=mod
print(ans%mod)
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
a=0
b=sum(p)/len(p)

for i in range(n-k+1):
    if sum(p[i:i+k])/k >= b:
        a = max(a,sum([(k+1)/2 for k in p[i:i+k]]))
print(a)

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
a=0
for i in range(n-k+1):
    if i==0:
        xe=sum(p[0:k])
    else:
        xe=xe-p[i-1]+p[i+k-1]
    a=max(a,xe)
print((k+a)/2)
### BUGGY CODE ###

mod = 10**9+7
n = int(input())
s = input()
d = {}
for i in list(s):
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
result = 0
for i in range(1, 2**len(d)):
    c = 1
    num = i
    for n, j in d.items():
        if num%2==1:
            c *= j
            c %= mod
        num >>= 1
    result += c
    result %= mod

print(result%mod)

### FIXED CODE ###

mod = 10**9+7
n = int(input())
s = input()
d = {}
for i in s:
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
result = 1
for i, j in d.items():
    result = (result*(j+1))%mod

print((result-1)%mod)
### BUGGY CODE ###

a,b = map(int,input().split())

A = 1

for i in range(a,b+1):
  A *= i

if A == 0:
  print("Zero")
elif A > 0:
  print("Positive")
else:
  print("Negative")

### FIXED CODE ###

a,b = map(int,input().split())

if a > 0:
  print("Positive")
elif (a <= 0 and b >= 0):
  print("Zero")
else:
  if (b - a) % 2 == 0:
    print("Negative")
  else:
    print("Positive")
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
s=[[0]for _ in range(n)]
#print(s)

import math
import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
    
for i in range(n):
    if i==0:
        s[0]=l[1:]
    
    else:
        s[i]=l[:i]+l[i+1:]
ans=1
for i in s:
    ans=max(gcd_list(i),ans)
print(ans)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
s=[[0]for _ in range(n)]
#print(s)
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort(reverse=True)
    return divisors

l.sort()
ans=1

b=l[1]
bl=make_divisors(b)
for i in bl:
    check=True
    for j in range(1,n):
        if l[j]%i!=0:
            check=False
            break
    if check:
        ans=max(ans,i)
        break
a=min(l)
al=make_divisors(a)
#print(al)
for i in al:
    cnt=0
    for j in range(n):
        if l[j]%i!=0:
            cnt+=1
        if cnt>1:
            break
    if cnt==0 or cnt==1:
        ans=max(ans,i)
        break
print(ans)
### BUGGY CODE ###

N, A = map(int, input().split())
x = [int(i) for i in input().split()]

dp = [[0]*(50*N + 1) for i in range(N + 1)]

dp[0][0] = 1

for i in range(N):
    for k in range(N, 0, -1):
        for v in range(50*N, x[i] - 1, -1):
            dp[k][v] += dp[k - 1][v - x[i]]

ans = sum(dp[k][k * A] for k in range(1, N + 1))

print(ans)

### FIXED CODE ###

import sys
from collections import Counter

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N, A = map(int, input().split())
    x = [int(i) for i in input().split()]

    # 3d DP
    max_x = max(x)

    dp = [[[0] * (max_x * N + 1) for j in range(N + 1)]
                                 for i in range(N + 1)]

    dp[0][0][0] = 1

    for i in range(0, N):
        for k in range(0, N + 1):
            for y in range(max_x * N + 1):
                if dp[i][k][y]:
                    dp[i + 1][k][y] += dp[i][k][y]
                    dp[i + 1][k + 1][y + x[i]] += dp[i][k][y]

            # print(dp[i][k])
        # print()

    cnt = 0
    for k in range(1, N + 1):
        for y in range(1, max_x * N + 1):
            if y // k == A and y % k == 0:
                cnt += dp[N][k][y]

    print(cnt)

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

#! python3
# maximum_profit.py

n = int(input())
R = [int(input()) for i in range(n)]

max_val = R[1] - R[0]
for i in range(n-1):
    for j in range(i+1, n):
        val = R[j] - R[i]
        if max_val < val:
            max_val = val

print(max_val)


### FIXED CODE ###

#! python3
# maximum_profit.py

n = int(input())
R = [int(input()) for i in range(n)]

min_i = 0
max_val = R[1]-R[0]
max_j = -1
for i in range(n-1):
    if R[min_i] < R[i]:
        continue
    elif R[min_i] > R[i]:
        min_i = i

    if max_j <= i:
        max_j = i+1
        for j in range(i+1, n):
            if R[max_j] < R[j]:
                max_j = j

    if max_val < R[max_j] - R[min_i]:
        max_val = R[max_j] - R[min_i]

print(max_val)
### 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]


def main():
    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))


if __name__ == '__main__':
    main()

### 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 ###

N = int(input())
S = [sorted(str(input())) for _ in range(N)]

B = []
for i in range(N):
    s = ''.join(S[i])
    B.append(s)

ans = 0
for i in range(N-1):
    for j in range(i+1,N):
        if B[i] == B[j]:
            ans += 1
print(ans)

### FIXED CODE ###

from collections import Counter

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

A = []
for i in S:
    ew_str = ''.join(sorted(i[-1]))
    A.append(ew_str)

cnt = Counter(A)
cnt = list(cnt.values())
#print(cou)

ans = 0
for i in cnt:
    ans +=i*(i-1)//2
print(ans)
### BUGGY CODE ###

def tasu(x):
    return x / 2 * (x + 1)

def kitaiti(n , k , p):

    ans = 0
    kitai = [0]*n

    for i in range(n):
        kitai[i] = tasu(p[i]) / p[i]

    for i in range(n - k + 1):
        count = 0
        for w in range(i , i + k):
            count += kitai[w]

        ans = max(ans , count)

    return ans

def main():
    n , k = map(int , input().split())
    p = list(map(int,input().split()))
    print(kitaiti(n , k , p))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def tasu(x):
    return x / 2 * (x + 1)

def kitaiti(n , k , p):

    ans = 0
    count = 0
    kitai = [0]*n
    kitaisum = [0]*n
    mod = 10**9+7

    for i in range(n):
        kitai[i] = tasu(p[i]) / p[i]

    for i in range(n):
        if i == 0:
            kitaisum[i] += kitai[i]
        else:
            kitaisum[i] += kitai[i] + kitaisum[i-1]

    for i in range(n - k + 1):

        ans = max(ans , (kitaisum[i + k - 1] - kitaisum[i-1]) if i != 0 else kitaisum[i + k - 1])

    return ans

def main():
    n , k = map(int , input().split())
    p = list(map(int,input().split()))
    print(kitaiti(n , k , p))

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

import sys
sys.setrecursionlimit(10000000)
from collections import defaultdict
N,Q = map(int,input().split())

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

adds = {}
ans = {}
for i in range(1,N+1):
    adds[i] = 0
    ans[i] = 0
for q in range(Q):
    p,x = map(int,input().split())
    adds[p] += x

def dig(i,tmp):
    tmp += adds[i]
    ans[i] = tmp
    for v in tree[i]: dig(v,tmp)

tmp = 0
dig(1,tmp)

for i in range(1,N+1):
    print(ans[i], end=' ')
print()

### FIXED CODE ###

from queue import deque
N,Q = map(int,input().split())
tree = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)

ans = {i+1:0 for i in range(N)}
for i in range(Q):
    p,x = map(int,input().split())
    ans[p] += x

checked = [False for i in range(N+1)]
myq = deque()
myq.append(1)

while myq:
    v = myq.pop()
    checked[v] = True
    for n in tree[v]:
        if not checked[n]:
            ans[n] += ans[v]
            myq.append(n)
print(' '.join(str(ans[i]) for i in range(1,N+1)))
### BUGGY CODE ###

# https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d

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

from collections import deque

ans = 0

# Rnum: 000 ~ 999
for Rnum in range(0,1000):
    R = deque(str(Rnum).zfill(3))

    for s in S:
        if s == R[0]:
            R.popleft()
        if not R:
            ans += 1
            break

print(ans)

### FIXED CODE ###

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

def my_index(LIST, VALUE,START):
    if VALUE in LIST[START:]:
        return LIST.index(VALUE,START)
    else:
        return float("inf")

answer = 0
# 暗証番号がiとなるか判定
for i in range(1000):
    PIN = str(i).rjust(3,"0")
    if PIN[0] in S:
        one_digit = S.index(PIN[0])
    else:
        continue
    if PIN[1] in S:
        two_digit = my_index(S,PIN[1],one_digit+1)
        if two_digit == float("inf"):
            continue
    else:
        continue
    if PIN[2] in S:
        three_digit = my_index(S,PIN[2],two_digit+1)
        if three_digit == float("inf"):
            continue
    else:
        continue
    answer += 1

print(answer)
### BUGGY CODE ###

MOD = 1000000007

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

digits = [0] * 60
for i in A:
    for j in range(60):
        if i>>j&1 == 1:
            digits[j] += 1

ans = 0
for i in range(60):
    ans += digits[i] * (N - digits[i]) * (1<<i)
    ans %= MOD

print(ans)

### FIXED CODE ###

MOD = 1000000007

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

digits = [0] * 60
for i in A:
    for j in range(60):
        if i>>j&1 == 1:
            digits[j] += 1

ans = 0
for i in range(60):
    ans += digits[i] * (N - digits[i]) * (1<<i)
    ans %= MOD

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

def Is(): return map(int, input().split())  # '123 456' -> 123, 456
def LI(): return list(map(int, input().split()))  # '123 456' -> [123, 456]


N, M = Is()
H = LI()
AB = [[0]*N for _ in range(N)]
for i in range(M):
    a, b = Is()
    a -= 1
    b -= 1
    AB[a][b] = H[b]
    AB[b][a] = H[a]

ans = 0
notgood = [False]*N

# print(AB)

for i in range(N):
    if notgood[i]:
        continue
    if sum(AB[i]) == 0:
        ans += 1
        continue
    if max(AB[i]) < H[i]:
        ans += 1
        for j in range(N):
            if AB[i][j] != 0:
                notgood[j] = True


print(ans)

### FIXED CODE ###

def Is(): return map(int, input().split())  # '123 456' -> 123, 456
def LI(): return list(map(int, input().split()))  # '123 456' -> [123, 456]


N, M = Is()
H = LI()
AB = [set() for _ in range(N)]
for i in range(M):
    a, b = Is()
    a -= 1
    b -= 1
    AB[a].add(b)
    AB[b].add(a)

ans = 0
notgood = [False]*N

# print(AB)

for i in range(N):
    # print("{} start".format(i))
    # print(AB[i])
    if notgood[i]:
        continue
    if len(AB[i]) == 0:
        ans += 1
        continue
    for x in AB[i]:
        # print(H[x], H[i])
        if H[x] > H[i]:
            notgood[i] = True
            break
        elif H[x] == H[i]:
            notgood[x] = True
            notgood[i] = True
            break
        else:
            notgood[x] = True
    else:
        ans += 1
        # print("{} is GOOD!!!".format(i))

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

n = int(input())

p = list(map(int, input().split(' ')))

ans = 0
for i in range(n):
    flag = True

    if i > 0:

        if min(p[:i+1]) != p[i]:
            flag = False

    if flag:
        ans += 1

print(ans)


### FIXED CODE ###

n = int(input())

p = list(map(int, input().split(' ')))


ans = 1
min_num = p[0]

for i in range(n-1):
    if p[i+1] < min_num:
        ans += 1
        min_num = p[i+1]

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

import array
from functools import reduce
from operator import xor

N = int(input())
A = array.array("L", map(int, input().split()))

Q = array.array("L", [0]) * N

for i in range(N):
    print(reduce(xor, array.array("L", (A[n] for n in range(N) if n!=i))))


### FIXED CODE ###

import array
from functools import reduce
from operator import xor

N = int(input())
A = array.array("L", map(int, input().split()))

Q = array.array("L", [0]) * N

R = reduce(xor, A)
for i in range(N):
    print(R^A[i])
### BUGGY CODE ###

import sys
from collections import defaultdict
from queue import deque
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


ans = 0


def main():
    N, S = geta(int)
    A = list(geta(int))
    A.sort()
    mod = 998244353

    def dfs(n, s, ret):

        global ans

        if s == 0:
            ans = (ans + pow(2, N - ret)) % mod
            return
        if n == 0:
            return

        if sum(A[:n]) < s:
            return

        dfs(n - 1, s - A[n - 1], ret + 1)

        dfs(n - 1, s, ret)

    dfs(N, S, 0)

    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from collections import defaultdict
from queue import deque
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def egcd(a: int, b: int):
    """
    A solution of ax+by=gcd(a,b). Returns
    (gcd(a,b), (x, y)).
    """
    if a == 0:
        return b, 0, 1
    else:
        g, x, y = egcd(b % a, a)
        return g, y - (b // a) * x, x


def modinv(a: int, mod: int = 10**9 + 7):
    """
    Returns a^{-1} modulo m.
    """
    g, x, y = egcd(a, mod)
    if g > 1:
        raise Exception('{}^(-1) mod {} does not exist.'.format(a, mod))
    else:
        return x % mod


def main():
    N, S = geta(int)
    A = list(geta(int))
    A.sort()
    mod = 998244353

    inv2 = modinv(2, mod)

    dp = [[0] * (S + 1) for _ in range(N + 1)]
    for s in range(S + 1):
        dp[0][s] = 0

    _t = pow(2, N, mod)
    for n in range(N + 1):
        dp[n][0] = _t

    for i in range(1, N + 1):
        for j in range(1, S + 1):
            if j >= A[i - 1]:
                dp[i][j] = dp[i - 1][j - A[i - 1]] * inv2 + dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j]

            dp[i][j] %= mod

    print(dp[N][S])


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

from collections import deque
S = input()
Q = int(input())
ans = deque(S)
for i in range(Q):
    query = input()
    if query == "1":
        ans.reverse()
    elif query[2] == "1":
        ans.appendleft(query[4])
    else:
        ans.append(query[4])

print("".join(ans))


### FIXED CODE ###

from collections import deque
S = input()
Q = int(input())
ans = deque(S)
rev_flag = False
for i in range(Q):
    query = input()
    if query == "1":
        rev_flag = not rev_flag
    elif not rev_flag:
        if query[2] == "1":
            ans.appendleft(query[4])
        else:
            ans.append(query[4])
    else:
        if query[2] == "2":
            ans.appendleft(query[4])
        else:
            ans.append(query[4])

if rev_flag:
    ans.reverse()

print("".join(ans))