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


def main():
    N, K = map(int,input().split())

    mod = 998244353

    S = []
    for _ in range (K):
        l,r = map(int,input().split())
        for i in range (l,r+1):
            S.append(i)

    S.sort()

    ans = [0]*N
    ans[0] = 1

    for i in range (1,N):
        for j in S:
            if i-j < 0:
                break
            else:
                ans[i] += ans[i-j]
        ans[i] %= mod


    print(ans[N-1])


main()


### FIXED CODE ###

def main():
    N, K = map(int,input().split())

    mod = 998244353

    S = []
    for _ in range (K):
        S.append(list(map(int,input().split())))

    S.sort()
    #print(S)

    ans = [0]*N
    acc = [0]*N
    ans[0] = 1
    acc[0] = 1

    for i in range (1,N):
        for l,r in S:

            if i-l < 0:
                break
            else:
                ans[i] += acc[i-l]
            if i-r -1 < 0:
                break
            else:
                ans[i] -= acc[i-r-1]

        ans[i] %= mod
        acc[i] = (acc[i-1]+ans[i])%mod


    print(ans[N-1])


main()
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
readline = sys.stdin.buffer.readline

N = int(readline())
A = list(map(int, readline().split()))
Q = int(readline())

for _ in range(Q):
    B, C = map(int, readline().split())

    A = [(C if num == B else num) for num in A]
    print(sum(A))


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import Counter
readline = sys.stdin.buffer.readline

N = int(readline())
A = list(map(int, readline().split()))
Q = int(readline())
d = Counter(A)

total = sum(A)

for _ in range(Q):
    B, C = map(int, readline().split())

    total -= B * d[B]
    total += C * d[B]

    d[C] += d[B]
    d[B] = 0

    print(total)
### BUGGY CODE ###

INF = 10e17
N = int(input())
A = list(map(int, input().split()))
ans = 1
for a in A:
    ans = ans*a
if ans > INF:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import sys

INF = 10e17
N = int(input())
A = list(map(int, sys.stdin.readline().rstrip().split()))
ans = 1
for a in A:
    if a == 0:
        print(0)
        sys.exit()
for a in A:
    ans = ans*a
    if ans > INF:
        print(-1)
        sys.exit()

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

N, K = [int(x) for x in input().split()]
P = [int(x) for x in input().split()]

def calc(n):
  return sum(range(1, n + 1)) / n

max_value = -1
max_index = -1

for i in range(N - K + 1):
  s = sum(P[i:i+K])
  max_value = max(max_value, s)
  if max_value == s:
    max_index = i

print(sum([calc(P[i]) for i in range(max_index, max_index + K)]))

### FIXED CODE ###

N, K = [int(x) for x in input().split()]
P = [int(x) for x in input().split()]

def calc(n):
  return sum(range(1, n + 1)) / n

sums = [0]
s = 0
for i in range(N):
  s += calc(P[i])
  sums.append(s)

max_value = -1
max_index = -1

# print(sums)
for i in range(N - K + 1):
  s = sums[i+K] - sums[i]
  # print(i)
  # print(i+K)
  max_value = max(max_value, s)
  if max_value == s:
    max_index = i

print(max_value)
# print(sum([calc(P[i]) for i in range(max_index, max_index + K)]))
### BUGGY CODE ###

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

a=sorted(a)
if n==1:
  for i in range(m):
    a[0]=a[0]/2
else:
  for i in range(m):
    if a[n-2]>a[n-1]:
      a=sorted(a)
    a[n-1]=a[n-1]/2

ans=0
for j in range(n):
  ans=ans+int(a[j])
  
print(ans)

### FIXED CODE ###

import heapq	

n,m=map(int,input().split())
a=list(map(int,input().split()))
hq=[]
for i in range(len(a)):
  heapq.heappush(hq,-a[i])

