Alice and Bob decided to stop sending each other cryptic messages for once, and are now sharing a bar of chocolate. The bar is split into a row of $n$ pieces, and as part of a cute gimmick from the chocolate-maker, each piece of the chocolate bar has a single letter written on it!

Alice and Bob agree on the following protocol: before they reach for a piece, they must first simultaneously declare if they want the leftmost piece or the rightmost piece. That way, they can confirm there won’t be any conflict (but if they do end up wanting the same piece... oops, their protocol didn’t plan for that).

Thankfully, Alice and Bob are simple predictable creatures and will always choose to get from the same side. The following procedure repeats until the chocolate bar is all eaten up (or until they fight):

• Alice says “I want to eat the leftmost remaining piece!” and Bob says “I want to eat the rightmost remaining piece!”
• If they want different pieces, then they each break off the piece that they want and eat it.
• If they want the same piece, they will fight over it. Oh no!

Please determine whether or not Alice and Bob will fight. And if they will fight, determine what letter is written on the piece that causes them to fight.

Input

Input consists of a single line, containing a single string $s$, which consists of $n$ uppercase English letters—from left to right, these are the letters written on the pieces on the chocolate bar.

Output

If they will not fight, output the two characters :)

If they will fight, output a single letter, the one written on the piece that causes them to fight.

Constraints

• $2 \le n \le 2 \times 10^5$
• $s$ consists only of $n$ uppercase English letters.

Examples

Input 1

ICPCMANILA

Output 1

:)

Input 2

RACECAR

Output 2

E