Harryxun/stf_run huggingface dataset:
# -*- coding:utf-8 -*-

import math

def insertion_sort(num_list, length, interval):
    cnt = 0
    for i in range(interval, length):
        v = num_list[i]
        j = i - interval
        while j >= 0 and num_list[j] > v:
            num_list[j+interval] = num_list[j]
            j = j - interval
            cnt = cnt + 1
        num_list[j+interval] = v
    return cnt

def shell_sort(num_list, length):
    cnt = 0
    h = 1
    intervals = list()
    while length > h:
        intervals.append(h)
        h = 3 * h + 1
    for i in reversed(range(len(intervals))):
        cnt = cnt + insertion_sort(num_list, length, intervals[i])
    print(len(intervals))
    show_list(intervals)
    print(cnt)

def show_list(list):
    i = len(list) - 1;
    while i > 0:
        print(list[i], end=" ")
        i = i - 1
    print(list[i])

input_num = int(input())
input_list = list()
for i in range(input_num):
    input_list.append(int(input()))
shell_sort(input_list, input_num)
for num in input_list:
    print(num)

### FIXED CODE ###

def insertion_sort(A, g):
    cnt = 0
    for i in range(g, len(A)):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j -= g
            cnt += 1
        A[j+g] = v
    return cnt

def shell_sort(A):
    cnt = 0
    h = 1
    G = []
    while h <= len(A)/2:
        G.append(h)
        h = 3 * h + 1
    if len(G) == 0:
        G.append(1)
    print(len(G))
    print(*G[::-1])
    for g_i in G[::-1]:
        cnt += insertion_sort(A, g_i)
    return cnt

if __name__ == '__main__':
    n = int(input())
    A = []
    for i in range(n):
        A.append(int(input()))

    print(shell_sort(A))
    for a in A:
        print(a)
N = int(input())						# 5
#a = [int(i) for i in input().split()]	# 1 2 3 4 5 ...
s = "0 " + input()
a = [int(i) for i in s.split()]	# 1 2 3 4 5 ...

N = len(a)
#print(a)

ans = 0
bSkip = False

for i in range(N):
	if i==0: continue;
	if bSkip:
		bSkip = False
		continue;
#	print(i, a[i])
	
	if i==a[i]:
		ans += 1
		if(i+1)==a[i+1]:
			bSkip = True

print(ans)


### FIXED CODE ###

N = int(input())						# 5

s = "0 " + input()
a = [int(i) for i in s.split()]	# 1 2 3 4 5 ...


ans = 0
bSkip = False

for i in range(N+1):
	if i==0: continue;
	if bSkip:
		bSkip = False
		continue;
#	print(i, a[i])
	
	if i==a[i]:
		ans += 1
		if(i<N):
			if(i+1)==a[i+1]:
				bSkip = True

print(ans)
n, k = map(int, input().split())
p = list(map(int, input().split()))

p.sort(reverse=True)

i = 0
while i < k:
  i += p[i]
  i ++
  
print(i)

### FIXED CODE ###

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

i = 0
price = 0
while i < k:
  price += p[i]
  i += 1
 
print(price)
n = input()
for i in range(0, n):
    a,b,c = map(int, input().split())
    if a*a+b*b==c*c or a*a+c*c==b*b or b*b+c*c==a*a:
        print("YES")
    else:
        print("NO")

### FIXED CODE ###

n = int(input())
for i in range(0, n):
    a,b,c = map(int, input().split())
    if a*a+b*b==c*c or a*a+c*c==b*b or b*b+c*c==a*a:
        print("YES")
    else:
        print("NO")
x = in(input())
print(**3)


### FIXED CODE ###

