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

import sys

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(inputs):
    [N] = string_to_int(inputs[0])
    M = [x for x in range(1, N)]
    return sum(M)


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    ret = solve(inputs(1))
    print(ret)


### FIXED CODE ###

import sys
import math

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(inputs):
    [N] = string_to_int(inputs[0])
    num = N - 1
    if num == 0:
        return 0
    if num == 1:
        return 1
    if num % 2 == 0:
        # half_l = math.floor(num / 2)
        # half = (half_l + half_l + 1) / 2
        half = num // 2
        append = num // 2
    else:
        half = (num + 1) // 2
        append = 0
        # half = math.floor(num / 2)
    return half * num + append


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    ret = solve(inputs(1))
    print(ret)
### BUGGY CODE ###

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

import bisect
# insert_index = bisect.bisect_left(a,x)

A = sorted(A)
for i in range(M):
    B,C = map(int,input().split())
    
    index = bisect.bisect_right(A,C)
    index = min(index, B)
    A = [C]*index + A[index:]
    A = sorted(A)


print(sum(A))

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    N,M = map(int,input().split())
    A= list(map(int,input().split()))
    A = sorted(A)

    BC=[list(map(int,input().split())) for i in range(M)]
    BC = sorted(BC, key=lambda x: x[1],reverse=True)
    index=0
    max_index=len(A)
    
    for B,C in BC:
        temp = [C]*B
        for t in temp:
            if max_index>index and  t>A[index]:
                A[index] = t
            else:
                return A
            index+=1
    return A
    
if __name__ == '__main__':
    A=main()
    print(sum(A))
### BUGGY CODE ###

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

for i in range(n):
    print(a.count(i+1))


### FIXED CODE ###

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

c = collections.Counter(a)

for i in range(n):
    print(c[i+1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

n=int(input())

edge=[[]for i in range(n+1)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    edge[a].append((b,c))
    edge[b].append((a,c))
q,k=map(int,input().split())

dis=[None]*(n+1)
def set_dist(x,d):
    dis[x]=d
    for y,f in edge[x]:
        if dis[y] is not None:
            continue
        set_dist(y,d+f)
set_dist(k,0)

for i in range(q):
    x,y=map(int,input().split())
    print(dis[x]+dis[y])

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


n=int(input())
graph=[[] for i in range(n+1)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    graph[a].append((b,c))
    graph[b].append((a,c))
    
q,k=map(int,input().split())

dis=[None]*(n+1)

def set_dis(x,d):
    dis[x]=d
    for yy,dd in graph[x] :
        if dis[yy] is not None:
            continue
        set_dis(yy,dd+d)
set_dis(k,0)

for i in range(q):
    x,y=map(int,input().split())
    print(dis[x]+dis[y])
### BUGGY CODE ###

from heapq import heappop,heappush
n = int(input())
a = [-int(input()) for i in range(n)]
x = [a[0]]
for i in range(1,n):
    if max(x)<=a[i]:
        heappush(x,a[i])
    else:
        p = heappop(x)
        y = [p]
        while p<=a[i]:
            p = heappop(x)
            y.append(p)
        heappush(x,a[i])
        for i in range(len(y)-1): heappush(x,y[i])
print(len(x))

### FIXED CODE ###

from bisect import bisect
n = int(input())
a = [-int(input()) for i in range(n)]
x = [a[0]]
for i in range(1,n):
    if x[-1]<=a[i]: x.append(a[i])
    else: x[bisect(x,a[i])] = a[i]
print(len(x))
### BUGGY CODE ###

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

import bisect

n = int(input())

A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort()
B.sort()
C.sort()


Ac, Cc = [0]*n, [0]*n
Ap, Cp = 0, 0

for i in range(n):
    index = bisect.bisect_left(A[Ap:], B[i])
    Ac[i], Ap = index + Ap, index + Ap
    index = bisect.bisect_right(C[Cp:], B[i])
    Cc[i], Cp = n - index - Cp, index + Cp


count = 0
for i in range(n):
    count += Ac[i]*Cc[i]

print(count)


### FIXED CODE ###

# -*- coding: utf-8 -*-
 
import bisect
 
n = int(input())
 
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
 
A.sort()
B.sort()
C.sort()
 
Ac, Cc = [0]*n, [0]*n
# Ap, Cp = 0, 0
 
for i in range(n):
    Ac[i] = bisect.bisect_left(A, B[i])#[Ap:], B[i])
    # Ac[i], Ap = index + Ap, index + Ap
    Cc[i] = n - bisect.bisect_right(C, B[i])#[Cp:], B[i])
    # Cc[i], Cp = n - index - Cp, index + Cp
 
 
count = 0
for i in range(n):
    count += Ac[i]*Cc[i]
 
print(count)
### BUGGY CODE ###

n = int(input())
numlist = list(map(int, input().split(" ")))
ans = []

for i in range(1, n + 1):
    ans.append(numlist.count(i))

sum = 0
for i in ans:
    sum += int(i * (i - 1) / 2)

for i in numlist:
    print(sum - ans[i - 1] + 1)


### FIXED CODE ###

n = int(input())
numlist = list(map(int, input().split(" ")))

import collections

numcount=collections.Counter(numlist)


sum = 0
for i in numcount.values():
    sum += int(i * (i - 1) / 2)

for i in numlist:
    print(sum - numcount[i] + 1)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
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()))

h, w = LI()
ch, cw = LI()
dh, dw = LI()
s = [list(input()) for _ in range(h)]

dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]
d = [[10**10] * w for _ in range(h)]
d[ch-1][cw-1] = 0
H = []
heappush(H, (0, cw-1, ch-1))
while H:
    D, x, y = heappop(H)
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < w and 0 <= ny < h:
            if s[ny][nx] == '.' and d[ny][nx] > D:
                d[ny][nx] = D
                heappush(H, (D, nx, ny))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nx, ny = x + i, y + j
            if 0 <= nx < w and 0 <= ny < h:
                if s[ny][nx] == '.' and d[ny][nx] > D + 1:
                    d[ny][nx] = D + 1
                    heappush(H, (D + 1, nx, ny))
if d[dh-1][dw-1] == 10**10:
    print(-1)
else:
    print(d[dh-1][dw-1])

### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
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()))

