E. Email
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

The email application that Enzo developed during his college days has now become one of the largest in the world in the electronic mail field. Although some users have complained about the lack of basic features, such as deleting emails and spam checking, the app is still a hit, thanks to its "simplicity", according to Enzo himself.

Enzo's next task is to implement a password recovery system in case a user forgets their password. However, the internal workings of Enzo's email app are anything but "simple":

  • The app users' passwords consist only of the digits '0' and '1'; as unusual as it may seem, that's how it works. No one really knows why Enzo made it this way.
  • The app encrypts the passwords by transforming '0's into the string "ab" and '1's into the string "aba".
  • The database sometimes fails and saves corrupted passwords like "abb" or "abaaaab" (passwords that can't be obtained from a combination of "ab"s and "aba"s).

Enzo wants to create a program that, given a sequence of characters 'a' and 'b', retrieves the string of characters '0' and '1' that represents the user's original password, so he can send it directly to them via SMS (he didn't worry much about security, as long as it works). If it's not possible to retrieve the user's password due to corruption, the program should print ":(" to indicate there was a problem in the process.

However, as he's nearing retirement and has been spending most of his time watching Cruzeiro's soccer games, he's lost his touch and can't solve problems anymore. That's why he's asking for your help.

Input

The first line of the input contains an integer $$$N$$$ $$$(1 \leq N \leq 10^5)$$$, the length of the encrypted password. The encrypted password of length $$$N$$$, made up only of characters 'a' and 'b', follows in the second line.

Output

Print a string made up only of characters '0' and '1', the decrypted user password, or, print ":(" (without the quotes) if the password is corrupted.

Examples
Input
5
ababa
Output
01
Input
9
ababaabab
Output
0100
Input
8
abababaa
Output
:(