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


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

#Aは小さい順に並べる
A_list = list(map(int,input().split()))
A_list = sorted(A_list)
C_list = []

ans = 0

for i in range(M):
    bi,ci = map(int,input().split())
    for j in range(bi):
        C_list.append(ci)

C_list=sorted(C_list,reverse=True)

#NにたりないばあいはNまで1で埋める、Nより大きい場合はNまでを使う
if len(C_list) > N:
    C_list = C_list[0:N]
else:
    for i in range(N-len(C_list)):
        C_list.append(1)

#どこの添字からAとCが逆転するか調べる
for i in range(N):
    #Aは昇順、Cは降順
    if C_list[i] > A_list[i]:
        A_list[i] = C_list[i]
    else:
        break

print(sum(A_list))


### FIXED CODE ###


#AのリストにCのリストを加えて大きい順に並べ替えてNまでの和を求める
N,M = map(int,input().split())

#Aの入力
A_list = list(map(int,input().split()))

C_list = []

#Cのリストに追加する
for i in range(M):
    bi,ci = map(int,input().split())
    C_list.append([bi,ci])

#C_listをCの値でソート
C_list=sorted(C_list, reverse=True, key=lambda x:x[1])

count = 0
for bi,ci in C_list:
    count += bi
    if count > N:
        #countがNより大きくなったらNより大きくなった分だけ使う
        bi = N - count + bi
    A_list.extend([ci]*bi)

#A_Listを大きい順に並べ替える
A_list=sorted(A_list,reverse=True)

