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

class UnionFind:
  def __init__(self, size):
    self.parents = [x for x in range(size)]
    self.sizes = [1] * size
  
  def unite(self, a, b):
    if self.find(a) == self.find(b):
      return
    
    if self.size_of(a) > self.size_of(b):
      self.sizes[self.find(a)] += self.size_of(b)
      self.parents[self.find(b)] = self.find(a)
    else:
      self.sizes[self.find(b)] += self.size_of(a)
      self.parents[self.find(a)] = self.find(b)
  
  def is_same(self, a, b):
    return self.find(a) == self.find(b)
  
  def size_of(self, a):
    return self.sizes[self.find(a)]
  
  def find(self, a):
    if a == self.parents[a]:
      return a
    else:
      self.parents[a] = self.find(self.parents[a])
      return self.parents[a]


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

u = UnionFind(N)

# 自分自身・友達・ブロック関係のいずれかの場合はフラグ立つ
relations = [1 << i for i in range(N)]

for _ in range(M):
  a, b = map(int, input().split())
  a, b = a - 1, b - 1
  relations[a] |= 1 << b
  relations[b] |= 1 << a
  u.unite(a, b)
  
for _ in range(K):
  c, d = map(int, input().split())
  c, d = c - 1, d - 1
  
  # 同じ連結成分に含まれないブロック関係は無視してok
  if u.is_same(c, d):
    relations[c] |= 1 << d
    relations[d] |= 1 << c

candidates = []

for i in range(N):
  candidates.append(u.size_of(i) - bin(relations[i]).count('1'))
    
print(' '.join(str(x) for x in candidates))

### FIXED CODE ###

import sys
sys.setrecursionlimit(2 ** 30)
N, M, K = map(int, input().split())

groups = [None] * N
visited = set()

# 連結成分を求める
def dfs(group, i):
  if i in visited:
    return
  
  visited.add(i)
  group.add(i)
  groups[i] = group
  # 他のノード
  for c in graph[i]:
    if not c in visited:
      dfs(group, c)
  

graph = [set() for _ in range(N)]

friends_count = [0] * N
block_count = [0] * N

for _ in range(M):
  a, b = map(int, input().split())
  a, b = a - 1, b - 1
  friends_count[a] += 1
  friends_count[b] += 1
  graph[a].add(b)
  graph[b].add(a)
  
for i in range(N):
  dfs(set(), i)
      
for _ in range(K):
  c, d = map(int, input().split())
  c, d = c - 1, d - 1
  
  # 同じ連結成分に含まれないブロック関係は無視してok
  if d in groups[c]:
    block_count[c] += 1
    block_count[d] += 1

candidates = []

for i in range(N): 
  candidates.append(
    len(groups[i]) - friends_count[i] - block_count[i] - 1
  )
    
print(' '.join(str(x) for x in candidates))
### BUGGY CODE ###

L,R = map(int,input().split())
array = []
for i in range(L,R+1):
    for j in range(L,R+1):
        if i < j:
            m = (i%2019)*(j%2019)
            array.append(m%2019)
print(min(array))

### FIXED CODE ###

L,R = map(int,input().split())
array = []
array2 = []
if R+1 - L <= 2019:
    for i in range(L,R+1):
        if i%2019 not in array2:
            array2.append(i%2019)

    for i in range(len(array2)):
        for j in range(len(array2)):
            if i < j:
                array.append((array2[i]*array2[j])%2019)
    print(min(array))
else:
    for i in range(1,2020):
        if i%2019 not in array2:
            array2.append(i%2019)

    for i in range(len(array2)):
        for j in range(len(array2)):
            if i < j:
                array.append((array2[i]*array2[j])%2019)
    print(min(array))
### BUGGY CODE ###

s = input()
n = len(s)
odd = [0] * n
even = [1] * n
count = 1
loop = 0
for i in range(1, n):
    if s[i] == s[i - 1]:
        count += 1
    else:
        loop = max(loop, count)
        count = 1
loop = max(loop, count)
for i in range(1, loop + 1):
    if i % 2:
        for j in range(n):
            if s[j] == "R":
                odd[j + 1] += even[j]
            else:
                odd[j - 1] += even[j]
            if i != loop:
                even[j] = 0
    else:
        for j in range(n):
            if s[j] == "R":
                even[j + 1] += odd[j]
            else:
                even[j - 1] += odd[j]
            odd[j] = 0
