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

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

for i in range(q):
  temp = query[i].split()
  if int(temp[0]) == 1:
    s = ''.join(list(reversed(s)))
#    s = s[::-1]
  else:
    if int(temp[1]) == 1:
      s = '{}{}'.format(temp[2], s)
    else:
      s = '{}{}'.format(s, temp[2])

print(s)


### FIXED CODE ###

from collections import deque

def main():
  rev = False
  s = deque(input())
  q = int(input())
  query = tuple(input() for i in range(q))

  for i in range(q):
    temp = query[i].split()
    if int(temp[0]) == 1:
      rev = not rev
    else:
      if (int(temp[1]) == 1 and (not rev)) or (int(temp[1]) == 2 and rev):
        s.appendleft(temp[2])
      else:
        s.append(temp[2])

  if rev:
    s.reverse()

  print(''.join(s))

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


def main():
    L = input()
    n = len(L)
    t = []
    mod = 10 ** 9 + 7
    for i, v in enumerate(L):
        if v == '1':
            t.append(i)
    r = 1
    for i in reversed(t):
        r *= 2
        r += 3 ** (n - i - 1)
        r %= mod
    print(r % mod)
main()


### FIXED CODE ###


def main():
    L = input()
    n = len(L)
    t = []
    mod = 10 ** 9 + 7
    for i, v in enumerate(L):
        if v == '1':
            t.append(i)
    r = 1
    p = 1
    for i, v in enumerate(reversed(L)):
        p %= mod
        if v == '1':
            r *= 2
            r += p
            r %= mod
        p *= 3
    print(r % mod)
main()
### BUGGY CODE ###

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

B = []

rev = False

for i in range(N):
  if rev:
    B = [A[i]] + B
  else:
    B = B + [A[i]]
  rev ^= True
  
if rev:
  B = B[::-1]
    
print(*B)


### FIXED CODE ###

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

from collections import deque

q = deque([])

for i in range(N):
  if i % 2:
    q.appendleft(A[i])
  else:
    q.append(A[i])
    
if N % 2:
  q = list(q)[::-1]
  
print(*q)
### BUGGY CODE ###

import math

Q = int(input())
sosu = set([2])

for L in range(3, 10**5, 2): # 2 以外の素数は奇数なので
    for L2 in sosu:
        if L % L2 == 0:
            break # 素数でないことがわかったらそれ以上ループする必要はない
    else: # break で抜けることがなかったら L は素数（Python 特有の制御構文）
        sosu.add(L)


li = []
for i in range(Q):
    l, r = map(int, input().split())
    li.append((l, r))

for l,r in li:
    ans = 0
    for x in range(l, r+1):
        if x % 2 == 1:
            if x in sosu and (x+1)/2 in sosu:
                ans += 1
    print(ans)

### FIXED CODE ###

import math

Q = int(input())
sosu = [2]

for L in range(3, 10**5, 2): # 2 以外の素数は奇数なので
    for L2 in sosu:
        if L % L2 == 0:
            break # 素数でないことがわかったらそれ以上ループする必要はない
    else: # break で抜けることがなかったら L は素数（Python 特有の制御構文）
        sosu.append(L)

sosu = set(sosu)

d = {0:0}
now = 0
for x in range(1, 10**5+1):
    if x % 2 == 1:
        if x in sosu and (x+1)/2 in sosu:
            now += 1
    d[x] = now

li = []
for i in range(Q):
    l, r = map(int, input().split())
    li.append((l, r))

for l,r in li:
    ans = 0
    print(d[r]-d[l-1])
### BUGGY CODE ###

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

from queue import deque

def main():
  h, w = map(int, input().split())
  grids = [False] * (w * h)
  dq = deque()
  for i in range(h):
    for j, c in enumerate(list(input().strip())):
      if c == '#':
        grids[i*w + j] = True
        dq.append((0, i, j))
  
  while dq:
    cnt, i, j = dq.popleft()
    for dx, dy in zip([-1, 0, 1, 0], [0, -1, 0, 1]):
      if 0 <= i+dx < h and 0 <= j+dy < w and not grids[(i+dx)*w + (j+dy)]:
        grids[(i+dx)*w + (j+dy)] = True
        dq.append((cnt+1, i+dx, j+dy))
  print(cnt)
  
