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


def main():
    mod = 998244353
    N, K = map(int,input().split())
    v = []
    
    for _ in range(K):
        L, R = map(int,input().split())
        # for d in range(L, R+1):
        #     moves.append(d)
        v.append((L, R))
    
    dp = [0] * N        # マスi-1に到達するまでの操作列の個数
    sdp = [0] * (N + 1) # dp[i]までの累積和 
    dp[0] = 1
    sdp[1] = 1

    for n in range(1, N):
        for p in v:
            left = max(0, n - p[1])
            right = max(0, n - p[0]+1)
            dp[n] += sdp[right] - sdp[left]
        sdp[n+1] = sdp[n] + dp[n]

    print(dp[-1] % mod)

if __name__ == "__main__":
    main()



### FIXED CODE ###

n, k = map(int, input().split())
sec = [list(map(int, input().split())) for _ in range(k)]
sec.sort()
    
mod = 998244353
    
dp = [0] * n
dp[0] = 1
sum_dp = [0, 1]
for i in range(1, n):
    for l, r in sec:
        if i - l < 0:
            break
        elif i - r > 0:
            dp[i] = ((dp[i] + sum_dp[i-l+1]) % mod - sum_dp[i-r]) % mod
        else:
            dp[i] = (dp[i] + sum_dp[i-l+1]) % mod
    
    sum_dp.append((sum_dp[-1] + dp[i]) % mod)
    
print(dp[n-1])
### BUGGY CODE ###

from math import factorial

n, m = map(int, input().split())
A = [0] * m
for i in range(m):
    A[i] = int(input())
B = []
if m > 1:
    for i in range(m - 1):
        if A[i + 1] - A[i] == 1:
            print(0)
            exit()
if m:
    B.append(A[0])
    A.append(n + 1)
    for i in range(len(A) - 2, -1, -1):
        B.append(A[i + 1] - A[i] - 1)
else:
    B.append(n + 1)
div = 1000000007
ans = 1
for b in B:
    if b < 3:
        continue
    c = b - 1
    two_max = c // 2
    a = 0
    for two in range(two_max + 1):
        one = c - (2 * two)
        a += factorial(one + two) // (factorial(one) * factorial(two))
    ans *= a
    ans %= div
print(ans)


### FIXED CODE ###

def generate_range_combinations(n):
    C = [1] * n
    for i in range(2, n):
        C[i] = (C[i - 1] + C[i - 2]) % DIV
    return C


def solve(n, m, A):
    from collections import defaultdict

    if m == 0:
        C = generate_range_combinations(n + 1)
        return C[-1]

    D = defaultdict(lambda: 0)
    for i in range(m - 1):
        d = A[i + 1] - A[i] - 1
        if d == 0:
            return 0
        D[d] += 1
    D[A[0]] += 1
    D[n - A[-1]] += 1

    ans = 1
    C = generate_range_combinations(max(D.keys()))
    for k, v in D.items():
        ans *= C[k - 1] ** v
        ans %= DIV
    return ans


DIV = 1000000007
n, m = map(int, input().split())
A = [int(input()) for _ in range(m)]
print(solve(n, m, A))
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for i in range(q)]

ans = [0] * n
for i in range(n - 1):
    if s[i] == "A" and s[i + 1] == "C":
        ans[i] = 1

for i in lr:
    cnt = sum(ans[i[0]-1:i[1]-1])
    print(cnt)

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for i in range(q)]

ans = [0] * n
for i in range(n - 1):
    if s[i] == "A" and s[i + 1] == "C":
        ans[i + 1] = ans[i] + 1
    else:
        ans[i + 1] = ans[i]

for i in lr:
    print(ans[i[1]-1]-ans[i[0]-1])
### BUGGY CODE ###

N, K = map(int, input().split())
l = []
for i in range(N):
  a, b = map(int, input().split())
  for j in range(b):
      l.append(a)
print(sorted(l)[K-1])

### FIXED CODE ###

N, K = map(int, input().split())
l = [0 for i in range(100001)]
num_count = 0
n = 0
for j in range(N):
    a, b = map(int, input().split())
    l[a] += b
for k in l:
    num_count += k
    if num_count >= K:
        print(n)
        break
    else:
        n += 1
### BUGGY CODE ###

import math

# input
N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]

# process
XH.sort()

