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

from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:k,l,r=t=[*map(int,i().split())];x+=[t]*(l>r);y+=[[n-k,r,l]]*(l<=r)
 for x in x,y:
  x.sort();n,*h=len(x),
  while h+x:
   while[[n]]<x[-1:]:k,l,r=x.pop();heappush(h,(r-l,l,r))
   if h:s+=heappop(h)[2-(n>0)]
   n-=1
 print(s)

### FIXED CODE ###

import sys
from heapq import*
input=sys.stdin.buffer.readline
def solve():
    n=int(input())
    x,y=[],[]
    for _ in range(n):
        k,l,r=map(int,input().split())
        if l>r:
            x+=(k,l,r),
        else:
            y+=(n-k,r,l),
    x.sort()
    y.sort()
    s=0
    h=[]
    for i in range(len(x),0,-1):
        while x and x[-1][0]>=i:
            k,l,r=x.pop()
            heappush(h,(r-l,l,r))
        if h:s+=heappop(h)[1]
    s+=sum(r for _,_,r in x+h)
    h=[]
    for i in range(len(y),0,-1):
        while y and y[-1][0]>=i:
            k,l,r=y.pop()
            heappush(h,(r-l,l,r))
        if h:s+=heappop(h)[1]
    s+=sum(r for _,_,r in y+h)
    return s
t=int(input())
print('\n'.join(str(solve())for _ in range(t)))
### BUGGY CODE ###

N = input()
li = list(map(int, input().split()))
 
cnt = 0
while True:
  if 1 in map(lambda x: x % 2, li):
    break
  else:
    cnt += 1
    li = map(lambda x: x // 2, li)
print(cnt)

### FIXED CODE ###

def main():
    N = int(input())
    li = list(map(int, input().split()))

    num_of_operation = 0
    is_dividable = True

    while True:
        for num in li:
            if num % 2 != 0:
                is_dividable = False
                break

        if not is_dividable:
            break

        for i in range(N):
            li[i] //= 2
        num_of_operation += 1

    print(num_of_operation)


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

from functools import reduce
from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))

r = reduce(lambda x,y : x^y , A[2:],0)

a,b = A[:2]

def answer(ta,tb,tr):
    for i in range(ta):
        if (ta-i)^(tb+i) == tr:
            ans = i
            break
    else:
        ans = -1
    return ans