if __name__=='__main__':
  main()



### FIXED CODE ###

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

from queue import deque

def main():
  h, w = map(int, input().split())
  grids = [False] * (w * h)
  dq = deque()
  for i in range(h):
    for j, c in enumerate(list(input().strip())):
      if c == '#':
        grids[i*w + j] = True
        dq.append((0, i, j))
  
  while dq:
    cnt, i, j = dq.popleft()
    for dx, dy in zip([-1, 0, 1, 0], [0, -1, 0, 1]):
      if 0 <= i+dx < h and 0 <= j+dy < w and not grids[(i+dx)*w + (j+dy)]:
        grids[(i+dx)*w + (j+dy)] = True
        dq.append((cnt+1, i+dx, j+dy))
  print(cnt)
  
if __name__=='__main__':
  main()
### BUGGY CODE ###

s = list(input())

q = int(input())

me = 1#1:sei  -1:gyaku
for i in range(q):
    t = input().split()
    if t[0] == '1':
        me *= -1
            
    else:# 0=2
        if t[1]=='1':#1=1
            if me == 1:
                s.insert(0,t[2])
            else:
                s.append(t[2])
        else:#1=2
            if me == 1:
                s.append(t[2])
            else:
                s.insert(0,t[2])

if me == 1:
    print(''.join(s))
else:
    for i in range((len(s)-1),-1,-1):
        print(s[i],end='')

### FIXED CODE ###

from collections import deque

s = deque(input())
q = int(input())
 
me = 1#1:sei  -1:gyaku
for i in range(q):
    t = input().split()
    if t[0] == '1':
        me *= -1
            
    else:# 0=2
        if t[1]=='1':#1=1
            s.appendleft(t[2]) if me == 1 else s.append(t[2])
        else:#1=2
            s.append(t[2]) if me == 1 else s.appendleft(t[2])
s= list(s) 
if me != 1:
    s = s[::-1]
print(''.join(s))
### BUGGY CODE ###

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

product=1
for i in range(len(a)):
    product*=a[i]


mods=[]
for i in range(product):
    mods.append(sum([i%a_l for a_l in a]))

ans=max(mods)
print(ans)


### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
ans=sum(a)-N
print(ans)
### BUGGY CODE ###

def main():
    N, Q = map( int, input().split())
    C = list( map( int, input().split()))
    LRI = []
    for i in range(Q):
        l, r = map( int, input().split())
        LRI.append((r,l,i))
    LRI.sort()
    lastAppend = [-1]*(N+1)
    BIT = [0]*(N+1)
    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        if idx == 0:
            return 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= N:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    ANS = [0]*Q
    now = 1
    for r, l, i in LRI:
        while now <= r:
            c = C[now-1]
            if lastAppend[c] == -1:
                BIT_update(now, 1)
            else:
                BIT_update( now, 1)
                BIT_update(lastAppend[c],-1)
            lastAppend[c] = now                
            now += 1
        ANS[i] = BIT_query(r) - BIT_query(l-1)
    print( "\n".join( map( str, ANS)))
    
    

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, Q = map( int, input().split())
    C = list( map( int, input().split()))
    LRI = []
    for i in range(Q):
        l, r = map( int, input().split())
        LRI.append((r,l,i))
    LRI.sort(key=lambda x:x[0])
    lastAppend = [-1]*(N+1)
    BIT = [0]*(N+1)
    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        if idx == 0:
            return 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= N:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    ANS = [0]*Q
    now = 1
    for r, l, i in LRI:
        while now <= r:
            c = C[now-1]
            if lastAppend[c] == -1:
                BIT_update(now, 1)
            else:
                BIT_update( now, 1)
                BIT_update(lastAppend[c],-1)
            lastAppend[c] = now                
            now += 1
        ANS[i] = BIT_query(r) - BIT_query(l-1)
    print( "\n".join( map( str, ANS)))
    
    

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

from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
if n == 2:
    print(max(a))
    exit()
x = [a[0], gcd(a[0], a[1])]
y = [gcd(a[-2], a[-1]), a[-1]]
for i in range(1, n - 2):
    x.append(gcd(x[i], a[i + 1]))
    y.insert(0, gcd(y[0], a[-i - 2]))