#N番目までの総和を求める
print(sum(A_list[0:N]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from operator import itemgetter

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

Max = [[(0, A[0])]]
ans = 0
for bit in range(1, (1<<N)):
    dic = {}
    for i in range(N):
        if bit&(1<<i) != 0:
            for ind, val in Max[bit-(1<<i)]:
                dic[ind] = val
    com = [(bit, A[bit])]
    for ind, val in dic.items():
        com.append((ind, val))
    com.sort(reverse=True, key=itemgetter(1))
    Max.append(com[:2])
    tmp = com[0][1] + com[1][1]
    if tmp > ans:
        ans = tmp
    print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

Max = [[(0, A[0])]]
ans = 0
for bit in range(1, (1<<N)):
    dic = {bit: A[bit]}
    for i in range(N):
        if bit&(1<<i) != 0:
            for ind, val in Max[bit-(1<<i)]:
                dic[ind] = val
    com = []
    for ind, val in dic.items():
        if len(com) < 2:
            com.append((ind, val))
        else:
            if com[0][1] < com[1][1]:
                if com[0][1] < val:
                    com[0] = (ind, val)
                elif com[1][1] < val:
                    com[1] = (ind, val)
            else:
                if com[1][1] < val:
                    com[1] = (ind, val)
                elif com[0][1] < val:
                    com[0] = (ind, val)               
    Max.append(com)
    tmp = com[0][1] + com[1][1]
    if tmp > ans:
        ans = tmp
    print(ans)
### BUGGY CODE ###

from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
import sys

for line in sys.stdin:
    small, large = sorted(int(n) for n in line .split())
    for i in (n for n in xrange(small, 0, -1) if not small % n):
        if not large % i:
            gcd = i
            break
    for i in xrange(2, small + 1):
        if not i * large % small:
            lcm = i * large
            break
    print(gcd, lcm)

### FIXED CODE ###

from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
import sys
from fractions import gcd

for line in sys.stdin:
    small, large = sorted(int(n) for n in line .split())
    G = gcd(large, small)
    print(G, large // G * small)
### BUGGY CODE ###

N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ans = 0
cmb = [0]*N
cmb[K-1] = 1
for i in range(K, N):
    cmb[i] = cmb[i-1]*i//(i - K + 1)
for i in range(K, N):
    cmb[i] = cmb[i]%(10**9+7)
    
for i in range(N):
    fac = cmb[i] - cmb[N-i-1]
    num = (fac*a[i])%(10**9+7)
    ans += num
    ans = ans%(10**9+7)
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
mod = 10**9+7
ans = 0
cmb = [0]*N
x = [0]*N
cmb[K-1] = 1
def Pow(a, n):
    if n == 0: return 1
    if n%2 == 0:
        return (Pow(a, n//2))**2%mod
    else:
        return Pow(a, n-1)*a%mod
for i in range(1,N-K+1):
    x[i] = Pow(i, mod-2)
    
for i in range(K, N):
    cmb[i] = cmb[i-1]*i%mod*x[i-K+1]%mod
for i in range(N):
    fac = cmb[i] - cmb[N-i-1]
    num = fac*a[i]%mod
    ans += num
    ans = ans%(10**9+7)
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
h=[]
for i in range(n):
   h.append(int(input())) 
h.sort()
ans=10**9
a=[]
for i in range(n-k+1):
    ans=min(ans,max(h[i:i+k])-min(h[i:i+k]))
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
h = [int(input()) for i in range(n)]
h.sort()
ans=10**9
for i in range(n-k+1):
    ans=min(ans,h[i+k-1]-h[i])
print(ans)
### BUGGY CODE ###

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

b = [0] * 60
for i in a:
    for j in range(60):
        b[j] += bool(i & (1 << j))
#print(b[j])
ans = 0
inf = int(1e9 + 7)
for i in range(60):
    ans += b[i] * (n - b[i]) * (1 << i) % inf
    ans %= inf
print(ans)

### FIXED CODE ###

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

b = [0] * 60
for i in a:
    for j in range(60):
        b[j] += bool(i & (1 << j))
#print(b[j])
ans = 0
inf = int(1e9 + 7)
for i in range(60):
    ans += b[i] * (n - b[i]) * (1 << i) % inf
    ans %= inf
print(ans)
### BUGGY CODE ###


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


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a*b // gcd(a, b)


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

MOD = 10 ** 9 + 7
ans = 0
for a in A:
    ans += l * pow(a, MOD-2, MOD)
    ans %= MOD

print(ans)


### FIXED CODE ###

from functools import reduce
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))


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


MOD = 10 ** 9 + 7
lcm %= MOD
ans = 0
for a in A:
    ans += lcm * pow(a, MOD-2, MOD)
    ans %= MOD

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

s = input()
q = int(input())
f = False
# Falseだと左が先頭
for _ in range(q):
    t = input().split()
    if t[0]=="1":
        f = not f
    elif t[0]=="2":
        if f:
            t[2]=t[2][::-1]
            if t[1]=="1":
                s = s+t[2]
            elif t[1]=="2":
                s = t[2]+s
        else:
            if t[1]=="1":
                s = t[2]+s
            elif t[1]=="2":
                s = s+t[2]
if f:
    print(s[::-1])
else:
    print(s)

### FIXED CODE ###

from collections import deque
s = deque(input())
q = int(input())
f = False
# Falseだと左が先頭
for _ in range(q):
    t = input().split()
    if t[0]=="1":
        f = not f
    elif t[0]=="2":
        t[2]=list(t[2])
        if f:
            t[2]=t[2][::-1]
            if t[1]=="1":
                s.extend(t[2])
            elif t[1]=="2":
                s.extendleft(t[2])
        else:
            if t[1]=="1":
                s.extendleft(t[2])
            elif t[1]=="2":
                s.extend(t[2])
if f:
    print("".join(s)[::-1])
else:
    print("".join(s))
### BUGGY CODE ###

import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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


while k:
    lst=[1]*n
    dic=defaultdict(int)
    cnt=0
    for i in range(n):
        lst[i]+=cnt
        cnt-=dic[i]
        if a[i]>0:
            dic[i+a[i]]+=1
            cnt+=1
    # print(lst)
    dic=defaultdict(int)
    cnt=0
    for i in range(n)[::-1]:
        lst[i]+=cnt
        cnt-=dic[i]
        if a[i]>0:
            dic[i-a[i]]+=1
            cnt+=1
    # print(lst)
    k-=1
    if sum(lst)==n*n:
        break
    # print(k)
    a=lst[:]

print(*lst)

### FIXED CODE ###

import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]


def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))

    # if sum(a)==0:
    #     print(*a)
    #     quit()
    while k:
        lst=[1]*n
        dic={}
        cnt=0
        for i in range(n):
            lst[i]+=cnt
            if i in dic:
                cnt-=dic[i]
            if a[i]>0:
                if not i+a[i] in dic:
                    dic[i+a[i]]=1
                else:
                    dic[i+a[i]]+=1
                cnt+=1

        dic={}
        cnt=0
        for i in range(n)[::-1]:
            lst[i]+=cnt
            if i in dic:
                cnt-=dic[i]
            if a[i]>0:
                if not i-a[i] in dic:
                    dic[i-a[i]]=1
                else:
                    dic[i-a[i]]+=1
                cnt+=1
        k-=1
        if sum(lst)==n*n:
            break
        # print(k)
        a=lst[:]

    print(*lst)

