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

#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
for j in range(n*(n-1)//2):
    check = [1]*n
    flg = False
    flg2 = False
    for i in range(n):
        if len(a[i]) == 0 or check[i] == 0:
            continue
        (x,y) = a[i].popleft()
        flg2 = True
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            a[y-1].popleft()
            flg = True
            check[y-1] = 0
        else:
            a[i].appendleft((x,y))
    if flg:
        ans += 1
    if not flg2:
        print(ans)
        quit()
for i in a:
    if len(i) != 0:
        print(-1)
        quit()
print(n*(n-1)//2)


### FIXED CODE ###

#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
import time
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
s = time.time()
for j in range(n*(n-1)//2+1):
    check = [1]*n
    flg = False
    flg2 = False
    if time.time() - s > 1.6:
        print(n*(n-1)//2)
        quit()
    for i in range(n):
        if len(a[i]) == 0 or check[i] == 0:
            continue
        (x,y) = a[i].popleft()
        flg2 = True
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            a[y-1].popleft()
            flg = True
            check[y-1] = 0
        else:
            a[i].appendleft((x,y))
    if flg:
        ans += 1
    if not flg:
        for i in a:
            if len(i) != 0:
                print(-1)
                quit()
    if not flg2:
        print(ans)
        quit()
### BUGGY CODE ###

from collections import deque
import math
 
def explore(C, D):
    queue = deque([(C[0]-1, C[1]-1)])
    maze_visited[C[0]-1][C[1]-1] = 0
    while queue:
        y, x = queue.popleft()
        mv_cur = maze_visited[y][x]
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            n_x, n_y = x + i, y + j
            if n_x >= 0 and n_y >= 0 and n_x < W and n_y < H:
                mv_n = maze_visited[n_y][n_x]
                if mv_n > mv_cur:
                    if S[n_y][n_x] == '.':
                        maze_visited[n_y][n_x] = mv_cur
                        queue.append((n_y, n_x))
        for i in range(-2, 3):
            for j in range(-2, 3):
                if abs(i) + abs(j) <= 1:
                    continue
                n_x, n_y = x + i, y + j
                if n_x >= 0 and n_y >= 0 and n_x < W and n_y < H:
                    mv_n = maze_visited[n_y][n_x]
                    if mv_n > mv_cur + 1:
                        if S[n_y][n_x] == '.':
                            maze_visited[n_y][n_x] = mv_cur + 1
                            queue.append((n_y, n_x))
    
H, W = list(map(int, input().split()))
C = list(map(int, input().split()))
D = list(map(int, input().split()))
 
S = [list(input()) for i in range(H)]
 
maze_visited = [[math.inf] * W for i in range(H)]
 
explore(C,D)
 
if maze_visited[D[0] - 1][D[1] - 1] == math.inf:
    print('-1')
else:
    print(maze_visited[D[0] - 1][D[1] - 1])

### FIXED CODE ###

from collections import deque
import math
 
def explore(C, D):
    queue = deque([(C[0]-1, C[1]-1)])
    maze_visited[C[0]-1][C[1]-1] = 0
    while queue:
        y, x = queue.popleft()
        mv_cur = maze_visited[y][x]
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            n_x, n_y = x + i, y + j
            if n_x >= 0 and n_y >= 0 and n_x < W and n_y < H:
                mv_n = maze_visited[n_y][n_x]
                if mv_n > mv_cur:
                    if S[n_y][n_x] == '.':
                        maze_visited[n_y][n_x] = mv_cur
                        queue.appendleft((n_y, n_x))
        for i in range(-2, 3):
            for j in range(-2, 3):
                if abs(i) + abs(j) <= 1:
                    continue
                n_x, n_y = x + i, y + j
                if n_x >= 0 and n_y >= 0 and n_x < W and n_y < H:
                    mv_n = maze_visited[n_y][n_x]
                    if mv_n > mv_cur + 1:
                        if S[n_y][n_x] == '.':
                            maze_visited[n_y][n_x] = mv_cur + 1
                            queue.append((n_y, n_x))
    
H, W = list(map(int, input().split()))
C = list(map(int, input().split()))
D = list(map(int, input().split()))
 
S = [list(input()) for i in range(H)]
 
maze_visited = [[math.inf] * W for i in range(H)]
 
explore(C,D)
 
if maze_visited[D[0] - 1][D[1] - 1] == math.inf:
    print('-1')
else:
    print(maze_visited[D[0] - 1][D[1] - 1])
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-

# import numpy as np
# from itertools import *
# from collections import *
from collections import Counter

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

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

number = range(1, N+1)
numhei = [0] * N
for n in range(N):
    numhei[n] = number[n] + A[n]

count = 0
for n in number:
    count += Counter(numhei)[n - A[n-1]]

print(count)


### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-

# import numpy as np
# from itertools import *
# from collections import *
from collections import Counter

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

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

number = range(1, N+1)
numhei = [0] * N
for n in range(N):
    numhei[n] = number[n] + A[n]

c = Counter(numhei)
count = 0
for n in number:
    count += c[n - A[n-1]]

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

N=int(input())
A=[int(input()) for i in range(N)]
amax = max(A)

for i in range(N):
	if amax!=A[i]:
		print(amax)
	else:
		B = A.copy()
		B.pop(i)
		print(max(B))

### FIXED CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
#print(A)
B = A.copy()
#print(B)
B.sort()


for i in range(N):
	k = A[i]
	#print(k)
	if k != B[N-1]:
		print(B[N-1])
	else:
		print(B[N-2])
### BUGGY CODE ###

import numpy as np

N,K = map(int,input().split())
A = np.array(input().split(),dtype=np.int64)

bit_cnt = [((A>>k)&1).sum() for k in range(50)]

def F(K,k = 49):
  # K以下、k-bit目まで見た(inclusive)の和、最大値
  if k == -1:
    return 0
  bit = 1<<k
  # k-bitを使う
  x = 0
  if K >= bit:
    x = ((N-bit_cnt[k])<<k) + F(K-bit,k-1)
  # k-bitを使わない
  y = (bit_cnt[k]<<k) + F(min(K,bit-1),k-1)
  return max(x,y)

answer = F(K)
print(answer)


### FIXED CODE ###

import numpy as np
from functools import lru_cache

N,K = map(int,input().split())
A = np.array(input().split(),dtype=np.int64)

bit_cnt = [((A>>k)&1).sum() for k in range(50)]

@lru_cache(maxsize = None)
def F(K,k = 49):
  # K以下、k-bit目まで見た(inclusive)の和、最大値
  if k == -1:
    return 0
  bit = 1<<k
  # k-bitを使う
  x = 0
  if K >= bit:
    x = ((N-bit_cnt[k])<<k) + F(K-bit,k-1)
  # k-bitを使わない
  y = (bit_cnt[k]<<k) + F(min(K,bit-1),k-1)
  return max(x,y)

answer = F(K)
print(answer)
### BUGGY CODE ###

s = input()
K = int(input())
N = len(s)

slist = []
for i in range(N):
    for j in range(i + 1, N + 1):
        slist.append(s[i:j])

slist = sorted(slist)

if K == 1:
    print(slist[0])
else:
    c = 1
    ss = slist[0]
    for i in range(1, N ** 2):
        if ss != slist[i]:
            c += 1

        if K == c:
            print(slist[i])
            break

        ss = slist[i]

### FIXED CODE ###

s = input()
N = len(s)
K = int(input())
L = []
for i in range(N):
	for j in range(5):
		if i + j < N:
			L.append(s[i:i + j + 1])

L = sorted(L)

sub = ""
x = 0
for i in L:
	if sub != i:
		sub = i
		x += 1
	
	if x == K:
		print(sub)
		break
### BUGGY CODE ###

mod=10**9+7
n=int(input())
A=map(int,input().split())

cnt=[0]*60
for a in A:
    for j in range(60):
        cnt[j]+=a&1
        a>>=1

ans=0
b=1
for c in cnt:
    ans+=b*c*(n-c)
    ans%=mod
    b=b*2%mod

print(ans)

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    md = 10 ** 9 + 7
    n = int(input())
    aa = LI()
    cnt = [[0] * 2 for _ in range(61)]
    for a in aa:
        for i in range(61):
            cnt[i][a & 1] += 1
            a >>= 1
    #print(cnt)
    base = 1
    ans = 0
    for c0, c1 in cnt:
        ans += base * c0 * c1
        ans %= md
        base = base * 2 % md
    print(ans)

main()
### BUGGY CODE ###

N, M = map(int,input().split())
H = list(map(int, input().split()))
arr = [list(map(int, input().split())) for i in range(M)]
tenbo = [True for i in range(N)]

for i in range(N):
    if tenbo[i]:
        for a, b in arr:
            if a == i+1:
                if H[b-1]>=H[i]:
                   tenbo[i] = False
                else:
                   tenbo[b-1] = False
            elif b == i+1:
                if H[a-1]>=H[i]:
                    tenbo[i] = False
                else:
                    tenbo[a-1] = False

ans = 0
for t in tenbo:
  if t:
    ans+=1
print(ans)

### FIXED CODE ###

N, M = map(int,input().split())
H = list(map(int, input().split()))
arr = [list(map(int, input().split())) for i in range(M)]
highest_tenbo = [0 for i in range(N)]

for a, b in arr:
    highest_tenbo[a-1] = max(highest_tenbo[a-1], H[b-1])
    highest_tenbo[b-1] = max(highest_tenbo[b-1], H[a-1])

ans = 0
for i, t in enumerate(highest_tenbo):
  if t < H[i]:
    ans+=1
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
a_list = list(map(int, input().split()))
dp = [False]*(k+1)

for i in range(1,k+1):
  for j in range(n):
    if i-a_list[j] >= 0:
      dp[i] |= not(dp[i-a_list[j]])


if dp[k]:
  print('First')
else:
  print('Second')

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
  n, k = map(int, input().split())
  a_list = list(map(int, input().split()))
  dp = [False]*(k+1)

  for i in range(1,k+1):
    for j in range(n):
      if i-a_list[j] >= 0:
        dp[i] |= not(dp[i-a_list[j]])


  if dp[k]:
    print('First')
  else:
    print('Second')
main()
### BUGGY CODE ###

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

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

mn = 0
Amax = max(An)
Amin = min(An)
for i in range(len(An)):
    cal = 0
    A = An[i:]  + An[:i]
    for i in range(len(A)-1):
        if A[i] == Amax and A[i+1] == Amin:
            cal += A[i+1] + k - A[i]
        elif A[i] == Amin and A[i+1] == Amax:
            cal += A[i] + k - A[i+1]
        elif A[i+1] >= A[i]:
            cal += A[i+1] - A[i]
        else:
            cal += A[i] - A[i+1]
        
        if mn > 0 and cal > mn:
            break
    
    if mn ==0 or mn > cal:
        mn = cal
        
rAn = An[:]
rAn.reverse()
for i in range(len(rAn)):
    cal = 0
    A = rAn[i:]  + rAn[:i]
    for i in range(len(A)-1):
        if A[i] == Amax and A[i+1] == Amin:
            cal += A[i+1] + k - A[i]
        elif A[i] == Amin and A[i+1] == Amax:
            cal += A[i] + k - A[i+1]
        elif A[i+1] >= A[i]:
            cal += A[i+1] - A[i]
        else:
            cal += A[i] - A[i+1]
            
        if mn > 0 and cal > mn:
            break

    if mn ==0 or mn > cal:
        mn = cal
print(mn)

### FIXED CODE ###

k, n = map(int, input().split())
 
An = list(map(int, input().split()))
 
node = [An[i+1] - An[i]  for i in range(len(An) - 1)]
 
node = node[:] + [k - An[n-1] + An[0]]
 
print(k - max(node))
### BUGGY CODE ###

from collections import Counter
N = int(input())
S = input()

c = N
for a in range(0, N):
	left = Counter(S[0:a])
	right = Counter(S[(a+1):N])
	c = min(c, left['W'] + right['E'])
print(c)

### FIXED CODE ###

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

nE = 0
n = 0
minn = 0
for a in range(1, N):
	wE = (1 if S[a] == 'E' else 0)
	n = n + (1 if S[a-1] == 'W' else 0) - wE
	minn = min(minn, n)
	nE = nE + wE
print(minn + nE)
### BUGGY CODE ###

N=int(input())

clear_flag=0
tmp=0
tmp_x=0
tmp_y=0
for i in range(N):
  txy=list(map(int,input().split()))
  x=0
  y=0
  next_flag=0
  for x_plus in range(txy[0]-tmp+1):
    if next_flag==1:
      break
    for x_minus in range(txy[0]-tmp+1-x_plus):
      if next_flag==1:
        break
      for y_plus in range(txy[0]-tmp+1-x_plus-x_minus):
        y_minus=txy[0]-tmp-x_plus-x_minus-y_plus
        x=x_plus-x_minus+tmp_x
        y=y_plus-y_minus+tmp_y
        if x==txy[1] and y==txy[2]:
          next_flag=1
          clear_flag+=1
          tmp=txy[0]
          tmp_x=txy[1]
          tmp_y=txy[2]
          break
            
if clear_flag==N:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N=int(input())

clear_flag=0
for i in range(N):
  txy=list(map(int,input().split()))
  if txy[0]>=(txy[1]+txy[2]) and (txy[0]+txy[1]+txy[2])%2==0:
    clear_flag+=1
  else:
    break
    
if clear_flag==N:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

import math
from functools import reduce
ans = 0
k = int(input())

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

for i in range(1,k+1):
    for j in range(1,k+1):
        for m in range(1,k+1):
            ans += gcd(i,j,m)

print(ans)
            

### FIXED CODE ###

import math
from functools import reduce
ans = 0
k = int(input())

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

for i in range(1,k+1):
    for j in range(1,k+1):
        for m in range(1,k+1):
            ans += gcd(i,j,m)

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

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

X = list()
for i in range(N):
    x_i = A[i]
    keisu = -1
    for j in range(1, N):
        x_i += keisu * A[(i + j) % N]
        keisu = keisu * -1
    X.append(str(x_i))
print(' '.join(X))

### FIXED CODE ###

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

# x1さえ求めてしまえば連立方程式の解は連鎖的にO(N)で求まる
X = list()
x_1 = sum(A)
for i in range(N):
    if i % 2 != 0:
        x_1 -= 2 * A[i]
X.append(x_1)

for i in range(1, N):
    x_i = 2 * A[i - 1] - X[i - 1]
    X.append(x_i)
print(' '.join([str(x) for x in X]))
### BUGGY CODE ###

from collections import defaultdict

n=int(input())
a_=list(map(int,input().split()))
#n=4
#a_=[1,3,4,2]
a=[]
for i,ai in enumerate(a_):
      a.append([1+i,ai])
a.sort(key=lambda x:x[1],reverse=True)
dp=defaultdict(lambda:0)
dp[(0,1)]=max(a[0][1]*(n-a[0][0]),0)
dp[(1,0)]=max(a[0][1]*(a[0][0]-1),0)
for i in range(2,n+1):#i人目の幼児。a[i-1]
      for x in range(i+1):
            y=i-x
            if x==0:
                  dp[(x,y)]=dp[(x,y-1)]+a[i-1][1]*(n-a[i-1][0]-(y-1))
            elif y==0:
                  dp[(x,y)]=dp[(x-1,y)]+a[i-1][1]*(a[i-1][0]-1-(x-1))
            else:
                  dp[(x,y)]=max(dp[(x-1,y)]+a[i-1][1]*(a[i-1][0]-1-(x-1)),dp[(x,y-1)]+a[i-1][1]*(n-a[i-1][0]-(y-1)))
ans=0
for i in range(n+1):
      ans=max(ans,dp[(i,n-i)])
print(ans)


### FIXED CODE ###

from collections import defaultdict
n=int(input())
a_=list(map(int,input().split()))
a=[]
for i,ai in enumerate(a_):
      a.append([1+i,ai])
a.sort(key=lambda x:x[1],reverse=True)
dp=defaultdict(lambda:0)
dp[(0,1)]=max(a[0][1]*(n-a[0][0]),0)
dp[(1,0)]=max(a[0][1]*(a[0][0]-1),0)
for i in range(2,n+1):#i人目の幼児。a[i-1]
      for x in range(i+1):
            y=i-x
            if x==0:
                  dp[(x,y)]=dp[(x,y-1)]+a[i-1][1]*(n-a[i-1][0]-(y-1))
            elif y==0:
                  dp[(x,y)]=dp[(x-1,y)]+a[i-1][1]*(a[i-1][0]-1-(x-1))
            else:
                  dp[(x,y)]=max(dp[(x-1,y)]+a[i-1][1]*(a[i-1][0]-1-(x-1)),dp[(x,y-1)]+a[i-1][1]*(n-a[i-1][0]-(y-1)))
ans=0
for i in range(n+1):
      ans=max(ans,dp[(i,n-i)])
print(ans)
### BUGGY CODE ###

K, S = map(int, input().split())
count = 0
for x in range(0, K + 1):
	if (x > S):
		break
	for y in range(0, K + 1):
		if (x + y > S):
			break
		for z in range(0, K + 1):
			if (x + y + z == S):
				count = count + 1
			elif (x + y + z > S):
				break
print(count)


### FIXED CODE ###

K, S = map(int, input().split())
count = 0
for x in range(0, K+1):
	if (x > S):
		break
	for y in range(0, min(S-x+1, K+1)):
		if (S-x-y >= 0 and S-x-y <= K):
			count = count + 1

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

from networkx import*
def main():
    g=Graph()
    for a in[*open(x:=0)][1:]:
        a,b=map(int,a.split())
        g.add_edge(a,7**6+b)
    for c in connected_components(g):
        a,b=map(len,algorithms.bipartite.sets(s:=g.subgraph(c)))
        x+=a*b-s.size()
    print(x)
main()

### FIXED CODE ###

class UnionFind():
    def __init__(self,size):
        self.table=[-1]*size
    def root(self,x):
        while self.table[x]>=0:
            x=self.table[x]
        return x
    def unite(self,x,y):
        s1=self.root(x)
        s2=self.root(y)
        if s1!=s2:
            if self.table[s1]>self.table[s2]:
                s1,s2=s2,s1
            self.table[s1]+=self.table[s2]
            self.table[s2]=s1
        return
    def same(self,x,y):
        return self.root(x)==self.root(y)
    def size(self,x):
        return -self.table[self.root(x)]
n,*z=map(int,open(0).read().split())
u=UnionFind(10**5*2+1)
for x,y in zip(*[iter(z)]*2):
    u.unite(x,10**5+y)
d=[[0,set(),set()]for _ in range(10**5*2+1)]
for x,y in zip(*[iter(z)]*2):
    t=d[u.root(x)]
    t[0]+=1
    t[1].add(x)
    t[2].add(y)
print(sum(len(x)*len(y)-a for a,x,y in d))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N,M = list(map(int,input().split()))
A = sorted(list(map(int,input().split())))
Amin = min(A)
tmp = sorted([list(map(int,input().split())) for i in range(M)],key = lambda x:-x[1])

cnt = 0
t = []
for a,b in tmp:
    t=t+[b]*a
    cnt+= a
    if cnt >=N:
        break
    if cnt<N and b <= A[cnt-1]:
        break
for i in range(min(N,len(t))):
    if A[i] < t[i]:
        A[i] = t[i]
print(sum(A))



### FIXED CODE ###

import sys
input = sys.stdin.readline

def sol():
    N,M = list(map(int,input().split()))
    A = list(map(int,input().split()))
    tmp = sorted([list(map(int,input().split())) for _ in range(M)],key = lambda x:-x[1])

    t = []
    for a,b in tmp:
        t+=[b]*a
        
        if len(t) >=N:
            break

    A += t
    A.sort(reverse = 1)
    print(sum(A[:N]))

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

from collections import Counter
N=int(input())
X=list(map(int,input().split()))
Y=sorted(X)
a=Y[N//2]
b=Y[N//2-1]
for i in range(N):
    for j in range(N):
        if X[i]==Y[j]:
            if j<N//2:
                print(a)
                break
            else:
                print(b)
                break

### FIXED CODE ###

from collections import Counter
N=int(input())
X=list(map(int,input().split()))
Y=sorted(X)
a=Y[N//2]
b=Y[N//2-1]
for i in X:
    if i<=b:
        print(a)
    else:
        print(b)
### BUGGY CODE ###

import sys

N=int(input())
amat=[[-1]]
for i in range(N):
  alist=list(map(int,input().split()))
  amat.append(list(reversed(alist)))
  
#print(amat)
answer=0
matched_flag=[False]*(N+1)
for answer in range(1,N**3):
  if N>900 and answer>5000:
    print(N*(N-1)//2)
    sys.exit()
  
  matched_flag=[False]*(N+1)
  unchanged=True
  
  for i in range(1,N+1):
    if matched_flag[i] or len(amat[i]) == 0:
      continue
      
    ai_next = amat[i][-1]
    if amat[ai_next][-1]==i and not matched_flag[ai_next]:
      #print(i,ai_next,answer)
      matched_flag[amat[i].pop()]=True
      matched_flag[amat[ai_next].pop()]=True
      unchanged=False
  
  if unchanged:
    print(-1)
    sys.exit()
  else:
    for i in range(1,N+1):
      if len(amat[i])>0:
        break
    else:
      print(answer)
      sys.exit()


### FIXED CODE ###

import sys

N=int(input())
amat=[[-1]]
for i in range(N):
  alist=list(map(int,input().split()))
  amat.append(list(reversed(alist)))
  
#print(amat)
answer=0
matched_flag=[False]*(N+1)
for answer in range(1,N**3):
  if N>900 and answer>3000:
    print(N*(N-1)//2)
    sys.exit()
  
  matched_flag=[False]*(N+1)
  unchanged=True
  
  for i in range(1,N+1):
    if matched_flag[i] or len(amat[i]) == 0:
      continue
      
    ai_next = amat[i][-1]
    if amat[ai_next][-1]==i and not matched_flag[ai_next]:
      #print(i,ai_next,answer)
      matched_flag[amat[i].pop()]=True
      matched_flag[amat[ai_next].pop()]=True
      unchanged=False
  
  if unchanged:
    print(-1)
    sys.exit()
  else:
    for i in range(1,N+1):
      if len(amat[i])>0:
        break
    else:
      print(answer)
      sys.exit()
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
s = {}
for i in range(1,n+1):
    s[i] = a.count(i)
for i in range(1,n+1):
    if s[i] == 0:
        s.pop(i)
    else:
        continue
cnt = 0
t = sorted(s.items(), key=lambda x:x[1])

if len(s) > k:
    y = len(s) - k
    for j in range(y):
        cnt = cnt + t[j][1]
    print(cnt)
else:
    print(cnt)

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
b = [0]*n
for i in range(n):
    b[a[i]-1] += 1
c = [i for i in b if i != 0]
c.sort()
if len(c) - k > 0:
    print(sum((c[0:len(c)-k])))
else:
    print(0)
### BUGGY CODE ###

n,c=map(int,input().split())
D=[]
for i in range(c):
    D.append(list(map(int,input().split())))
C=[]
for i in range(n):
    C.append(list(map(int,input().split())))

#print(D)

C1=[]
C2=[]
C3=[]
for i in range(n):
    for j in range(n):
        f=(i+j)%3
        if f==0:
            C1.append(C[i][j])
        if f==1:
            C2.append(C[i][j])
        if f==2:
            C3.append(C[i][j])
        

miniwa=1000*500*500

#print(C3)

for c1 in range(0,c):
    iwa1=sum(D[i-1][c1] for i in C1)
    for c2 in range(0,c):
        iwa2=sum(D[j-1][c2] for j in C2)
        for c3 in range(0,c):
            if c1!=c2 and c2!=c3 and c3!=c1 :
                iwa3=sum(D[k-1][c3] for k in C3)
                iwa=iwa1+iwa2+iwa3
                miniwa=min(miniwa,iwa)

print(miniwa)


### FIXED CODE ###

n,c=map(int,input().split())
D=[]
for i in range(c):
    D.append(list(map(int,input().split())))
C=[]
for i in range(n):
    C.append(list(map(int,input().split())))

#print(D)

C1=[]
C2=[]
C3=[]
for i in range(n):
    for j in range(n):
        f=(i+j)%3
        if f==0:
            C1.append(C[i][j])
        if f==1:
            C2.append(C[i][j])
        if f==2:
            C3.append(C[i][j])
        

miniwa=1000*500*500

#print(C3)
iwa1=[]
iwa2=[]
iwa3=[]

for cc in range(0,c):
    iwa1.append(sum(D[i-1][cc] for i in C1))
    iwa2.append(sum(D[i-1][cc] for i in C2))
    iwa3.append(sum(D[i-1][cc] for i in C3))

for c1 in range(0,c):
    for c2 in range(0,c):
        for c3 in range(0,c):
            if c1!=c2 and c2!=c3 and c3!=c1 :
                iwa=iwa1[c1]+iwa2[c2]+iwa3[c3]
                miniwa=min(miniwa,iwa)

print(miniwa)
### BUGGY CODE ###

def main():
  s=input()
  q=int(input())
  turn = 2

  for _ in [0]*q:
      query = input()
      try:
          t = int(query)
          turn = 3 - turn
      except ValueError:
          t,f,c = map(str,query.split())
          if (int(f) + turn)% 2  == 0:
              s = s + c
          else:
              s = c + s
  if turn == 2:
      print(s)
  else:
      print(s[::-1])
main()

### FIXED CODE ###

def main():
  from collections import deque
  s=input()
  q=int(input())
  turn = 2
  d=deque(s)

  for _ in [0]*q:
      query = input()
      if query[0] == "1":
          t = int(query)
          turn = 3 - turn
      else:
          t,f,c = map(str,query.split())
          if (int(f) + turn)% 2  == 0:
              d.append(c)
          else:
              d.appendleft(c)
  if turn == 2:
      print("".join(d))
  else:
      print("".join(list(d)[::-1]))
main()