x.insert(0, y[0])
y.append(x[-1])
ans = 0
for i in range(n):
    ans = max(ans, gcd(x[i], y[i]))
print(ans)


### FIXED CODE ###

from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
if n == 2:
    print(max(a))
    exit()
x = [a[0], gcd(a[0], a[1])]
for i in range(n - 3):
    x.append(gcd(x[i + 1], a[i + 2]))
ans = x[-1]
y = a[-1]
for i in range(1, n - 1):
    z = gcd(y, a[-i])
    ans = max(ans, gcd(x[-i - 1], z))
    y = z
print(max(ans, gcd(y, a[1])))
### BUGGY CODE ###

import sys
from functools import lru_cache
 
sys.setrecursionlimit(4100000)
 
@lru_cache(maxsize=None)
def f(n):
    if n == 0:
        return 0

    return f(n % bin(n).count('1')) + 1

def main():
    N = int(input())
    X = list(input())
    pc = X.count('1')
    now = 0
    for i in range(N):
        if X[i] == '1':
            now += pow(2,N-i-1)

    ac = pc + 1
    dc = pc - 1
    for i in range(N):
        cnt = 0
        if X[i] == '1' and dc:
            tmp = (now - pow(2, N-i-1, dc)) % dc
            cnt = 1 + f(tmp)
        elif X[i] == '0':
            tmp = (now + pow(2, N-i-1, ac)) % ac
            cnt = 1 + f(tmp)

        print(cnt)



if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from functools import lru_cache
 
sys.setrecursionlimit(4100000)
 
@lru_cache(maxsize=None)
def f(n):
    if n == 0:
        return 0

    return f(n % bin(n).count('1')) + 1

def main():
    N = int(input())
    X = list(input())
    pc = X.count('1')
    now = 0
    for i in range(N):
        if X[i] == '1':
            now += pow(2,N-i-1)

    ac = pc + 1
    dc = pc - 1
    ac_now = now % ac
    if dc:
        dc_now = now % dc
    for i in range(N):
        cnt = 0
        if X[i] == '1' and dc:
            tmp = (dc_now - pow(2, N-i-1, dc)) % dc
            cnt = 1 + f(tmp)
        elif X[i] == '0':
            tmp = (ac_now + pow(2, N-i-1, ac)) % ac
            cnt = 1 + f(tmp)

        print(cnt)



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

# coding: utf-8
# Your code here!
n,k = map(int,input().split())

s = input()

now = s[0]
tmp = 0

h = []
if s[0]=="0":
    h.append(0)

for i in s:
    if i != now:
        now = i
        h.append(tmp)
        tmp=0
    tmp+=1
h.append(tmp)

ans = 0

for i in range(0,max(len(h),len(h)-k),2):
    ans = max(ans,sum(h[i:i+k*2+1]))
    
print(ans)


### FIXED CODE ###

# coding: utf-8
# Your code here!

import numpy as np

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

s = input()

now = s[0]
tmp = 0

h = []
if s[0]=="0":
    h.append(0)

for i in s:
    if i != now:
        now = i
        h.append(tmp)
        tmp=0
    tmp+=1
h.append(tmp)

h = np.array(h)

ans = 0

for i in range(0,max(len(h),len(h)-k),2):
    ans = max(ans,np.sum(h[i:i+k*2+1]))
    
print(ans)
### BUGGY CODE ###

from sys import stdin

n, *a = map(int, stdin.read().split())
lengths = sorted(set(a), reverse=1)     
a.sort()

long_side, short_side = 0, 0
for l in lengths:
    c = a.count(l)
    if c != 1:
        if not long_side:
            if c >= 4:
                print(l ** 2)
                exit()
            else:
                long_side = l
        else:
            short_side = l
            break

print(long_side * short_side)

### FIXED CODE ###

from sys import stdin

n, *a = map(int, stdin.read().split())    
a.sort(reverse=1)

l_count = {}
for l in a:
    l_count.update({l: l_count.get(l, 0) + 1})
  
long_side, short_side = 0, 0
for l, c in sorted(l_count.items(), reverse=1):
    if c != 1:
        if not long_side:
            if c >= 4:
                print(l ** 2)
                exit()
            else:
                long_side = l
        else:
            short_side = l
            break

