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

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

def resolve():
    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()

    def binSearch(a, x):
        l = -1
        r = len(a)
        while r-l>1:
            m = (l+r)//2
            if x<a[m]:
                r = m
            else:
                l = m
        return r

    ans = 0
    for a in A:
        b_l = binSearch(B, a)
        for b in B[b_l:]:
            c_l = binSearch(C, b)
            ans += N - c_l

    print(ans)

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

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

def resolve():
    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()

    def binsearch_left(a, x):
        l = -1
        r = len(a)
        while r-l>1:
            m = (l+r)//2
            if x<a[m]:
                r = m
            else:
                l = m
        return r

    def binsearch_right(a, x):
        l = -1
        r = len(a)
        while r-l>1:
            m = (l+r)//2
            if x<=a[m]:
                r = m
            else:
                l = m
        return r

    ans = 0
    for b in B:
        a_r = binsearch_right(A, b)
        c_l = binsearch_left(C, b)
        ans += a_r * (N - c_l)

    print(ans)

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

n, k = map(int, input().split())
h = sorted(map(int, input().split()), reverse=True)
if k == 0:
    print(sum(h))
elif k < n:
    for i in range(k):
        h.pop(0)
    print(sum(h))
else:
    print(0)


### FIXED CODE ###

n, k = map(int, input().split())
h = sorted(map(int, input().split()), reverse=True)
if k == 0:
    print(sum(h))
elif k < n:
    print(sum(h[k:]))
else:
    print(0)
### BUGGY CODE ###

N = int(input())
a = []
for i in range(N):
  a.append(int(input()))

for i in range(N):
  b = a[:]
  b.pop(i)
  print(max(b))


### FIXED CODE ###

N = int(input())
a = []
for i in range(N):
  a.append(int(input()))

sort = sorted(a)
m1 = sort[-1]
m2 = sort[-2]
if m1 == m2:
  for i in range(N):
    print(m1)
else:
  j = a.index(m1)
  for i in range(N):
    if i == j:
      print(m2)
    else:
      print(m1)
### BUGGY CODE ###

a=int(input())
b = list(map(int, input().split()))
b.sort()
S=0

for i in range(0,a):
    S=S+b[i]*sum(b[i+1:a])
print(S % (10**9+7))

### FIXED CODE ###

a=int(input())
b = list(map(int, input().split()))
b.sort()
S=0
c=sum(b)
for i in range(0,a):
    c=c-b[i]
    S=S+b[i]*c
print(S % (10**9+7))
### BUGGY CODE ###

H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]

x = [0]*(H*W+1)

for h1 in range(H):
    for w1 in range(W):
        if A[h1][w1] > H*W-D:
            continue
        f = False
        for h2 in range(H):
            for w2 in range(W):
                if A[h1][w1]+D == A[h2][w2]:
                    x[A[h2][w2]] = abs(h1-h2)+abs(w1-w2)
                    f = True
                    break
            if f:
                break

y = x[:D+1]
for i in range(D+1, H*W+1):
    y.append(y[i-D]+x[i])

for _ in range(int(input())):
    l, r = map(int, input().split())
    print(y[r]-y[l])

### FIXED CODE ###

H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]

x = [0]*(H*W+1)
p = [[] for _ in range(H*W+1)]

for h in range(H):
    for w in range(W):
        p[A[h][w]] = [h, w]

for i in range(D+1, H*W+1):
    x[i] = x[i-D]+abs(p[i][0]-p[i-D][0])+abs(p[i][1]-p[i-D][1])

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

def comb(n, k):
    m = 1
    if n < 2 * k:
        k = n - k
    for i in range(1, k + 1):
        m = m * (n - i + 1) / i    
    return m
n = int(input())
a = list(map(int, input().split()))
a_sorted = sorted(a)
d = []
e = []
f = []
for i in range(n-1):
    b = a_sorted[i+1]
    for c in a_sorted:
        if c <  b:
            e.append(b)
            f.append(c)
            d.append(comb(b,c))
g = d.index(max(d))
print('%d %d'%(e[g],f[g]))

### FIXED CODE ###