h, w = LI()
ch, cw = LI()
dh, dw = LI()
s = [input() for _ in range(h)]

dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]
que = deque([(cw-1, ch-1)])
d = [[10**10] * w for _ in range(h)]
d[ch-1][cw-1] = 0
while que:
    x, y = que.popleft()
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < w and 0 <= ny < h:
            if s[ny][nx] == '.' and d[ny][nx] > d[y][x]:
                d[ny][nx] = d[y][x]
                que.appendleft((nx, ny))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nx, ny = x + i, y + j
            if 0 <= nx < w and 0 <= ny < h:
                if s[ny][nx] == '.' and d[ny][nx] > d[y][x] + 1:
                    d[ny][nx] = d[y][x] + 1
                    que.append((nx, ny))
if d[dh-1][dw-1] == 10**10:
    print(-1)
else:
    print(d[dh-1][dw-1])
### BUGGY CODE ###

N = int(input())

for n in range(1, N+1):
  cnt = 0
  for x in range(1, 51):
    for y in range(1, 51):
      for z in range(1, 51):
        if (x + y + z) ** 2 - (x * y) - (y * z) - (z * x) == n:
          cnt += 1
  print(cnt)

### FIXED CODE ###

# ans

N = int(input())

ans = [0] * (N + 1)
for x in range(1, 101):
  for y in range(1, 101):
    for z in range(1, 101):
      n = x * x + y * y + z * z + x * y + y * z + z * x
      if n <= N:
        ans[n] += 1

for i in range(1, len(ans)):
  print(ans[i])
### BUGGY CODE ###

n = int(input())
s = []
for i in range(n):
    s.append(input())

from collections import Counter
 
def verify_anagrams(first_word, second_word):
    def get_counter(s):
        return Counter(s.upper().replace(' ', ''))
 
    return get_counter(first_word) == get_counter(second_word)
count = 0
for i in range(n-1):
    for j in range(i+1,n):
        if verify_anagrams(s[i], s[j]) == True:
            count += 1

print(count)


### FIXED CODE ###

