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".
#!/us
assistant
#Here is Python code to find some s that Bob could have used to generate t.
r/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
else:
    from builtins import str as __str__

    str = lambda x=b"": x if type(x) is bytes else __str__(x).encode()

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._buffer = BytesIO()
        self._fd = file.fileno()
        self._writable = "x" in file.mode or "r" not in file.mode
        self.write = self._buffer.write if self._writable else None

    def read(self):
        if self._buffer.tell():
            return self._buffer.read()
        return os.read(self._fd, os.fstat(self._fd).st_size)

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()

    def flush(self):
        if self._writable:
            os.write(self._fd, self._buffer.getvalue())
            self._buffer.truncate(0), self._buffer.seek(0)

sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip(b"\r\n")

def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", b" "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", b"\n"))
    if kwargs.pop("flush", False):
        file.flush()

def main():
    t = input()
    lens = len(t) + t.count("a")

    if lens % 2 == 1:
        print(":(")
    else:
        lens //= 2
        s = t[:lens]
        sd = "".join(si for si in s if si != "a")
        if s + sd ==...