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

from collections import deque
S=input()
S_list=deque()
for k in range(len(S)):
    S_list.append(S[k])
Q=int(input())
kouho=[input().split() for i in range(Q)]
"""for i in range(Q):
    kari=input().split()
    kouho.append(kari)"""
for j in range(len(kouho)):
    if kouho[j][0]=="1":
        S_list.reverse()
    else:
        if kouho[j][1]=="1":
            S_list.appendleft(kouho[j][2])
        else:
            S_list.append(kouho[j][2])
print(*S_list,sep="")

### FIXED CODE ###

from collections import deque
S=input()
S_list=deque()
for k in range(len(S)):
    S_list.append(S[k])
Q=int(input())
kouho=[input().split() for i in range(Q)]
"""for i in range(Q):
    kari=input().split()
    kouho.append(kari)"""
hanten=[]
count=0
flaag=["sonomama","hantai"]

for j in range(Q):
    flag=flaag[count%2]
    if kouho[j][0]=="1":
        count+=1
    else:
        if flag=="sonomama":
            if kouho[j][1]=="1":
                S_list.appendleft(kouho[j][2])
            else:
                S_list.append(kouho[j][2])
        else:
            if kouho[j][1]!="1":
                S_list.appendleft(kouho[j][2])
            else:
                S_list.append(kouho[j][2])
for k in range(count%2):
    S_list.reverse()
print(*S_list,sep="")
### BUGGY CODE ###

import sys

sys.setrecursionlimit(100000)

N,M = map(int,input().split(' '))
l = [int(input()) for i in range(M)]

pre = 0
last = -1
ans_l = []
flag = False
l.append(N+1)

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

for i in l:
    if i==1:
        last = 1
        continue
    if i-last==1:
        flag =True
        break
    n = i - last - 3
    r = 0
    tmp = 1
    dif = 1
    # print("n",n)
    while dif>0:
        r += 1
        if n<=0 or n<r:
            break
        # print(n,r)
        tmp += cmb(n, r)
        dif = n-r
        # print("tmp",tmp,n,r)
        n -= 1
    ans_l.append(tmp)
    # print(i,ans_l)
    last = i
if flag:
    print(0)
else:
    ans = 1
    for i in ans_l:
        ans*=i
    print(ans%1000000007)


### FIXED CODE ###

N,M = map(int,input().split(' '))
l = set([int(input()) for i in range(M)])

mod = 10**9+7
dp = {}
for i in range(N+1):
    dp[i] = 1
dp[1] = 0 if 1 in l else 1

for i in range(2,N+1):
    if i in l:
        dp[i] = 0
        continue
    else:
        dp[i] = dp[i-1]%mod + dp[i-2]%mod
        dp[i] = dp[i]%mod

print(dp[N]%mod)
### BUGGY CODE ###

n = input()
m = []
for i in range(n):
    m.append(input())

interest = [m[1]-m[0]]
for i in range(n-1):
    M = max(m[i+1:])
    if interest[-1] <M-m[i]:
        interest.append(M-m[i])
print(interest[-1])
 

### FIXED CODE ###

n = int(input())
a = [0 for i in range(n)]
for i in range(n):
    a[i] = int(input())
minimum = a[0]
profit = a[1]-a[0]

for i in range(1,n):
    if profit < a[i]- minimum:
        profit = a[i] - minimum
    if minimum > a[i]:
        minimum = a[i]
        
print(profit)
### BUGGY CODE ###

import bisect

N=int(input())
A=[int(input()) for i in range(N)]
lst=[A[-1]]
nowN=max(A)+1
i=len(A)-2
while i>=0:
    #print(lst)
    if max(lst)>A[i]:
        maxvalue=0
        maxvaluei=100000
        for n in range(len(lst)):
            if lst[n]>A[i] and lst[n]>maxvalue:
                maxvalue=lst[n]
                maxvaluei=n
        lst[maxvaluei]=A[i]
                #break
    else:
        lst.append(A[i])

    i-=1
print(len(lst))


### FIXED CODE ###

import bisect
import collections

N=int(input())
A=[int(input()) for i in range(N)]
B=[0 for i in range(N)]
C=sorted(A)
count=0
lst=collections.deque([])
for i in range(N):
    if A[i]==C[-1]:
        C.pop()
        if lst:
            lst.pop()
        else:
            count+=1
        continue
    idx=bisect.bisect_left(lst,A[i])-1
    #print(idx,lst,A[i])
    if idx<0:
        lst.appendleft(A[i])
        count+=1
    else:
        lst[idx]=A[i]

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