x = int(input())
print(x**3)
s=str("As=str("ACL")
n=int(input())
print(s*n)

### FIXED CODE ###

s=str("ACL")
n=int(input())
print(s*n)
n = [int(input()) for i in range(1,5)]

x = min(n[1], n[2])+ min(n[3], n[4])

print(x)


### FIXED CODE ###

l = [int(input()) for i in range(1, 5)]
print(min(l[0], l[1]) + min(l[2], l[3]))
from collections import deque

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

def intinp():
    return int(input())


N, M = mapint_inp()
ABs = [list(mapint_inp()) for _ in range(N)]

adjacency_matrix = [[]*(N+1) for _ in range(N+1)]

for AB in ABs:
    A, B = AB
    # 隣接しているA,Bに関して、
    # A番目のリストに値Bを、B番目のリストに値Aを追加して
    # 隣接を管理する
    adjacency_matrix[A].append(B)
    adjacency_matrix[B].append(A)

result = [0]*(N+1)

q = deque([1])
while q:
    now = q.popleft()
    for i in adjacency_matrix[now]:
        if result[i] == 0:
            result[i] == now
            q.append(i)

print("Yes")
print('\n'.join(str(i) for i in result[2:]))

### FIXED CODE ###

from collections import deque

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

def intinp():
    return int(input())


n, m = mapint_inp()
graph = [[] for _ in range(n)]
ans = [0]*n

for _ in range(m):
    a, b = mapint_inp()
    a -= 1; b -= 1
    graph[a].append(b)
    graph[b].append(a) 

q = deque([0])
visited = [False]*n
visited[0] = True
while q:
    now = q.popleft()
    for i in graph[now]:
        if visited[i]: continue
        visited[i] = True
        ans[i] = now
        q.append(i)

print("Yes")
for i in range(1, n):
    print(ans[i]+1)
import numpy as np
from collections import deque
infinity = 10**5
H,W = map(int,input().split())

A = np.zeros((H+1,W+1))

for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == ".":
            A[i][j] = 1
        else:
            A[i][j] = -1

N = H*W
G=[[] for i in range(N)]

for i in range(H):
    for j in range(W):
        if A[i+1][j] == 1:
            G[W*(i+1)+j].append(W*i+j)
            #G[W*i+j].append(W*(i+1)+j)

        if i>=1:
            if A[i-1][j] == 1:
                G[W*(i-1)+j].append(W*i+j)
                #G[W*i+j].append(W*(i-1)+j)            
            
        
        if A[i][j+1] == 1:
            G[W*i+(j+1)].append(W*i+j)
            #G[W*i+j].append(W*i+(j+1))
        
        if j>=1:
            if A[i][j-1] == 1:
                G[W*i+(j-1)].append(W*i+j)
                #G[W*i+j].append(W*i+(j-1))

def BFS (s):
    queue = deque()
    d = [infinity]*N
    
    queue.append(s)
    d[s]= 0
    
    while len(queue)!=0:
      u = queue.popleft()
      for v in G[u]:
      	if d[v] == infinity:
        	d[v] = d[u]+1
        	queue.append(v) 	  
  
    return d

ans = 0
#print(G)
for i in range(N):
    #print(i)
   
    I = i//W
    J = i%W
    #print(I,J)
    if A[I][J] == 1:
        d = BFS(i)
        for k in range(N):
            if d[k] == infinity:
                d[k] = -1
        ans = max(ans,max(d))

print(ans)

### FIXED CODE ###

import numpy as np
from collections import deque
infinity = 10**5
H,W = map(int,input().split())

A = np.zeros((H+1,W+1))

for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == ".":
            A[i][j] = 1
        else:
            A[i][j] = -1
#print(A)
N = H*W
G=[[] for i in range(N)]

for i in range(H):
    for j in range(W):
        if A[i+1][j] == 1:
            #if W*(i+1)+j ==1:
                #print("a")
            #G[W*(i+1)+j].append(W*i+j)
            G[W*i+j].append(W*(i+1)+j)

        if i>=1:
            if A[i-1][j] == 1:
                #if W*(i-1)+j ==1:
                    #print("b")
                #G[W*(i-1)+j].append(W*i+j)
                G[W*i+j].append(W*(i-1)+j)            
            
        
        if A[i][j+1] == 1:
            #if W* ==1:
                #print("c")
            #G[W*i+(j+1)].append(W*i+j)
            G[W*i+j].append(W*i+(j+1))
        
        if j>=1:
            if A[i][j-1] == 1:
                #if W*(i+1)+j ==1:
                    #print("d")
                #G[W*i+(j-1)].append(W*i+j)
                G[W*i+j].append(W*i+(j-1))

def BFS (s):
    queue = deque()
    d = [infinity]*N
    
    queue.append(s)
    d[s]= 0
    
    while len(queue)!=0:
      u = queue.popleft()
      for v in G[u]:
      	if d[v] == infinity:
        	d[v] = d[u]+1
        	queue.append(v) 	  
  
    return d

ans = 0

#print(G)

for i in range(N):
    #print(i)
    I = i//W
    J = i%W
    #print(I,J)
    if A[I][J] == 1:
        d = BFS(i)
        for k in range(N):
            if d[k] == infinity:
                d[k] = -1
        ans = max(ans,max(d))

print(ans)
from typing import List


def lunlun_maker(l: List[int]) -> List[int]:
    next_lunluns = []
    for e in l:
        nxt = e * 10
        mod = e % 10
        if 0 < mod < 9:
            next_lunluns.extend([nxt + mod - 1, nxt + mod, nxt + mod + 1])
        elif mod == 0:
            next_lunluns.extend([nxt, nxt + 1])
        elif mod == 9:
            next_lunluns.extend([nxt + 8, nxt + 9])
    return next_lunluns


def get_lunlun(num: int) -> int:
    lunluns = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    counter = len(lunluns)
    counter_tmp = counter
    while counter < num:
        lunluns = lunlun_maker(lunluns)
        counter_tmp = counter
        counter += len(lunluns)
    return lunluns[num - counter_tmp - 1]


K = int(input())
print(get_lunlun(K))

### FIXED CODE ###

def lunlun_maker(l: int) -> int:
    next_lunluns = []
    for e in l:
        nxt = e * 10
        mod = e % 10
        if 0 < mod < 9:
            next_lunluns.extend([nxt + mod - 1, nxt + mod, nxt + mod + 1])
        elif mod == 0:
            next_lunluns.extend([nxt, nxt + 1])
        elif mod == 9:
            next_lunluns.extend([nxt + 8, nxt + 9])
    return next_lunluns


def get_lunlun(num: int) -> int:
    lunluns = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    counter = len(lunluns)
    counter_tmp = counter
    while counter < num:
        lunluns = lunlun_maker(lunluns)
        counter_tmp = counter
        counter += len(lunluns)
    return lunluns[num - counter_tmp - 1]


K = int(input())
print(get_lunlun(K))
from collections import Counter
 
N = int(input())
A = list(map(int, input().split()))
 
C = Counter(A)
 
ans = 0
for i in range(max(A)+1):
    ans = max(C[i] + C[i-1] + C[i+1], ans)
 
print(ans)
from collections import Counter

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

C = Counter(A)

ans = 0
for i in range(max(A)+1):
    ans = max(C[i] + C[i-1] + C[i+1], ans)

print(ans)


### FIXED CODE ###

from collections import Counter
 
N = int(input())
A = list(map(int, input().split()))
 
C = Counter(A)
 
ans = 0
for i in range(max(A)+1):
    ans = max(C[i] + C[i-1] + C[i+1], ans)
 
print(ans)
N = list(input)
for i in range(len(N)):
  if N[i] in'ACGT':
    N[i] += 1
    N[i+1] = N[i]
print(max(N))

### FIXED CODE ###

N = list(input())
dp = [0]*(len(N)+1)
for i in range(len(N)):
  if N[i] in'ACGT':
    dp[i] += 1
    dp[i+1] = dp[i]
  else:
    dp[i] = 0
print(max(dp))
import sys
sys.setrecursionlimit(10**9)

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

goal_cnt = [10**20]
def dfs(x, y, cnt):
    if cnt >= goal_cnt[0]:
        return
    if field[x][y] == "#":
        cnt += 1
    if x == W-1 and y == H-1:
        goal_cnt[0] = min(goal_cnt[0], cnt)
        return
    for nx, ny in ((1,0),(0,1)):
        nx += x
        ny += y
        if nx >= W or ny >= H:
            continue
        dfs(nx, ny, cnt)

dfs(0,0,0)
print(goal_cnt[0])


### FIXED CODE ###

H, W = map(int, input().split())
#field = [list(input()) for _ in range(H)]
field =[["."] * (W+1)]
for _ in range(H):
    tmp = ["."]
    tmp.extend(list(input()))
    field.append(tmp)

dp = [[10**9] * (W+1) for _ in range(H+1)]
dp[1][0] = 0
dp[0][1] = 0
for h in range(1,H+1):
    for w in range(1,W+1):
        if field[h][w] == ".":
            dp[h][w] = min(dp[h-1][w], dp[h][w-1])
        else:
            u = dp[h-1][w] if field[h-1][w] == "#" else dp[h-1][w] + 1
            l = dp[h][w-1] if field[h][w-1] == "#" else dp[h][w-1] + 1
            dp[h][w] = min(u,l)

print(dp[-1][-1])
print(sum(list(map(int,input().split))))

### FIXED CODE ###

while True:
    try:
        print(sum(list(map(int,input().split()))))
    except:
        break
from collections import deque
from itertools import chain, combinations
import json
from typing import List




def main():
    a = "abcdefghijklmnopqrstuvwxyz"
    c=input()
    print(a[a.index(c)+1])

    # N = int(input())
    # A = [int(a) for a in input().split()]
    # B = [
    #     [int(a) for a in input().split()]
    #     for _ in range(N)
    # ]
    print()


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque
from itertools import chain, combinations
import json




def main():
    a = "abcdefghijklmnopqrstuvwxyz"
    c=input()
    print(a[a.index(c)+1])

    # N = int(input())
    # A = [int(a) for a in input().split()]
    # B = [
    #     [int(a) for a in input().split()]
    #     for _ in range(N)
    # ]
    print()


if __name__ == "__main__":
    main()
import numpy as np
s = input()
n = len(s)
chid = np.ones(n)
x = np.zeros((n,n))
for i in range(n):
    if s[i] == 'R':
        x[i][i+1] = 1
    else:
        x[i][i-1] = 1
        
x = np.linalg.matrix_power(x,10*100)
print(' '.join(map(str,map(int, np.dot(chid,x)))))

### FIXED CODE ###


S = input()
n = len(S)
ans = [0 for i in range(n)]
for i in range(n):
    if S[i:i+2] == "RL":
        for j in range(i,-1,-1):
            if S[j] == "R":
                ans[i + (i-j) % 2] += 1
            else:
                break
        for j in range(i+1,n):
            if S[j] == "L":
                ans[i + (j-i) % 2] += 1
            else:
                break

print(*ans)
N, M = map(int, input().split())
S = input()
T = input()
# def gcd(a, b):
#     if a < b:
#         return gcd(b, a)
#     else:
#         return a if b == 0 else gcd(b, a % b)

import fractions
def lcm(a, b):
    return a * b // fractions.gcd(b, a % b)


L = lcm(N, M)

r = ["*" for i in range(L)]
f = False

s_step = L // N
t_step = L // M
sL = lcm(s_step, t_step)
s = 0
t = 0

for i in range(0, L, sL):
    if i == 0:
        if S[i] == T[i]:
            continue
        else:
            f = True
            break
    else:
        s = i // s_step
        t = i // t_step
        if s > N - 1:
            break
        if t > M - 1:
            break
        if S[s] == T[t]:
            continue
        else:
            f = True
            break

if f:
    print(-1)
else:
    print(L)
N, M = map(int, input().split())
S = input()
T = input()


def gcd(a, b):
    if a < b:
        return gcd(b, a)
    else:
        return a if b == 0 else gcd(b, a % b)


def lcm(a, b):
    return a * b // gcd(b, a % b)


L = lcm(N, M)

f = False

s_step = L // N
t_step = L // M
sL = lcm(s_step, t_step)
s = 0
t = 0

for i in range(0, L, sL):
    if i == 0:
        if S[i] == T[i]:
            continue
        else:
            f = True
            break
    else:
        s = i // s_step
        t = i // t_step
        if s > N - 1:
            break
        if t > M - 1:
            break
        if S[s] == T[t]:
            continue
        else:
            f = True
            break

if f:
    print(-1)
else:
    print(L)


### FIXED CODE ###

N, M = map(int, input().split())
S = input()
T = input()
# def gcd(a, b):
#     if a < b:
#         return gcd(b, a)
#     else:
#         return a if b == 0 else gcd(b, a % b)

import fractions
def lcm(a, b):
    return a * b // fractions.gcd(b, a % b)


L = lcm(N, M)

f = False

s_step = L // N
t_step = L // M
sL = lcm(s_step, t_step)
s = 0
t = 0

for i in range(0, L, sL):
    if i == 0:
        if S[i] == T[i]:
            continue
        else:
            f = True
            break
    else:
        s = i // s_step
        t = i // t_step
        if s > N - 1:
            break
        if t > M - 1:
            break
        if S[s] == T[t]:
            continue
        else:
            f = True
            break

if f:
    print(-1)
else:
    print(L)
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.append(k+1)
b.append(k+1)
ia = 0
ib = 0
count = 0

for i in range(n + m + 1):
    if (a[ia] < b[ib]):
        if(a[ia] > k):
            print(count)
            break
        else:
            k -= a[ia]
            ia += 1
            count += 1
    else:
        if(b[ib] > k):
            print(count)
            break
        else:
            k -= b[ib]
            ib += 1
            count += 1

### FIXED CODE ###

a = int(input())
ans = a * (1 + a + a * a)
print(ans)
N,A=map(int, input().split())
x=[int(x) for x in input().split()]
sort(x)
W=sum(x)
dp=[[[0]*(W+1) for _ in range(N+1)] for _ in range(N+1)]
for j in range(N+1):
    dp[j][0][0]=1
for j in range(1,N+1):
    xj=x[j-1]
    for k in range(1, N+1):
        for s in range(1, W+1):
            if s<xj:
                dp[j][k][s]=dp[j-1][k][s]
            else:
                dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-xj]