n = int(input())
s = []
for i in range(n):
    ss = ''.join(sorted(input()))
    s.append(ss)

from collections import Counter
d = Counter(s)

count = 0
for s in d.values():
    if s > 1:
        count += s/2*(s-1) 


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

from collections import defaultdict
INF = 10000
def lcs(s1, s2):
    c = defaultdict(list)
    for i, s in enumerate(s1):
        c[s].append(i)
    for s in set(s2):
        c[s].append(INF)
    def g(li, a):
        for i in li:
            if i >= a:
                return i
        return -1
    dp = []
    for s2_k in s2:
        bgn_idx = 0
        for i, cur_idx in enumerate(dp):
            chr_idx = g(c[s2_k], bgn_idx)
            if chr_idx == INF:
                continue
            dp[i] = min(cur_idx, chr_idx + 1)
            bgn_idx = cur_idx
        else:
            chr_idx = g(c[s2_k], bgn_idx)
            if chr_idx != INF:
                dp.append(chr_idx + 1)
    return len(dp)
def solve():
    N = int(input())
    for _ in range(N):
        x = input()
        y = input()
        print(lcs(x, y))
solve()



### FIXED CODE ###

for _ in range(int(input())):
    a = input()
    b = input()
    if len(a) < len(b):
        a, b = b, a
    indices = []
    for cb in b:
        bgn_idx = 0
        for i, cur_idx in enumerate(indices):
            chr_idx = a.find(cb, bgn_idx) + 1
            if not chr_idx:
                break
            if chr_idx < cur_idx:
                indices[i] = chr_idx
            bgn_idx = cur_idx
        else:
            chr_idx = a.find(cb, bgn_idx) + 1
            if chr_idx:
                indices.append(chr_idx)
    print(len(indices))
### BUGGY CODE ###

s = input()
l = len(s)
ans = 0
for i in range(0, l-4):
    for j in range(i+3, l):
        num = int(s[i:j+1])
        if num%3 == 0:
            if num%673 == 0:
                ans += 1
print(ans)

### FIXED CODE ###

s = input()
s = s[::-1]
l = len(s)
count = [0] * 2019
res = 0
count[res] = 1
d = 1
for i in s:
    res += int(i) * d
    res %= 2019
    count[res] += 1
    d *= 10
    d %= 2019
print(int(sum([m*(m-1)/2 for m in count])))
### BUGGY CODE ###

import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip()

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

ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

visited = {}

maze = []
for i in range(H):
    a = list(input())
    maze.append(a)

queue = deque([(ch-1, cw-1, 0)])
ans = float("inf")

visited[(ch-1, cw-1)] = 0
while queue:
    y, x, cnt = queue.popleft()

    if y == dh-1 and x == dw-1:
        print(cnt)
        exit()

    for a, b in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        new_y, new_x = y+a, x+b
        if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] != '#':
            if (new_y, new_x) not in visited or visited[(new_y, new_x)] > cnt:
                queue.appendleft((new_y, new_x, cnt))
                visited[(new_y, new_x)] = cnt

    for a in range(-2, 3):
        for b in range(-2, 3):
            new_y, new_x = y + a, x + b
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] != '#':
                if (new_y, new_x) not in visited or visited[(new_y, new_x)] > cnt + 1:
                    queue.append((new_y, new_x, cnt+1))
                    visited[(new_y, new_x)] = cnt+1

print(-1 if ans == float("inf") else ans)

### FIXED CODE ###

import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip()

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

ch, cw = map(int, input().split())
ch -= 1
cw -= 1
dh, dw = map(int, input().split())
dh -= 1
dw -= 1

maze = []
for i in range(H):
    a = list(input())
    maze.append(a)

queue = deque([(ch, cw, 0)])

dist = [[float("inf") for _ in range(W)] for _ in range(H)]
dist[ch][cw] = 0

while queue:
    y, x, cnt= queue.popleft()

    for a, b in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        new_y, new_x = y+a, x+b
        if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] != '#':
            if dist[new_y][new_x] == float("inf") or dist[new_y][new_x] > cnt:
                queue.appendleft((new_y, new_x, cnt))
                dist[new_y][new_x] = cnt

    for a in range(-2, 3):
        for b in range(-2, 3):
            new_y, new_x = y + a, x + b
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] != '#':
                if dist[new_y][new_x] == float("inf") or dist[new_y][new_x] > cnt + 1:
                    queue.append((new_y, new_x, cnt+1))
                    dist[new_y][new_x] = cnt + 1