if n==1:
  for i in range(m):
    hq[0]=(((-1)*hq[0])//2)*(-1)
else:
  for i in range(m):
    v=heapq.heappop(hq)
    heapq.heappush(hq,((v*-1)//2)*(-1))

ans=0
for i in range(len(hq)):
  ans=ans+(-1)*heapq.heappop(hq)

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

s = input()[::-1]
counts = [0]*2019
counts[0] = 1
sum = 0
d = 1
for c in s:
  sum += int(c)*d
  remain = sum%2019
  d *= 10
  counts[remain] += 1

ans = 0
for count in counts:
  ans += count*(count - 1) / 2
print(int(ans))

### FIXED CODE ###

s = input()[::-1]
counts = [0]*2019
counts[0] = 1
sum = 0
d = 1
for c in s:
  sum += int(c)*d
  remain = sum%2019
  d *= 10
  d %= 2019
  counts[remain] += 1

ans = 0
for count in counts:
  ans += count*(count - 1) / 2
print(int(ans))
### BUGGY CODE ###

from heapq import heappush, heappop
from itertools import permutations, accumulate, combinations
from math import pi, ceil, floor

from collections import defaultdict, deque,Counter
from operator import itemgetter
from bisect import bisect_left, bisect_right, insort_left, insort_right
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 6)
# MOD = 10 ** 9 + 7
# INF = float("inf")


def main():
    n, m, q = map(int, input().split())
    l = [tuple(map(int, input().split())) for _ in range(q)]
    ans = 0
    for i in range(2 ** q):  # とるかとらないかの2択
        check = [0] * q
        for j in range(q):
            if i >> j & 1:
                check[j] = 1
        # print(check)
        A = [1] * n
        used = [0] * n
        tmp = 0
        for k in range(q):
            if check[k]:  # とる時
                a, b, c, d = l[k]
                a -= 1
                b -= 1
                if not used[b]:  # 使ってない時は変更できる
                    A[b] = c + A[a]
                    tmp += d
                    used[b] = 1  # 変更ずみにする
                    used[a] = 1
                    if A[b] > m:  # m以上の場合はダメ
                        tmp = 0
                        break
                elif A[b] == c + A[a]:  # たまたま変更してからあってたら追加
                    tmp += d
                else:  # 条件に合わない場合
                    tmp = 0
                    break
        ans = max(ans, tmp)
    print(ans)





if __name__ == '__main__':
    main()

### FIXED CODE ###

from itertools import permutations, accumulate, combinations, combinations_with_replacement
import sys
input = sys.stdin.readline


def main():
    n, m, q = map(int, input().split())
    # <方針>：Aを全列挙する
    ans = 0
    a = [0] * q
    b = [0] * q
    c = [0] * q
    d = [0] * q
    for i in range(q):
        a[i], b[i], c[i], d[i] = map(int, input().split())
        a[i] -= 1
        b[i] -= 1
    for A in combinations_with_replacement(range(1, m + 1), n):
        tmp = 0
        for i in range(q):
            if A[b[i]] - A[a[i]] == c[i]:
                tmp += d[i]
        ans = max(ans, tmp)
    print(ans)


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

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

if n%2==0:
	ans=1
	for i in range(n//2):
		ans=ans*a[i]*a[i+n//2]
else:
	if n==1:
		ans=a[0]
	else:
		ans=a[0]
		for i in range(1,(n-1)//2+1):
			ans=ans*a[i]*a[i+(n-1)//2]

if ans>1000000000000000000:
	print("-1")
else:
	print(ans)

### FIXED CODE ###

import sys

def main():
    n = int(input())
    a=sys.stdin.readline().rstrip().split()
    if '0' in a:
        print(0)
        return
    ans=1
 
    for i in a:
        ans=ans*int(i)
        if ans>1000000000000000000:
            print("-1")
            return
    else:
        print(ans)
main()
### BUGGY CODE ###

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

for i in range(m):
    l, r = map(int,input().split())
    rg = range(l, r + 1)
    if i == 0:
        s = set(rg)
    else:
        x = s & set(rg)
        s = x

rg2  = set(range(1, n + 1))
ans = rg2 & s

print(len(ans))


### FIXED CODE ###

n, m = map(int,input().split())
lsl = []
lsr = []
for i in range(m):
    l, r = map(int,input().split())
    lsl.append(l)
    lsr.append(r)
lmax = max(lsl)
rmin = min(lsr)

if lmax > rmin:
    print(0)
else:
    ans1 = set(range(1,n + 1))
    ans2 = set(range(lmax,rmin + 1))
    ans = ans1 & ans2
    print(len(ans))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import queue

def main():
     n = int(input())
     s = input()

     r_list = []
     g_list = []
     b_list = []

     ans = 0

     for i in range(n):
          if s[i] == 'R':
               r_list.append(i)
          elif s[i] == 'G':
               g_list.append(i)
          else:
               b_list.append(i)

     for i in range(n):
          if s[i] == 'R':
               ans += check(i, g_list, b_list)

          if s[i] == 'G':
               ans += check(i, r_list, b_list)

          if s[i] == 'B':
               ans += check(i, r_list, g_list)

     print(ans)

def check(spot, first, second):
     ret = 0
     small_first = []
     big_first = []
     small_second = []
     big_second = []

     for f in first:
          if f < spot: small_first.append(f)
          else: big_first.append(f)

     for s in second:
          if s < spot: small_second.append(s)
          else: big_second.append(s)

     ret += len(small_first) * len(big_second) + len(small_second) * len(big_first)
     for n in small_first:
          ignore = spot + (spot - n)
          if ignore in big_second:
               ret += -1
     
     for n in small_second:
          ignore = spot + (spot - n)
          if ignore in big_first:
               ret += -1
     
     return ret

if __name__ == "__main__":
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-

import queue

def main():
     n = int(input())
     s = input()

     r_list = []
     g_list = []
     b_list = []

     ans = 0

     for i in range(n):
          if s[i] == 'R':
               r_list.append(i)
          elif s[i] == 'G':
               g_list.append(i)
          else:
               b_list.append(i)

     for i in range(n):
          if s[i] == 'R':
               ans += check(i, g_list, b_list)

          if s[i] == 'G':
               ans += check(i, r_list, b_list)

          if s[i] == 'B':
               ans += check(i, r_list, g_list)

     print(ans)

def check(spot, first, second):
     ret = 0
     small_first = []
     big_first = []
     small_second = []
     big_second = []

     for f in first:
          if f < spot: small_first.append(spot - f)
          else: big_first.append(f - spot)

     for s in second:
          if s < spot: small_second.append(spot - s)
          else: big_second.append(s - spot)

     return len(small_first) * len(big_second) + len(small_second) * len(big_first) - len(set(small_first) & set(big_second)) - len(set(small_second) & set(big_first))
     
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
D = []

for i in range(M):
    B, C = map(int, input().split())
    D += [C]*B

E = sorted(A + D, reverse=True)
print(sum(E[0:N]))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
D = []
E = []
for i in range(M):
    B, C = map(int, input().split())
    D.append([C, B])
D = sorted(D, reverse = True)

for j in range(len(D)):
    E += [D[j][0]]*D[j][1]
    if len(E) >= N:
        break

F = sorted(A + E, reverse = True)
print(sum(F[0:N]))
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
s = set(a)
s2 = set([])
for i in s:
    if a.count(i) % 2 == 1:
        s2.add(i)
print(len(s2))

### FIXED CODE ###

from collections import Counter
n=int(input())
c=Counter([int(input())for i in range(n)])
a=0
for i in c.values():a+=1if i%2else 0
print(a)
### BUGGY CODE ###

import math
from functools import reduce
s=0
K=int(input())
for a in range(K):
    for b in range(K):
        for c in range(K):
            x=reduce(math.gcd,(a+1,b+1,c+1))
            s+=x
print(s)

### FIXED CODE ###

import math
from functools import reduce
s=0
K=int(input())+1
for a in range(1,K):
    for b in range(a,K):
        for c in range(b,K):
            if a==b==c:
                s+=a
                continue
            x=reduce(math.gcd,(a,b,c))
            if a==b or b==c or c==a:
                s+=x*3
            else:
                s+=x*6
print(s)
### BUGGY CODE ###

import itertools
import math

d, g = map(int, input().split())
ls = [list(map(int, input().split())) for _ in range(d)]

res = float('inf')
for indices in itertools.permutations(range(d)):
    count = 0
    s = 0
    for i in indices:
        p, c = ls[i]
        if s + 100 * (i + 1) * p >= g:
            count += math.ceil((g - s) / (100 * (i + 1)))
            break
        else:
            count += p
            s += 100 * (i + 1) * p + c
            if s >= g:
                break
    res = min(res, count)
print(res)

### FIXED CODE ###

import itertools
import math

d, g = map(int, input().split())
ls = [[100 * (i + 1)] + list(map(int, input().split())) for i in range(d)]
s0 = [a * p for a, p, _ in ls]
s1 = [a * p + c for a, p, c in ls]

res = float('inf')
for indices in itertools.permutations(range(d)):
    count = 0
    s = 0
    for i in indices:
        if s + s0[i] >= g:
            count += math.ceil((g - s) / (100 * (i + 1)))
            break
        else:
            count += ls[i][1]
            if count >= res:
                break
            s += s1[i]
            if s >= g:
                break
    res = min(res, count)
print(res)
### BUGGY CODE ###

S = input()
T = input()

# dp[i][j] := Sのi文字目, Tのj文字目まで見た場合のLCS
dp = [[''] * (len(T) + 1) for i in range(len(S) + 1)]

for i in range(1, len(S) + 1):
    for j in range(1, len(T) + 1):
        if S[i - 1] == T[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + S[i - 1]
        else:
            if len(dp[i - 1][j]) > len(dp[i][j - 1]):
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = dp[i][j - 1]

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


### FIXED CODE ###

S = input()
T = input()

# dp[i][j] := Sのi文字目, Tのj文字目まで見た場合のLCS
dp = [[0] * (len(T) + 1) for i in range(len(S) + 1)]

for i in range(1, len(S) + 1):
    for j in range(1, len(T) + 1):
        if S[i - 1] == T[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

ans = ''
i, j = len(S), len(T)
while i > 0 and j > 0:
    if S[i - 1] == T[j - 1]:
        ans += S[i - 1]
        i, j = i - 1, j - 1
    elif dp[i][j - 1] > dp[i - 1][j]:
        j -= 1
    else:
        i -= 1

print(ans[::-1])
### BUGGY CODE ###

N=int(input())
L=list(map(int,input().split()))
R=list()
for i in range(1,N+1):
  R.append(L.index(i)+1)
print(" ".join(list(map(str,R))))

### FIXED CODE ###

N=int(input())
L=list(map(int,input().split()))
R=[0]*N
for i in range(0,N):
  R[L[i]-1]=i+1
print(" ".join(list(map(str,R))))
### BUGGY CODE ###

import copy

s = input()
s_sub = copy.deepcopy(s)

tar1 = "01"
tar2 = "10"

while((tar1 in s )or(tar2 in s)):
    if tar1 in s:
        s = s.replace(tar1,"")
    if tar2 in s:
        s = s.replace(tar2,"")



print(len(s_sub)-len(s))


### FIXED CODE ###

import copy

s = input()
s_sub = copy.deepcopy(s)
# # 
# tar1 = "01"
# tar2 = "10"
# tar3 = ["1010","1001","0101","0110","1100","0011",""]
# 
# while((tar1 in s )or(tar2 in s)):
# 
# 
#     # for i in range(4):
#     #     if tar3[i] in s:
#     #         s = s.replace(tar3[i],"")
# 
# 
#     if tar1 in s:
#         s = s.replace(tar1,"",1)
#     if tar2 in s:
#         s = s.replace(tar2,"",1)
# 
# 
# 
# print(len(s_sub)-len(s))

#0と1の数数えて差分が残るのでは？
l1 = s.count("0")
l2 = s.count("1")
l3 = abs(l1-l2)

print(len(s_sub)-l3)
### BUGGY CODE ###

N = int(input())
A= list(map(int, input().split()))
mod = 10 ** 9 + 7
sum = 0
for i in range(60):
    count0 = 0
    count1 = 0
    count2 = 0

    for j in range(N):
        if A[j] & 1:
            count1 += 1
        else:
            count0 += 1
        A[j] = A[j] >> 1
    count2 = count0 * count1
    sum += count2 * (2 ** i)

print(sum % mod)


### FIXED CODE ###

N = int(input())
A= list(map(int, input().split()))
mod = 10 ** 9 + 7
sum = 0
for i in range(60):
    count0 = 0
    count1 = 0
    count2 = 0

    for j in range(N):
        if A[j] & 1:
            count1 += 1
        else:
            count0 += 1
        A[j] = A[j] >> 1
    count2 = count0 * count1
    sum += count2 * (2 ** i)

print(sum % mod)
### BUGGY CODE ###

input = raw_input

M = 2019
s = input()
n = len(s)
s = int(s)

div = 10

counts = [0] * M
m = 1
for i in range(n+1):
    j = (s % m) % M
    counts[j] += 1
    m *= 10

out = 0
for c in counts:
    out += (c * (c-1) // 2)

print(out)

### FIXED CODE ###

input = raw_input

M = 2019
s = input()
#n = len(s)
#s = int(s)

div = 10

counts = [0] * M
#m = 1

counts[0] += 1
cur = 0

m = 1
for c in reversed(s):
    cur = (int(c) * m + cur) % M
    counts[cur] += 1
    m = (m * 10) % M
    #m *= 10

out = 0
for c in counts:
    out += (c * (c-1) // 2)

print(out)
### BUGGY CODE ###

N,K = [int(i) for i in input().split(' ')]
A = [int(i) for i in input().split(' ')]
 
where_li = []
pre = 0
for i in range(N):
	if A[pre] in where_li:
		break
	where_li.append(A[pre])
	pre = A[pre]-1

len_w = len(where_li)
mod_s = len_w-where_li.index(A[pre])
if K<=len_w:
	print(where_li[K-1])
else:
	if (K-len_w)%mod_s==0:
		d = mod_s
	else:
		d = (K-len_w)%mod_s
	print(where_li[d-1+where_li.index(A[pre])])

### FIXED CODE ###

N,K = [int(i) for i in input().split(' ')]
A = [int(i) for i in input().split(' ')]
 
where_li = []
pre = 0
for i in range(N):
	where_li.append(A[pre])
	pre = A[pre]-1

len_w = len(where_li)
a = where_li.index(A[pre])
mod_s = len_w-a
if K<=len_w:
	print(where_li[K-1])
else:
	if (K-len_w)%mod_s==0:
		d = mod_s
	else:
		d = (K-len_w)%mod_s
	print(where_li[d-1+a])
### BUGGY CODE ###

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

S = input()
n = len(S)
integer = int(S)

ans = 0
for i in range(n-3):
    for j in range(i+4, n+1):
        num = (integer//10**(n-j) - integer//10**(n-i)*10**(j-i))
        if num % 2019 == 0:
            # print((integer//10**j - integer//10**i))
            ans += 1

print(ans)

### FIXED CODE ###

S = input()

res = [0] * 2019
res[0] = 1

d = 1
a = 0

for c in reversed(S):
    a += int(c) * d
    a %= 2019
    res[a] += 1
    d *= 10
    d %= 2019

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

s = input()
q = int(input())
is_head = True
 
for _ in range(q):
    tmp = input().split(" ")
    if (len(tmp) == 1):
        is_head = not is_head
    else:
        t, f, c = tmp
        if (f == '1'):
            if (is_head):
                s = c + s
            else:
                s =  s + c
        else:
            if (is_head):
                s = s + c
            else:
                s =  c + s
 
if is_head:
    print(s)
else:
    print(s[::-1])

### FIXED CODE ###

import collections

d = collections.deque()
for i in input():
    d.append(i)
q = int(input())
is_head = True

for _ in range(q):
    tmp = input().split(" ")
    if (len(tmp) == 1):
        is_head = not is_head
    else:
        t, f, c = tmp
        if (f == '1'):
            if (is_head):
                d.appendleft(c)
            else:
                d.append(c)
        else:
            if (is_head):
                d.append(c)
            else:
                d.appendleft(c)

ans = ""
if is_head:
    while len(d) > 0:
        ans += d.popleft()
else:
    while len(d) > 0:
        ans += d.pop()
print(ans)
### BUGGY CODE ###

import sys
sys.stdin.readline

n = int(input())
a = []
for _ in range(n):
    sa = input().strip()
    tmp = 0
    for i in range(len(sa)):
        if sa[i] == '.':
            break
        tmp = tmp * 10 + int(sa[i])
    i += 1
    for j in range(i, i + 9):
        if j < len(sa):
            tmp = tmp * 10 + int(sa[j])
        else:
            tmp *= 10
    a.append(tmp)

div25 = [[0, 0] for _ in range(n)]
for i, _a in enumerate(a):
    while _a % 2 == 0:
        div25[i][0] += 1
        _a //= 2
    while _a % 5 == 0:
        div25[i][1] += 1
        _a //= 5

div25.sort(key=lambda x: (-x[1], -x[0]))

plot = [[0 for _ in range(50)] for _ in range(25)]
ans = 0
for d25 in div25:
    rem2, rem5 = max(0, 18 - d25[0]), max(0, 18 - d25[1])
    for j in range(rem5, 25):
        for k in range(rem2, 50):
            ans += plot[j][k]
    plot[d25[1]][d25[0]] += 1
print(ans)

### FIXED CODE ###

import sys
sys.stdin.readline

n = int(input())
a = []
for _ in range(n):
    sa = input().strip()
    tmp = 0
    for i in range(len(sa)):
        if sa[i] == '.':
            break
        tmp = tmp * 10 + int(sa[i])
    i += 1
    for j in range(i, i + 9):
        if j < len(sa):
            tmp = tmp * 10 + int(sa[j])
        else:
            tmp *= 10
    a.append(tmp)

div25 = [[0, 0] for _ in range(n)]
for i, _a in enumerate(a):
    while _a % 2 == 0:
        div25[i][0] += 1
        _a //= 2
    while _a % 5 == 0:
        div25[i][1] += 1
        _a //= 5

div25.sort(key=lambda x: (-x[1], -x[0]))

plot = [[0 for _ in range(45)] for _ in range(20)]
ans = 0
for d25 in div25:
    rem2, rem5 = max(0, 18 - d25[0]), max(0, 18 - d25[1])
    for j in range(rem5, 20):
        for k in range(rem2, 45):
            ans += plot[j][k]
    plot[d25[1]][d25[0]] += 1
print(ans)
### BUGGY CODE ###

s = input()
q = int(input())
for i in range(q):
    query = list(map(str, input().split()))
    if len(query) == 1:
        s = s[::-1]
    else:
        if int(query[1]) == 1:
            s = query[2] + s
        else:
            s = s + query[2]
print(s)            

### FIXED CODE ###

import sys
input = sys.stdin.readline
s = input().rstrip()
q = int(input())
query = []
rev = 0
for i in range(q):
    query.append(list(map(str, input().split())))
sa = []
sb = []
for i in range(q):
    if len(query[i]) == 1:
        rev = (rev + 1) % 2
    else:
        if rev == 0:
            if query[i][1] == '1':
                sa.append(query[i][2])
            else:
                sb.append(query[i][2])
        else:
            if query[i][1] == '2':
                sa.append(query[i][2])
            else:
                sb.append(query[i][2])
ssa = ''.join(sa)
ssa = ssa[::-1]
ssb = ''.join(sb)
ss = ssa + s + ssb
if rev == 1:
    ss = ss[::-1]
print(ss)
### BUGGY CODE ###

from collections import deque

s = input()
q = int(input())
query = [input().split() for i in range(q)]

d = deque(['S'])

#d = ['S']

rev = 0

for i in range(q):
    if query[i][0] == '2':
        if query[i][1] == '1':
            d.appendleft(query[i][2])
        else:
            d.append(query[i][2])
    else:
        d.reverse()
        rev += 1

ans = deque()

if rev % 2 == 1:
    s = ''.join(list(reversed(s)))

while len(d):
    tmp = d.popleft()
    if tmp == 'S':
        ans.append(s)
    else:
        ans.append(tmp)

print(*ans,sep='')

### FIXED CODE ###

from collections import deque

s = input()
q = int(input())
query = [input().split() for i in range(q)]

d = deque(['S'])

#d = ['S']

rev = False

for i in range(q):
    if query[i][0] == '1':
        rev = not rev
        continue
    
    if not rev:
        if query[i][0] == '2':
            if query[i][1] == '1':
                d.appendleft(query[i][2])
            else:
                d.append(query[i][2])
    else:
        if query[i][0] == '2':
            if query[i][1] == '1':
                d.append(query[i][2])
            else:
                d.appendleft(query[i][2])

#ans = deque()
if rev:
    #d = ''.join(list(reversed(d)))
    s = s[::-1]



while len(d):
    if rev:
        tmp = d.pop()
    else:
        tmp = d.popleft()
    if tmp == 'S':
        #ans.append(s)
        print(s,end='')
    else:
        print(tmp,end='')
        #ans.append(tmp)

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

from collections import Counter
n = int(input())
s_inputs = [input() for i in range(n)]

s_dic = Counter(s_inputs)
print('\n'.join(sorted([k for k,v in s_dic.items() if v==max(s_dic.values())])))

### FIXED CODE ###

from collections import Counter
n = int(input())
s_inputs = [input() for i in range(n)]

s_dic = Counter(s_inputs)
s_max = max(s_dic.values())
print('\n'.join(sorted([k for k,v in s_dic.items() if v==s_max])))
### BUGGY CODE ###

N,W=map(int,input().split())
WV=[list(map(int,input().split())) for i in range(N)]

DP_W=[0]*(W+1)

for i in range(N):
    for j in range(W,-1,-1):
        if j+WV[i][0]<=W:
            DP_W[j+WV[i][0]]=max(DP_W[j+WV[i][0]],DP_W[j]+WV[i][1])

print(max(DP_W))

### FIXED CODE ###

N,W=map(int,input().split())
WV=[list(map(int,input().split())) for i in range(N)]

DP_W=[0]*(W+1)

for i in range(N):
    for j in range(W,-1,-1):
        if j+WV[i][0]<=W:
            DP_W[j+WV[i][0]]=max(DP_W[j+WV[i][0]],DP_W[j]+WV[i][1])

print(max(DP_W))