ans=0
for k in range(1,N+1):
    if k*A<=W:
        ans+=dp[N][k][k*A]
print(ans)


### FIXED CODE ###

import sys
from sys import stdin
input = stdin.readline

def solve(N, A, x):
    W=sum(x)
    dp=[[[0]*(W+1) for _ in range(N+1)] for _ in range(N+1)]
    for j in range(N+1):
        dp[j][0][0]=1
    for j in range(1,N+1):
        xj=x[j-1]
        for k in range(1, N+1):
            for s in range(1, W+1):
                if s<xj:
                    dp[j][k][s]=dp[j-1][k][s]
                else:
                    dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-xj]

    ans=0
    for k in range(1,N+1):
        if k*A<=W:
            ans+=dp[N][k][k*A]
        else:
            break
    return ans


def main(args):
    N,A=map(int, input().split())
    x=[int(x) for x in input().split()]
    ans=solve(N,A,x)
    print(ans)

if __name__ == '__main__':
    main(sys.argv[1:])
import numpy as np
N = map(int, raw_input().split())
a = np.array( [] )
a = np.append(a,map(int, raw_input().split()))

prod = a.prod()
out  = 0

while prod%2 == 0:
    prod = prod/2
    out = out +1

print out

### FIXED CODE ###

N = map(int, raw_input().split())
a = map(int, raw_input().split())