print(-1 if dist[dh][dw] == float("inf") else dist[dh][dw])
### BUGGY CODE ###

k,s = map(int,input().split())
count = 0
for i in range(k+1):
    for j in range(k+1):
        for l in range(k+1):
            if i + j + l == s:
                count += 1
print(count)


### FIXED CODE ###

k,s = map(int,input().split())
count = 0
for i in range(k+1):
    for j in range(k+1):
        if 0<=s - i - j < k+1:
            count += 1
print(count)
### BUGGY CODE ###

from collections import Counter
import math

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

c2 = math.factorial(2)

for k in range(1, N+1):
    a = A[:k-1] + A[k:]
    count = Counter(a)

    sum = 0
    for k, v in count.items():
        if v < 2:
            continue
        sum += math.factorial(v) // (math.factorial(v - 2) * c2)
    print(sum)

### FIXED CODE ###

from collections import Counter
import math

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

c = Counter(A)

all_ans = 0
for n in c.values():
    if n <= 1:
        continue
    all_ans += math.factorial(n)//(math.factorial(n-2)*math.factorial(2))

for n in A:
    print(all_ans - (c[n]-1))
### BUGGY CODE ###


import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)



def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())


#N=list(map(int,list(input())[::-1]))
N = list(map(int, list(input())))

dp=[[-1,-1] for i in range(len(N)+1)]
dp[0]=[0,1]
b=0
N.insert(0,0)

for i in range(1,len(N)):
    up = 10-N[i]
    dp[i][0]=min(dp[i-1][0]+N[i],dp[i-1][1]+up)
    dp[i][1] = min(dp[i-1][0]+N[i]+1, dp[i-1][1]+up-1)
   

print(dp[-1][0])


### FIXED CODE ###

N = list(map(int, list(input())))

dp=[[-1,-1] for i in range(len(N)+1)]
dp[0]=[0,1]
b=0
N.insert(0,0)

for i in range(1,len(N)):
    up = 10-N[i]
    dp[i][0]=min(dp[i-1][0]+N[i],dp[i-1][1]+up)
    dp[i][1] = min(dp[i-1][0]+N[i]+1, dp[i-1][1]+up-1)
   

print(dp[-1][0])
### BUGGY CODE ###

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

L = []
R = []

for i in range(int((B-A+1) / 2)):
    L.append((A + 2 * i) ^ (A + 2 * i + 1))
if (B - A+1) % 2 == 1:
    L.append(B)

while len(L) != 1 and len(R) != 1:
    if len(L) == 0:
        if len(R) % 2 == 1:
            R.append(0)
        for i in range(int(len(R)/2)):
            L.append(R[2*i] ^ R[2*i+1])
        # if len(R) % 2 == 1:
        #     L.append(R[-1])
        R = []#.clear
    else:
        if len(L) % 2 == 1:
            L.append(0)
        for i in range(int(len(L)/2)):
            R.append(L[2*i] ^ L[2*i+1])
        # if len(L) % 2 == 1:
        #     R.append(L[-1])
        L = []

if len(L) == 0:
    print(R[0])
else:
    print(L[0])

### FIXED CODE ###

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

def f(n):
    if n % 2 == 0:
        if int(n / 2) % 2 == 0:
            return n
        else:
            return 1 ^ n
    else:
        if (int(n + 1) / 2) % 2 == 0:
            return 0
        else:
            return 1

if A > 0:
    print(f(A-1) ^ f(B))
else:
    print(f(B))
### BUGGY CODE ###

from functools import reduce
N, Q = map(int, input().split(" "))
S = input()
bi_gram = [S[k:k+2] for k in range(N - 1)]
qs = [list(map(int, input().split(" "))) for i in range(Q)]

for q in qs:
    print(reduce(lambda x, y: x + (1 if y == "AC" else 0), bi_gram[q[0]-1: q[1]-1], 0))

### FIXED CODE ###