# -*- coding: utf-8 -*-
# kakomon toku
import math
import sys
import itertools
import numpy as np
 
n = int(input())
a = [int(i) for i in input().split()]
 
#print(a)
a = np.sort(a)
ai = a[n-1]
aj = a[0]
center = ai / 2
diff = ai
i=0
for m in a:
    if diff > abs(m - center) :
        aj = m
        diff = abs(aj - center)
    else:
        break
 
print(ai,aj)
### BUGGY CODE ###

a,b=map(int,input().split())
c=0
for l in range(a+1):
    for m in range(l,a+1):
        for r in range(m,a+1):
            if l+m+r==b:
                if l==m and m==r:
                    c+=1
                elif l==m:
                    c+=3
                elif m==r:
                    c+=3
                else:
                    c+=6
print(c)

### FIXED CODE ###

a,b=map(int,input().split())
c=0
for l in range(a+1):
    for m in range(l,a+1):
        r=b-l-m
        if r >a:
            continue
        elif r<m:
            continue
        elif r==l==m:
            c+=1
        elif r==m:
            c+=3
        elif m==l:
            c+=3
        else:
            c+=6
print(c)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def readstr():
    return input().strip()


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


def readstrs():
    return input().split()


def main():
    N = readint()
    X = list(readnums())
    xs = sorted(X)
    for i in X:
        d = xs.index(i)
        if d >= N // 2:
            print(xs[N // 2 - 1])
        else:
            print(xs[N // 2])


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import bisect
input = sys.stdin.readline


def readstr():
    return input().strip()


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


def readstrs():
    return input().split()


def main():
    N = readint()
    X = list(readnums())
    xs = sorted(X)
    for i in X:
        d = bisect.bisect_left(xs, i)
        if d >= N // 2:
            print(xs[N // 2 - 1])
        else:
            print(xs[N // 2])


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

from itertools import permutations

D, G = map(int, input().split())
PC = []
for _ in range(D):
    p, c = map(int, input().split())
    PC.append((p, c))

ans = sum(p for p, _ in PC)
for ids in permutations(range(D)):
    score = 0
    num = 0
    for i in ids:
        p, c = PC[i]
        if score + (i + 1) * 100 * p + c < G:
            score += (i + 1) * 100 * p + c
            num += p
        else:
            for j in range(p):
                score += (i + 1) * 100
                num += 1
                if G <= score:
                    ans = min(ans, num)
                    break
            else:
                score += c
                if G <= score:
                    ans = min(ans, num)
        if G <= score:
            break
print(ans)

### FIXED CODE ###

from itertools import permutations

D, G = map(int, input().split())
PC = []
for _ in range(D):
    p, c = map(int, input().split())
    PC.append((p, c))

ans = sum(p for p, _ in PC)
for ids in permutations(range(D)):
    score = 0
    num = 0
    for i in ids:
        p, c = PC[i]
        if score + (i + 1) * 100 * p + c < G:
            score += (i + 1) * 100 * p + c
            num += p
        else:
            for j in range(p):
                score += (i + 1) * 100
                num += 1
                if G <= score:
                    ans = min(ans, num)
                    break
            else:
                score += c
                if G <= score:
                    ans = min(ans, num)
        if G <= score:
            break
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[0 for i in range(m)]
b=[0 for i in range(m)]
c=[[] for i in range(m)]
for i in range(m):
    a[i],b[i]=map(int,input().split())
    c[i]=list(map(int,input().split()))
dp = [float("inf") for i in range(1<<n)]
dp[0] = 0
for i in range(m):
    now = 0
    for j in c[i]:
        jj = 1<< j-1
        now |= jj
    for k in range(1<<n):
        kk = k | now
        dp[kk] = min(dp[kk], dp[k]+a[i])
if dp[-1]==float("inf"):
    print(-1)
else:
    print(dp[-1])

### FIXED CODE ###

def main():
  n,m=map(int,input().split())
  a=[0 for i in range(m)]
  b=[0 for i in range(m)]
  c=[[] for i in range(m)]
  for i in range(m):
    a[i],b[i]=map(int,input().split())
    c[i]=list(map(int,input().split()))
  
  dp=[float("inf") for i in range(2**n)]
  dp[0]=0
  for i in range(m):
    now=0
    for j in c[i]:
      jj=1<<j-1
      now|=jj
    for k in range(2**n):
      kk=k|now
      dp[kk]=min(dp[kk],dp[k]+a[i])
    
 
  if dp[-1]==float("inf"):
    print(-1)
  else:
    print(dp[-1])
    
if __name__ == '__main__':  
  main()
### BUGGY CODE ###

n = int(input())

ss = []
for i in range(n):
    tmp = list(input())
    tmp.sort()
    ss.append(tmp)

checked = set()
count = 0

for i in range(n-1):
    if i in checked:
        continue
    same_str = set()
    for j in range(i+1, n):
        if ss[i] == ss[j]:
            count += 1

            for s in same_str:
                count += 1

            same_str.add(j)
            checked.add(j)

print(count)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())

#ss = [sorted(list(input())) for _ in range(n)]
ss = []
checked = {}
count = 0
for i in range(n):
    tmp = list(input())
    tmp.sort()
    tmp = str(tmp)
    if not(tmp in checked):
        checked[tmp] = 1
    else:
        count += checked[tmp]
        checked[tmp] += 1

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

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

INF = float('inf')
ww = [0]*n
vv = [0]*n
vm = 1000
dp = [[INF]*(n*vm+1) for _ in range(n+1)]

for i in range(n):
  ww[i],vv[i] = map(int,input().split())      

dp[0][0] = 0  
for i in range(1,n+1):
  dp[i][0] = 0
  for j in range(1,n*vm+1):        
    if j < vv[i-1]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = min(dp[i-1][j], dp[i-1][j-vv[i-1]] + ww[i-1])        

ans = 0
for i in range(n*vm+1):
  if dp[n][i]<=w:
    ans = i
print(ans)    

### FIXED CODE ###

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

INF = float('inf')
ww = [0]*n
vv = [0]*n
vm = 1000
dp = [[INF]*(n*vm+1) for _ in range(n+1)]

for i in range(n):
  ww[i],vv[i] = map(int,input().split())      

dp[0][0] = 0  
for i in range(1,n+1):
  dp[i][0] = 0
  for j in range(1,n*vm+1):        
    if j < vv[i-1]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = min(dp[i-1][j], dp[i-1][j-vv[i-1]] + ww[i-1])        

ans = 0
for i in range(n*vm+1):
  if dp[n][i]<=w:
    ans = i
print(ans)
### BUGGY CODE ###

N, Q = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(N - 1)]
px = [list(map(int, input().split())) for _ in range(Q)]

class Tree:
  C = {}
  N, D = None, None
  def __init__(s, num):
    s.N = num
  def setC(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def exe(s):
    L = [-1] * N
    A = [0] * N
    for p, x in px:
      p -= 1
      A[p] += x
    S = [0]
    while S != []:
      t = S.pop()
      L[t] = 1
      for i in s.C[t]:
        if L[i] == -1:
          A[i] += A[t]
          S.append(i)
    for i in range(N):
      print(A[i], end = " ")

  

T = Tree(N)
for a, b in ab:
  a -= 1
  b -= 1
  T.setC(a, b)

T.exe()



### FIXED CODE ###

import sys
input = sys.stdin.readline

N, Q = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(N - 1)]
px = [list(map(int, input().split())) for _ in range(Q)]

class Tree:
  C = {}
  N, D = None, None
  def __init__(s, num):
    s.N = num
  def setC(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def exe(s):
    L = [-1] * N
    A = [0] * N
    for p, x in px:
      p -= 1
      A[p] += x
    S = [0]
    while S != []:
      t = S.pop()
      L[t] = 1
      for i in s.C[t]:
        if L[i] == -1:
          L[i] = 1
          A[i] += A[t]
          S.append(i)
    for i in range(N):
      print(A[i], end = " ")

T = Tree(N)
for a, b in ab:
  a -= 1
  b -= 1
  T.setC(a, b)

T.exe()
### BUGGY CODE ###

import collections
n,m = map(int, input().split())
cnt = [0 for _ in range(n)]
for i in range(m):
	l,r = map(int, input().split())
	for i in range(l-1, r):
		cnt[i] += 1
c = collections.Counter(cnt)
print(c[m])

### FIXED CODE ###

n,m = map(int, input().split())
minn, maxn = 1, n
for i in range(m):
	l, r = map(int,input().split())
	minn, maxn = max(minn, l), min(maxn, r)
print(max(maxn-minn+1, 0))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

S = list(input().strip())
P = [list(v) for v in ["dream", "dreamer", "erase", "eraser"]]

sys.setrecursionlimit(10000)
def dfs(n):
    if len(S[n:]) == 0:
        return True
    
    for v in P:
        if S[n:n+len(v)] == v:
            if dfs(n + len(v)):
                return True
    
    return False

if dfs(0):
    print("YES")
else:
    print("NO")

### FIXED CODE ###

import sys
input = sys.stdin.readline

S = list(reversed(input().strip()))
P = [list(reversed(v)) for v in ["dream", "dreamer", "erase", "eraser"]]

n = 0
while n < len(S):
    if S[n:n+5] == P[0] or S[n:n+5] == P[2]:
        n += 5
    elif S[n:n+7] == P[1]:
        n += 7
    elif S[n:n+6] == P[3]:
        n += 6
    else:
        print("NO")
        exit()
        
print("YES")
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**7)

n = int(input())
graph = {i : [] for i in range(n)}
ls = []
for i in range(n-1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    ls.append((a,b))
    graph[a].append(b)
    graph[b].append(a)
_max = 0
_max_node = None
for k, v in graph.items():
    if len(v) > _max:
        _max = len(v)
        _max_node = k

colors = [[0 for i in range(n)] for j in range(n)]

que = deque()
color_dict = {i : [] for i in range(n)}
cur = _max_node
while True:
    cnt = 1
    for _next in graph[cur]:
        if colors[cur][_next] == 0:
            que.append(_next)
            candidate = color_dict[_next] + color_dict[cur]
            while cnt in candidate:
                cnt = cnt + 1 if cnt + 1 <= _max else 1
            colors[cur][_next] = cnt
            colors[_next][cur] = cnt
            color_dict[cur].append(cnt)
            color_dict[_next].append(cnt)
            cnt += 1
    if len(que) == 0:
        break
    cur = que.popleft()
print(_max)
for a, b in ls:
    print(colors[a][b])

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**7)

n = int(input())
graph = {i : [] for i in range(n)}
ls = []
for i in range(n-1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    ls.append((a,b))
    graph[a].append(b)
    graph[b].append(a)
_max = 0
_max_node = None
for k, v in graph.items():
    if len(v) > _max:
        _max = len(v)
        _max_node = k

parent = [_max_node] * (n)
order = []
stack = [_max_node]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

colors = [-1 for i in range(n)]
for i in order:
    c = 1
    for _next in graph[i]:
        if _next == parent[i]:
            continue
        if c == colors[i]:
            c += 1
        colors[_next] = c
        c += 1
print(_max)
for a, b in ls:
    if parent[a] == b:
        print(colors[a])
    else:
        print(colors[b])
### BUGGY CODE ###

import sys

#+++++

def is_tr(a,b,c):
	if a < b+c:
		return True
	return False


def main():
	n = int(input())
	ll = list(map(int, input().split()))
	n=len(ll)
	ll.sort(reverse = True)
	pa(ll)
	
	ret = 0
	for i,l1 in enumerate(ll[:-2]):
		for j, l2 in enumerate(ll[i+1:-1]):
			pa(ret)
			if not is_tr(l1, l2, ll[j+1]):
				break
			if is_tr(l1,l2,ll[-1]):
				pa('ggg')
				ret += n-(i+1+j+1)
				continue
			ok=i+j+1
			ng=n-1
			while ng-ok > 1:
				mid = (ok+ng)//2
				if is_tr(l1,l2,ll[mid]):
					ok =mid
				else:
					ng = mid
			pa((ok,j+i+1))
			ret += (ok - (i+j+1))
	
	print(ret)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

### FIXED CODE ###

import sys

#+++++

def is_tr(a,b,c):
	if a < b+c:
		return True
	return False


def main():
	n = int(input())
	ll = list(map(int, input().split()))
	n=len(ll)
	ll.sort(reverse = True)
	pa(ll)
	
	ret = 0
	for i,l1 in enumerate(ll[:-2]):
		for j, l2 in enumerate(ll[i+1:-1]):
			pa(ret)
			if not is_tr(l1, l2, ll[j+1]):
				break
			if is_tr(l1,l2,ll[-1]):
				pa('ggg')
				ret += n-(i+1+j+1)
				continue
			ok=i+j+1
			ng=n-1
			while ng-ok > 1:
				mid = (ok+ng)//2
				if is_tr(l1,l2,ll[mid]):
					ok =mid
				else:
					ng = mid
			pa((ok,j+i+1))
			ret += (ok - (i+j+1))
	
	print(ret)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
### BUGGY CODE ###

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

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

for discount_i in range(m):
  max_item = max(item_list)
  target_index = item_list.index(max_item)
  item_list[target_index] = item_list[target_index]//2
  
print(sum(item_list))

### FIXED CODE ###

import heapq

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

item_list = list(map(lambda x: -1 * int(x), input().split()))
heapq.heapify(item_list)

for discount_i in range(m):
  target = -1*(-1*heapq.heappop(item_list)//2)
  heapq.heappush(item_list, target)

print(-1*sum(item_list))
### BUGGY CODE ###

N = int(input())
A = input().split()

L = []
F = 0

for i in range(N):
  if A[i] not in L:
    L.append(A[i])
  else:
    print('NO')
    F = 1
    break
    
if F == 0:
  print('YES')

### FIXED CODE ###

N = int(input())
seq = input().split()
 
if len(seq) != len(set(seq)):
  print('NO')
else:
  print('YES')
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(1, n + 1):
    x, y = i, (n // i) * i
    #等差数列の和は(1/2)*(項数(今回はn//i))*(初項＋末項)
    ans += ((n // i) * (x + y) // 2)
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
for i in range(1, n + 1):
    x, y = i, (n // i) * i
    #等差数列の和は(1/2)*(項数(今回はn//i))*(初項＋末項)
    ans += ((n // i) * (x + y) // 2)
print(ans)
### BUGGY CODE ###

S = input()

index_A = [n+1 for n, v in enumerate(S) if v == "A"]
index_Z = [n+1 for n, v in enumerate(S) if v == "Z"]

ans = 0
for i in range(len(index_A)):
    for j in range(len(index_Z)):
        if ans < index_Z[j] - index_A[i]:
            ans = index_Z[j] - index_A[i]
            
print(ans+1)


### FIXED CODE ###

S = input()

index_A = []
index_Z = []
for i in range(len(S)):
    if S[i] == "A" and len(index_A) == 0:
        index_A.append(i+1)
    if S[i] == "Z":
        index_Z.append(i+1)
            
print(max(index_Z) - index_A[0] + 1)
### BUGGY CODE ###

n=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s

def bitadd(BIT,i,x):
  while i<=2**n:
    BIT[i]+=x
    i+=i&(-i)
  return BIT
nn=2**n
ans=float("inf")
for i in range(nn):
  E,O=[],[]
  for j in range(n):
    if i&(1<<j)==0:
      if j%2==0:
        E.append(A[j]*100+j)
      else:
        O.append(A[j]*100+j)
    else:
      if j%2==0:
        O.append(B[j]*100+j)
      else:
        E.append(B[j]*100+j)
  if len(E)!=(n+1)//2:
    continue
  else:
    E.sort()
    O.sort()

    chk=True
    C=[E[0]]
    for i in range(1,n):
      if i%2==0:
        C.append(E[i//2])
      else:
        C.append(O[i//2])
      if C[-1]//100<C[-2]//100:
          chk=False
          break
    
  if chk:
    ct=0
    BIT=[0]*nn
    BIT.insert(0,0)
    for i1 in range(n):
      c=(C[i1]%100)+1
      ct+=i1-bitsum(BIT,c)
      bitadd(BIT,c,1)


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



### FIXED CODE ###

import itertools
n=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s

def bitadd(BIT,i,x):
  while i<=64:
    BIT[i]+=x
    i+=i&(-i)
  return BIT

def tentou(X):
  ret=0
  BIT=[0]*64
  BIT.insert(0,0)
  for i1 in range(n):
    x=X[i1]+1
    ret+=i1-bitsum(BIT,x)
    bitadd(BIT,x,1)
  return ret
N=[int(i) for i in range(n)]
nn=2**n
ans=float("inf")
for _ in range(n//2+1):
  for com in itertools.combinations(N,2*_):
    i=0
    for ura in com:
      i+=2**ura
    E,O=[],[]
    for j in range(n):
      if i&(1<<j)==0:
        if j%2==0:
          E.append(A[j]*100+j)
        else:
          O.append(A[j]*100+j)
      else:
        if j%2==0:
          O.append(B[j]*100+j)
        else:
          E.append(B[j]*100+j)
    if len(E)!=(n+1)//2:
      continue
    else:
      E.sort()
      O.sort()

      chk=True
      C=[E[0]%100]
      prev=E[0]//100
      for i in range(1,n):
        ii=i//2
        if i%2==0:
          C.append(E[ii]%100)
          if E[ii]//100<prev:
            chk=False
            break
          else:
            prev=E[ii]//100
        else:
          C.append(O[ii]%100)
          if O[ii]//100<prev:
            chk=False
            break
          else:
            prev=O[ii]//100
    
    if chk:
      ans=min(ans,tentou(C))
print(-1 if ans==float("inf") else ans)
### BUGGY CODE ###

from operator import mul
from functools import reduce
def cmb(n,r):
  r = min(n-r,r)
  if r == 0:
    return 1
  over = reduce(mul, range(n, n - r, -1))
  under = reduce(mul, range(1,r + 1))
  return over // under
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
mn = 0
mx = 0
for i in range(n-k+1):
  mn = (mn + a[i]*cmb(n-i-1,k-1))%(10**9+7)
a.reverse() 
for i in range(n-k+1):
  mx = (mx + a[i]*cmb(n-i-1,k-1))%(10**9+7)
print((mx-mn)%(10**9+7))

### FIXED CODE ###

from operator import mul
from functools import reduce
n,k = map(int,input().split())
a = list(map(int,input().split()))
m = 10**9+7
a.sort()
mn = 0
mx = 0
x = 1
if k == 1:
  print(0)
  exit()
def extgcd(a,b):
  r = [1,0,a]
  w = [0,1,b]
  while w[2]!=1:
    q = r[2]//w[2]
    r2 = w
    w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
    r = r2
    w = w2
  return [w[0],w[1]]
def mod_inv(a,m):
  x = extgcd(a,m)[0]
  return (m+x%m)%m
gy = 1
for i in range(1,k):
    gy = gy*mod_inv(i,m)%m
for i in range(n-k+1,n):
  x= x*i
for i in range(n-k+1):
  mn = (mn + a[i]*x)%m
  mx = (mx + a[n-i-1]*x)%m
  x = (mod_inv(n-i-1,m)*x*(n-i-k))%m
print(((mx-mn)*gy)%m)
### BUGGY CODE ###

S = input()
Q = int(input())
head = 1

for _ in range(Q):
    q = input().split()
    if q[0]=='1':
        head = head*-1
    else:
        if q[1]=='1':
            h = head*1
        else:
            h = head*-1
        
        if h==1:
            S = q[2] + S
        else:
            S = S + q[2]
if head == -1:
    S = S[::-1]
print(S)

### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())
head = 1
d = deque([S])

for _ in range(Q):
    q = input().split()
    if q[0]=='1':
        head = head*-1
    else:
        if q[1]=='1':
            h = head*1
        else:
            h = head*-1
        
        if h==1:
            d.appendleft(q[2])
        else:
            d.append(q[2])
ans = "".join(list(d))
if head == -1:
    ans = ans[::-1]

print(ans)