print(" ".join(map(str, even)))

### FIXED CODE ###

s = input()
n = len(s)
count_R = 0
count_L = 0
ans = [0] * n
for i in range(n):
    if s[i] == "R":
        if count_L:
            su = count_R + count_L
            if su % 2:
                if count_L % 2:
                    ans[sakai] = su // 2 + 1
                    ans[sakai - 1] = su // 2
                else:
                    ans[sakai] = su // 2
                    ans[sakai - 1] = su // 2 + 1
            else:
                ans[sakai] = su // 2
                ans[sakai - 1] = su // 2
            count_R = 0
            count_L = 0
        count_R += 1
    else:
        if s[i - 1] == "R":
            sakai = i
        count_L += 1
if count_L:
    su = count_R + count_L
    if su % 2:
        if count_L % 2:
            ans[sakai] = su // 2 + 1
            ans[sakai - 1] = su // 2
        else:
            ans[sakai] = su // 2
            ans[sakai - 1] = su // 2 + 1
    else:
        ans[sakai] = su // 2
        ans[sakai - 1] = su // 2
    count_R = 0
    count_L = 0
print(" ".join(map(str, ans)))
### BUGGY CODE ###

N = int(input())
l = [int(x) for x in input().split()]
n = min(N,len(l))
ans = 1
for i in l[:n]:
    ans *= i
if ans > 10**18:
    ans = -1
print(ans)

### FIXED CODE ###

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

if 0 in l:
    ans = 0
else:
    n = min(N,len(l))
    ans = 1
    for i in l[:n]:
        ans *= i
        if ans > 10**18:
            ans = -1
            break
print(ans)
### BUGGY CODE ###

n,q = map(int, input().split())
s = input()

for _ in range(q):
  l,r = map(int, input().split())
  l -= 1
  print(s[l:r].count("AC"))

### FIXED CODE ###

n,q = map(int, input().split())
s = input()

nums = [0]*n
for i in range(n):
  if s[i] == "C":
    if s[i-1] == "A": nums[i] += 1
  if i != n-1: nums[i+1] = nums[i]

for _ in range(q):
  l,r = map(lambda x: int(x)-1, input().split())
  print(nums[r]-nums[l])
### BUGGY CODE ###

a,b,k=map(int,input().split())
for _ in range(k):
	if a > 0:
		a-=1
	elif b > 0:
		b-=1
	else:
		break
print(a,b)

### FIXED CODE ###

a,b,k=map(int,input().split())
if k<=a:
    print(a-k,b)
elif a<k<=a+b:
    print(0,b-(k-a))
else:
    print(0,0)
### BUGGY CODE ###

N, M = map(int,input().split())
X = [int(x) for x in input().split()]
X.sort(reverse=True)
valX = [X[x] - X[x + 1] for x in range(M - 1)]

if N >= M:
    print(0)
    exit()

if N == 1:
    print(max(X) - min(X))
    exit()

for i in range(1,N):
    valX[valX.index(max(valX))] = 0

print(sum(valX))

### FIXED CODE ###

N, M = map(int,input().split())
X = [int(x) for x in input().split()]
X.sort(reverse=True)
valX = [X[x] - X[x + 1] for x in range(M - 1)]
valX.sort(reverse=True)

if N >= M:
    print(0)
    exit()

if N == 1:
    print(max(X) - min(X))
    exit()

for i in range(N - 1):
    valX[i] = 0

print(sum(valX))
### BUGGY CODE ###

from collections import Counter
n = int(input())
s = [input() for _ in range(n)]
alrdy = []
 
def is_anagrams(word1, word2):
    def get_counter(s):
        return Counter(s.upper().replace(' ', ''))
 
    return get_counter(word1) == get_counter(word2)

cnt = 0
for i in range(n-1):
  for j in range(i+1, n):
    if is_anagrams(s[i], s[j]):
      cnt += 1
      continue
print(cnt)

### FIXED CODE ###

n = int(input())
s = [input() for _ in range(n)]
existed = {}
cnt = 0
for i in range(n):
  sorted_s = ''.join(sorted(s[i]))
  if sorted_s in existed:
    cnt += existed[sorted_s]
    existed[sorted_s] += 1
  else:
    existed[sorted_s] = 1
print(cnt)
### BUGGY CODE ###

