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

def resolve():
    n = int(input())
    am = []

    from collections import deque

    for i in range(n):
        am.append(deque(list(map(lambda x: int(x) - 1, input().split()))))

    cnt = n * (n - 1) // 2

    day = 0
    while cnt > 0:
        day += 1
        match = 0
        done = {}
        for i in range(n):
            if i in done:
                continue
            if len(am[i]) == 0:
                continue
            j = am[i][0]
            if j < i:
                continue
            if j not in done and am[j][0] == i:
                am[i].popleft()
                am[j].popleft()
                done[i] = 1
                done[j] = 1
                match += 1

        if match == 0:
            print(-1)
            return
        else:
            cnt -= match

    print(day)
    
resolve()

### FIXED CODE ###

def resolve():
    n = int(input())
    a = []

    for i in range(n):
        row = list(map(lambda x: int(x) - 1, input().split()))
        row.reverse()
        a.append(row)

    q = set()

    def check(i):
        if len(a[i]) == 0:
            return
        j = a[i][-1]
        if i == a[j][-1]:
            p = (i, j) if i < j else (j, i)
            q.add(p)

    for i in range(n):
        check(i)

    day = 0
    while len(q) > 0:
        day += 1
        prev_q, q = q, set()

        for p in prev_q:
            (i, j) = p
            a[i].pop()
            a[j].pop()

        for p in prev_q:
            (i, j) = p
            check(i)
            check(j)

    for i in range(n):
        if len(a[i]) != 0:
            print(-1)
            return
    print(day)
    
resolve()
### BUGGY CODE ###

import bisect

n, m = map(int, input().split())
a_array = sorted([int(x) for x in input().split()])
bc_array = sorted([[int(x) for x in input().split()] for x in range(m)], key=lambda x: x[1], reverse=True)

candidate_replace_cnt = n
replace_array = []
replace_cnt = 0
for b, c in bc_array:
    if a_array[0] > c:
        break
    # 何枚入れられそうか
    num = bisect.bisect_left(a_array, c)
    # 入れ替えられる最大枚数が決まる
    candidate_replace_cnt = min(candidate_replace_cnt, num)
    # 全部入れ替えられる
    if candidate_replace_cnt <= b:
        replace_array += [c for x in range(candidate_replace_cnt)]
        a_array = a_array[candidate_replace_cnt:]
        break
    candidate_replace_cnt -= b
    replace_array += [c for x in range(b)]
    a_array = a_array[b:]
print(sum(replace_array + a_array))


### FIXED CODE ###

import bisect

n, m = map(int, input().split())
a_array = sorted([int(x) for x in input().split()])
bc_array = sorted([[int(x) for x in input().split()] for x in range(m)], key=lambda x: x[1], reverse=True)

# 何枚入れ替えられるか
candidate_replace_cnt = n
for b, c in bc_array:
    if a_array[0] >= c or candidate_replace_cnt < 0:
        break
    for i in range(b):
        a_array.append(c)
    candidate_replace_cnt -= b
a_array.sort(reverse=True)
print(sum(a_array[:n]))
### BUGGY CODE ###

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

numset = set([0,1,2,3,4,5,6,7,8,9])
resset = set()

for i in range(N):
    for j in range(i+1,N):
        useset = set(S[j+1:N])
        for k in useset:
            L = [S[i],S[j],k]
            temp = ''.join(L)
            resset.add(temp)

print(len(resset))


### FIXED CODE ###

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

res = 0

for i in range(10):
    p1 = S.find(str(i))
    if p1 == -1:
        continue
    elif p1 > N-3:
        continue
    for j in range(10):
        p2 = S[p1+1:N].find(str(j))
        if p2 == -1:
            continue
        elif p2 > N-p1-3:
            continue
        for k in range(10):
            p3 = S[p1+p2+2:N].find(str(k))
            if p3 == -1:
                continue
            res += 1


print(res)
### BUGGY CODE ###