N = int(input())
L = list(map(int,input().split()))
ans = 0
L.sort()
lst = [0 for i in range(10**3+1)]
for i in range(N):
    lst[L[i]]+=1
for i in range(N-1):
    for j in range(i+1,N):
        p = L[i]+L[j]
        ans += sum(lst[:p])-(j+1)
print(ans)

### FIXED CODE ###

N = int(input())
L = list(map(int,input().split()))
ans = 0
L.sort()
lst = [0 for i in range(10**3+1)]
for i in range(N):
    lst[L[i]]+=1
for i in range(10**3+1):
    if i != 0:
        lst[i]=lst[i-1]+lst[i]
for i in range(N-1):
    for j in range(i+1,N):
        p = L[i]+L[j]
        if p-1>=10**3+1:
            ans += lst[10**3]-(j+1)
        else:
            ans += lst[p-1]-(j+1)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

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

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

ikeru = [set() for _ in range(n+1)]

for i,j in tsuro:
    ikeru[i].add(j)
    ikeru[j].add(i)

ans = [0]*(n+1)
visited = [n+5]*(n+1)

def dfs(mae,heya,kaiso):
    if visited[heya] <= kaiso:
        return True
    else:
        visited[heya] = kaiso
        ans[heya] = mae
        for j in ikeru[heya]:
            dfs(heya, j, kaiso+1)
        return True

hantei = True
dfs(0,1,0)
for i in range(1, n+1):
    if visited[i] == n+5:
        hantei = False
        break
if hantei:
    print('Yes')
    for k in range(2,n+1):
        print(ans[k])
else:
    print('No')


### FIXED CODE ###

from collections import deque

n, m = map(int,input().split())
graph =[[] for _ in range(n+1)]
for _ in range(m):
    a,b =map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
queue = deque([1])
visited = [False] * (n+1)
visited[0] = True
ans = [0] * (n+1)
while queue:
    node = queue.popleft()
    for xnode in graph[node]:
        if visited[xnode]:
            continue
        ans[xnode]=node
        visited[xnode]=True
        queue.append(xnode)
print("Yes")
for a in ans[2:]:
    print(a)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

N,Q = map(int,input().split())
edges = [list(map(int,input().split())) for _ in range(N-1)]
PX = [list(map(int,input().split())) for _ in range(Q)]

c = [0]*N
res = [0]*N
for p,x in PX:
    c[p-1] += x

def BFS(start,edges,N,c):
    roots=[[] for _ in range(N)]
    for a,b in edges:
        roots[a-1]+=[(b-1,c[b-1])]
    queue=[]
    visited=[start]
    queue.append(start)
    res[start] = c[start]
    while queue:
        label = queue.pop()
        for i,c in roots[label]:
            if i not in visited:
                res[i]= res[label]+c
                queue += [i]
                visited.append(i)
    return res
print(*BFS(0,edges,N,c))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

N,Q = map(int,input().split())
edges = [list(map(int,input().split())) for _ in range(N-1)]
PX = [list(map(int,input().split())) for _ in range(Q)]

c = [0]*N
res = [-1]*N
for p,x in PX:
    c[p-1] += x

def BFS(start,edges,N,c):
    roots=[[] for _ in range(N)]
    for a,b in edges:
        roots[a-1]+=[(b-1,c[b-1])]
    queue=[]
    queue.append(start)
    res[start] = c[start]
    while queue:
        label = queue.pop()
        for i,c in roots[label]:
            if res[i] == -1:
                res[i]= res[label]+c
                queue += [i]
    return res
print(*BFS(0,edges,N,c))
### BUGGY CODE ###

import sys
input=sys.stdin.readline

x,n=map(int,input().split())
if n==0:
    print(x)
else:
    p=list(map(int,input().split()))
    a=0
    d=0
    while a==0:
        if x-d in p:
            if x+d in p:
                d+=1
            else:
                a=x+d
        else:
            a=x-d
    print(a)

### FIXED CODE ###

import sys
input=sys.stdin.readline
x,n=map(int,input().split())
if n==0:
    print(x)
else:
    p=list(map(int,input().split()))
    d=0
    while True:
        if x-d in p:
            if x+d in p:
                d+=1
            else:
                a=x+d
                break
        else:
            a=x-d
            break
    print(a)
### BUGGY CODE ###

