You are given a string s, consisting of lowercase English letters, and the integer m.

One should choose some symbols from the given string so that any contiguous subsegment of length m has at least one selected symbol. Note that here we choose positions of symbols, not the symbols themselves.

Then one uses the chosen symbols to form a new string. All symbols from the chosen position should be used, but we are allowed to rearrange them in any order.

Formally, we choose a subsequence of indices 1 ≤ i_1 < i_2 < ... < i_{t} ≤ |s|. The selected sequence must meet the following condition: for every j such that 1 ≤ j ≤ |s| - m + 1, there must be at least one selected index that belongs to the segment [j,  j + m - 1], i.e. there should exist a k from 1 to t, such that j ≤ i_{k} ≤ j + m - 1.

Then we take any permutation p of the selected indices and form a new string s_{i}_{p}_1s_{i}_{p}_2... s_{i}_{p}_{t}.

Find the lexicographically smallest string, that can be obtained using this procedure.


-----Input-----

The first line of the input contains a single integer m (1 ≤ m ≤ 100 000).

The second line contains the string s consisting of lowercase English letters. It is guaranteed that this string is non-empty and its length doesn't exceed 100 000. It is also guaranteed that the number m doesn't exceed the length of the string s.


-----Output-----

Print the single line containing the lexicographically smallest string, that can be obtained using the procedure described above.


-----Examples-----
Input
3
cbabc

Output
a

Input
2
abcab

Output
aab

Input
3
bcabcbaccba

Output
aaabb



-----Note-----

In the first sample, one can choose the subsequence {3} and form a string "a".

In the second sample, one can choose the subsequence {1, 2, 4} (symbols on this positions are 'a', 'b' and 'a') and rearrange the chosen symbols to form a string "aab".

Difficulty: competition

Starter code:

Solutions:
m = int(input())
s = input().strip()

sa = [0] * len(s)
for i in range(len(s)):
	sa[i] = ord(s[i]) - ord('a')

sa = [-1] + sa + [-1]

def check_value(sa, m, threshold):
	prev_ind = 0
	for i in range(len(sa)):
		if sa[i] <= threshold:
			if i - prev_ind <= m:
				prev_ind = i
			else:
				return False
	return True

def get_indexes(sa, threshold):
	seq = [i for i in range(len(sa)) if sa[i] <= threshold]
	# seq = []
	# for i in range(len(sa)):
	# 	if sa[i] < threshold:
	# 		seq[i].append(sa[i], i)
	return seq

def filter_indexes(sa, seq, el, m):
	new_seq = [0]
	for i in range(1, len(seq) - 1):
		if sa[seq[i]] != el or (sa[seq[i]] == el and seq[i+1] - new_seq[-1] > m):
			new_seq.append(seq[i])
	return new_seq[1:]


threshold = -1
while (not check_value(sa, m, threshold)):
	# print(threshold, get_indexes(sa, threshold))
	threshold += 1
# print(threshold, get_indexes(sa, threshold), sa)

seq = get_indexes(sa, threshold)
seq = filter_indexes(sa, seq, threshold, m)

s = ''.join(sorted([chr(ord('a') + sa[x]) for x in seq]))
print(s)

abc = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
m = int(input())
string = input()
good = False
toCheck = []
lenS = len(string)
holes = [(-1, lenS)]
have = {'s': 0, 'i': 0, 'y': 0, 'h': 0, 'r': 0, 'f': 0, 'd': 0, 'z': 0, 'q': 0, 't': 0, 'n': 0, 'g': 0, 'l': 0, 'k': 0, 'o': 0, 'c': 0, 'w': 0, 'm': 0, 'b': 0, 'u': 0, 'a': 0, 'v': 0, 'e': 0, 'p': 0, 'j': 0, 'x': 0}
for sym in range(26):
    if not good:
        good = True
        for hole in holes:
            i = hole[0] + 1
            end = hole[1]
            while i < end:
                fill = string[i:min(end, i + m)].rfind(abc[sym])
                if fill == -1:
                    good = False
                    break
                else:
                    have[abc[sym]] += 1
                    i = i + fill + 1
                    if end - i < m:
                        break
            if not good:
                break
        holes = []
    if not good:
        have = {'s': 0, 'i': 0, 'y': 0, 'h': 0, 'r': 0, 'f': 0, 'd': 0, 'z': 0, 'q': 0, 't': 0, 'n': 0, 'g': 0, 'l': 0, 'k': 0, 'o': 0, 'c': 0, 'w': 0, 'm': 0, 'b': 0, 'u': 0, 'a': 0, 'v': 0, 'e': 0, 'p': 0, 'j': 0, 'x': 0}
        toCheck.append(abc[sym])
        good = True
        lastSeen = -1
        for i in range(lenS):
            if string[i] in toCheck:
                have[string[i]] += 1
                if i - lastSeen > m:
                    holes.append((lastSeen, i))
                    good = False
                lastSeen = i
        if lenS - lastSeen > m:
            holes.append((lastSeen, lenS))
            good = False