n = int(input())

d0={}
d1={}

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

for i in range(n//2):
    v_even = v[2*i]
    v_odd  = v[2*i+1]
    if v_even in d0.keys():
        d0[v_even]+=1
    else:
        d0[v_even]=1

    if v_odd in d1.keys():
        d1[v_odd]+=1
    else:
        d1[v_odd]=1

v11,v12,v21,v22 = [0]*4
k1,k2 = [0]*2

for k in d0.keys():
    v = d0[k]
    if v11<v:
        v11=v
        k1=k
for k in d1.keys():
    v = d1[k]
    if v12<v and k!=k1:
        v12=v
    if v22<v:
        v22=v
        k2=k

for k in d0.keys():
    v = d0[k]
    if v21<v and k!=k2:
        v21=v

print(min(n-v11-v12,n-v21-v22))



### FIXED CODE ###

from collections import Counter

n = int(input())
v = list(map(int,input().split()))
v_even,v_odd =[[],[]]

for i in range(n//2):
    v_even.append(v[2*i])
    v_odd.append(v[2*i+1])

mc1 = Counter(v_even).most_common()
mc2 = Counter(v_odd).most_common()

k1,v1 = mc1[0]
k2,v2 = mc2[0]

if k1!=k2:
    print(n-v1-v2)
else:
    w1=0
    if len(mc1)>1:
        w1=mc1[1][1]
    w2=0
    if len(mc2)>1:
        w2=mc2[1][1]
    print(n-max(v1+w2,v2+w1))
### BUGGY CODE ###

n,k,q=map(int,input().split())
a=[(input()) for l in range(q)]
if q-k<0:
    for i in range(n):
        print('Yes')
else:
    import collections
    c = collections.Counter(a)
    l=([int(i[0]) for i in c.items() if i[1] > q-k])
    #print(l)
    for i in range(n):
        if l.count(i+1)>0:
            print('Yes')
        else:
            print('No')

### FIXED CODE ###

n,k,q=map(int,input().split())
a=[(input()) for l in range(q)]
#if q-k<0:
 #   for i in range(n):
  #      print('Yes')
#else:
import collections
c = collections.Counter(a)
for i in range(n):
    #print(k-c[str(i+1)])
    if q-c[str(i+1)]<k:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

H,W = map(int, input().split())
A = []
for _ in range(H):
    A += [ [ x == "#" for x in input()] ]

import numpy as np
from scipy import ndimage
A = np.array(A, dtype= np.bool)
B = np.zeros(A.shape, dtype=np.bool)
i = 0
S = H * W
struct = ndimage.generate_binary_structure(2, 1)
while True:
    if np.alltrue(A):
        break
    ndimage.binary_dilation(A, structure=struct, output=B)
    A, B = B, A

    i += 1

print(i)

### FIXED CODE ###

from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = [None] * (H*W)
matS = matE = 0
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "#":
            mat[matE] = (h, w, 0)
            matE+=1
    dp[h] = s

def search(dp, mat, nH, nW, cnt):
    global matE
    if dp[nH][nW] == ".":
        mat[matE] = (nH, nW, cnt+1)
        matE+=1
        dp[nH][nW] = "#"

while matS < matE:
    h, w, cnt = mat[matS]
    matS += 1

    if h > 0:
        search(dp, mat, h - 1, w, cnt)
    if h < H-1:
        search(dp, mat, h + 1, w, cnt)
    if w > 0:
        search(dp, mat, h , w - 1, cnt)
    if w < W-1:
        search(dp, mat, h , w + 1, cnt)

print(cnt)
### BUGGY CODE ###

# N枚の投票用紙
N = int(input())

s = {}
for _ in range(N):
    tmp = input()
    try:
        if s[tmp]:
            s[tmp] +=1
    except:
        s[tmp] = 1
    
#print(s)
max_kv_list = [kv[0] for kv in s.items() if kv[1] == max(s.values())]
#print(max_kv_list)

max_kv_list.sort()
for tmp in max_kv_list:
    print(tmp)

### FIXED CODE ###

import collections
import itertools

# N枚の投票用紙
N = int(input())

s = []
for _ in range(N):
    s.append(input())

counter = collections.Counter(s)

mode_v = counter.most_common()[0][-1]
it = itertools.takewhile(
    lambda kv: kv[-1] == mode_v, counter.most_common()
)

l_it=list(it)
l_it.sort()
for k, v in l_it:
    print(k)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
for i in a:
    ans *= i
if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a = sorted(a, reverse=True)
ans = 1
flag = 0
if a[-1] == 0:
    print(0)
else:
    for i in a:
        ans *= i
        if ans > 10**18:
            flag +=1
            break
    if flag>0:
        print(-1)
    else:
        print(ans)
### BUGGY CODE ###

from collections import defaultdict


N, K = map(int, input().split())
p = list(map(int, input().split()))
pd = defaultdict(int)

kitai = []
for i in p:
    if not pd[i]:
        dice = list(range(1, i+1))
        ex = 0
        p = 1 / len(dice)

        for x in dice:
            px = p*x
            ex += px
        pd[i] = ex
        kitai.append(ex)
    else:
        kitai.append(pd[i])

ans = 0
for i in range(N):
    if i + (K-1) >= N:
        break
    else:
        ans = max(ans, sum(kitai[i:i+K]))

print(ans)

### FIXED CODE ###

from collections import defaultdict


N, K = map(int, input().split())
p = list(map(int, input().split()))
pd = defaultdict(int)

kitai = []
for i in p:
    if not pd[i]:
        ex = (1 + i) / 2
        kitai.append(ex)
    else:
        kitai.append(pd[i])

# 累積和
rui = []
for i, j in enumerate(kitai):
    if i == 0:
        rui.append(j)
    else:
        rui.append(rui[i-1] + j)

ans = 0
for i, j in enumerate(rui):
    if i + (K-1) >= N:
        continue
    else:
        if i == 0:
            ans = rui[i+K-1]
        else:
            ans = max(ans, rui[i+K-1] - rui[i-1])

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

S=input()
Q=int(input())
for i in range(Q):
	K=input().split()
	if K[0]=="1":
		S=S[::-1]
	if K[0]=="2":
		if K[1]=="1":
			S=K[2]+S
		elif K[1]=="2":
			S=S+K[2]
print(S)

### FIXED CODE ###

from collections import deque
D=deque(input().rstrip())
Q=int(input())
count=0
for _ in range(Q):
	Y=list(input().split())
	if Y[0]=="1":
		count=(count+1)%2
	else:
		if Y[1]=="1":
			if count==0:
				D.appendleft(Y[2])
			else:
				D.append(Y[2])
		else:
			if count==0:
				D.append(Y[2])
			else:
				D.appendleft(Y[2])
D=list(D)
if count==0:
	print("".join(D))
else:
	D.reverse()
	print("".join(D))
### BUGGY CODE ###

n = int(input())
A = [int(i) for i in input().split()]
b = str(A[0])

for i in range(1, n):
    if i % 2 == n % 2:
        b += " " + str(A[i])
    else:
        b = str(A[i]) + " " + b

print(b)

### FIXED CODE ###

n = int(input())
A = [int(i) for i in input().split()]

if n % 2 != 0:
    r = A[1::2]
    l = A[::2]
else:
    r = A[::2]
    l = A[1::2]
l.reverse()
print(" ".join(map(str, l + r)))
### BUGGY CODE ###

N= int(input())

A = list(map(int, input().split()))
A.reverse()
B = []
    
if N%2==0:
    for i in range(N):
        if i%2==0:
            B.append(A.pop())
        else:
            B.insert(0,A.pop())
else:
    for i in range(N):
        if i%2!=0:
            B.append(A.pop())
        else:
            B.insert(0,A.pop())

[print("{} ".format(b),end="") for b in B ]


### FIXED CODE ###

from collections import deque

N= int(input())

A = list(map(int, input().split()))
A.reverse()
B = deque()
    
if N%2==0:
    for i in range(N):
        if i%2==0:
            B.append(A.pop())
        else:
            B.appendleft(A.pop())
else:
    for i in range(N):
        if i%2!=0:
            B.append(A.pop())
        else:
            B.appendleft(A.pop())

[print("{} ".format(b),end="") for b in B ]
### BUGGY CODE ###

h, w = map(int, input().split())

todo = []
draw = ((1, 0), (-1, 0), (0, 1), (0, -1))
done = [[1] * (w + 2)]
for i in range(h):
    done.append([1] + [0 for _ in range(w)] + [1])
done.append([1] * (w + 2))

grid = [list("#" * (w + 2))]
for i in range(h):
    s = input()
    for j, k in enumerate(s):
        if k == "#":
            todo.append((i + 1, j + 1))
            done[i + 1][j + 1] = 1
    grid.append(list("#" + s + "#"))
grid.append(list("#" * (w + 2)))

cnt = 0
while todo:
    tmp = []
    while todo:
        n, m = todo.pop(0)
        for dn, dm in draw:
            if done[n + dn][m + dm] != 0:
                pass
            elif grid[n + dn][m + dm] == "#":
                pass
            elif grid[n + dn][m + dm] == ".":
                tmp.append((n + dn, m + dm))
                done[n + dn][m + dm] = 1
                grid[n + dn][m + dm] = "#"
    todo = tmp
    cnt += 1

print(cnt - 1)


### FIXED CODE ###

import numpy as np

h, w = map(int, input().split())
grid = (np.array([list(input())
                  for _ in range(h)]) == "#")
cost = np.full((h, w), 10 ** 9, dtype=np.int64)
cost[grid[:, :]] = 0

for i in range(1, h):
    cost[i] = np.minimum(cost[i], cost[i - 1] + 1)

for i in range(h - 1)[::-1]:
    cost[i] = np.minimum(cost[i], cost[i + 1] + 1)

for i in range(1, w):
    cost[:, i] = np.minimum(cost[:, i], cost[:, i - 1] + 1)

for i in range(w - 1)[::-1]:
    cost[:, i] = np.minimum(cost[:, i], cost[:, i + 1] + 1)

print(np.max(cost))
### BUGGY CODE ###

from collections import deque
n = int(input())
Ps = list(map(int, input().split()))
Ps = [p-1 for p in Ps]
fs = [0] * (n**2)

## フロアフィールドを作る
for i in range(n):
    x = min(i,n-1-i)
    for j in range(n):
        y = min(j,n-1-j)
        fs[i*n+j] = min(x,y)

ans = 0
mvs = [1, -1, n, -n]
occupied = [1] * (n**2)
for p in Ps:
    ans += fs[p]
    occupied[p] = 0
    q = deque([])
    q.append(p)
    while len(q) > 0: #pを起点にBFS
        p_ = q.popleft()
        dist = fs[p_]
        for mv in mvs:
            if 0 <= p_+mv < n**2:
                p_next = p_ + mv
                # ある位置h,wが
                # occupiedなら、隣接マス+1で到達
                # vacantなら、隣接マス+0で到達
                if dist+occupied[p_] < fs[p_next]:
                    q.append(p_next)
                    fs[p_next] = dist + occupied[p_]

print(ans)
    
    

### FIXED CODE ###

from collections import deque
n = int(input())
Ps = list(map(int, input().split()))
Ps = [p-1 for p in Ps]
fs = [0] * (n**2)

## フロアフィールドを作る
for x in range(n**2):
    i,j = divmod(x,n)
    x = min(i,n-1-i)
    y = min(j,n-1-j)
    fs[i*n+j] = min(x,y)

ans = 0
mvs = [1, -1, n, -n]
occupied = [1] * (n**2)
for p in Ps:
    ans += fs[p]
    occupied[p] = 0
    q = deque([])
    q.append(p)
    while len(q) > 0: #pを起点にBFS
        p_ = q.popleft()
        dist = fs[p_]
        for mv in mvs:
            if 0 <= p_+mv < n**2:
                p_next = p_ + mv
                # ある位置h,wが
                # occupiedなら、隣接マス+1で到達
                # vacantなら、隣接マス+0で到達
                if dist+occupied[p_] < fs[p_next]:
                    q.append(p_next)
                    fs[p_next] = dist + occupied[p_]

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

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

moji = ''

while len(moji) < N:
    for i in range(A):
        moji += 'b'
    for j in range(B):
        moji += 'r'

moji = moji[:N]

print(moji.count('b'))

### FIXED CODE ###

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

nn = N // (A+B)

amari = N % (A+B)

if amari < A:
    print(A*nn + amari)
else:
    print(A*nn + A)
### BUGGY CODE ###

import sys
import copy

h, w = map(int, input().split())
S = [input() for _ in range(h)]


def get_shortest_steps(S, visited, i, j, l, m, steps):
    if i == l and j == m:
        return steps
    if i == -1 or i == h or j == -1 or j == w:
        return sys.maxsize
    if visited[i * 20 + j]:
        return sys.maxsize
    if S[i][j] == "#":
        return sys.maxsize
    visited[i * 20 + j] = True
    returned_steps1 = get_shortest_steps(S, copy.copy(visited), i + 1, j, l, m, steps + 1)
    returned_steps2 = get_shortest_steps(S, copy.copy(visited), i, j + 1, l, m, steps + 1)
    returned_steps3 = get_shortest_steps(S, copy.copy(visited), i - 1, j, l, m, steps + 1)
    returned_steps4 = get_shortest_steps(S, copy.copy(visited), i, j - 1, l, m, steps + 1)
    # print(returned_steps1, returned_steps2, returned_steps3, returned_steps4)
    return min(returned_steps1, returned_steps2, returned_steps3, returned_steps4)


result = -1
for i in range(h):
    for j in range(w):
        for l in range(h):
            for m in range(w):
                visited = [False] * (h * 20 + w + 1)
                shortest_steps = get_shortest_steps(S, visited, i, j, l, m, 0)
                if shortest_steps == sys.maxsize:
                    continue
                if shortest_steps > result:
                    result = shortest_steps
print(result)


### FIXED CODE ###

import sys
import numpy as np
from collections import deque

h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]

max_step = 0
for i in range(h):
    for j in range(w):
        largest_step = 0
#        print("start: ", i, j)
        if maze[i][j] == "#":
            continue
        visited = [[False] * w for _ in range(h)]
        distance = [[-1] * w for _ in range(h)]
        plan = deque()
        step = 0
        plan.appendleft((i, j, step))
        distance[i][j] = step
        visited[i][j] = True
        while plan:
            y, x, step = plan.pop()
#            print(" ", x, y, step)
            # if step > largest_step:
            #     largest_step = step
            for next_direction in direction:
                next_y = y + next_direction[0]
                next_x = x + next_direction[1]
                if -1 == next_x or next_x == w or -1 == next_y or next_y == h or maze[next_y][next_x] == "#" or visited[next_y][next_x]:
                    continue
                distance[next_y][next_x] = distance[y][x] + 1
                visited[next_y][next_x] = True
                plan.appendleft((next_y, next_x, step + 1))
#        print(largest_step)
        # if largest_step > max_step:
        #     max_step = largest_step
        max_step = max(max_step, np.max(np.array(distance)))

print(max_step)
### BUGGY CODE ###

N = int(input())
n = N
m = N ** 0.5
L = []
i = 3

print(str(N) + ': ', end = '')

while n%2 == 0:
    n = n/2
    L.append(2)

while i <= N:
    while n%i == 0:
        n = n/i
        L.append(i)
    i += 2
    
#if len(L) == 0:
#    L.append(N)

print(' '.join(map(str, L)))



### FIXED CODE ###

N = int(input())
n = N
m = N ** 0.5
L = []
i = 3

print(str(N) + ': ', end = '')

while n%2 == 0:
    n = n/2
    L.append(2)

while i <= m:
    while n%i == 0:
        n = n/i
        L.append(i)
    i += 2

if n not in L:
    L.append(int(n))  

if 1 in L:
    L.remove(1)

if len(L) == 0:
    L.append(N)

print(' '.join(map(str, L)))
### BUGGY CODE ###

n = int(input())
s = input()

R_inds = [0] * n
G_inds = [0] * n
B_inds = [0] * n

for i in range(n):
    if s[i] == 'R':
        R_inds[i] = i
    elif s[i] == 'G':
        G_inds[i] = i
    else:
        B_inds[i] = i
R_inds = list(set(R_inds))
G_inds = list(set(G_inds))
B_inds = list(set(B_inds))

if s[0] == 'R':
    G_inds.remove(0)
    B_inds.remove(0)
elif s[0] == 'G':
    R_inds.remove(0)
    B_inds.remove(0)
else:
    R_inds.remove(0)
    G_inds.remove(0)
    
ans = 0
for r in R_inds:
    for g in G_inds:
        big = max(r,g)
        small = min(r,g)
        bigger = big + (big - small)
        smaller = small - (big - small)
        if (big - small) % 2 == 0:
            middle = (big + small) // 2
        else:
            middle = -1
        
        subans = 0
        subans += len(B_inds)
        if smaller in B_inds:
            subans -= 1
        if bigger in B_inds:
            subans -= 1
        if middle in B_inds:
            subans -= 1
        if subans > 0:
            ans += subans

print(ans)

### FIXED CODE ###

n = int(input())
s = input()
R_ls = [0] * n
G_ls = [0] * n
B_ls = [0] * n
R_csum = [0] * n
G_csum = [0] * n
B_csum = [0] * n
for i in range(n):
    if s[i] == 'R':
        R_ls[i] = 1
        R_csum[i] = R_csum[i-1] + 1
        G_csum[i] = G_csum[i-1]
        B_csum[i] = B_csum[i-1]
    elif s[i] == 'G':
        G_ls[i] = 1
        G_csum[i] = G_csum[i-1] + 1
        R_csum[i] = R_csum[i-1]
        B_csum[i] = B_csum[i-1]
    else:
        B_ls[i] = 1
        B_csum[i] = B_csum[i-1] + 1
        R_csum[i] = R_csum[i-1]
        G_csum[i] = G_csum[i-1]
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        if (s[i] == 'R' and s[j] == 'G') or (s[i] == 'G' and s[j] == 'R'):
            now = B_csum[-1] - B_csum[j]
            if j + (j-i) < n and s[2*j-i] == 'B':
                now -= 1
        elif (s[i] == 'R' and s[j] == 'B') or (s[i] == 'B' and s[j] == 'R'):
            now = G_csum[-1] - G_csum[j]
            if j + (j-i) < n and s[2*j-i] == 'G':
                now -= 1
        elif (s[i] == 'G' and s[j] == 'B') or (s[i] == 'B' and s[j] == 'G'):
            now = R_csum[-1] - R_csum[j]
            if j + (j-i) < n and s[2*j-i] == 'R':
                now -= 1
        else:
            now = 0
        ans += now
print(ans)
### BUGGY CODE ###

s = list(str(input()))
t = list(str(input()))

t.reverse()

S = set(list(s))
for c in t:
    if c not in S:
        print(-1)
        exit()

cnt = 0
#print(s)
#print(t)
while True:
    for i in range(len(s)):
        if t:
            if s[i] == t[-1]:
                t.pop()
        else:
            break
    else:
        cnt += 1
        continue
    break
print(cnt*len(s)+i)


### FIXED CODE ###

S = list(str(input()))
T = list(str(input()))

S_ = set(list(S))
T_ = set(list(T))
for c in T:
    if c not in S_:
        print(-1)
        exit()

d = [[] for _ in range(26)]
for i, s in enumerate(S):
    d[ord(s)-ord('a')].append(i)
#print(d)

q = 0
pre = -1
import bisect
for t in T:
    j = ord(t)-ord('a')
    idx = bisect.bisect_right(d[j], pre)
    if idx == len(d[j]):
        q += 1
        pre = d[j][0]
    else:
        pre = d[j][idx]
print(q*len(S)+pre+1)
### BUGGY CODE ###

import sys
s = sys.stdin.readline().strip()
Q = int(sys.stdin.readline().strip())
#s = str(input())
#Q = int(input())

for _ in range(Q):
	qu = input()
	if qu == '1':
		s = s[::-1]
	else:
		_, fi, ci = qu.split()
		if fi == '1':
			s = ci + s
		if fi == '2':
			s += ci
print(s)

### FIXED CODE ###

from collections import deque
import sys

def main():
    s = sys.stdin.readline().strip()
    qn = int(sys.stdin.readline().strip())
    qs = [input().split() for _ in range(qn)]

    s = deque(s)
    r = 1
    for q in qs:
        if len(q) == 1:
            r = r * -1

        else:
            if q[1] == '1':
                if r == 1:
                    s.appendleft(q[2])
                else:
                    s.append(q[2])
            else:
                if r == 1:
                    s.append(q[2])
                else:
                    s.appendleft(q[2])

    if r == 1:
        print(''.join(s))
    else:
        s.reverse()
        print(''.join(s))

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

import heapq

N, M = map(int, input().split())
income = [[] for _ in range(M+1)]  # income[i]はi日後に報酬が得られる全ての仕事についての報酬のリスト
for _ in range(N):
    a, b = map(int, input().split())
    if a <= M:
        income[a].append(-b)

# 後ろから考える。残りi日のときに終了までに報酬が得られる仕事のうち報酬最大のものを選ぶ
ans = 0
tmp = []
for rest_days in range(1, M+1):
    tmp += income[rest_days]
    heapq.heapify(tmp)
    if tmp:
        ans += heapq.heappop(tmp)

print(-ans)

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
income = [[] for _ in range(M+1)]  # income[i]はi日後に報酬が得られる全ての仕事についての報酬のリスト
for _ in range(N):
    a, b = map(int, input().split())
    if a <= M:
        income[a].append(-b)

# 後ろから考える。残りi日のときに終了までに報酬が得られる仕事のうち報酬最大のものを選ぶ
ans = 0
tmp = []
heapq.heapify(tmp)

for rest_days in range(1, M+1):
    for x in income[rest_days]:
        heapq.heappush(tmp, x)
    if tmp:
        ans += heapq.heappop(tmp)

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

n, m = map(int, input().split())
a, b = [], []
hp = [[] for _ in range(m+1)]
ignore = [0] * (n+1)
ans = 0
for _ in range(n):
    x, y = map(int, input().split())
    a.append(x)
    b.append(y)
for x in range(1, m+1):
    candidate = []
    for i, e in enumerate(a):
        if e <= x and not ignore[i]: candidate.append(b[i])
    if candidate:
        m = max(candidate)
        ans += m
        ignore[b.index(m)] = 1
print(ans)

### FIXED CODE ###

import heapq
import collections

n, m = map(int, input().split())
work = collections.defaultdict(list)
hp = [[] for _ in range(m+1)]
ignore = []
ans = 0
for _ in range(n):
    x, y = map(int, input().split())
    work[x].append(-y)
candidate = []
for x in range(1, m+1):
    if work[x]:
        for e in work[x]:
            heapq.heappush(candidate, e)
    if candidate:
        ans += heapq.heappop(candidate)
print(abs(ans))