def solve(a,b,r):
    orga = a

    ans = 0
    l = max(map(lambda x : len(bin(x)), [a,b,r])) - 2
    cand = {(a,b,r):0}
    for i in range(l):
        temp = defaultdict(lambda : 10**10)
        for (a,b,r),s in cand.items():
            x,y,z = a%2,b%2,r%2
            if not x^y == z:
                continue
            else:
                if s < temp[(a//2,b//2,r//2)]:
                    temp[(a//2,b//2,r//2)] = s
                a -= 1
                b += 1
                if a < 0:
                    continue
                s += (1<<i)
                if s < temp[(a//2,b//2,r//2)]:
                    temp[(a//2,b//2,r//2)] = s
        cand = temp

    if not (0,0,0) in cand:
        ans = -1
    else:
        ans = cand[(0,0,0)]
        if ans == orga:
            ans = -1
    return ans

print(answer(a,b,r))


### FIXED CODE ###

from functools import reduce
from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))

r = reduce(lambda x,y : x^y , A[2:],0)

a,b = A[:2]

def answer(ta,tb,tr):
    for i in range(ta):
        if (ta-i)^(tb+i) == tr:
            ans = i
            break
    else:
        ans = -1
    return ans

def solve(a,b,r):
    orga = a

    ans = 0
    l = max(map(lambda x : len(bin(x)), [a,b,r])) - 2
    cand = {(a,b,r):0}
    for i in range(l):
        temp = defaultdict(lambda : 10**20)
        for (a,b,r),s in cand.items():
            x,y,z = a%2,b%2,r%2
            if not x^y == z:
                continue
            else:
                if s < temp[(a//2,b//2,r//2)]:
                    temp[(a//2,b//2,r//2)] = s
                a -= 1
                b += 1
                if a < 0:
                    continue
                s += (1<<i)
                if s < temp[(a//2,b//2,r//2)]:
                    temp[(a//2,b//2,r//2)] = s
        cand = temp

    if not (0,0,0) in cand:
        ans = -1
    else:
        ans = cand[(0,0,0)]
        if ans == orga:
            ans = -1
    return ans

print(solve(a,b,r))
### BUGGY CODE ###

#AIsing2020 d

import sys,math,collections,itertools,copy
input = sys.stdin.readline


def popcount(n):
    cou1 = 0
    while n>0:
        cou1+=n%2
        n = n//2
    return cou1

def count(nc):
    co = 0
    while nc >0:
        cou1 = popcount(nc)
        nc = nc%cou1
        co +=1
    return co

N = int(input())
X = list(input().rstrip())

for i in range(N):
    Y = copy.copy(X)
    if Y[i] == '1':
        Y[i] = '0'
    else:
        Y[i] = '1'
    s = '0b'+"".join(Y)
    a =int(s,2)
    co = count(a)
    print(co)
    


### FIXED CODE ###

#AIsing2020 d

def f(n):
        cnt = 0
        while n:
            cnt+= 1
            n = n%bin(n).count('1')
        return cnt

def main():
    N = int(input())
    X = input()
    X10 = int(X,2)
    X10_num1 = X.count('1')
    X10_pulse = X10%(X10_num1+1)
    X10_ninus = X10%(X10_num1-1) if X10_num1 >1 else 0


    for i in range(N,0,-1):
        j = N-i
        if (X[j] == '1') and X10_num1 >1:
            mod = X10_num1-1
            amari = (X10_ninus - pow(2,i-1,mod))%(mod) 
        elif (X[j] == '1') and X10_num1 ==1:
            print(0)
            continue
        else:
            mod = X10_num1+1
            amari = (X10_pulse + pow(2,i-1,mod))%(mod)

        print(1+f(amari))


main()
### BUGGY CODE ###

s = input()
x, y = map(int, input().split())
n = len(s)

D = [[], []]
st_x = 0
st_y = 0
st = 0
while st <= len(s)-1 and s[st] == "F":
    x -= 1
    st += 1

di = 0
for i in range(st, n):
    if s[i] == "T":
        di = (di+1) % 2
        D[di].append(0)
    else:
        D[di][-1] += 1

# print(D)


ANS = [0, 0]
st_po = [0, 0]
go_po = [x, y]
for i in range(2):
    mid = 8005#sum(D[i]) + 5
    DP = [[0] * (mid*2) for i in range(len(D[i]) + 1)]
    DP[0][st_po[i] + mid] = 1
    for j in range(len(D[i])):
        dd = D[i][j]
        for k in range(len(DP[0])):
            aa = 0
            bb = 0
            if 0 <= k-dd <= len(DP[0])-1:
                aa = DP[j][k-dd]
            if 0 <= k+dd <= len(DP[0])-1:
                bb = DP[j][k+dd]

            DP[j+1][k] = int(aa or bb)

    if 0 <= go_po[i]+mid <= len(DP[0])-1:
        ANS[i] = DP[-1][go_po[i]+mid]
    # print("len",mid*2)
    #if i == 1:
        # print(DP[1][7999+mid])
# print(ANS)

print("Yes" if ANS[0] and ANS[1] else "No")

### FIXED CODE ###

s = input()
x, y = map(int, input().split())
n = len(s)

D = [[], []]
st_x = 0
st_y = 0
st = 0
while st <= len(s)-1 and s[st] == "F":
    x -= 1
    st += 1

di = 0
for i in range(st, n):
    if s[i] == "T":
        di = (di+1) % 2
        D[di].append(0)
    else:
        D[di][-1] += 1

# print(D)


ANS = [0, 0]
st_po = [0, 0]
go_po = [x, y]
for i in range(2):
    mid = sum(D[i]) + 5
    DP = [[0] * (mid*2) for i in range(len(D[i]) + 1)]
    DP[0][st_po[i] + mid] = 1
    for j in range(len(D[i])):
        dd = D[i][j]
        for k in range(len(DP[0])):
            aa = 0
            bb = 0
            if 0 <= k-dd <= len(DP[0])-1:
                aa = DP[j][k-dd]
            if 0 <= k+dd <= len(DP[0])-1:
                bb = DP[j][k+dd]

            DP[j+1][k] = int(aa or bb)

    if 0 <= go_po[i]+mid <= len(DP[0])-1:
        ANS[i] = DP[-1][go_po[i]+mid]
    # print("len",mid*2)
    #if i == 1:
        # print(DP[1][7999+mid])
# print(ANS)

print("Yes" if ANS[0] and ANS[1] else "No")
### BUGGY CODE ###

L, R = map(int, input().split())

mod = 2019
ans = 10 ** 7
for low in range(L, R+1):
    for up in range(low+1, R+1):
        ans = min(ans, low * up % mod)

print(ans)


### FIXED CODE ###

L, R = map(int, input().split())

mod = 2019
ans = 10 ** 7
results = [False for _ in range(2019)]
for low in range(L, R+1):
    for up in range(low+1, R+1):
        ans = min(ans, low * up % mod)
        if ans == 0:
            print(ans)
            exit()
        # results[low * up % mod] = True
        # if all(results):
        #     print(ans)
        #     exit()
print(ans)
### BUGGY CODE ###

from collections import Counter
class Combination:
    _maxNum = 0
    _divider = 0
    _fact = []
    _inv = []
    _finv = []

    def __init__(self, maxNum, divider):
        self._maxNum = maxNum
        self._divider = divider
 
        _fact = [0] * (maxNum + 1)
        _fact[0] = _fact[1] = 1


        if divider != 0:
            _inv = [0] * (maxNum + 1)
            _finv = [0] * (maxNum + 1)
            _inv[0] = _inv[1] = _finv[0] = _finv[1] = 1
        else:
            _inv = []
            _finv = []

        for i in range(2, maxNum + 1):
            _fact[i] = _fact[i - 1] * i;
            if divider != 0:
                _fact[i] %= _divider
                _inv[i] = _divider - _inv[_divider % i] * (_divider // i) % _divider
                _finv[i] = _finv[i - 1] * _inv[i] % _divider

        self._fact = _fact
        self._inv = _inv
        self._finv = _finv

    def nPk(self, n, k):
        if(k > self._maxNum) or (n > self._maxNum) or (k > n) or (k < 0) or (n < 0):
            return 0
        return(self._fact[n] // self._fact[n - k])

    def nCk(self, n, k):
        ans = 0
        if(k > self._maxNum) or (n > self._maxNum) or (k > n) or (k < 0) or (n < 0):
            ans = 0
        elif self._divider == 0:
            ans = self.nPk(n, k)
            ans //= self._fact[k]
        else:
            ans = self._fact[n] * (self._finv[k] * self._finv[n - k] % self._divider) % self._divider

        return ans

def ABC137C_GreenBin():
    N = int(input().strip())
    S = [input().strip() for i in range(N)]

    di = Counter()
    for s in S:
        s = ''.join(sorted(list(s)))
        di[s] += 1
    
    cmb = Combination(max(di.values()), 0)

    ans = 0
    for num in di.values():
        ans += cmb.nCk(num, 2)

    print(ans)


def main():
    ABC137C_GreenBin()

if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import Counter

def ABC137C_GreenBin():
    N = int(input().strip())
    S = [input().strip() for i in range(N)]

    ans = 0
    di = Counter()
    for s in S:
        s = ''.join(sorted(list(s)))
        
        if s in di:
            ans += di[s]

        di[s] += 1
    
    print(ans)


def main():
    ABC137C_GreenBin()

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

import sys,queue,copy
sys.setrecursionlimit(10**8)
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
INF = float('inf')

N,K = inpl()

hlist = inpl()

dp = [INF]*N

for i in range(N):
    if i == 0 :
        dp[i] = 0
        continue
    for j in range(1,K+1):
        if i-j >= 0:
            dp[i] = min(dp[i-j]+abs(hlist[i]-hlist[i-j]),dp[i])

print(dp[N-1])


### FIXED CODE ###

import numpy as np
import sys
def inpl(): return list(map(int, sys.stdin.readline().split()))
INF = float('inf')

N,K = inpl()

hlist = np.array(inpl())

dp = np.full(N,INF)

dp[0]=0

for i in range(1,N):
    s = max(0,i-K)
    dp[i] = np.min(dp[s:i]+abs(hlist[i]-hlist[s:i]))

print(int(dp[N-1]))
### BUGGY CODE ###

def main():
    n = int(input())
    primelist = []
    for _ in range(n):
        x = int(input())
        if isprime(x) == 1:
            primelist.append(x)
    print(len(primelist))

def isprime(x: int):    
    yesno = 1
    for y in range(2, x):
        if gcd(x, y) != 1:
            yesno = 0
            break
    return yesno

def gcd(x, y):    
    # x > y となるように並べ替え
    if x < y:
        (x, y) = (y, x)
    return x if y == 0 else gcd(y, x%y)

if __name__ == '__main__':
    main()



### FIXED CODE ###

def main():
    A = set()
    n_prime = 0
    while True:
        try:
            x = int(input())
            A.add(x)
        except:
            break

    for x in A:
        n_prime += is_prime(x)

    print(n_prime)


def is_prime(x):  
    if x == 2:
        return 1
    elif x % 2 == 0:
        return 0
    else:
        return pow(2, x - 1, x) == 1   

main()
### BUGGY CODE ###

#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N = II()
    print(0)
    g = {'Vacant':0, 'Male':1, 'Female':2}
    sl = g[input()]
    if sl == 0:
        return
    print(N-1)
    sr = g[input()]
    if sr == 0:
        return
    l = 0
    r = N-1
    while r-l>1:

        m = (l+r)//2
        print(m)
        a = g[input()]
        if a == 0:
            return
        
        if (m-l) % 2 == 1:
            if sl == a:
                l = m
                sl = a
            else:
                r = m
                sr = a

        else:
            if a != sr:
                l = m
                sl = a
            else:
                r = m
                sr = a
        

    print(-1)


if __name__ == '__main__':
    main()

### FIXED CODE ###

#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N = II()
    g = {'Vacant':0, 'Male':1, 'Female':2}



    print(0,flush=True)
    sl = g[input()]
    if sl == 0:
        return

    print(N-1,flush=True)
    sr = g[input()]
    if sr == 0:
        return
    
    l = 0
    r = N-1
    while r-l>1:

        m = (l+r)//2
        print(m,flush=True)
        a = g[input()]
        if a == 0:
            return
        
        if (m-l) % 2 == 1:
            if sl == a:
                r = m
                sr = a
            else:
                l = m
                sl = a

        else:
            if a != sl:
                r = m
                sr = a
            else:
                l = m
                sl = a
        

    print(-1)


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

N,K,Q=map(int,input().split())
A=[K]*N

for q in range(Q):
  win=int(input())
  for i in range(N):
    if i!=win-1:
      A[i]-=1

def hantei(x):
    if x >0:
        return('Yes')
    else:
        return('No')
      
for answer in map(hantei,A):
    print(answer)

### FIXED CODE ###

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

n, k = map(int, input().split())
l = []
for i in range(n):
    a, b = map(int, input().split())
    l += [a]*b
l.sort()
print(l[k-1])

### FIXED CODE ###

n, k = map(int, input().split())
l = [0]*(10**5+10)

for i in range(n):
    a, b = map(int, input().split())
    l[a] += b

sum = 0
for i in range(len(l)):
    sum += l[i]
    if sum >= k:
        print(i)
        break
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for i in range(M)]

L = []

# cnt_sum = 0
# min_num = BC[0][1]
# for i in range(M):
#     cnt = BC[i][0]
#     for j in range(N):
#         if cnt_sum <= N:
#             L.append(BC[i][1])
#             cnt_sum += 1
#             cnt -= 1
#             if BC[i][1] < min_num:
#                 min_num = BC[i][1]
#         else:
#             if BC[i][1] < min_num:
#                 break
#             if L[j] < BC[i][1]:
#                 L[j] = BC[i][1]
#                 cnt -= 1
#         if cnt <= 0:
#             break
for i in range(M):
    # for j in range(BC[i][0]):
    #     L.append(BC[i][1])
    L.extend([BC[i][1] for j in range(BC[i][0])])
L.sort(reverse=True)
A.sort()
ans = sum(A)
LL = len(L)
for k in range(N):
    if k <= LL-1 and L[k] > A[k]:
        ans += (L[k] - A[k])
    else:
        break
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)]

L = []
BC.sort(key=lambda x:x[1], reverse=True)
A.sort()
# ans = sum(A)
ans = 0
# flag = False
cnt = 0
# for k in range(N):
#     if k <= len_L-1:
#         if flag and L[k] > A[k]:
#             ans += L[k]
#         else:
#             flag = False
#             ans += A[k]
#     else:
#         ans += A[k]
for i in range(M):
    for j in range(BC[i][0]):
        if cnt < N and A[cnt] < BC[i][1]:
            ans += BC[i][1]
            cnt += 1
        else:
            break
    else:
        continue
    break

if cnt < N:
    ans += sum(A[cnt::])

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

import array
import collections
import heapq

AdjacentVertex = collections.namedtuple("AdjacentVertex", "vertex cost")
INF = 2 ** 31 - 1
NO_VERTEX = -1


# Prim法で頂点0からの最小全域木を求める
def compute_mst_prim(max_v, adj_list):
    # pred[u]は頂点uの「ひとつ前」の頂点を表す
    pred = collections.defaultdict(lambda: NO_VERTEX)
    # uとpred[u]を結ぶ辺の重みがkey[u]に入る
    key = collections.defaultdict(lambda: INF)
    key[0] = 0
    # 二分ヒープを優先度付きキューとして用いる
    pq = [(key[v], v) for v in range(max_v)]
    heapq.heapify(pq)
    # 優先度付きキューに頂点が入っているかを示す配列
    in_pq = array.array("B", (True for _ in range(max_v)))
    while pq:
        _, u = heapq.heappop(pq)
        in_pq[u] = False
        for v, v_cost in adj_list[u]:
            if in_pq[v]:
                weight = v_cost
                if weight < key[v]:
                    pred[v] = u
                    key[v] = weight
                    heapq.heappush(pq, (weight, v))
                    in_pq[v] = True
    return (pred, key)


def main():
    n = int(input())
    z = []
    for i in range(n):  # h:高さ
        z.append([int(m) for m in input().split()] + [i])

    zx = sorted(z, key=lambda x: (x[0]))
    zy = sorted(z, key=lambda x: (x[1]))

    # 最小木問題をプリム法で解く

    # 点群を発生
    p = [[zx[i][2], zx[i + 1][2], min(abs(zx[i][0] - zx[i + 1][0]), abs(zx[i][1] - zx[i + 1][1]))] for i in range(n - 1)]
    p += [[zy[i][2], zy[i + 1][2], min(abs(zy[i][0] - zy[i + 1][0]), abs(zy[i][1] - zy[i + 1][1]))] for i in range(n - 1)]

    max_v, max_e = n, len(p)
    adjacency_list = collections.defaultdict(set)
    for i in range(max_e):
        s, t, w = p[i][0], p[i][1], p[i][2]
        adjacency_list[s].add(AdjacentVertex(t, w))
        adjacency_list[t].add(AdjacentVertex(s, w))
    (_, key) = compute_mst_prim(max_v, adjacency_list)
    print(sum(key.values()))


if __name__ == '__main__':
    main()

### FIXED CODE ###

N = int(input())

towns = []
for i in range(N):
    x, y = map(int, input().split())
    towns.append((i, x, y))

# x, y座標の値でソートして、隣接する街の間の道を、隣接リストadjに追加する
adj = [[] for i in range(N)]
for xy in [1, 2]:
    towns.sort(key=lambda t: t[xy])
    for i in range(N - 1):
        t1 = towns[i][0]
        t2 = towns[i + 1][0]
        cost = min(abs(towns[i + 1][1] - towns[i][1]), abs(towns[i + 1][2] - towns[i][2]))#towns[i + 1][xy] - towns[i][xy]
        adj[t1].append((t2, cost))
        adj[t2].append((t1, cost))

# 最小全域木を求める（プリム法）
import heapq
pq = []
heapq.heappush(pq, (0, 0))

done = set()
ans = 0
while pq:
    cost, v_now = heapq.heappop(pq)

    if v_now in done:
        continue

    ans += cost
    done.add(v_now)

    if len(done) == N:
        break

    for v, c in adj[v_now]:
        if v not in done:
            heapq.heappush(pq, (c, v))

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

L,R = list(map(int,input().split()))
lt = []
for i in range(L,R+1):
    for j in range(i+1,R+1):
        s = 0
        t = 0
        s = i % 2019 
        t = j % 2019
        ans = (s*t) % 2019
        lt.append(ans)
print(min(lt))

### FIXED CODE ###

L,R = list(map(int,input().split()))
lt = []
if R-L == 1:
    print((L*R) % 2019)
elif R-L >= 2:
    for k in range(L,R+1):
        if k % 673 == 0:
            lt.append(0)
            break
    l = L % 673
    r = R % 673
    for i in range(l,r+1):
        for j in range(i+1,r+1):
            ans = (i*j) % 2019
            lt.append(ans)
    print(min(lt))
### BUGGY CODE ###

s = input()
n = int(input())
c = 0
left_l = ['', '']
right_l = ['', '']
s_l = [s, s[::-1]]
for _ in range(n):
  lst = [i for i in input().split()]
  if lst[0] == '1':
    if c == 1:
      s_l[0], s_l[1] = s_l[1], s_l[0]
      #print(s)
    else:
      s_l = [right_l[1] + s_l[1] + left_l[1], left_l[0] + s_l[0] + right_l[0]]
      left_l = ['', '']
      right_l = ['', '']
      c = 1
      #print(s)
  elif lst[0] == '2':
    c = 0
    if lst[1] == '1':
      left_l = [lst[2] + left_l[0], left_l[1] + lst[2]]
    elif lst[1] == '2':
      right_l = [right_l[0] + lst[2], lst[2] + right_l[1]]
s = left_l[0] + s_l[0] + right_l[0]
print(s)

### FIXED CODE ###

s = input()
n = int(input())
c = 0
left_l = ['', '']
right_l = ['', '']
s_l = [s, s[::-1]]
for _ in range(n):
  lst = [i for i in input().split()]
  if lst[0] == '1':
    if c == 1:
      s_l[0], s_l[1] = s_l[1], s_l[0]
      #print(s)
    else:
      s_l = [right_l[1] + s_l[1] + left_l[1], left_l[0] + s_l[0] + right_l[0]]
      left_l[0], left_l[1] = '', ''
      right_l[0], right_l[1] = '', ''
      c = 1
      #print(s)
  elif lst[0] == '2':
    c = 0
    if lst[1] == '1':
      left_l[0] = lst[2] + left_l[0]
      left_l[1] = left_l[1] + lst[2]
    elif lst[1] == '2':
      right_l[0] = right_l[0] + lst[2]
      right_l[1] = lst[2] + right_l[1]
w = left_l[0] + s_l[0] + right_l[0]
print(w)
### BUGGY CODE ###

N=int(input())
key=1
for i in range(1,N+1):
  key*=i
print(key%1000000007)

### FIXED CODE ###

N=int(input())
key=1
for i in range(1,N+1):
  key=(key*i)%1000000007
print(key)
### BUGGY CODE ###

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

pn = list(map(lambda x: sum([i for i in range(1, x+1)]) / x, pn))

ans = sum(pn[:k])
spn = sum(pn[:k])
for i in range(1, n-k+1):    
    spn = spn - pn[i-1] + pn[i+k-1]
    ans = max(ans, spn)

print(ans)

### FIXED CODE ###

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

p = [0]*1001
for i in range(1, 1001):
    p[i] = p[i-1] + i
pn = list(map(lambda x: p[x] / x, pn))

ans = sum(pn[:k])
spn = sum(pn[:k])
for i in range(1, n-k+1):    
    spn = spn - pn[i-1] + pn[i+k-1]
    ans = max(ans, spn)

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

from queue import deque
import heapq

def countposdoc(string):
    return string.count('D') + string.count('PD')

T = input()

queue = deque([T])

res = (0, '')
#heapq.heapify(res)

while queue:
    string = queue.pop()
    if '?' not in string:
        #heapq.heappush(res, (countposdoc(string), string))
        res = max(res, (countposdoc(string), string))
    else:
        queue.append(string.replace('?', 'P', 1))
        queue.append(string.replace('?', 'D', 1))
print(res[1])

### FIXED CODE ###

T = input()

print(T.replace('?', 'D'))
### BUGGY CODE ###

while 1:
	n=input()
	n3=n**3
	if n==0:break
	mn=n3
	i=j=0
	while 1:
		i+=1
		j=i
		if n3-i**3-j**3<0:break
		while 1:
			j+=1
			m=n3-i**3-j**3
			if m<0:break
			if m<mn:mn=m
	print mn

### FIXED CODE ###

while 1:
	z3=m=input()**3
	if z3==0:break
	x=0
	while 1:
		x+=1
		x3=x**3
		y=int((z3-x3)**(1/3.))
		if y<x:break
		n=z3-x3-y**3
		if n<m:m=n
	print m
### BUGGY CODE ###

s = input()
k = int(input())
N = len(s)
subs = set()
for i in range(1, N):
    l = s[:i]
    r = s[i:]
    while not l == '':
        subs.add(l)
        l = l[1:]
    while not r == '':
        subs.add(r)
        r = r[:-1]
subs.add(s)
subs = sorted(subs)
print(subs[k-1])

### FIXED CODE ###

s = input()
k = int(input())
N = len(s)
subs = set()
for i in range(1, N):
    l = s[:i]
    r = s[i:]
    if len(l) > k:
        l = l[-k:]
    if len(r) > k:
        r = r[:k]
    while not l == '':
        subs.add(l)
        l = l[1:]
    while not r == '':
        subs.add(r)
        r = r[:-1]
subs.add(s)
subs = sorted(subs)
print(subs[k-1])