N, Q = map(int, input().split(" "))
S = input()
ac_cnts = [0]
ac_cnt = 0
for i in range(N-1):
    if S[i:i+2] == "AC":
        ac_cnt += 1
    ac_cnts.append(ac_cnt)
for j in range(Q):
    l, r = map(int, input().split(" "))
    print(ac_cnts[r-1] - ac_cnts[l-1])
### BUGGY CODE ###

# reference: https://www.onakasuitacity.com/abc144-f/

import numpy as np

n, m = map(int, input().split())
outgoing = [[] for _ in range(n)]
incoming = [[] for _ in range(n)]
for _ in range(m):
    si, ti = map(int, input().split())
    outgoing[si-1].append(ti-1)
    incoming[ti-1].append(si-1)


ex_dp = np.zeros(n)
for v in reversed(range(n-1)):   # O(m)
    outgoing_degree = len(outgoing[v])
    ex_dp[v] = 1 + sum(ex_dp[post] for post in outgoing[v])/outgoing_degree if outgoing_degree!=0 else np.inf

p_dp = np.ones(n)
for v in range(1,n):      # O(m)
    p_dp[v] = sum(p_dp[prev]/len(outgoing[prev]) for prev in incoming[v])

min_ex = ex_dp[0]
for v, posts in enumerate(outgoing):      # O(m)
    for w in posts:     # cut: edge from v to w
        outgoing_degree = len(outgoing[v])
        if outgoing_degree <= 1:
            continue
        diff_remain_edge_p = 1/(outgoing_degree*(outgoing_degree-1))
        diff_cut_edge_p = 1/outgoing_degree
        diff_v_ex = sum(diff_remain_edge_p * ex_dp[post] for post in outgoing[v] if post!=w) - diff_cut_edge_p * ex_dp[w]
        min_ex = min(ex_dp[0] + p_dp[v] * diff_v_ex, min_ex)

print(min_ex)


### FIXED CODE ###

# reference: https://www.onakasuitacity.com/abc144-f/

import numpy as np

n, m = map(int, input().split())
outgoing = [[] for _ in range(n)]
incoming = [[] for _ in range(n)]
for _ in range(m):
    si, ti = map(int, input().split())
    outgoing[si-1].append(ti-1)
    incoming[ti-1].append(si-1)


ex_dp = np.zeros(n)
for v in reversed(range(n-1)):   # O(m)
    outgoing_degree = len(outgoing[v])
    ex_dp[v] = 1 + sum(ex_dp[post] for post in outgoing[v])/outgoing_degree if outgoing_degree!=0 else np.inf

p_dp = np.ones(n)
for v in range(1,n):      # O(m)
    p_dp[v] = sum(p_dp[prev]/len(outgoing[prev]) for prev in incoming[v])

min_ex = ex_dp[0]
for v, posts in enumerate(outgoing):      # O(m)
    outgoing_degree = len(outgoing[v])
    if outgoing_degree <= 1:
        continue

    max_post = max(posts, key= lambda pos: ex_dp[pos])
    diff_v_ex = 0
    for w in posts:
        if w == max_post:
            diff_v_ex -= 1/outgoing_degree * ex_dp[w]
        else:
            diff_v_ex += 1/(outgoing_degree*(outgoing_degree-1)) * ex_dp[w]
    min_ex = min(ex_dp[0] + p_dp[v] * diff_v_ex, min_ex)

print(min_ex)
### BUGGY CODE ###

def solve(n, h, a):
    size = 1 << ((n + 1) - 1).bit_length()  # 元の配列サイズ以上の最小の二冪 == 最下段
    seg = [0] * (size * 2 - 1)

    def update(k, x):
        k += size - 1
        seg[k] = x  # 値を更新する
        while k > 0:
            k = (k - 1) // 2  # 親のindex
            seg[k] = max(seg[k * 2 + 1], seg[k * 2 + 2])

    def get(a, b, k=0, l=0, r=-1):
        # [a,b)区間の処理結果を返す
        # 注目区間[l,r)
        if r < 0:
            r = size

        if r <= a or b <= l:
            return 0
        # 区間が重ならない

        if a <= l and r <= b:
            return seg[k]
        # 完全被覆

        m = (l + r) // 2
        vl = get(a, b, k * 2 + 1, l, m)
        vr = get(a, b, k * 2 + 2, m, r)
        return max(vl, vr)
        # 部分被覆

    for h_, a_ in zip(h, a):
        tmp = get(0, h_)
        update(h_, tmp + a_)
        # 1回あたり更新するのは1箇所だから、iを状態にもつ必要はなくて、配列を使い回すことができる
        # 区間maxが高速に計算できればいいから、セグメント木を使えばできる
    return get(0, n + 1)