main()
### BUGGY CODE ###

x, k, d = map(int, input().split())
mind = 1000000000000000
c = 0
while k > 0:
    k -= 1
    if abs(x - d - 0) <= abs(x + d - 0):
        x -= d
    else:
        x += d
    if abs(x) == mind:
        break
    mind = min(mind, abs(x))

if k%2 == 0 or k == 0:
    print(abs(mind - 0))
else:
    mind = min(abs(mind + d - 0), abs(mind - d - 0))
    print(mind)
    

### FIXED CODE ###

x, k, d = map(int, input().split())
x = abs(x)
if (x - k*d) >= 0:
    x -= k*d
else:
    k -= int(x/d)
    x -= int(x/d) * d
    if (k%2) != 0:
        x -= d 
print(abs(x))
### BUGGY CODE ###

N=input()
s=input()

N=int(N)
score=[]
wn=[]
bn=[]
a=0
b=0

for i in range(N):
    j=N-(i+1)
    if(s[j]=="."):
        a+=1
    if(s[i]=="#"):
        b+=1
    bn.insert(0,a)
    wn.append(b)
bn.append(0)
wn.insert(0,0)
#print(bn)
#print(wn)

#score算出
a=0
for i in range(N+1):
    score.append(bn[i]+wn[i])

score.sort()
print(score[0])

### FIXED CODE ###

N=input()
s=input()

N=int(N)
wn=[]
bn=[]
a=0
b=0

#各行間よりも前と後ろに何個白（黒）があるかをカウント
wn.append(0)
for i in range(N):
    j=N-(i+1)
    if(s[j]=="."):
        a+=1
    if(s[i]=="#"):
        b+=1
    bn.append(a)
    wn.append(b)

bn.reverse()
bn.append(0)
#print(bn)
#print(wn)

#各行間のscore算出
min=1000000
for i in range(N+1):
    score=bn[i]+wn[i]
    if(score<min):
        min=score

print(min)
### BUGGY CODE ###

import heapq

n, m = map(int, input().split())
A_list = list(map(int, input().split()))
B_list = [0]*m
C_list = [0]*m
for i in range(m):
    b, c = map(int, input().split())
    B_list[i] = b
    C_list[i] = c
heap = []
ans = 0
for a in A_list:
    heapq.heappush(heap, a)
for i in range(m):
    for _ in range(B_list[i]):
        min_ = heapq.heappop(heap)
        if min_ < C_list[i]:
            heapq.heappush(heap, C_list[i])
        else:
            heapq.heappush(heap, min_)
while heap:
    ans += heapq.heappop(heap)
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
A_list = list(map(int, input().split()))
BC_list = []
for _ in range(m):
    BC_list.append(list(map(int, input().split())))
A_list.sort()
BC_list.sort(key=lambda x: x[1], reverse=True)
C_list = []
for i in range(m):
    for _ in range(BC_list[i][0]):
        if len(C_list) < n:
            C_list.append(BC_list[i][1])
        else:
            break
    else:
      continue
    break

for i in range(min(n, len(C_list))):
    if A_list[i] < C_list[i]:
        A_list[i] = C_list[i]
    else:
        break