almost = [have[i] * i for i in abc]
print(''.join(almost))


n = int(input())
word = input()

cnt = [0]*26
for x in word:
    cnt[ord(x)-ord('a')] += 1

ind = 25
sum = 0

for i in range(26):
    pre = -1
    cur = -1
    ans = 0
    flag = True
    for j,x in enumerate(word):
        if ord(x)-ord('a')<i:
            pre = j
        elif ord(x)-ord('a')==i:
            cur = j
        if j-pre==n:
            if j-cur>=n:
                flag = False
                break
            pre = cur
            ans += 1
        #print(i, j, pre, cur, ans)
    if flag:
        ind = i
        sum = ans
        break

for i in range(ind):
    print(chr(ord('a')+i)*cnt[i],end='')
print(chr(ord('a')+ind)*sum)
        
    

from collections import Counter
from string import ascii_lowercase as asc
m, s = int(input()), input()
g = Counter(s)

def solve(c):
    p = 0
    for q in ''.join(x if x >= c else ' ' for x in s).split():
        i, j = 0, -1 
        while j + m < len(q):
            j = q.rfind(c, j + 1, j + m + 1)
            if j == -1:
                return None
            i += 1
        p += i
    return p

for c in asc:
    f = solve(c)
    if f is not None:
        g[c] = f
        print(''.join(x*g[x] for x in asc if x <= c))
        break


m = int(input())
s = input()
ans = []
mark = [True for _ in range(len(s))]
z = 'a'
i = 0
while i <= len(s) - m:
    k = i
    for j in range(i, i + m):
        if s[j] <= s[k]:
            k = j
    ans.append(s[k])
    z = max(z, s[k])
    mark[k] = False
    i = k
    i += 1
for i in range(len(s)):
    if s[i] < z and mark[i]:
        ans.append(s[i])
print(''.join(str(i) for i in sorted(ans)))

m = int(input())
s = list(input())

d = [0 for _ in range(26)]

for c in s:
    d[ord(c) - ord('a')] += 1

for i in range(26):
    c = chr(ord('a') + i)
    l = -1
    r = -1
    cnt = 0
    for j in range(len(s)):
        if s[j] < c:
            l = j
        if s[j] == c:
            r = j

        if j - l >= m:
            if j - r >= m:
                cnt = -1
                break
            cnt += 1
            l = r

    if ~cnt:
        for k in range(i):
            print(chr(ord('a') + k) * d[k], end='')
        print(chr(ord('a') + i) * cnt)
        break


m = int(input()) - 1
k = input()
r = ''
i = 97
t = [k]
while 1:
    q = chr(i)
    p = []
    for d in t:
        for s in d.split(q):
            if len(s) > m: p += [s]
    if not p: break
    r += q * k.count(q)
    i += 1
    t = p
y = chr(i)
for d in t:
    i = 0
    for x in d:
        if x == y: j = i
        if i == m:
            r += y
            i -= j
            j = 0
        else: i += 1
print(r)

m = int(input())
s = input()
n = len(s)
t = []
u = [1] * n
d = 'a'
i = 0
while i <= n - m:
    k = i
    for j in range(m):
        if s[i + j] <= s[k]: k = i + j
    t += [s[k]]
    d = max(d, s[k])
    u[k] = 0
    i = k + 1
t += [q for q, v in zip(s, u) if q < d and v]
print(''.join(sorted(t)))

from collections import defaultdict

class DenseSubsequence():
    def __init__(self, m, s):
        self.m = m
        self.s = s
        self.chars = sorted(set(s))

    def get_min_sequence(self, ch, mask):
        lv, lch, i = -1, -1, 0
        is_possible = True
        seq = []
        while i < len(self.s):
            if mask[i] == 1:
                lv = i
            elif self.s[i] == ch:
                lch = i

            if i-lv == self.m:
                if lch > lv:
                    seq.append(lch)
                    lv = lch
                else:
                    is_possible = False
                    break
            i += 1
        if not is_possible:
            return False, []
        else:
            return True, seq

    def get_sequence(self):
        char_map = defaultdict(list)
        for i in range(len(self.s)):
            char_map[self.s[i]].append(i)

        mask = [0]*len(self.s)

        res = ''

        for ch in self.chars:
            is_possible, seq = self.get_min_sequence(ch, mask)
            if is_possible:
                res = res+''.join([ch]*len(seq))
                break
            else:
                res = res+''.join([ch]*len(char_map[ch]))
                for v in char_map[ch]:
                    mask[v] = 1
        print(res)

m = int(input())
s = input().strip(' ')
DenseSubsequence(m,s).get_sequence()