Vasya is an administrator of a public page of organization "Mouse and keyboard" and his everyday duty is to publish news from the world of competitive programming. For each news he also creates a list of hashtags to make searching for a particular topic more comfortable. For the purpose of this problem we define hashtag as a string consisting of lowercase English letters and exactly one symbol '#' located at the beginning of the string. The length of the hashtag is defined as the number of symbols in it without the symbol '#'.

The head administrator of the page told Vasya that hashtags should go in lexicographical order (take a look at the notes section for the definition).

Vasya is lazy so he doesn't want to actually change the order of hashtags in already published news. Instead, he decided to delete some suffixes (consecutive characters at the end of the string) of some of the hashtags. He is allowed to delete any number of characters, even the whole string except for the symbol '#'. Vasya wants to pick such a way to delete suffixes that the total number of deleted symbols is minimum possible. If there are several optimal solutions, he is fine with any of them.


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 500 000) — the number of hashtags being edited now.

Each of the next n lines contains exactly one hashtag of positive length.

It is guaranteed that the total length of all hashtags (i.e. the total length of the string except for characters '#') won't exceed 500 000.


-----Output-----

Print the resulting hashtags in any of the optimal solutions.


-----Examples-----
Input
3
#book
#bigtown
#big

Output
#b
#big
#big

Input
3
#book
#cool
#cold

Output
#book
#co
#cold

Input
4
#car
#cart
#art
#at

Output
#
#
#art
#at

Input
3
#apple
#apple
#fruit

Output
#apple
#apple
#fruit



-----Note-----

Word a_1, a_2, ..., a_{m} of length m is lexicographically not greater than word b_1, b_2, ..., b_{k} of length k, if one of two conditions hold:   at first position i, such that a_{i} ≠ b_{i}, the character a_{i} goes earlier in the alphabet than character b_{i}, i.e. a has smaller character than b in the first position where they differ;  if there is no such position i and m ≤ k, i.e. the first word is a prefix of the second or two words are equal. 

The sequence of words is said to be sorted in lexicographical order if each word (except the last one) is lexicographically not greater than the next word.

For the words consisting of lowercase English letters the lexicographical order coincides with the alphabet word order in the dictionary.

According to the above definition, if a hashtag consisting of one character '#' it is lexicographically not greater than any other valid hashtag. That's why in the third sample we can't keep first two hashtags unchanged and shorten the other two.

Difficulty: MEDIUM_HARD
Tags: String algorithms

Sorting

Implementation

Greedy algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
n = int(input())
l = []
for i in range(n):
	l.append(input())

def lexi(i):
	j = 1
	while j < len(l[i]) and l[i - 1][j] == l[i][j]:
		j += 1
	l[i - 1] = l[i - 1][:j]
for i in range(n - 1, 0, -1):
	if l[i - 1] > l[i]:
		lexi(i)
print('\n'.join(l))


def cut_to_lexicographic(word_bigger, word_smaller):
	for l in range(len(word_bigger[:len(word_smaller)])):
		if word_bigger[l] != word_smaller[l]:
			return word_smaller[:l]
	return word_bigger[:len(word_smaller)]
n = int(input())
array = [str(input()) for c in range(n)]
b = n - 2
while b > -1:
	if array[b + 1] >= array[b]:
		b = b - 1
	else:
		array[b] = cut_to_lexicographic(array[b], array[b + 1])
print('\n'.join(array))


n = int(input())
arr = [input() for i in range(n)]
for i in range(n - 1, 0, -1):
	new = arr[i]
	old = arr[i - 1]
	le1 = len(new)
	le2 = len(old)
	for j in range(min(le1, le2)):
		if new[j] < old[j]:
			arr[i - 1] = old[:j]
			break
		elif new[j] > old[j]:
			break
	else:
		if le2 > le1:
			arr[i - 1] = arr[i]
print('\n'.join(arr))


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
mod = 10 ** 9 + 7

def LI():
	return list(map(int, input().split()))

def II():
	return int(input())

def LS():
	return input().split()

def S():
	return input()

def main():
	n = II()
	a = [S() for _ in range(n)]
	for i in range(n - 2, -1, -1):
		t = a[i]
		s = a[i + 1]
		sl = len(s)
		for j in range(1, len(t)):
			if j >= sl:
				a[i] = s
				break
			if t[j] > s[j]:
				a[i] = t[:j]
				break
			if t[j] < s[j]:
				break
	return '\n'.join(a)
print(main())


num = int(input())
hts = list((input() for _ in range(num)))
i = num - 2
while i >= 0:
	if hts[i] > hts[i + 1]:
		n = 1
		while n < len(hts[i + 1]) and hts[i][n] == hts[i + 1][n]:
			n += 1
		hts[i] = hts[i][:n]
	i -= 1