ans = sum(A_list)
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
if K <41:
    for q in range(K):
        foo = [1 for k in range(N)]
        for k in range(N):
            for j in range(1, min(A[k]+1, N-k)):
                foo[k+j] +=1
            for j in range(1, min(A[k]+1, k+1)):
                foo[k-j] +=1
        #print(foo)

        for k in range(N):
            A[k] = foo[k]
        #print(A)
else:
    for k in range(N):
        A[k] = N


print(" ".join(map(str, A)))

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
foo = [[0 for k in range(N)] for k in range(42)]
for k in range(len(A)):
    foo[0][k] = A[k]
if K <42:
    for q in range(K):
        unko = [0 for k in range(N)]
        for k in range(N):
            if k + foo[q][k]+1 < N:
                unko[k + foo[q][k]+1] -=1
            unko[max(k - foo[q][k], 0)] +=1
        unchi = 0
        for k in range(N):
            unchi += unko[k]
            foo[q+1][k] = unchi
        #print(unko)
        #print(foo[q+1])
        count =0
        for l in range(N):
            if foo[q+1][l] < N:
                break
            else:
                count +=1
        
        if count == N:
            break
        
                        
        #print(foo)
    print(" ".join(map(str, foo[q+1])))

     
else:
    print((str(N)+" ")*(N-1)+str(N))
### BUGGY CODE ###

K,S = map(int, input().split())

def binaly_serch(ls,k):#lsはリスト、kが求めたいもの
    ls.sort()
    n = len(ls)
    s = 0
    e = n#あえてls から一つ出たのにしておく。このおかげでk = ls[n-1]の時でも探索できる
    while int(e - s) >= 1:#intでcastして繰り下がった方を見て、e = bという条件にしてるからこれで全部探せる
        b = int((s+e)/2)
        if ls[b] == k:
            return True
        elif ls[b] < k:
            s = b + 1
        else:
            e = b
    return False
ans = 0
kls = [i for i in range(K+1)]
for i in range(K+1):
    for j in range(K+1):
        if S-(i+j) > K:
            continue
        else:
            if binaly_serch(kls,S-(i+j)):
                ans += 1

print(ans)


### FIXED CODE ###

K,S = map(int, input().split())

ans = 0
for i in range(K+1):
    for j in range(K+1):
        z = S-(i+j)
        if 0<= z and z <= K:
            ans += 1
print(ans)
### BUGGY CODE ###

import collections
n,rev,q = int(raw_input()) ,False,collections.deque()

stack = []
for ai in map(int, raw_input().split()):
	stack.append(ai)
	stack = stack[::-1]
print ' '.join(map(str, stack))

### FIXED CODE ###

import collections
n,rev,q = int(raw_input()) ,False,collections.deque()

for ai in map(int, raw_input().split()):
	if rev: q.append(ai)
	else: q.appendleft(ai)
	rev ^= True

print ' '.join(map(str, list(q)[::1 if rev else -1]))
### BUGGY CODE ###

s = input()
x = int(input())
n = len(s)

pos = [[] for __ in range(256)]
for i in range(n):
    pos[ord(s[i])].append(i)

f = set()
for c in range(97, 123):
    for i in pos[c]:
        for j in range(i, n):
            f.add(s[i:j+1])
            if len(f) >= 1000:
                break
    if len(f) >= x:
        break

def cmp(u, v):
    while len(u) < len(v): u = u + '1'
    while len(u) > len(v): v = v + '1'
    return u > v

p = [u for u in f]
for i in range(len(p)):
    for j in range(i+1, len(p)):
        if cmp(p[i], p[j]):
            p[i], p[j] = p[j], p[i]

print(p[x - 1])

### FIXED CODE ###

s = input()
x = int(input())
n = len(s)

pos = [[] for __ in range(256)]
for i in range(n):
    pos[ord(s[i])].append(i)

f = set()
for c in range(97, 123):
    for i in pos[c]:
        for j in range(x):
            f.add(s[i:i+j+1])
    if len(f) >= x:
        break

p = [u for u in f]
p.sort()
print(p[x - 1])
### BUGGY CODE ###

from heapq import heappush, heappop