import numpy as np
N, K, Q = map(int, input().split())
p = [K] * N
m = [1] * N
for i in range(Q):
  A = int(input())
  p = [p[i] - m[i] for i in range(len(p))]
  #p = p - m
  p[A-1] = p[A-1] + 1
  if sum(p) == 0:
    break
for s in p:
  if s > 0:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

import numpy as np
N, K, Q = map(int, input().split())
p = np.array([K - Q] * N)
for i in range(Q):
  A = int(input())
  p[A-1] = p[A-1] + 1
for s in p:
  if s > 0:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

X=int(input())
stp=0
for a in range(10**5):
    if stp==1:
        break
    else:
        for b in range(10**5):
            A=a**5
            B=b**5
            tmp1=A-B
            tmp2=-A+B
            tmp3=-A-B
            tmp4=A+B
            if tmp1==X:
                print(a,b)
                stp=1
                break
            elif tmp2==X:
                print(-a,-b)
                stp=1
                break
            elif tmp3==X:
                print(-a,b)
                stp=1
                break
            elif tmp4==X:
                print(a,-b)
                stp=1
                break

### FIXED CODE ###

X=int(input())
stp=0
for a in range(120):
    if stp==1:
        break
    else:
        for b in range(120):
            A=a**5
            B=b**5
            tmp1=A-B
            tmp2=-A+B
            tmp3=-A-B
            tmp4=A+B
            if tmp1==X:
                print(a,b)
                stp=1
                break
            elif tmp2==X:
                print(-a,-b)
                stp=1
                break
            elif tmp3==X:
                print(-a,b)
                stp=1
                break
            elif tmp4==X:
                print(a,-b)
                stp=1
                break
### BUGGY CODE ###

from heapq import heappop, heappush
n, m = map(int, input().split())
lst = [list(map(int, input().split())) for i in range(n)]
lst_f = [[] for i in range(m)]
#lst = sorted(lst, key=lambda x:x[0])
#lst = sorted(lst, key=lambda x:x[1], reverse=True)
cnt = 0
ans = 0
cntup = m
for a, b in lst:
  if a <= m:
    lst_f[a-1].append(b)
  #print(filter(lambda y:y<=m-i, map(lambda x:x[0], lst)))
  #lst2 = list(filter(lambda y:y[1]<=m-i, lst))
avb = [] 
for i in lst_f:
  for j in i:
    avb.append(-j)
  if avb != []:
    ans -= avb.pop(avb.index(min(avb)))
print(ans)


### FIXED CODE ###

from heapq import heappop, heappush
n, m = map(int, input().split())
lst = [list(map(int, input().split())) for i in range(n)]
lst_f = [[] for i in range(m)]
#lst = sorted(lst, key=lambda x:x[0])
#lst = sorted(lst, key=lambda x:x[1], reverse=True)
cnt = 0
ans = 0
cntup = m
for a, b in lst:
  if a <= m:
    lst_f[a-1].append(b)
  #print(filter(lambda y:y<=m-i, map(lambda x:x[0], lst)))
  #lst2 = list(filter(lambda y:y[1]<=m-i, lst))
avb = [] 
for i in lst_f:
  for j in i:
    heappush(avb, -j)
  if avb != []:
    ans -= heappop(avb)
print(ans)
### BUGGY CODE ###

"""
3*10**5
単純に両側の差を全探索だと間に合わないO(N*2)

情報を先に保存しておきそれを使う
"""

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

E_list = [0]
W_list = [0]

n = 0
for i in range(1,N):
    if S[i-1] == "W":
        n += 1
        W_list.append(n)
    else:
        W_list.append(n)

n = 0
for i in reversed(range(N-1)):
    if S[i+1] == "E":
        n += 1
        E_list.insert(0,n)
    else:
        E_list.insert(0,n)

ans = []
for i in range(N):
    ans.append(E_list[i] + W_list[i])
print(min(ans))


### FIXED CODE ###

"""
3*10**5
単純に両側の差を全探索だと間に合わないO(N*2)

情報を先に保存しておきそれを使う
"""

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

E_list = [0] * N 
W_list = [0] * N

n = 0
for i in range(1,N):
    if S[i-1] == "W":
        n += 1
        W_list[i] = n
    else:
        W_list[i] = n

n = 0
for i in reversed(range(N-1)):
    if S[i+1] == "E":
        n += 1
        E_list[i] = n
    else:
        E_list[i] = n

print(min([e+w for e,w in zip(E_list, W_list)]))
### BUGGY CODE ###