N, W = map(int, input().split())
p = []
for it in range(N):
    p.append(list(map(int,input().split())))
    
import numpy as np
dp = np.zeros((N+1,W+1), dtype=np.int64)

i = 0
for w, v in p:
    i += 1
    for w_limit in range(1, W+1):
        if w_limit < w:
            dp[i,w_limit]=dp[i-1,w_limit]
            continue
        if (dp[i-1, w_limit-w] + v) > dp[i-1, w_limit]:
            dp[i, w_limit] = dp[i-1, w_limit-w] + v
        else:
            dp[i,w_limit]=dp[i-1,w_limit]
print(dp.max())

### FIXED CODE ###

N, W = map(int, input().split())
p = []
for it in range(N):
    p.append(list(map(int,input().split())))
    
dp = [[0 for i in range(W+1)] for j in range(N+1)]
i = 0
for w, v in p:
    i += 1
    for w_limit in range(1, W+1):
        if w_limit < w:
            dp[i][w_limit]=dp[i-1][w_limit]
            continue
        if (dp[i-1][w_limit-w] + v) > dp[i-1][w_limit]:
            dp[i][w_limit] = dp[i-1][w_limit-w] + v
        else:
            dp[i][w_limit]=dp[i-1][w_limit]
print(max(max(dp)))
### BUGGY CODE ###

import math
x = int(input())

if x == 1: print(0, -1)