if __name__ == '__main__':
    # ??????????????\???
    # ???????????????
    h = []
    while True:
        raw_input = input()
        if raw_input == 'end':
            break
        if raw_input == 'extract':
            pri, item = heappop(h)
            print(item)
        else:
            data = raw_input.split(' ')
            heappush(h, (-1*int(data[1]), data[1]))

### FIXED CODE ###

from heapq import heappush, heappop

if __name__ == '__main__':
    # ??????????????\???
    # ???????????????
    h = []
    while True:
        raw_input = input()
        if raw_input == 'extract':
            pri, item = heappop(h)
            print(item)
        elif raw_input == 'end':
            break
        else:
            cmd, pri = raw_input.split()
            heappush(h, (-1*int(pri), pri))
### BUGGY CODE ###

def hahaha():
    n=int(input())
    list=[]
    count=0
    for i in range(0,n):
        x=str(input())
        if not(x in list):
            count+=1
            list.append(x)

    print(count)
if __name__ == '__main__':
    hahaha()


### FIXED CODE ###

def hahaha():
    n=int(input())
    count=1
    list=[]
    for i in range(0,n):
        list.append(str(input()))
    list.sort()
    a=list[0]
    for j in range(0,n):
        if a!=list[j]:
            a=list[j]
            count+=1
    print(count)
if __name__ == '__main__':
    hahaha()
### BUGGY CODE ###

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

x = []
for i in range(max(d)+1):
	x.append(d.count(i))
ans = 1
if d[0] == 0 and x[0] == 1:
	for i in range(1, len(x)-1):
		ans = ans * (x[i]**x[i+1])
else:
	ans = 0

print(ans%998244353)

### FIXED CODE ###

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

dd = sorted(d)
c = []
j = 0
for i in range(max(d)+1):
	tmp = 0
	while dd[j] == i:
		tmp += 1
		j += 1
		if j == n:
			break
	c.append(tmp)

ans = 1
if d[0] == 0 and d.count(0) == 1 and c.count(0) == 0:
	for i in range(1, max(d)):
		ans = ans * (c[i]**c[i+1])
else:
	ans = 0

print(ans%998244353)
### BUGGY CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product#accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
def run():
    N, M = map(int, sysread().split())
    to = [[] for _ in range(N+1)]
    AB = list(map(int, read().split()))
    for i in range(M):
        a = AB[2*i]
        b = AB[2*i+1]
        to[a].append(b)
        to[b].append(a)

    seen = [False] * (N+1)
    stack = []
    seen[1] = True
    heappush(stack, (0, 1, 0))# (distance, node, prev)
    mark = [-1] * (N+1)
    while stack:
        dist, current, prev = heappop(stack)
        seen[current] = True
        if mark[current] == -1:
            mark[current] = str(prev)
        for next in to[current]:
            if not seen[next]:
                heappush(stack, (dist+1, next, current))

    print('Yes')
    print('\n'.join(mark[2:]))

if __name__ == "__main__":
    run()

### FIXED CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product#accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
from collections import deque
def run():
    N, M = map(int, sysread().split())
    to = [[] for _ in range(N+1)]
    AB = list(map(int, read().split()))
    A = AB[::2]
    B = AB[1::2]
    for a,b in zip(A,B):
        to[a].append(b)
        to[b].append(a)

    seen = [False] * (N+1)
    queue = deque([])
    seen[1] = True
    queue.append((1, 0))# (node, prev)
    mark = [0] * (N+1)

    while queue:
        current, prev = queue.popleft()
        for next in to[current]:
            if not seen[next]:
                queue.append((next, current))
                mark[next] = current
                seen[next] = True

    print('Yes')
    mark = [str(val) for val in mark]
    print('\n'.join(mark[2:]))

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

n = int(input())
l = list(map(int,input().split()))
c = 1
for q in range(10000000):
  for i in range(n-1):
    if l[i]==0:
      continue
    elif l[i]<=l[i+1] and i!=n-2:
      l[i] -= 1
    elif l[i]<=l[i+1] and i==n-2:
      l[i] -= 1
      l[i+1] -=1
    else:
      c += 1
      l[i] -= 1
      break