if __name__ == '__main__':
    import sys

    input = sys.stdin.readline

    n = int(input())
    h = tuple(map(int, input().rstrip().split()))
    a = tuple(map(int, input().rstrip().split()))
    print(solve(n, h, a))

# https://kyopro-friends.hatenablog.com/entry/2019/01/12/231035


### FIXED CODE ###

class SegmentTree:
    def __init__(self, a: list, e: 'default', f: 'function'):
        n = len(a)
        size = 1 << (n - 1).bit_length()  # 元の配列サイズ以上の最小の二冪 == 最下段
        v = [e] * (size * 2 - 1)
        for i in range(n):
            # size-1個の上段の次、size個目からn個が元の配列の代入位置
            v[size - 1 + i] = a[i]
        for i in range(size - 2, -1, -1):
            v[i] = f(v[i * 2 + 1], v[i * 2 + 2])

        self.n = n  # 元の配列の長さ
        self.size = size  # 元の配列サイズ以上の最小の二冪 == 最下段の要素数
        self.v = v  # Segtreeの配列
        self.e = e  # 初期値
        self.f = f  # 比較関数

    def update(self, k: 'index', x: 'val'):
        k += self.size - 1  # 最下段のindexに変更する
        self.v[k] = x  # 値を更新する
        while k > 0:
            k = (k - 1) // 2  # 親のindex
            self.v[k] = self.f(self.v[k * 2 + 1], self.v[k * 2 + 2])

    def get(self, a, b, k=0, l=0, r=-1):
        # [a,b)区間の処理結果を返す
        # 注目区間[l,r)
        if r < 0:
            r = self.size

        if r <= a or b <= l:
            return self.e
        # 区間が重ならない

        if a <= l and r <= b:
            return self.v[k]
        # 完全被覆

        m = (l + r) // 2
        vl = self.get(a, b, k * 2 + 1, l, m)
        vr = self.get(a, b, k * 2 + 2, m, r)
        return self.f(vl, vr)
        # 部分被覆


def solve(n, h, a):
    seg = SegmentTree([0] * (n + 1), 0, max)
    for i in range(n):
        tmp = seg.get(0, h[i])
        seg.update(h[i], tmp + a[i])
        # 1回あたり更新するのは1箇所だから、iを状態にもつ必要はなくて、配列を使い回すことができる
        # 区間maxが高速に計算できればいいから、セグメント木を使えばできる
    return seg.get(0, n + 1)


if __name__ == '__main__':
    n = int(input())
    h = tuple(map(int, input().split()))
    a = tuple(map(int, input().split()))
    print(solve(n, h, a))

# https://kyopro-friends.hatenablog.com/entry/2019/01/12/231035
### BUGGY CODE ###

from collections import deque

S_deque = deque(input())
Q = int(input())

for _ in range(Q):
  item = list(input().split())
  if item[0] == '1':
    S_deque.reverse()

  else:
    if item[1] == '1':
      S_deque.appendleft(item[2])

    else:
      S_deque.append(item[2])

print(''.join(S_deque))

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline

S_deque = list(input())
S_deque = deque(S_deque[:-1])
Q = int(input())

top_flag = 1 # 0なら末尾、1なら最初

for _ in range(Q):
  item = list(input().split())
  if item[0] == '1':
    if top_flag == 0:
      top_flag = 1
    else:
      top_flag = 0

  else:
    in_flag = top_flag + int(item[1])
    if in_flag % 2 == 0:
      S_deque.appendleft(item[2])
    else:
      S_deque.append(item[2])

if top_flag == 0:
  S_deque.reverse()
else:
  pass

print(''.join(S_deque))