else:
    def make_divisors(n):
        divisors = []
        for i in range(2, int(n**0.5)+1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n//i)
        return divisors

    l = make_divisors(x)
    for i in l:
        for j in range(i+1):
            if j**5 - (-(i-j)) ** 5 == x:
                print(j, -(i-j))
                exit()

### FIXED CODE ###

x = int(input())

for i in range(-120, 120):
    for j in range(-120, 120):
        if x == i ** 5 - j **5:
            print(i, j)
            exit()
### BUGGY CODE ###

from string import ascii_lowercase


def solve(s):
    d = [('', 0)]
    while True:
        e = []
        for ds, di in d:
            max_ci = -1
            for c in ascii_lowercase:
                ci = s.find(c, di) + 1
                ns = ds + c
                if not ci:
                    return ns
                if max_ci >= ci:
                    continue
                max_ci = ci
                e.append((ns, ci))
        d = e


print(solve(input().strip()))


### FIXED CODE ###

from string import ascii_lowercase
from bisect import bisect


def solve(s):
    pos = [[] for _ in range(26)]
    offset = ord('a')
    for i, c in enumerate(s):
        c = ord(c) - offset
        pos[c].append(i)
    for l in pos:
        l.append(len(s))

    all_char_sequence_start_pos = []
    pos_i = [len(l) - 1 for l in pos]
    while all(pi >= 0 for pi in pos_i):
        i = min(l[pi] for pi, l in zip(pos_i, pos))
        all_char_sequence_start_pos.append(i)
        for j in range(26):
            while pos_i[j] >= 0 and pos[j][pos_i[j]] >= i:
                pos_i[j] -= 1
    all_char_sequence_start_pos.reverse()
    ans = []
    curr = -1
    for i in all_char_sequence_start_pos:
        for c in range(26):
            cj = bisect(pos[c], curr)
            j = pos[c][cj]
            if j >= i:
                ans.append(c)
                curr = j
                break
    return ''.join(chr(c + offset) for c in ans)


print(solve(input().strip()))
### BUGGY CODE ###

import copy
n, m = map(int, input().split()) #n: 展望台の数, m: 道の数
height = list(map(int, input().split())) #高さリスト。nコある。
path = [list(map(int, input().split())) for _ in range(m)] #道リスト。
good_tower = 0 #解答

for i in range(n): #各展望台について.i+1の周辺をサーチ。
  h_i = height[i]
  con_num = [] #隣接する台番号を格納
  for j in range(m): #全pathをサーチ
    if i+1 in path[j]:
      p = copy.deepcopy(path[j])
      p.remove(i+1)
      c = p[0]
      con_num.append(c)
  if len(con_num) == 0:
    good_tower += 1
  else:
    con_num = list(set(con_num))
    cl = len(con_num)
    h_near_l = []
    for k in range(cl):
      t_num = con_num[k] #隣接台のナンバー
      h_near = height[t_num-1]
      h_near_l.append(h_near)
    if all(h_i > h_near_l[i] for i in range(cl)):
      good_tower += 1
      
print(good_tower)

### FIXED CODE ###

n, m = map(int, input().split()) #n: 展望台の数, m: 道の数
height = list(map(int, input().split())) #高さリスト.nコある.
ans_set = set(range(1, n+1))

for i in range(m):
  a, b = map(int, input().split())
  if height[a-1] >= height[b-1]:
    ans_set.discard(b)	#setのdiscardは存在しない場合は何もしない.
  if height[a-1] <= height[b-1]:
    ans_set.discard(a)
    
print(len(ans_set))
### BUGGY CODE ###

import re
def MAIN():
    T = input()
    P = input()
    pat = re.compile(P)
    t = 0
    while True:
        t = pat.search(T, t)
        if t is None:
            break
        print(t.span()[0])
        t = t.span()[0] + 1
MAIN()


### FIXED CODE ###

def kmpTable(w):
    lw = len(w)
    nx = [-1] * (lw + 1)
    j = -1
    for i in range(lw):
        while j >= 0 and w[i] != w[j]:
            j = nx[j]
        j += 1
        nx[i + 1] = j
    return tuple(nx)
def kmpSearch(s, w):
    ls = len(s)
    start = 0
    w_idx = 0
    ret = []
    nx = kmpTable(w)
    while start + w_idx < ls:
        if s[start + w_idx] == w[w_idx]:
            w_idx += 1
            if w_idx == len(w):
                ret.append(start)
                start = start + w_idx - nx[w_idx]
                w_idx = nx[w_idx]
        else:
            if w_idx == 0:
                start += 1
            else:
                start = start + w_idx - nx[w_idx]
                w_idx = nx[w_idx]
    return ret
T = input()
P = input()
ans = kmpSearch(T, P)

if ans:
    print(*ans, sep="\n")
#    print("\n".join(map(str, ans)))
### BUGGY CODE ###

from heapq import heapify,heappop,heappush
N,M=map(int,input().split())
S,T=map(int,input().split())
Graph=[set() for i in range(N)]
Edge=[]
mod=10**9+7
inf=float("inf")
for i in range(M):
  a,b,c=map(int,input().split())
  Graph[a-1].add((c,b-1))
  Graph[b-1].add((c,a-1))
  Edge.append((a-1,b-1,c))
  Edge.append((b-1,a-1,c))
def dijkstra(s,n,links):
  Visited=[False]*n
  cost=[inf]*n
  P=[0]*n
  P[s]=1
  cost[s]=0
  heap=[(0,s)]
  heapify(heap)
  while heap:
    hc,hp=heappop(heap)
    if Visited[hp]:
      continue
    Visited[hp]=True
    for c,p in links[hp]:
      if Visited[p]:
        continue
      if c+hc<cost[p]:
        cost[p]=c+hc
        P[p]=P[hp]
        heappush(heap,(cost[p],p))
      elif c+hc==cost[p]:
        P[p]=(P[p]+P[hp])%mod
  return cost,P

cost_S,P_S=dijkstra(S-1,N,Graph)
cost_T,P_T=dijkstra(T-1,N,Graph)
print
D=cost_S[T-1]
Pat=P_S[T-1]
ans=(Pat**2)%mod
for a,b,c in Edge:
  if cost_S[a]+cost_T[b]+c==D:
    if 2*cost_S[a]<D and 2*cost_T[b]<D:
      ans-=((P_S[a]*P_T[b])**2)%mod
for i in range(N):
  if 2*cost_S[i]==2*cost_T[i]==D:
    ans-=((P_S[i]*P_T[i])**2)%mod
print(ans%mod)



      
  
  
  
  


### FIXED CODE ###

from heapq import heapify,heappop,heappush
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
S,T=map(int,input().split())
Graph=[set() for i in range(N)]
Edge=[]
mod=10**9+7
inf=float("inf")
for i in range(M):
  a,b,c=map(int,input().split())
  Graph[a-1].add((c,b-1))
  Graph[b-1].add((c,a-1))
  Edge.append((a-1,b-1,c))
  Edge.append((b-1,a-1,c))
def dijkstra(s,n,links):
  Visited=[False]*n
  cost=[inf]*n
  P=[0]*n
  P[s]=1
  cost[s]=0
  heap=[(0,s)]
  heapify(heap)
  while heap:
    hc,hp=heappop(heap)
    if Visited[hp]:
      continue
    Visited[hp]=True
    for c,p in links[hp]:
      if Visited[p]:
        continue
      if c+hc<cost[p]:
        cost[p]=c+hc
        P[p]=P[hp]
        heappush(heap,(cost[p],p))
      elif c+hc==cost[p]:
        P[p]=(P[p]+P[hp])%mod
  return cost,P

def dp(s,n,links,d):
  Visited=[False]*n
  cost=[inf]*n
  P=[0]*n
  P[s]=1
  cost[s]=0
  heap=[(0,s)]
  heapify(heap)
  while heap:
    hc,hp=heappop(heap)
    if 2*hc>d:
      break
    if Visited[hp]:
      continue
    Visited[hp]=True
    for c,p in links[hp]:
      if Visited[p]:
        continue
      if c+hc<cost[p]:
        cost[p]=c+hc
        P[p]=P[hp]
        heappush(heap,(cost[p],p))
      elif c+hc==cost[p]:
        P[p]=(P[p]+P[hp])%mod
  return cost,P

cost_S,P_S=dijkstra(S-1,N,Graph)
D=cost_S[T-1]
cost_T,P_T=dp(T-1,N,Graph,D)
Pat=P_S[T-1]
ans=(Pat**2)%mod
for a,b,c in Edge:
  if cost_S[a]+cost_T[b]+c==D:
    if 2*cost_S[a]<D and 2*cost_T[b]<D:
      ans-=((P_S[a]*P_T[b])**2)%mod
for i in range(N):
  if 2*cost_S[i]==2*cost_T[i]==D:
    ans-=((P_S[i]*P_T[i])**2)%mod
print(ans%mod)
### BUGGY CODE ###

P = 10**9+7

fact = [1 for _ in range(2000001)]
inv = [1 for _ in range(2000001)]
fact_inv = [1 for _ in range(2000001)]

for i in range(2, 2000001):
    fact[i] = (fact[i-1]*i) % P
    inv[i] = P - (inv[P % i] * (P // i)) % P
    fact_inv[i] = (fact_inv[i-1] * inv[i]) % P

K = int(input())
S = input()
N = K + len(S)
p = 1
ans = 0
for i in range(K+1):
    ans += p * (fact[N] * fact_inv[N-i] * fact_inv[i] % P)
    ans = ans % P
    p *= 25
    p = p % P

print(ans)

### FIXED CODE ###

P = 10**9+7

fact = [1 for _ in range(2000001)]
inv = [1 for _ in range(2000001)]
fact_inv = [1 for _ in range(2000001)]

for i in range(2, 2000001):
    fact[i] = (fact[i-1]*i) % P
    inv[i] = P - (inv[P % i] * (P // i)) % P
    fact_inv[i] = (fact_inv[i-1] * inv[i]) % P

K = int(input())
S = input()
N = K + len(S)
p = 1
ans = 0
for i in range(K+1):
    ans += p * (fact[N] * fact_inv[N-i] * fact_inv[i] % P)
    ans = ans % P
    p *= 25
    p = p % P

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

import sys, heapq
input = sys.stdin.readline
n, q = map(int, input().split())
c = list(map(int, input().split()))


que = []
for i in range(q):
    l, r = map(int, input().split())
    heapq.heappush(que, (r, l, i))

bit = [0 for _ in range(n+1)]
def sum(i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= (i & -i)
    return s
def add(i, x):
    while i <= n:
        bit[i] += x
        i += (i & -i)


lastAppeared = [-1 for _ in range(n+1)]
ans = [None for _ in range(q)]
for i in range(1, n+1):
    if lastAppeared[c[i-1]] != -1:
        add(lastAppeared[c[i-1]], -1)
    lastAppeared[c[i-1]] = i
    add(i, 1)

    while len(que) > 0 and que[0][0] == i:
        r, l, x = heapq.heappop(que)
        ans[x] = sum(r) - sum(l-1)

    if len(que) == 0:
        break

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


### FIXED CODE ###

import sys, heapq
input = sys.stdin.readline
n, q = map(int, input().split())
c = [int(x) - 1 for x in input().split()]

que = []
for i in range(q):
    l, r = map(int, input().split())
    que.append((l, r, i))



class SegTree(object):
    def __init__(self, n):
        self.BIT = [0] * (n + 1)
        self.num = n

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.BIT[i]
            i -= i & (-i)
        return s

    def add(self, i, x):
        while i <= self.num:
            self.BIT[i] += x
            i += i & (-i)
    

que.sort(key=lambda x: -x[1])
ans = [None] * q
last = [-1] * n
BIT = SegTree(n)

for i in range(1, n+1):
    if last[c[i-1]] != -1:
        BIT.add(last[c[i-1]], -1)
    last[c[i-1]] = i
    BIT.add(i, 1)

    while que and que[-1][1] == i:
        l, r, x = que.pop()
        ans[x] = BIT.sum(r) - BIT.sum(l-1)

print(*ans, sep='\n')
### BUGGY CODE ###

def main():

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

    query = []
    flag = 0
    ctn = 0
    for _ in range(q):
        temp = input().split()
        if len(temp) == 1:
            if flag == 0:
                flag = 1
            else:
                flag = 0
            ctn += 1
        else:
            query.append(temp + [flag])

    for q in query:
        if q[-1] == 0:
            if q[1] == "1":
                s = q[2] + s
            else:
                s = s + q[2]
        else:
            if q[1] == "1":
                s = s + q[2]
            else:
                s = q[2] + s

    if ctn % 2 == 1:
        print(s[::-1])
    else:
        print(s)

main()

### FIXED CODE ###

from collections import deque

def main():

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

    flag = 0
    query = []

    for _ in range(q):
        temp = input().split()
        if len(temp) == 1:
            flag += 1
        else:
            query.append(temp + [flag%2])

    for q in query:
        if q[-1] == 0:
            if q[1] == "1":
                s.appendleft(q[2])
            else:
                s.append(q[2])
        else:
            if q[1] == "1":
                s.append(q[2])
            else:
                s.appendleft(q[2])

    if flag % 2 == 1:
        print("".join(list(s)[::-1]))
    else:
        print("".join(s))

main()
### BUGGY CODE ###

import numpy as np
import sys

LI = lambda: list(map(int, sys.stdin.readline().rstrip().split()))

def main():
    n, s = LI()
    a = LI()
    dp = np.zeros((n+1, s+1), dtype=np.int)
    dp[0][0] = 1

    for i in range(n):
        for w in range(s+1):
            dp[i+1][w] = 2*dp[i][w]
            if w >= a[i]:
                dp[i+1][w] += dp[i][w-a[i]]
            dp[i+1][w] %= 998244353

    print(dp[n][s])

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

LI = lambda: list(map(int, sys.stdin.readline().rstrip().split()))

def main():
    n, s = LI()
    a = LI()
    dp = [[0 for i in range(s+1)] for j in range(n+1)]
    dp[0][0] = 1

    for i in range(n):
        for w in range(s+1):
            dp[i+1][w] = 2*dp[i][w]
            if w >= a[i]:
                dp[i+1][w] += dp[i][w-a[i]]
            dp[i+1][w] %= 998244353

    print(dp[n][s])

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

n,q = map(int, input().split())
A = [float("inf")] * n
for i in range(q):
 c,x,y = map(int,input().split())
 if c == 0:
  A[x] = y
 else:
  a = min(A[x:y+1])
  if a == float("inf"): a = "2147483647"
  else: a = str(a)
  print(a)

### FIXED CODE ###

import math, sys
MAX = pow(2, 31) - 1

#??°????????????????????§????°????????????¨???????????°??????????????????????§????
class SegmentTree():
    def __init__(self, n):
        self.TreeRange = pow(2, math.ceil(math.log2(n)))
        self.List = [MAX] * (2 * self.TreeRange - 1)

    def update(self, i, x):
        i += self.TreeRange - 1
        self.List[i] = x
        while i > 0:
            i = (i - 1) // 2
            self.List[i] = min (self.List[i * 2 + 1], self.List[i * 2 + 2])

    def find(self, s, t, i=0, left=0, right=float("inf")):
        #??¢?´¢????±?????????????????????§????????°?????§???????????????
        if right <= s or t <= left:
            return MAX
        #??¢?´¢????±?????????????????????§????????°??????????????????????????????
        elif s <= left <= right <= t:
            return self.List[i]
        #??¢?´¢????±????????????????????????????????????°????????????????????°
        else:
            l = self.find(s, t, i * 2 + 1, left, (left + right) // 2)
            r = self.find(s, t, i * 2 + 2, (left + right) // 2, right)
            return min(l, r)

_input = sys.stdin.readlines()
n,q = map(int, _input[0].split())
qlist = map(lambda x:x.split(), _input[1:])
ST = SegmentTree(n)

for q in qlist:
    cmd, x, y = map(int, q)
    if cmd == 0:
        ST.update(x, y)
    elif cmd == 1:
        print(ST.find(x,y + 1, right = ST.TreeRange))