out  = 0
for i in range(N[0]):
    while a[i]%2 == 0:
        a[i] = a[i]/2
        out = out +1
print out
while 1:
    a, b = map(int, input().split())
    print(len(str(a+b)))


### FIXED CODE ###

while 1:
    try:
        print(len(str(sum(map(int, input().split())))))
    except:
        break
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,m = map(int,readline().split())
ab = [tuple(map(int,readline().split())) for _ in range(n)]
lr = [tuple(map(int,readline().split())) for _ in range(m)]

ab.sort()
a = []
b = []
for i,j in ab:
    a.append(i)
    b.append(j)

from bisect import *
g = [[] for _ in range(n+1)]
lidx = []
ridx = []
for i in range(m):
    l,r = lr[i]
    li = bisect_left(a,l)
    ri = bisect_right(a,r)
    if li != ri:
        lidx.append(li)
        ridx.append(ri)
        g[li].append((ri,i+1))
        g[ri].append((li,i+1))


b.append(0)
for i in range(n-1,-1,-1):
    b[i+1] ^= b[i]

#print(b)
# imos したので、lidx に +1, ridx に -1 と同じ
q = [0]
parent = [-1]*(n+1)
edge_idx = [-1]*(n+1)
order = []
for i in range(n):
    if parent[i] == -1:
        q = [i]
        while q:
            v = q.pop()
            order.append(v)
            if parent[v] == -1: parent[v] = -2
            for c,idx in g[v]:
                if parent[c] == -1:
                    parent[c] = v
                    edge_idx[c] = idx
                    q.append(c)

