human
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 ≤ |t| ≤ 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".
# s = ... What is a Python code to find some s that Bob could have used to generate t?
assistant
#Here is Python code to find some s that Bob could have used to generate t.
 input()

# def all_the_same(elements):
#     if len(elements) < 1:
#         return True
#     return len(elements) == elements.count(elements[0])

# if all_the_same(s) == True:
#     print(s)
# else:
#     c = 0
#     for x in range(1, len(s)):
#         ss = list(s)
#         s2 = ''.join(ss[:x+1])
#         s3 = ''.join(ss[x+1:])
#         s4 = ''.join(s2).replace('a', '')

#         if s4 == s3:
#             print(s2)
#             c += 1
#             break

#     if c == 0: print(':(')

e = input()
f = [i for i in e if i!="a"]
 
n = len(f) // 2
n2 = len(e)

if f[:n] == f[n:] and "a" not in e[n2-n:]: print(e[:n2-n])
else: print(":(")