print(c)

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
c = 0
if n==1:
  print(*l)
  exit()
while l.count(0)!=n:
  for i in range(n-1):
    if l[i]==0 and i!=n-2:
      continue
    elif l[i]==0 and i==n-2:
      c += 1
      l[n-1] -=1
    elif l[i]<=l[i+1] and i!=n-2:
      l[i] -= 1
    elif l[i]<=l[i+1] and i==n-2:
      l[i] -= 1
      l[i+1] -=1
      c += 1
    else:
      c += 1
      l[i] -= 1
      break
print(c)
### BUGGY CODE ###

#! cat input | python3 main.py

n, k = map(int, input().split())
a = list(map(int, input().split()))
if n == 1:
    if a[0] == k:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
    __import__("sys").exit()
a.sort()
ma = max(a)
def isfact(n):
    if n == 2: return True
    for i in (2, n**0.5 + 1):
        if n % i == 0:
            return False
    return True
def calcfacts():
    r = []
    for i in range(2, 10**5):
        if isfact(i):
            r.append(i)
    return r
allfacts = calcfacts()

def prim_fact(n):
    facts = []
    ti = 0
    t = allfacts[ti]
    nn = n ** 0.5 + 1
    while True:
        if n % t == 0:
            facts.append(t)
            n //= t
        else:
            ti += 1
            t = allfacts[ti]
        if t >= n or t > nn:
            if n != 1:
                facts.append(n)
            break
    return facts


def f(a, k, ma):
    minv = float("inf")
    for i, v in enumerate(a[1:]):
        if v - a[i] != 0:
            minv = min(minv, v - a[i])
    minv = min(minv, a[0])

    sets = []
    setn = set()
    for v in a:
        s = set(prim_fact(v))
        sets.append(s)
        for i in s: setn.add(i)
    # for v in setn:
    #     for s in sets:
    #         if v not in s:
    #             break
    #     else:
    #         minv = min(minv, v)
    #         break
    # else:
    #     return False

    if minv == 1:
        return False

    a = a[:]
    for i in range(0, ma + minv, minv):
        if i == k:
            return False
        if i < a[0]:
            continue
        if i == a[0]:
            del a[0]
        else:
            return False
    return True

if ma < k:
    print("IMPOSSIBLE")
elif f(a, k, ma):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")


### FIXED CODE ###

a, b = map(int, input().split())
array = list(map(int, input().split()))
impossible = "IMPOSSIBLE"
possible = "POSSIBLE"

array = list(set(array))

if len(array) == 1:
    if b == array[0]:
        print(possible)
    else:
        print(impossible)
    exit(0)

array.sort()

btw = [v1 - v2 for v1, v2 in zip(array[1:], array[0:])]
n = sorted(btw)[0]

same = len(set(btw)) == 1 or all([v % n == 0 for v in btw])

if b in array:
    print(possible)
elif array[-1] < b:
    print(impossible)
elif same and (b - array[0]) % n == 0:
    print(possible)
else:
    print(impossible)
### BUGGY CODE ###

def main():
    S = input()
    Q = int(input())
    S_reverse = S[::-1]

    for i in range(Q):
        q = list(input().split(' '))
        if len(q) > 1:
            if q[1] == '1':
                S = q[2] + S
                S_reverse = S_reverse + q[2] 
            elif q[1] == '2':
                S = S + q[2]
                S_reverse = q[2] + S_reverse
        elif q[0] == '1':
            temp = S_reverse
            S_reverse = S
            S = temp

    print(S)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import deque

def main():
    S = input()
    Q = int(input())

    t = deque(S)
    reverse = False
    for _ in range(Q):
        query = input()
        if query[0] == '1':
            reverse = not reverse
        elif query[0] == '2':
            _, F, C = query.split()
            if F == '1':
                if reverse:
                    t.append(C)
                else:
                    t.appendleft(C)
            elif F == '2':
                if reverse:
                    t.appendleft(C)
                else:
                    t.append(C)
    
    result = ''.join(t)
    if reverse:
        result = result[::-1]

    print(result)

if __name__ == '__main__':
    main()