"""
print(g)
print(lidx)
print(ridx)
print(b,"b")
print(parent,"parent")
print(edge_idx,"e_idx")
print(order)
"""
#print(b)
ans = []    
for i in order[::-1]:
    if b[i] and parent[i] != -2:
        b[i] = 0
        b[parent[i]] ^= 1
        ans.append(edge_idx[i])
    #print(b,i)
    
#print(b)

if all(not i for i in b):
    print(len(ans))
    print(*sorted(ans))
else:
    print(-1)

assert n!=3 and m!=4




### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,m = map(int,readline().split())
ab = [tuple(map(int,readline().split())) for _ in range(n)]
lr = [tuple(map(int,readline().split())) for _ in range(m)]

ab.sort()
a = []
b = []
for i,j in ab:
    a.append(i)
    b.append(j)

from bisect import *
g = [[] for _ in range(n+1)]
lidx = []
ridx = []
for i in range(m):
    l,r = lr[i]
    li = bisect_left(a,l)
    ri = bisect_right(a,r)
    if li != ri:
        lidx.append(li)
        ridx.append(ri)
        g[li].append((ri,i+1))
        g[ri].append((li,i+1))


b.append(0)
for i in range(n-1,-1,-1):
    b[i+1] ^= b[i]

#print(b)
# imos したので、lidx に +1, ridx に -1 と同じ
q = [0]
parent = [-1]*(n+1)
edge_idx = [-1]*(n+1)
order = []
for i in range(n,-1,-1):
    if parent[i] == -1:
        q = [i]
        while q:
            v = q.pop()
            order.append(v)
            if parent[v] == -1: parent[v] = -2
            for c,idx in g[v]:
                if parent[c] == -1:
                    parent[c] = v
                    edge_idx[c] = idx
                    q.append(c)