print(long_side * short_side)
### BUGGY CODE ###

import math
n=int(input())
for i in range(1,n+1):
    k=0
    j=int(math.sqrt(i))
    for x in range(1,j+1):
        for y in range(1,j+1):
            for z in range(1,j+1):
                if x**2+y**2+z**2+x*y+y*z+z*x==i:
                    k+=1
    print(k)

### FIXED CODE ###

import math
n=int(input())
j=int(math.sqrt(n))
k=[0]*n
for x in range(1,j+1):
     for y in range(1,j+1):
        for z in range(1,j+1):
            p=x**2+y**2+z**2+x*y+y*z+z*x
            if p<=n:
                k[p-1]+=1
[print(i)for i in k]
### BUGGY CODE ###

N = int(input())
li = list(map(int,input().split()))
li_ans = [0]*len(li)

for i in range(1,N+1):
    print(li.count(i))

### FIXED CODE ###

N = int(input())
li = list(map(int,input().split()))
li_ans = [0]*(len(li)+1)

for j in li:
    li_ans[j-1]+=1

for i in range(len(li_ans)):
    print(li_ans[i])
### BUGGY CODE ###

import sys
import bisect
input = sys.stdin.readline
N,M=map(int,input().split())
A=[int(i) for i in input().split()]
B=[0]*M
C=[0]*M
for i in range(M):
    B[i],C[i]=[int(x) for x in input().split()]
A.sort()
#print(A)
for i in range(M):
    index = bisect.bisect_left(A,C[i])
    #print(index)
    if index != 0:
        A[index:0] =[C[i]]*B[i]
        del A[:B[i]]
    #print(A)
print(sum(A))

### FIXED CODE ###

import sys
import bisect
import numpy as np
#input = sys.stdin.readline
N,M=map(int,input().split())
A=[int(i) for i in input().split()]
B=[0]*M
C=[0]*M
for i in range(M):
    B[i],C[i]=[int(x) for x in input().split()]
matrix = np.vstack((np.array(B),np.array(C)))
matrix = matrix[:, np.argsort(-matrix[1])]
list2=np.zeros(N)
i=0
for b,c in zip(matrix[0],matrix[1]):
    i += b
    #print(i-b,b)
    if i < N:
        list2[i-b:i] = c
        #print(list2)
    else: 
        list2[i-b:]=c
        #print(list2)
A.extend(list(list2))
A.sort()
print(int(sum(A[N:])))
### BUGGY CODE ###

#E
import math
N,K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))

A.sort(reverse=True)
F.sort()

left = 0
right = 10**12
while True:
    mid = (left+right)//2
    if right - left <= 1:
        count = 0
        for i in range(N):
            a = left//F[i]
            count+=max(0,A[i]-a)
        if count <= K:
            ans = left
        else:
            ans = right
        break
    
    
    count = 0
    for i in range(N):
        a = mid//F[i]
        count+=max(0,A[i]-a)
    #print(right,left,count)
    if count <= K:
        right = mid
    else:
        left = mid
        
        

print(ans)
        
            



### FIXED CODE ###

#E
N,K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))

A.sort(reverse=True)
F.sort()

left = 0
right = 10**12
while True:
    mid = (left+right)//2
    if right - left <= 1:
        count = 0
        for i in range(N):
            a = left//F[i]
            count+=max(0,A[i]-a)
        if count <= K:
            ans = left
        else:
            ans = right
        break
    
    
    count = 0
    for i in range(N):
        a = mid//F[i]
        count+=max(0,A[i]-a)
    if count <= K:
        right = mid
    else:
        left = mid
        
        

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

N, K = list(map(int, input().split()))
flag =False
while flag==False:
    if 2*N > K:
        N = N%K
    else:
        print(N)
        flag = True

### FIXED CODE ###

N, K = list(map(int, input().split()))
print(min(N%K, K-(N%K)))
### BUGGY CODE ###

n = int(input())

nums = map(int, input().split())

ans = 1

for num in nums:
  ans *= num
  
if ans > 10 ** 18:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

n = int(input())

MAX_NUM = 10 ** 18

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

for num in nums:
  if num == 0:
    print(0)
    exit()

ans = 1
for num in nums:
  ans *= num
  if ans > MAX_NUM:
    print(-1)
    exit()

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