print('\n'.join(hts))


from sys import stdin, stdout
n = int(stdin.readline())
a = [stdin.readline() for i in range(n)]
for i in range(len(a) - 1, 0, -1):
	if a[i - 1] > a[i]:
		s = 0
		while s < len(a[i]) and a[i - 1][s] == a[i][s]:
			s += 1
		a[i - 1] = a[i - 1][:s]
stdout.write('\n'.join(a))


import collections
import time
import os
import sys
import bisect
import heapq
from typing import List

def clip(word, target):
	if word <= target:
		return word
	(lo, hi) = (1, len(word))
	while lo <= hi:
		m = (lo + hi) // 2
		if word[:m] > target:
			hi = m - 1
		else:
			lo = m + 1
	return word[:hi]

def solve(N, A):
	ans = [A[-1]]
	for i in range(N - 2, -1, -1):
		ans.append(clip(A[i], ans[-1]))
	print('\n'.join(ans[::-1]))
	sys.stdout.flush()
N = int(input())
A = []
for i in range(N):
	row = input()
	A.append(row)
solve(N, A)


from sys import stdin, stdout

def ri():
	return list(map(int, input().split()))
n = int(input())
s = []
for i in range(n):
	s.append(stdin.readline().strip())
for i in range(n - 1, 0, -1):
	if s[i - 1] <= s[i]:
		continue
	else:
		mind = min(len(s[i]), len(s[i - 1]))
		for j in range(mind):
			if s[i - 1][j] > s[i][j]:
				s[i - 1] = s[i - 1][:j]
				break
		else:
			s[i - 1] = s[i - 1][:mind]
print('\n'.join(s))


n = int(input())
ss = [input().strip() for _ in range(n)]

def compare_and_truncate(s1, s2):
	if s1 > s2:
		i = 0
		while i < len(s2) and s1[i] == s2[i]:
			i += 1
		return s1[:i]
	return s1
for i in range(len(ss) - 2, -1, -1):
	ss[i] = compare_and_truncate(ss[i], ss[i + 1])
ans = ''
for s in ss:
	ans += s + '\n'
print(ans)


import sys
input = sys.stdin.readline
n = int(input())
a = []
for i in range(n):
	s = input()
	s = s[:len(s) - 1]
	a.append(s)
for i in range(n - 2, -1, -1):
	(l, r) = (a[i], a[i + 1])
	for j in range(len(l)):
		if j >= len(r) or l[j] > r[j]:
			a[i] = l[:j]
			break
		elif l[j] < r[j]:
			break
for s in a:
	print(s)


import sys
input = sys.stdin.readline

def I():
	return input().strip()

def II():
	return int(input().strip())

def LI():
	return [*map(int, input().strip().split())]
import copy
import string, math, time, functools, random, fractions
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter, OrderedDict
from itertools import permutations, combinations, groupby, count, filterfalse
from operator import itemgetter
for _ in range(1):
	n = II()
	l = []
	for i in range(n):
		l.append(I())
	l.reverse()
	for i in range(n - 1):
		if l[i] < l[i + 1]:
			c = 0
			while c < len(l[i]) and l[i + 1][c] <= l[i][c]:
				c = c + 1
			l[i + 1] = l[i + 1][:c]
	l.reverse()
	for i in range(len(l)):
		print(l[i])


import sys
n = int(sys.stdin.readline().strip())
ss = [sys.stdin.readline().strip() for _ in range(n)]

def compare_and_truncate(s1, s2):
	if s1 > s2:
		i = 0
		while i < len(s2) and s1[i] == s2[i]:
			i += 1
		return s1[:i]
	return s1
for i in range(len(ss) - 2, -1, -1):
	ss[i] = compare_and_truncate(ss[i], ss[i + 1])
ans = ''
for s in ss:
	ans += s + '\n'
sys.stdout.write(ans)


n = int(input())
hashtags = []
for i in range(n):
	hashtags.append(input())
for i in range(n - 2, -1, -1):
	if hashtags[i] > hashtags[i + 1]:
		pointer = 0
		while pointer < len(hashtags[i + 1]) and hashtags[i][pointer] == hashtags[i + 1][pointer]:
			pointer += 1
		hashtags[i] = hashtags[i][:pointer]
print('\n'.join(hashtags))


def g(c, d):
	s = 0
	while s < len(a[d]) and a[c][s] == a[d][s]:
		s += 1
	a[c] = a[c][:s]

def f(a):
	for i in range(len(a) - 1, 0, -1):
		if a[i - 1] > a[i]:
			g(i - 1, i)
	print('\n'.join(a))
n = int(input())
a = [input() for i in range(n)]
f(a)


import sys
input = sys.stdin.readline

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

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

