Длина самого длинного общего префикса двух строк \(s = s_1 s_2 \ldots s_n\) и \(t = t_1 t_2 \ldots t_m\) определяется как наибольшее целое число \(k\) (\(0 \le k \le min(n,m)\)) такое, что \(s_1 s_2 \ldots s_k\) равняется \(t_1 t_2 \ldots t_k\).
У Коалы Коа изначально есть \(n+1\) строка \(s_1, s_2, \dots, s_{n+1}\).
Для каждого \(i\) (\(1 \le i \le n\)) она вычислила \(a_i\) — длину самого длинного общего префикса \(s_i\) и \(s_{i+1}\).
Несколько дней спустя Коа нашла эти числа, но не могла вспомнить строки.
Поэтому Коа хотела бы найти какие-нибудь строки \(s_1, s_2, \dots, s_{n+1}\), которые дали бы числа \(a_1, a_2, \dots, a_n\). Можете ли вы ей помочь?
Если ответов несколько, выведите любой. Можно показать, что для данных ограничений ответ всегда существует.
Выходные данные
Для каждого набора входных данных:
Выведите \(n+1\) строку. В \(i\)-й строке выведите строку \(s_i\) (\(1 \le |s_i| \le 200\)), , состоящую из строчных латинских букв. Длина самого длинного общего префикса строк \(s_i\) и \(s_{i+1}\) должна быть равна \(a_i\).
Если ответов несколько, выведите любой. Можно показать, что для данных ограничений ответ всегда существует.
Примечание
В \(1\)-м наборе входных данных один из возможных ответов это \(s = [aeren, ari, arousal, around, ari]\).
Длины самых длинных общих префиксов равны:
- Между \(\color{red}{a}eren\) и \(\color{red}{a}ri\) \(\rightarrow 1\)
- Между \(\color{red}{ar}i\) и \(\color{red}{ar}ousal\) \(\rightarrow 2\)
- Между \(\color{red}{arou}sal\) и \(\color{red}{arou}nd\) \(\rightarrow 4\)
- Между \(\color{red}{ar}ound\) и \(\color{red}{ar}i\) \(\rightarrow 2\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4
1 2 4 2
2
5 3
3
1 3 1
3
0 0 0
|
aeren
ari
arousal
around
ari
monogon
monogamy
monthly
kevinvu
kuroni
kurioni
korone
anton
loves
adhoc
problems
|