"""
print(g)
print(lidx)
print(ridx)
print(b,"b")
print(parent,"parent")
print(edge_idx,"e_idx")
print(order)
"""

ans = []    
for i in order[::-1]:
    if b[i] and parent[i] != -2:
        b[i] = 0
        b[parent[i]] ^= 1
        ans.append(edge_idx[i])
    #print(b,i)
    
#print(b)

if all(not i for i in b[:-1]):
    print(len(ans))
    print(*sorted(ans))
else:
    print(-1)
@memoize
def fac(x):
  if x==0:
    return 1
  else:
    return x*fac(x-1)

N=int(input())
ans=fac(N)%(10**9+7)
print(ans)




### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    l = [0 for _ in range(N)]
    is_prime = [True for _ in range(N+1)]
    is_prime[0],is_prime[1] = False,False
    INF = 10**9+7
    
    for i in range(N+1):
        if is_prime[i]:
            for j in range(2*i,N+1,i):
                is_prime[j] = False

    fa = [0 for _ in range(N+1)]                
    for x in range(1,N+1):
        for i in range(1,x+1):
            if (is_prime[i] and x%i == 0):
                while x%i == 0:
                    fa[i] += 1
                    x //= i
 
    ans = 1
    for i in range(N+1):
        ans *= fa[i]+1
        ans %= INF
        
    print(ans)
    