ans = 0
for i in range(N):
    x, h = XH[i]
    if h <= 0:
        continue

    XH[i][1] = 0
    c = math.ceil(h/A)
    ans += c

    dmg = A*c
    scp_end = x+D*2

    for j in range(i+1, N):
        xj, hj = XH[j]
        if xj <= scp_end:
            if hj > 0:
                XH[j][1] -= dmg
        else:
            break
    
# output
print(ans)


### FIXED CODE ###

from collections import deque

# input
N, D, A = map(int, input().split())
XH = [tuple(map(int, input().split())) for _ in range(N)]

# process
XH.sort()
#print(XH)

ans = 0
dq = deque()
dam = 0
for x, h in XH:
    while dq:
        x2, h2 = dq[0]
        if x > x2:
            dam -= h2
            dq.popleft()
        else:
            break

    h -= dam
    if h <= 0:
#        print("x,h,dam: {},{},{}".format(x,h,dam))
        continue

    c = -(-h//A)
    ans += c
    d = A*c
    dam += d
    dq.append((x+D*2, d))
#    print("x,h,dam,ans,dq: {},{},{},{},{}".format(x,h,dam,ans,dq))
    
# output
print(ans)
### BUGGY CODE ###

n = int(input())
d = list(map(int, input().split()))
m = int(input())
t = list(map(int, input().split()))
for i in range(m):
  if t[i] in set(d):
    d.remove(t[i])
  else:
    print("NO")
    exit()
print("YES")


### FIXED CODE ###

import collections

n = int(input())
d = list(map(int, input().split()))
m = int(input())
t = list(map(int, input().split()))
dc = collections.Counter(d)
tc = collections.Counter(t)
for i in tc:
    if tc[i] > dc[i]:
        print("NO")
        exit()
print("YES")
### BUGGY CODE ###

from fractions import gcd
N,M=map(int,input().split())
S=input()
T=input()
s=(M//gcd(N,M))
t=(N//gcd(N,M))
SS=[i*s for i in range(N)]
TT=[j*t for j in range(M)]
p,q=0,0
ans=N*s
for k in range(N*s):
    if k in SS:
        if k in TT:
            if S[p]!=T[q]:
                ans=-1
        p+=1
    if k in TT:
        q+=1
print(ans)

### FIXED CODE ###

from fractions import gcd
N,M=map(int,input().split())
S=input()
T=input()
s=(M//gcd(N,M))
t=(N//gcd(N,M))
SS=[i*s for i in range(N)]
TT=[j*t for j in range(M)]
p,q=0,0
ans=N*s
while True:
    if SS[p]==TT[q]:
        if S[p]!=T[q]:ans=-1
        p+=1
        q+=1
    elif SS[p]>TT[q]:
        q+=1
    else:
        p+=1
    if p==N or q==M:
        break
print(ans)
### BUGGY CODE ###

# coding: utf-8
#-------------------------------------------------------------------
import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")
#-------------------------------------------------------------------

R,G,B,N = map(int, input().split())


r=g=b=0
ans=0

#p(N//R+2)
#p(N//G+2)
#X=[]
#p(r,g,b)

for r in range(N//R+2):
	if (R*r)>N: break

	for g in range(N//G+2):
		if (R*r)+(G*g)>N:
			break
			X.append("break")
		
		b = (N-(R*r)-(G*g))//B
		n = (R*r)+(G*g)+(B*b)
		if n==N:
			ans+=1
#			X.append([r,g,b])
#		p(r,g,b,n,N,ans)

print(ans)
#p(X)


### FIXED CODE ###

# coding: utf-8
#-------------------------------------------------------------------
import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")
#-------------------------------------------------------------------

R,G,B,N = map(int, input().split())


r=g=b=0
ans=0

#p(N//R+2)
#p(N//G+2)
#X=[]
#p(r,g,b)

for r in range(N//R+2):
	if (R*r)>N: break

	for g in range(N//G+2):
		if (R*r)+(G*g)>N:
			break
			X.append("break")
		
		b = (N-(R*r)-(G*g))//B
		n = (R*r)+(G*g)+(B*b)
		if n==N:
			ans+=1
#			X.append([r,g,b])
#		p(r,g,b,n,N,ans)

print(ans)
#p(X)
### BUGGY CODE ###

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

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

# N -> dp[N - A_i] + B_i

dp = [0 for i in range(H+1)]

for i in range(H+1):
  temp = 10 ** 8 + 1
  for j in range(N): # Use each Magic j
    if i - A[j] > 0:
      temp = min(temp, dp[ i - A[j] ] + B[j] )
    else:
      temp = min(temp, B[j] )
  dp[i] = temp
               
print(dp[H])

### FIXED CODE ###

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

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

# N -> dp[N - A_i] + B_i

dp = [0 for i in range(H+1)]

for i in range(H+1):
  temp = 10 ** 8 + 1
  for j in range(N): # Use each Magic j
    if i - A[j] > 0:
      temp = min(temp, dp[ i - A[j] ] + B[j] )
    else:
      temp = min(temp, B[j] )
  dp[i] = temp
               
print(dp[H])
### BUGGY CODE ###

n, m = map(int,input().split())
a = [int(input()) for i in range(m)]
x =  1000000007

p,q=(0,1)
#累積和っぽい考え
for i in range(1, n+1):
	p,q = q,(p+q)*(not i in a)
print(q%x)

### FIXED CODE ###

n, m = map(int,input().split())
a = set([int(input()) for i in range(m)])

p,q=(0,1)
#累積和っぽい考え
for i in range(1, n+1):
	p,q = q,(p+q)*(not i in a)
print(q%(10**9+7))
### BUGGY CODE ###

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

for i in range(n):
    x = a.index(i + 1) + 1
    print(x, end=' ')

### FIXED CODE ###

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

l = [0] * n

for i in range(n):
    l[a[i] - 1] = i + 1

print(*l)
### BUGGY CODE ###

from sys import stdin,stdout
INT_MAX= 100000000
n,k=map(int,stdin.readline().split())
dp  = [INT_MAX]*(n)
h=[int(X) for X in stdin.readline().split()]
dp[0]=0
dp[1]=abs(h[1]-h[0])
for i in range(2,n):
    p=1
    while(p<k+1 or i-p>=0):
        dp[i]= min(dp[i-p+1]+abs(h[i-p+1]-h[i]),dp[i])
        p+=1
stdout.write(str(dp[n-1])+"\n")

### FIXED CODE ###

from sys import stdin,stdout
INT_MAX= 10**18
n,k=map(int,stdin.readline().split())
dp  = [INT_MAX]*(n)
h=[int(X) for X in stdin.readline().split()]
dp[0]=0
dp[1]=abs(h[1]-h[0])
for i in range(2,n):
    p=1
    while(p<k+1 and (i-p)>=0):
        dp[i]= min(dp[i-p]+abs(h[i-p]-h[i]),dp[i])
        p+=1
stdout.write(str(dp[n-1])+"\n")
### BUGGY CODE ###

H,W=map(int,input().split())
S=[[d for d in input()] for i in range(H)]
ans=[[0 for j in range(W)] for i in range(H)]
t=0
for i in range(H):
 p=0
 for j in range(W):
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
for i in range(H):
 p=0
 for j in range(W)[::-1]:
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
for j in range(W):
 p=0
 for i in range(H):
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
for j in range(W):
 p=0
 for i in range(H)[::-1]:
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
  t=max(t,ans[i][j])
print(t-3)


### FIXED CODE ###

import sys
input = sys.stdin.readline
H,W=map(int,input().split())
S=[[d for d in input()] for i in range(H)]
ans=[[0 for j in range(W)] for i in range(H)]
t=0
for i in range(H):
 p=0
 for j in range(W):
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
for i in range(H):
 p=0
 for j in range(W)[::-1]:
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
for j in range(W):
 p=0
 for i in range(H):
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
for j in range(W):
 p=0
 for i in range(H)[::-1]:
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
  t=max(t,ans[i][j])
print(t-3)
### BUGGY CODE ###

def modpow(a: int, p: int, mod: int) -> int:
    # return a**p (mod MOD) O(log p)
    if p == 0:
        return 1
    if p % 2 == 0:
        half = modpow(a, p//2, mod)
        return half*half % mod
    else:
        return a * modpow(a, p-1, mod) % mod


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

ret = 0
cnt_0 = [0] * 60
cnt_1 = [0] * 60

for item in a_ls:
    for i in range(60):
        if len(bin(item)) <= i:
            cnt_0[i] += 1
        elif bin(item)[-1-i] == '1':
            cnt_1[i] += 1
        else:
            cnt_0[i] += 1

for i in range(60):
    tmp = (cnt_0[i] * cnt_1[i])
    tmp %= 10 ** 9 + 7
    tmp *= modpow(2, i, 10 ** 9 + 7)
    ret += tmp
    ret %= 10 ** 9 + 7

print(ret)


### FIXED CODE ###

def str2bitstr(chs):
    val = int(chs)
    tmp = bin(val)[2:]
    tmp2 = '0' * (60 - len(tmp))
    return tmp2 + tmp


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

cnts = [0] * 60

for item in a:
    for i, ch in enumerate(item):
        if ch == '1':
            cnts[i] += 1

ret = 0
now = 1

for i in range(1, 61):
    kumi = cnts[-i] * (n - cnts[-i]) % (10 ** 9 + 7)
    ret += kumi * now % (10 ** 9 + 7)
    now *= 2 % (10 ** 9 + 7)
    ret = ret % (10 ** 9 + 7)

print(ret % (10 ** 9 + 7))
### BUGGY CODE ###

N = int(input())
A,B = [],[]
for _ in range(N-1):
    array = list(map(int,input().split()))
    A.append(array[0])
    B.append(array[1])
from collections import defaultdict as ddict
children = ddict(list)
for a,b in zip(A,B):
    children[a].append(b)
ans = ddict(int)
col = 0
for child in sorted(children.keys()):
    used = set({ans[child]})
    for j in sorted(children[child]):
        temp = min(set(range(1,max(used)+2))-used)
        ans[j] = temp
        used.add(temp)
ans2 = [ans[b] for b in B]
print(max(ans2))
for a in ans2:
    print(a)

### FIXED CODE ###

N = int(input())
AB = [[]]*(N-1)
for i in range(N-1):
    AB[i] = list(map(int,input().split()))
from collections import defaultdict as ddict
from collections import deque
tree = ddict(list)
B = [0]*(N-1)
for i,ab in enumerate(AB):
    tree[ab[0]].append(ab[1])
    B[i] = ab[1]
# 各エッジの色を格納する変数の初期化
# C[0]は使わない
C = [0]*N
# 幅優先探索用のcue
Q = deque([1])
while Q:
    q = Q.popleft()
    c = 0
    for w in tree[q]:
        # 色をインクリメントした際に親の色とかぶったら更に1を加算する
        # 他は単純なインクリメント
        c += 1 + int(C[q-1] == c+1)
        # エッジの色を格納
        C[w-1] = c
        # 子供をcueに追加
        Q.append(w)
print(max(C))
for b in B:
    print(C[b-1])
### BUGGY CODE ###

N=int(input())

power=1
i=1
for i in range(1,N+1):
    power*=i


ans=power%(1000000000+7)
print(ans)

### FIXED CODE ###

import math
N=int(input())

power=math.factorial(N)

ans=power%(1000000000+7)
print(ans)
### BUGGY CODE ###

# YouTube
def main():
    n = int(input())
    s = input()
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for i, c in enumerate(s[:-1]):
        for j in range(i + 1, n):
            if c == s[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
    ans = 0
    for d in range(n // 2 + 1, 0, -1):
        if ans >= d: break
        for i in range(n - d + 1):
            a = min(d, dp[i][i + d])
            ans = max(a, ans)
            if a == d: break
    print(ans)

main()


### FIXED CODE ###

# YouTube
def main():
    n = int(input())
    s = input()
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for i, c in enumerate(s):
        for j in range(n):
            if c == s[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
    ans = 0
    for i in range(n):
        for j in range(i+1,n+1):
            tmp=min(dp[i][j],j-i)
            ans=max(tmp,ans)
    print(ans)

main()
### BUGGY CODE ###

X = int(input())

if X == 1:
    print(0, -1)
    exit()

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()
    return divisors

def solve(num, X):
    a = 1
    for i in range(1, X+1):
        if (i * 100) ** 5 - (i * 100 - num) ** 5 >= X:
            break
    max_a = 100 * i
    a = max_a - 99
    while a <= max_a:
        if (a) ** 5 - (a -num) ** 5 == X:
            return True, a, a-+ num
        a += 1
    return False, 0, 0

arr = make_divisors(abs(X))
for num in arr:
    flag, a, b = solve(num , X)
    if flag:
        print(a, b)
        exit()
    flag, a, b = solve(-num , X)
    if flag:
        print(a, b)
        exit()

### FIXED CODE ###

X = int(input())

if X == 1:
    print(0, -1)
    exit()

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()
    return divisors

def solve(num, X):
    a = 1
    for i in range(1, X+1):
        if (i * 100) ** 5 - (i * 100 - num) ** 5 >= X:
            break
    max_a = 100 * i
    a = max_a - 99
    while a <= max_a:
        if (a) ** 5 - (a -num) ** 5 == X:
            return True, a, a - num
        a += 1
    return False, 0, 0

arr = make_divisors(abs(X))
for num in arr:
    if (num - X) % 5:
        continue
    flag, a, b = solve(num , X)
    if flag:
        print(a, b)
        exit()
    #flag, a, b = solve(-num , X)
    #if flag:
    #    print(a, b)
    #    exit()
### BUGGY CODE ###

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

ans = [1 for i in range(n)]

for i in range(n):
    for j in range(i+1, n):
        if num[i] < num[j]:
            ans[j] = 0
            
print(sum(ans))

### FIXED CODE ###

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

now = num[0]
cnt = 1
for i in range(1,n):
    if (now > num[i]):
        cnt+=1
        now = num[i]
    
print(cnt)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

# D - Replacing
def get_sum(dic):
	sum = 0
	
	for k, v in dic.items():
		sum += k * v
	
	return sum


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

for ai in a:
	dic.setdefault(ai, 0)
	dic[ai] += 1

for i in range(q):
	b, c = map(int, input().split())

	count = dic.pop(b, 0)
	
	if count > 0:
		dic.setdefault(c, 0)
		dic[c] += count
	
	print(get_sum(dic))

### FIXED CODE ###

import sys
input = sys.stdin.readline

# D - Replacing
def get_sum(dic):
	sum = 0
	
	for k, v in dic.items():
		sum += k * v
	
	return sum


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

for ai in a:
	dic.setdefault(ai, 0)
	dic[ai] += 1

for i in range(q):
	b, c = map(int, input().split())

	count = dic.pop(b, 0)
	
	if count > 0:
		dic.setdefault(c, 0)
		dic[c] += count

	if i == 0:	
		sum = get_sum(dic)
	else:
		sum += (c - b) * count
	
	print(sum)
### BUGGY CODE ###

N = int(raw_input())
X_list = map(int, raw_input().split())

a = (N/2)-1

for i in range(N):
    tmp_x = X_list[:i] + X_list[i+1:]
    tmp_x.sort()
    print tmp_x[a]


### FIXED CODE ###

N = int(raw_input())
X_list = map(int, raw_input().split())

sorted_x = sorted(X_list)

small = sorted_x[N/2-1]
big = sorted_x[N/2]

for x in X_list:
    if x < big:
        print big
    else:
        print small
### BUGGY CODE ###

n,k  = map(int,input().split())
l = sorted([int(input()) for i in range(n)])
#print(l)
ansl = []
for m in range(n-k+1):
  ansl.append(max(l[m:m+k])-min(l[m:m+k]))
print(min(ansl))

### FIXED CODE ###

n,k  = map(int,input().split())
l = sorted([int(input()) for i in range(n)])
print(min(l[i+k-1] - l[i] for i in range(n-k+1)))
### BUGGY CODE ###

def D_joisino_travel(N, M, R, r, A):
    """
    N:国の中の町の数
    M:町を結ぶ道の総数
    R:訪れる町の数
    r:訪れる町の番号
    A:町の結び方とその間の距離
    """
    from itertools import permutations
    INF = float('inf')
    # 0行、0列は使わない(番号と配列の要素番号を一致させるため)
    dist = [[INF]*(N+1) for j in range(N + 1)]
    for i in range(1, N + 1):
        dist[i][i] = 0
    for m, n, c in A:
        dist[m][n] = c
        dist[n][m] = c

    # ワーシャルフロイド法(町A→Bの最短距離を求められる)
    for k in range(1, N + 1):
        for i in range(1, N + 1):
            for j in range(1, N + 1):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    permutation_route = permutations(r)
    min_dist = INF
    for i in permutation_route:
        cost = 0
        for j in range(R - 1):  # i(行く町の順列)の先頭から2つ要素を拾う
            cost += dist[i[j]][i[j + 1]]  # コストはワーシャルフロイド法で求めてある
        min_dist = min(min_dist, cost)
    return min_dist
  
N,M,R = [int(i) for i in input().split()]
r = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for i in range(M)]
print(D_joisino_travel(N, M, R, r, A))

### FIXED CODE ###

def D_joisino_travel(N, M, R, r, A):
    """
    N:国の中の町の数
    M:町を結ぶ道の総数
    R:訪れる町の数
    r:訪れる町の番号
    A:町の結び方とその間の距離
    """
    from itertools import permutations
    INF = float('inf')
    # 道の番号-1が要素の番号
    r = [x - 1 for x in r]
    dist = [[INF]*N for j in range(N)]
    for i in range(N):
        dist[i][i] = 0
    for m, n, c in A:
        m-=1
        n-=1
        dist[m][n] = c
        dist[n][m] = c

    # ワーシャルフロイド法(町A→Bの最短距離を求められる)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    permutation_route = permutations(r)
    min_dist = INF
    for i in permutation_route:
        cost = 0
        for j in range(R - 1):  # i(行く町の順列)の先頭から2つ要素を拾う
            cost += dist[i[j]][i[j + 1]]  # コストはワーシャルフロイド法で求めてある
        min_dist = min(min_dist, cost)
    return min_dist
  
N,M,R = [int(i) for i in input().split()]
r = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for i in range(M)]
print(D_joisino_travel(N, M, R, r, A))
### BUGGY CODE ###

import math

N = int(input())
S = input()
ans = 0

for pin in range(0,1000):
  counter = 0
  for s in S:
    if str(pin).zfill(3)[counter] == s:
      counter += 1
    if counter == 3:
      ans += 1
      break
    
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
ans = 0

for pin in range(0,1000):
  counter = 0
  for index in range(0, N):
    if str(pin).zfill(3)[counter] == S[index]:
      counter += 1
    if counter == 3:
      ans += 1
      break
    
print(ans)
### BUGGY CODE ###

import math

N = int(input())
for i in range(1,N+1):
    count = 0
    for x in range(1,int(math.sqrt(i))+1):
        for y in range(x,int(math.sqrt(i))+1):
            for z in range(y,int(math.sqrt(i))+1):
                if x**2+y**2+z**2+x*y+y*z+z*x != i:
                    continue
                if x == y and x == z:
                    count += 1
                elif x == y or x == z or y == z:
                    count += 3
                else:
                    count += 6
    print(count) 

### FIXED CODE ###

import math

N = int(input())
for i in range(1,N+1):
    count = 0
    for x in range(1,int(math.sqrt(i/6))+2):
        for y in range(x,int(math.sqrt(i/3))+2):
            for z in range(y,int(math.sqrt(i))+1):
                if x**2+y**2+z**2+x*y+y*z+z*x != i:
                    continue
                if x == y and x == z:
                    count += 1
                elif x == y or x == z or y == z:
                    count += 3
                else:
                    count += 6
    print(count)
### BUGGY CODE ###

N = int(input())
p = [int(e) for e in input().split(" ")]
c = 0
for i in range(N):
    if(p[i] <= min(p[0:i + 1])):
        c += 1
print(c)

### FIXED CODE ###

N = int(input())
p = [int(e) for e in input().split(" ")]
low = p[0]
c = 0
for i in range(N):
    if(p[i] <= low):
        c += 1
        low = p[i]
print(c)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    s = input()[:-1]
    q = int(input()[:-1])
#queries = []
    for _ in range(0, q):
        query = input()[:-1]
        if len(query) == 1:
     #       queries.append([int(query)])
            s = s[::-1]
        else:
            query = query.split(' ')
            query = [int(query[0]), int(query[1]), query[2]]
#        queries.append(query)
            if query[1] == 1:
                s = query[2] + s
            else:
                s = s + query[2]



#for i in range(0, q):
#    if queries[i][0] == 1:
#        s = s[::-1]
#    else:
#        if queries[i][1] == 1:
#            s = queries[i][2] + s
#        else:
#            s = s + queries[i][2]

    print(s)

main()


### FIXED CODE ###

#import sys
#input = sys.stdin.readline

def main():
    s = input()
    q = int(input())
    is_rev = False
    l = ''
    r = ''
    for _ in range(0, q):
        query = input()
        if len(query) == 1:
            is_rev = not is_rev
        else:
            query = query.split(' ')
            query = [int(query[0]), int(query[1]), query[2]]
            if (query[1] == 1 and is_rev) or (query[1] == 2 and not is_rev):
#                s = s + query[2]
                r += query[2]
            else:
#                s = query[2] + s
                l += query[2]
    if is_rev:
        print(r[::-1] + s[::-1] + l)
    else:
        print(l[::-1] + s + r)

main()