MOD = (10 ** 9) + 7

f_list = [1] * 100000
f_r_list = [1] * 100000

for i in range(99999):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

def power(n, x):
	if x == 1:
		return n
	elif x % 2 == 0:
		return power(int((n * n) % MOD), int(x / 2))
	else:
		return int((n * power(n, x - 1)) % MOD)

f_r_list[-1] = power(f_list[-1], MOD - 2)

for i in range(2, 100001):
	f_r_list[-i] = int((f_r_list[-i + 1] * (100002 - i)) % MOD)

def comb(n, r):
	if n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

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

for i in range(1, n + 1):
	x = a.index(i)
	y = a_r.index(i)
	if x + y != n:
		break

num = x + y

print(n)

for i in range(2, n + 2):
	if num >= i - 1:
		print(comb(n + 1, i) - comb(num, i - 1))
	else:
		print(comb(n + 1, i))

### FIXED CODE ###

MOD = (10 ** 9) + 7

f_list = [1] * 100001
f_r_list = [1] * 100001

for i in range(100000):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

def power(n, x):
	if x == 1:
		return n
	elif x % 2 == 0:
		return power(int((n * n) % MOD), int(x / 2))
	else:
		return int((n * power(n, x - 1)) % MOD)

f_r_list[-1] = power(f_list[-1], MOD - 2)

for i in range(2, 100002):
	f_r_list[-i] = int((f_r_list[-i + 1] * (100003 - i)) % MOD)

def comb(n, r):
	if n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

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


doubled = sum(a) - n * (n + 1) / 2
x = a.index(doubled)
y = a_r.index(doubled)
num = x + y

print(n)

for i in range(2, n + 2):
	if num >= i - 1:
		print(int((comb(n + 1, i) - comb(num, i - 1)) % MOD))
	else:
		print(comb(n + 1, i))
### BUGGY CODE ###



def main():
    import sys
    input = sys.stdin.readline
    
    H,W=map(int, input().split())
    S=[]
    
    import queue
    q=queue.Queue()
    
    for i in range(H):
        S.append(list(input()))
    
    for i in range(H):
        for j in range(W):
            if S[i][j]=="#":
                q.put((i,j,0))
    
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    
    while not q.empty():
        ii,jj,d=q.get()
        for k in range(4):
            nxt_i=ii+dx[k]
            nxt_j=jj+dy[k]
            
            if 0<=nxt_i<=H-1:
                if 0<=nxt_j<=W-1:
                    if S[nxt_i][nxt_j]==".":
                        q.put((nxt_i,nxt_j,d+1))
                        S[nxt_i][nxt_j]="#"
    print(d)

                
    
            

main()


### FIXED CODE ###

from collections import deque

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

black_idx = []
for h in range(H):
    for w in range(W):
        if A[h][w] == "#":
            black_idx.append([h,w])

distance = [[float("inf")]*W for _ in range(H)]
for b in black_idx:
    distance[b[0]][b[1]] = 0

d = deque(black_idx)
ans = 0

while d:
    y, x = d.popleft()
    for new_y, new_x in ([y+1, x], [y, x+1], [y-1, x], [y, x-1]):
        if 0 <= new_y <= H-1 and 0 <= new_x <= W-1 and distance[y][x] + 1 < distance[new_y][new_x]:
            distance[new_y][new_x] = distance[y][x] + 1
            ans = max(ans, distance[y][x] + 1)
            d.append([new_y, new_x])

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

import sys
readline = sys.stdin.buffer.readline

H, W = list(map(int, readline().split()))
CH, CW = list(map(int, readline().split()))
DH, DW = list(map(int, readline().split()))
S = []
for _ in range(H):
    S.append(list(input()))

import heapq
seen = set()
queue = [(0, CH-1, CW-1)]

while queue:
    move, row, col = heapq.heappop(queue)

    if (row, col) in seen:
        continue
    # print(row, col, S[row][col], move, queue)
    if row == DH-1 and col == DW-1:
        print(move)
        sys.exit(0)

    seen.add((row, col))

    for r_offset, c_offset in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        new_row = row + r_offset
        new_col = col + c_offset
        if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
            heapq.heappush(queue, (move, new_row, new_col))


    for i in range(-2, 3):
        for j in range(-2, 3):
            new_row = row + i
            new_col = col + j

            if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
                heapq.heappush(queue, (move+1, new_row, new_col))