if __name__ == "__main__":
    main()
l,n=map(int,input().split())
list=[]
for _ in range(n):
    list.append(str(input()))

list.sort()
ans=""
for i in list:
    ans+=i
print(ans)

### FIXED CODE ###

n,l=map(int,input().split())
list=[]
for _ in range(n):
    list.append(input())
 
list.sort()
ans=""
for i in list:
    ans+=i
print(ans)
#include<bits/stdc++.h>
using namespace std;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	uint64_t sum=0;
	map<int,int>mapper;
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		int temp;
		cin>>temp;
		if(mapper.find(temp)==mapper.end()){
			mapper[temp]=0;
		}
		mapper[temp]++;
		sum+=temp;
	}
	int q;
	cin>>q;
	for(int i=0;i<q;i++){
		int temp,temp1;
		cin>>temp>>temp1;
		if(mapper.find(temp1)==mapper.end()){
			sum-=temp*mapper[temp];
			sum+=temp1*mapper[temp];
			mapper[temp1]=mapper[temp];
			mapper.erase(temp);
		}else{
			sum-=temp*mapper[temp];
			sum+=temp1*mapper[temp];
			int val=mapper[temp];
			mapper.erase(temp);
			mapper[temp1]=mapper[temp1]+val;
		}
		cout<<sum<<"\n";
	}
}


### FIXED CODE ###

summ=0
mapper=dict()
n=int(input())
arr=[int(i) for i in input().split()]
for i in range(0,n):
    temp=arr[i]
    if temp not in mapper:
        mapper[temp]=0
    mapper[temp]+=1
    summ+=temp
q=int(input())
for i in range(0,q):
    temp,temp1=[int(j) for j in input().split()]
    if((temp in mapper) and  temp1 not in mapper):
        summ-=temp*mapper[temp]
        summ+=temp1*mapper[temp]
        mapper[temp1]=0
        mapper[temp1]+=mapper[temp]
        mapper.pop(temp)
    elif((temp in mapper) and (temp1 in mapper)):
        summ-=temp*mapper[temp]
        summ+=temp1*mapper[temp]
        val=mapper[temp]
        mapper.pop(temp)
        mapper[temp1]=mapper[temp1]+val
    print(summ)
l = list(map(int,input().split()))
p = list[0]
q = list[1]
r = list[2]
print(min([p+q,q+r,r+p]))


### FIXED CODE ###

l = list(map(int,input().split()))
p = l[0]
q = l[1]
r = l[2]
print(min(p+q,q+r,r+p))
N = int(input())
h_vals = input().split(' ')
hmax = -1
count = 0
for h in h_vals:
  if hmax <= h
  	hmax = h
  	count+=1
print(count)

### FIXED CODE ###

N = int(input())
h_vals = input().split(' ')
h_vals = [int(h) for h in h_vals]
hmax = -1
count = 0
for h in h_vals:
  if hmax <= h:
  	hmax = h
  	count+=1
print(count)
n = int(input())
L = list(map(int,input().split()))
L = [x for x in L if x%2 ==0]
for i in range(len(L)):
    if L[i]%3 == 0 or L[i]%5== 0:
        flag = True
    else:
        flag =False
        break
#print(L)
if flag:
    print("APPROVED")
else:
    print("DENIED")

### FIXED CODE ###

n = int(input())
L = list(map(int,input().split()))
L = [x for x in L if x%2 ==0]

if all((L[i]%3 == 0 or L[i]%5 == 0 for i in range(len(L)))):

    print("APPROVED")
else:
    print("DENIED")