n,k = map(int, input().split())
p = [(int(i)+1)/2 for i in input().split()]
ans = 0
for i in range(n-k+1):
    ans = max(sum(p[i:i+k]),ans)
print(ans)

### FIXED CODE ###

n,k = map(int, input().split())
p = [(int(i)+1)/2 for i in input().split()]
ansi = sum(p[0:k-1])
ans = 0
for i in range(k-1,n):
    a1 = p[i-k+1]
    if ansi + p[i] >= ans:
        ans = ansi + p[i]
    ansi = ansi - a1 + p[i]
print(ans)
### BUGGY CODE ###

# input 
def findmax(al, fl):
  max_n = -1
  max_id = -1
  for i in range(len(al)):
    if al[i]*fl[i] > max_n:
      max_n = al[i]*fl[i]
      max_id = i
  return max_n, max_id
n, k = map(int, input().split())
al = list(map(int, input().split()))
fl = list(map(int, input().split()))
al.sort()
fl.sort(reverse=True)
ans = max([al[i]*fl[i] for i in range(n)])
while k > 0 and sum(al) > 0:
    max_n, idx = findmax(al, fl)
    al[idx] -= 1
    k -= 1
ans = max([al[i]*fl[i] for i in range(n)])
print(ans)

### FIXED CODE ###

import math
import numpy as np
def yn(a, f, k, x):
  k_yt = np.maximum(np.zeros(a.shape),a - np.floor(np.divide(x, f)))
  k_yt = np.sum(k_yt)
  if k_yt <= k:
    return True
  else:
    return False

n, k = map(int, input().split())
a = list((map(int, input().split())))
f = list((map(int, input().split())))
a.sort()
f.sort(reverse = True)
xo = max([a[i]*f[i] for i in range(n)])
a = np.array(a)
f = np.array(f)
# binary search
if xo == 0:
  print(0)
else:
  l = 0
  r = xo
  m = xo
  while l <= r:
    piv = int((r+l)/2)
    if yn(a, f, k, piv):
      r = piv - 1 
      m = piv
    else:
      l = piv +1
  print(m)
### BUGGY CODE ###

import numpy as np
N = int(input())
a = [int(i) for i in input().split()]
zeros = np.zeros(N)
index = np.arange(1, N + 1)
middle = int(N / 2) + 1

for i, e in zip(a[::-1], index[::-1]):
    if e >= middle:
        zeros[e - 1] = i
    else:
        if sum(zeros[index % e == 0]) % 2 == i:
            pass
        else:
            zeros[e - 1] = 1

M = sum(zeros)
print(int(M))

for i, e in zip(zeros, index):
    if i == 1:
        print(e, end=" ")


### FIXED CODE ###

N = int(input())
a = [int(i) for i in input().split()]
zeros = [0] * N
ai = length = len(a)

for i in a[::-1]:
    s = 0
    for j in range(ai, length+1, ai):
        s += zeros[j-1]
    if s % 2 == i:
        pass
    else:
        zeros[ai-1] = 1
    ai -= 1

print(sum(zeros))
for i, v in enumerate(zeros, 1):
    if v:
        print(i)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

inf = float('inf')
p = 2**n
dp = [inf]*p
dp[0] = 0

for _ in range(m):
    a, _ = map(int, input().split())
    c = sum([2**(i-1) for i in map(int, input().split())])
    for i in range(p):
        dp[i|c] = min(dp[i|c], dp[i] + a)
    
if dp[-1] == inf:
    print(-1)
else:
    print(dp[-1])


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

inf = float('inf')
p = 2**n
dp = [inf]*p
dp[0] = 0

for _ in range(m):
    a, _ = map(int, input().split())
    c = sum([2**(i-1) for i in map(int, input().split())])
    for i in range(p):
        if dp[i|c] > dp[i] + a: 
            dp[i|c] = dp[i] + a
    
if dp[-1] == inf:
    print(-1)
else:
    print(dp[-1])
### BUGGY CODE ###

import sys
def main():
    input = sys.stdin.readline
    H,W = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    B = [list(map(int, input().split())) for _ in range(H)]

    dp = [[set() for _ in range(W)] for __ in range(H)]
    dp[0][0].add(abs(A[0][0] - B[0][0]))
    for i in range(H):
        for j in range(W):
            for s in dp[i][j]:
                for ni,nj in [(i,j+1),(i+1,j)]:
                    if ni >= H or nj >= W: continue
                    dp[ni][nj].add(s + abs(A[ni][nj] - B[ni][nj]))
                    dp[ni][nj].add(abs(s - abs(A[ni][nj] - B[ni][nj])))
    print(min(dp[H-1][W-1]))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