def main():
	n = int(input())
	a = []
	for i in range(n):
		s = input()
		a.append([len(s) - 2, s])
	ans = 0
	for i in range(n - 1, 0, -1):
		if a[i][0] == 0:
			ans += a[i - 1][0] + 1
			a[i - 1][0] = 0
		else:
			k = 0
			f = 0
			for j in range(a[i][0] + 1):
				if j > a[i - 1][0]:
					f = 1
					break
				if a[i - 1][1][j] > a[i][1][j]:
					ans += a[i - 1][0] + 1
					a[i - 1][0] = j - 1
					f = 1
					break
				if a[i - 1][1][j] < a[i][1][j]:
					f = 1
					break
			if f == 0:
				a[i - 1][0] = a[i][0]
	for i in a:
		print('#', end='')
		for j in range(1, i[0] + 1):
			print(i[1][j], end='')
		print('')
	return
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import Counter
import heapq
from collections import Counter

def valid(s):
	for i in range(len(s) - 1):
		if abs(ord(s[i]) - ord(s[i + 1])) == 1:
			return False
	return True
import os.path
ls = []
for _ in range(int(input())):
	s = input()
	ls.append(s)
for i in range(len(ls) - 1, 0, -1):
	if ls[i - 1] > ls[i]:
		s = 0
		while s < len(ls[i]) and ls[i - 1][s] == ls[i][s]:
			s += 1
		ls[i - 1] = ls[i - 1][:s]
print('\n'.join(ls))


def compareHesh(heshBottom, heshTop):
	(lenB, lenT) = (len(heshBottom), len(heshTop))
	flag = True
	for i in range(1, lenT):
		if i + 1 > lenB:
			return i
		elif heshTop[i] > heshBottom[i]:
			return i
		elif heshTop[i] < heshBottom[i]:
			return 0
	return 0
numberHesh = int(input())
wordHesh = []
for i in range(numberHesh):
	wordHesh.append(input())
for i in range(numberHesh - 1, 0, -1):
	cut = compareHesh(wordHesh[i], wordHesh[i - 1])
	if cut == 0:
		continue
	wordHesh[i - 1] = wordHesh[i - 1][:cut]
for i in range(numberHesh):
	print(wordHesh[i])


N = int(input())
A = [input() for i in range(N)]
for i in range(N - 1, 0, -1):
	if A[i - 1] > A[i]:
		ptr = 0
		while ptr < len(A[i]) and A[i - 1][ptr] == A[i][ptr]:
			ptr += 1
		A[i - 1] = A[i - 1][:ptr]
print('\n'.join(A))


def sorting(string, string1):
	if len(string) > len(string1):
		string = string[:len(string1)]
	for q in range(len(string)):
		if string[q] > string1[q]:
			string = string[:q]
			break
	return string
n = int(input())
array = [str(input()) for c in range(n)]
b = n - 2
while b > -1:
	if array[b + 1] >= array[b]:
		b = b - 1
	else:
		array[b] = sorting(array[b], array[b + 1])
print('\n'.join(array))


from sys import stdin, stdout
n = int(stdin.readline())
challengers = []
for i in range(n):
	challengers.append(stdin.readline().strip()[1:])
for i in range(n - 2, -1, -1):
	for j in range(min(len(challengers[i]), len(challengers[i + 1]))):
		if challengers[i][j] < challengers[i + 1][j]:
			break
		elif challengers[i][j] > challengers[i + 1][j]:
			challengers[i] = challengers[i][:j]
			break
	else:
		challengers[i] = min(challengers[i], challengers[i + 1])
for i in range(n):
	challengers[i] = '#' + challengers[i]
stdout.write('\n'.join(challengers))


import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz/'
M = 998244353
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
n = Int()
a = []
for i in range(n):
	a.append(input().lstrip('#'))
count = defaultdict(int)
count[n - 1] = len(a[-1])
for i in range(n - 2, -1, -1):
	prev = a[i + 1]
	now = a[i]
	count[i] = len(now)
	j = 0
	while j < count[i + 1] and j < count[i] and (prev[j] == now[j]):
		j += 1
	if j == count[i + 1]:
		count[i] = count[i + 1]
	elif j == count[i]:
		continue
	elif prev[j] < now[j]:
		count[i] = j
for i in range(n):
	print('#' + a[i][:count[i]])


import sys, os, io
input = sys.stdin.readline
n = int(input())
a = []
for i in range(n):
	a.append(input().strip())
a.reverse()
ans = [a[0]]
for i in range(1, n):
	if a[i] > ans[i - 1]:
		res = ''
		for j in range(len(a[i])):
			if j == len(ans[i - 1]):
				res = a[i][:j]
				break
			if a[i][j] > ans[i - 1][j]:
				res = a[i][:j]
				break
		if res == '':
			res = a[i][:]
		ans.append(res)
	else:
		ans.append(a[i])
