Есть строка \(a\) (она вам неизвестна), состоящая из латинских строчных букв, зашифрованная по следующему правилу в строку \(s\):
- после каждого символа строки \(a\) дописывается произвольное (возможно, нулевое) количество любых латинских строчных букв, отличных от самого символа;
- после каждого такого дописывания ставится тот символ, который мы дополняли.
Вам дана строка \(s\), выведите изначальную строку \(a\). Другими словами, вам нужно расшифровать строку \(s\).
Обратите внимание, что каждая зашифрованная таким образом строка расшифровывается единственным образом.
Выходные данные
Для каждого запроса выведите в отдельной строке строку \(a\) — расшифрованное сообщение.
Примечание
В первом зашифрованном сообщении буква \(a\) зашифрована в виде \(aba\), и буква \(c\) зашифрована в виде \(cabac\).
Во втором зашифрованном сообщении всего одна буква \(q\) зашифрована в виде \(qzxcq\).
В третьем зашифрованном сообщении к каждой букве дописано нулевое количество символов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
8
abacabac
5
qzxcq
20
ccooddeeffoorrcceess
|
ac
q
codeforces
|