У Боба есть строка $$$s$$$, которая состоит из английских букв нижнего регистра. Он определил $$$s'$$$ как строку, которую он получит, удаляя все буквы «a» из строки $$$s$$$ (оставляя все остальные символы в том же порядке). Он сгенерировал новую строку $$$t$$$ путем соединения $$$s$$$ и $$$s'$$$. Другими словами, $$$t=s+s'$$$ (смотрите примеры).
Вам дана строка $$$t$$$. Найдите такую строку $$$s$$$, которую использовал Боб, чтобы сгенерировать строку $$$t$$$. Можно показать, что если ответ существует, то он уникальный.
Первая строка содержит строку $$$t$$$ ($$$1 \leq |t| \leq 10^5$$$), которая состоит из английских букв нижнего регистра.
Выведите строку $$$s$$$, которую можно использовать для генерации $$$t$$$. Можно показать, что если ответ существует, то он уникальный. Если такой строки нет, то выведите «:(» (без кавычек, между символами нет пробела).
aaaaa
aaaaa
aacaababc
:(
ababacacbbcc
ababacac
baba
:(
В первом примере $$$s = $$$ «aaaaa», а $$$s' = $$$ «».
Во втором примере нет такой строки $$$s$$$, которая может сгенерировать $$$t$$$.
В третьем примере $$$s = $$$ «ababacac», а $$$s' = $$$ «bbcc», поэтому $$$t = s + s' = $$$ «ababacacbbcc».
Название |
---|