def main():
    input = sys.stdin.readline
    H,W = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    B = [list(map(int, input().split())) for _ in range(H)]
    C = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]

    M = 160*80
    dp = [[0 for _ in range(W)] for __ in range(H)]
    dp[0][0] = 1 << (C[0][0] + M)
    for i in range(H):
        for j in range(W):
            for ni,nj in [(i,j+1),(i+1,j)]:
                if ni >= H or nj >= W: continue
                t = C[ni][nj]
                dp[ni][nj] |= dp[i][j] << t
                dp[ni][nj] |= dp[i][j] >> t
    
    a = dp[H-1][W-1]
    ans = 0
    while True:
        if a & (1 << (M+ans)) or a & (1 >> (M-ans)): break
        ans += 1
    print(ans)

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

def add(s1,s2):
    l = []
    for x in s1:
        for y in s2:
            l.append(x+y)
    return l

def cake(s1,s2,s3):
    ans1 = add(s1,s2)
    ans2 = add(ans1,s3)
    return ans2    
    
a,b,c,d = map(int, input().split())
s1=list(map(int, input().split()))
s2=list(map(int, input().split()))
s3=list(map(int, input().split()))
z = sorted(cake(s1,s2,s3),reverse=True)
for i in range(0,d):
    print(z[i])

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
x, y, z, k = map(int, input().split())
a = sorted(int(i) for i in input().split())
b = sorted(int(i) for i in input().split())
c = sorted(int(i) for i in input().split())
 
#a.sort(reverse=True)
#b.sort(reverse=True)
#c.sort(reverse=True)
 
ab = sorted(i+j for i in a for j in b)[:-k-1:-1]
abc = sorted(i+j for i in ab for j in c)[:-k-1:-1]
 
print(*abc[:k], sep="\n")
### BUGGY CODE ###

import bisect

x,y,z,k = map(int, input().split())
aa = list(map(int, input().split()))
bb = list(map(int, input().split()))
cc = list(map(int, input().split()))

# A,Bでソート
score_ab = []
for a in aa:
    for b in bb:
            bisect.insort_right(score_ab, a+b)
# print(score_ab[::-1])
# A,B合計値の上位K個とCでソート
score = []
for s in score_ab[::-1][:k]:
    for c in cc:
            bisect.insort_right(score, s+c)
for s in score[::-1][:k]:
    print(s)

### FIXED CODE ###

x,y,z,k = map(int, input().split())
aa = sorted(list(map(int, input().split())))
bb = sorted(list(map(int, input().split())))
cc = sorted(list(map(int, input().split())))

ab = sorted(a+b for a in aa for b in bb)[:-k-1:-1]
abc = sorted(s+c for s in ab[:k] for c in cc)[:-k-1:-1]
print(*abc, sep='\n')
### BUGGY CODE ###

N,A,B=map(int,input().split())
MOD=10**9+7

def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
  
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
	
print((pow(2,N,MOD)-1-comb(N,A)-comb(N,B))%MOD)


### FIXED CODE ###

a,b,c = map(int,input().split())
MOD = 10**9+7

def comb(n,r):
    res = 1
    fac = 1
    for i in range(r):
        res *= n-i
        res %= MOD
        fac *= i+1
        fac %= MOD
    return res*pow(fac,MOD-2,MOD)%MOD 

p = pow(2,a,MOD)
q = comb(a,b)
r = comb(a,c)
ans = (p-q-r-1)%MOD
print(ans)
### BUGGY CODE ###

import itertools
import math
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
from functools import reduce
sys.setrecursionlimit(4100000)
from functools import lru_cache
INF = 1 << 60

#ここから書き始める
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))
x = [[0, 0]] * m
for i in range(m):
    b, c = map(int, input().split())
    x[i] = [c, b]
x.sort(reverse=True)
# print("x =", x)
# print("a =", a)
y = []
for i in range(m):
    z = [x[i][0]] * x[i][1]
    y.extend(z)
# print("y =", y)
ans = sum(a)
length = min(n, len(y))
for i in range(length):
    if a[i] >= y[i]:
        break
    ans += y[i] - a[i]