print(-1)


### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline

H, W = list(map(int, readline().split()))
CH, CW = list(map(int, readline().split()))
DH, DW = list(map(int, readline().split()))
S = []
for _ in range(H):
    S.append(list(input()))

# 1-index -> 0-index
CH -= 1
CW -= 1
DH -= 1
DW -= 1

from collections import deque
seen = set()
queue = deque([(0, CH, CW)])
offsets = [(-1, 0), (1, 0), (0, -1), (0, 1)]

while queue:
    move, row, col = queue.popleft()

    # print(row, col, queue)

    if (row, col) in seen:
        continue

    if row == DH and col == DW:
        print(move)
        sys.exit(0)

    seen.add((row, col))

    for r_offset, c_offset in offsets:
        new_row = row + r_offset
        new_col = col + c_offset
        if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
            queue.appendleft((move, new_row, new_col))


    for i in range(-2, 3):
        for j in range(-2, 3):
            new_row = row + i
            new_col = col + j

            if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
                queue.append((move+1, new_row, new_col))

print(-1)
### BUGGY CODE ###


a, b, c = map(int, input().split())

for i in range(a, b+1):
    if i<a+c or i>b-c:
        print(i)

### FIXED CODE ###


a, b, c = map(int, input().split())

if b - a + 1 > 2 * c:
    for i in range(a, a+c):
        print(i)
    for i in range(b-c+1, b+1):
        print(i)
else:
    for i in range(a, b+1):
        print(i)
### BUGGY CODE ###

import bisect

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

ruiseki = [0]*(n+1)
for i in range(n):
    ruiseki[i+1] = ruiseki[i] + a[i]

def solve(min_power):
    ans = 0
    for pos in range(n):
        tmp = min_power - a[pos]
        next_pos = bisect.bisect_left(a[pos:], tmp)
        times = n - pos - next_pos
        if times == n - pos:
            ans += 2 * (times - 1) + 1 
        else:
            ans += 2 * times
    if ans >= m:
        return True
    else:
        return False

ok = 0
ng = 10** 9
while abs(ok - ng) > 1:
    mid =  (ok + ng) // 2 
    if solve(mid):
        ok = mid
    else:
        ng = mid

cnt = 0
ans = 0

for pos in range(n):
    tmp = ok - a[pos]
    next_pos = bisect.bisect_left(a[pos:], tmp)
    times = n - pos - next_pos
    if times == n - pos:
        cnt += 2 * (times - 1) + 1 
        ans += 2 * (ruiseki[n] - ruiseki[n-times+1] + (times-1)*a[pos]) + 2*a[pos]
    else:
        cnt += 2 * times
        ans += 2 * (ruiseki[n] - ruiseki[n-times] + (times)*a[pos])

print(ans - (cnt-m)*ok)

### FIXED CODE ###

import bisect


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

ruiseki = [0]*(n+1)
for i in range(n):
    ruiseki[i+1] = ruiseki[i] + a[i]

def solve(min_power):
    ans = 0
    for pos in range(n):
        tmp = min_power - a[pos]
        next_pos = max(bisect.bisect_left(a, tmp), pos)
        times = n - pos - (next_pos - pos)
        if times == n - pos:
            ans += 2 * (times - 1) + 1 
        else:
            ans += 2 * times
    if ans >= m:
        return True
    else:
        return False

ok = 0
ng = 2*10**5 + 1
while abs(ok - ng) > 1:
    mid =  (ok + ng) // 2 
    if solve(mid):
        ok = mid
    else:
        ng = mid

cnt = 0
ans = 0

for pos in range(n):
    tmp = ok - a[pos]
    next_pos = max(bisect.bisect_left(a, tmp), pos)
    times = n - pos - (next_pos - pos)
    if times == n - pos:
        cnt += 2 * (times - 1) + 1 
        ans += 2 * (ruiseki[n] - ruiseki[n-times+1] + (times-1)*a[pos]) + 2*a[pos]
    else:
        cnt += 2 * times
        ans += 2 * (ruiseki[n] - ruiseki[n-times] + times*a[pos])

print(ans - (cnt-m)*ok)