Bob has a string $s$ consisting of lowercase English letters. He defines $s’$ to be the string after removing all “a” characters from $s$ (keeping all other characters in the same order). He then generates a new string $t$ by concatenating $s$ and $s’$. In other words, $t=s+s’$ (look at notes for an example).
You are given a string $t$. Your task is to find some $s$ that Bob could have used to generate $t$. It can be shown that if an answer exists, it will be unique.
Input
The first line of input contains a string $t$ ($1 \leq |t| \leq 10^5$) consisting of lowercase English letters.
Output
Print a string $s$ that could have generated $t$. It can be shown if an answer exists, it is unique. If no string exists, print “:(” (without double quotes, there is no space between the characters).
Examples
input
aaaaa
output
aaaaa
input
aacaababc
output
:(
input
ababacacbbcc
output
ababacac
input
baba
output
:(
Note
In the first example, we have $s = $ “aaaaa”, and $s’ = $ “”.
In the second example, no such $s$ can work that will generate the given $t$.
In the third example, we have $s = $ “ababacac”, and $s’ = $ “bbcc”, and $t = s + s’ = $ “ababacacbbcc”.
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); string s; cin >> s; int n = (int) s.size(); int cnt = 0; for (char c : s) { cnt += (c == 'a'); } if ((n - cnt) % 2 != 0) { cout << ":(" << '\n'; return 0; } string t = s.substr(0, cnt + (n - cnt) / 2); string w = t; for (char c : t) { if (c != 'a') { w += c; } } cout << (w == s ? t : ":(") << '\n'; return 0; }