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: HARD
Tags: String algorithms

Data structures

Greedy algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
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)


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))


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]
	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):
	threshold += 1
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)


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


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()


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 = input()
d = [0 for _ in range(26)]
for char in s:
	d[ord(char) - ord('a')] += 1
for i in range(26):
	(char, left, right, counter) = (chr(ord('a') + i), -1, -1, 0)
	for j in range(len(s)):
		if s[j] < char:
			left = j
		if s[j] == char:
			right = j
		if j - left >= m:
			if j - right >= m:
				counter = -1
				break
			counter += 1
			left = right
	if ~counter:
		for j in range(i):
			print(chr(ord('a') + j) * d[j], end='')
		print(chr(ord('a') + i) * counter)
		break


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()
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)))


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
	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)