print(ans)


### FIXED CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
bc = [list(map(int,input().split())) for i in range(m)]
bc.sort(key=lambda x:x[1], reverse=True)
  
for b,c in bc:
  a.extend([c]*b)
  if len(a) > n*2:
    break
a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

i = list(map(int, input().split()))
isTWin = False;

while i[0] and i[2]:
    i[2] -= i[1]
    if not i[2]:
        isTWin = True
        break

    i[0] -= i[3]
    if not i[0]:
        isTWin = False
        break
        
if isTWin:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

import math

i = list(map(int, input().split()))
turnT = math.ceil(i[0] / i[3]);
turnA = math.ceil(i[2] / i[1]);
        
if turnT >= turnA:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

S = str(input())
Q = int(input())
Qvery = [0]*Q
for i in range(Q):
    Qvery[i] = list(map(str,input().split()))
    
for i in range(Q):
    if Qvery[i][0]=='1':
        S = S[::-1]
    else:
        if Qvery[i][1]=='2':
            S = S + str(Qvery[i][2])
        else:
            S = str(Qvery[i][2]+S)
  
print(S)

### FIXED CODE ###

S = str(input())
Q = int(input())
Qvery = [0]*Q
for i in range(Q):
    Qvery[i] = list(map(str,input().split()))
frontback = 1
tail = ''
head = ''
for i in range(Q):
    if Qvery[i][0]=='1':
        frontback *= -1
        
    else:
        if Qvery[i][1]=='2':
            if frontback == 1:
                tail +=  str(Qvery[i][2])
            else:
                head = str(Qvery[i][2]) + head
        else:
            if frontback == 1:
                head = str(Qvery[i][2])+head
            else:
                tail += str(Qvery[i][2])
S = head + S + tail
if frontback == -1:
    S = S[::-1]
    
print(S)
### BUGGY CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))

B = np.sort(A)[::-1]
B_index = np.argsort(A)[::-1]
dp = [[0]*(N+1) for _ in range(N+1)]
ans = 0

for n in range(0,N+1):
    for y in range(0,n+1):
        x = n-y
        ind = B_index[x+y-1]
        if x==0 and y==0:
            dp[x][y] = 0
        elif x==0:
            dp[x][y] = dp[x][y-1] + B[x+y-1]*abs(ind-((N-1)-(y-1)))
        elif y==0:
            dp[x][y] = dp[x-1][y]+B[x+y-1]*abs(ind-(x-1))
        else:
            dp[x][y] = max(dp[x-1][y]+B[x+y-1]*abs(ind-(x-1)),dp[x][y-1] + B[x+y-1]*abs(ind-((N-1)-(y-1))))
        ans = max(ans,dp[x][y])

print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A = [[a,i] for a,i in zip(A,range(N))]
A = sorted(A,reverse=True)

dp = [[0]*(N+1) for _ in range(N+1)]
ans = 0

for n in range(0,N+1):
    for y in range(0,n+1):
        x = n-y
        a = A[n-1]
        ind = a[1]
        if x==0 and y==0:
            dp[x][y] = 0
        elif x==0:
            dp[x][y] = dp[x][y-1] + a[0]*abs(ind-((N-1)-(y-1)))
        elif y==0:
            dp[x][y] = dp[x-1][y]+a[0]*abs(ind-(x-1))
        else:
            dp[x][y] = max(dp[x-1][y]+a[0]*abs(ind-(x-1)),dp[x][y-1] + a[0]*abs(ind-((N-1)-(y-1))))
        ans = max(ans,dp[x][y])

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

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

    for query_list in query:
        if query_list[0] == '1':
            s = s[::-1]
        else:
            if query_list[1] == '1':
                s = ''.join([query_list[2], s])
            else:
                s = ''.join([s, query_list[2]])

    print(s)

main()

### FIXED CODE ###

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

Inv = False #反転しているか
front_str = [] #末尾側
back_str = [] #先頭側

for query_list in query:
    if query_list[0] == '1':
        Inv = not Inv
    else:
        if query_list[1] == '1': #先頭に追加
            if Inv:
                front_str.append(query_list[2])
            else:
                back_str.append(query_list[2])
        else:
            if Inv:
                back_str.append(query_list[2])
            else:
                front_str.append(query_list[2])

answer = "".join(back_str[::-1] + [s] + front_str)

if Inv:
    answer = answer[::-1]

print(answer)