ans.reverse()
for i in ans:
	print(i)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
a = int(input())
ans = []
for i in range(a):
	s = input()
	ans.append(s)
for i in range(len(ans) - 1, -1, -1):
	if i == len(ans) - 1:
		continue
	t = ans[i + 1]
	m = ans[i]
	j = 0
	while j < min(len(m), len(t)) and m[j] == t[j]:
		j += 1
		continue
	if j == min(len(m), len(t)):
		ans[i] = min(m, t)
		continue
	if m[j] < t[j]:
		continue
	ans[i] = m[0:j]
for i in range(len(ans)):
	print(ans[i])


n = int(input())
A = [input() for i in range(n)]
for i in range(n - 1, 0, -1):
	if A[i] < A[i - 1]:
		p = 0
		while p < len(A[i]) and A[i - 1][p] <= A[i][p]:
			p += 1
		A[i - 1] = A[i - 1][:p]
print('\n'.join(A))


n = int(input())
inp = [0] * n
for i in range(n):
	inp[i] = input()

def common_str(a, b):
	l = 1
	for i in range(1, len(a)):
		if a[i] != b[i]:
			break
		l += 1
	return a[:l]
for i in range(n - 1, 0, -1):
	if inp[i] < inp[i - 1]:
		inp[i - 1] = common_str(inp[i], inp[i - 1])
print('\n'.join(inp))


n = int(input())
a = [input() for i in range(n)]
for i in range(n - 1, 0, -1):
	b = a[i]
	c = a[i - 1]
	l1 = len(b)
	l2 = len(c)
	for j in range(min(l1, l2)):
		if b[j] < c[j]:
			a[i - 1] = c[:j]
			break
		elif b[j] > c[j]:
			break
	else:
		if l2 > l1:
			a[i - 1] = a[i]
print('\n'.join(a))


def cnt(a, b):
	ln = 0
	l = 0
	r = len(a) - 1
	if a > b:
		while r > l + 1:
			mid = (l + r) // 2
			if a[:mid + 1] > b:
				r = mid
			else:
				l = mid
		a = a[:l + 1]
	return a
n = int(input())
s = []
for i in range(n):
	b = input()
	s.append(b)
for i in range(n - 1, 0, -1):
	s[i - 1] = cnt(s[i - 1], s[i])
for x in s:
	print(x)


from sys import stdin, stdout
n = int(stdin.readline())
A = [0] * n
for j in range(n):
	A[j] = stdin.readline().strip()
answer = [0] * n
answer[-1] = A[-1]
for j in range(n - 2, -1, -1):
	if A[j] <= answer[j + 1]:
		answer[j] = A[j]
	else:
		for i in range(min(len(answer[j + 1]), len(A[j]))):
			if A[j][i] > answer[j + 1][i]:
				i -= 1
				break
		answer[j] = A[j][:i + 1]
print('\n'.join(answer))


import sys
import math
from collections import defaultdict, deque
import heapq
n = int(sys.stdin.readline())
arr = ['' for x in range(n)]
for i in range(n):
	arr[i] = sys.stdin.readline()[:-1]
if n == 1:
	print(arr[0])
	sys.exit()
for i in range(n - 2, -1, -1):
	cur1 = arr[i]
	cur2 = arr[i + 1]
	(a, b) = (len(cur1), len(cur2))
	z = True
	cnt = 1
	for j in range(1, min(a, b)):
		if cur1[j] == cur2[j]:
			cnt += 1
			continue
		elif cur1[j] < cur2[j]:
			z = False
			break
		else:
			break
	if not z:
		continue
	arr[i] = cur1[:cnt]
for i in range(n):
	print(arr[i])


n = int(input())
tags = []
for i in range(n):
	tags.append(input())
for i in range(n - 2, -1, -1):
	curr = tags[i]
	next = tags[i + 1]
	for c in range(min(len(curr), len(next))):
		if curr[c] != next[c]:
			if curr[c] > next[c]:
				tags[i] = curr[:c]
			break
	else:
		if len(curr) > len(next):
			tags[i] = curr[:len(next)]
print('\n'.join(tags))


def sortHashtags(htags):

	def shorten(j, i):
		s = 0
		while s < len(htags[i]) and htags[i][s] == htags[j][s]:
			s += 1
		htags[j] = htags[j][:s]
	n = len(htags)
	for i in range(n - 1, 0, -1):
		if htags[i - 1] > htags[i]:
			shorten(i - 1, i)
	return '\n'.join(htags)
n = int(input())
tags = []
for i in range(n):
	tags.append(input())
print(sortHashtags(tags))