1146B.md (1441B)
1 Source: https://codeforces.com/problemset/problem/1146/B 2 3 B. Hate "A" 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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). 22 23 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. 24 25 Input 26 27 The first line of input contains a string $t$ ($1 \leq |t| \leq 10^5$) consisting of lowercase English letters. 28 29 Output 30 31 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). 32 33 Examples 34 35 Input 36 37 ``` 38 aaaaa 39 ``` 40 41 Output 42 43 ``` 44 aaaaa 45 ``` 46 47 Input 48 49 ``` 50 aacaababc 51 ``` 52 53 Output 54 55 ``` 56 :( 57 ``` 58 59 Input 60 61 ``` 62 ababacacbbcc 63 ``` 64 65 Output 66 67 ``` 68 ababacac 69 ``` 70 71 Input 72 73 ``` 74 baba 75 ``` 76 77 Output 78 79 ``` 80 :( 81 ``` 82 83 Note 84 85 In the first example, we have $s = $ "aaaaa", and $s' = $ "". 86 87 In the second example, no such $s$ can work that will generate the given $t$. 88 89 In the third example, we have $s = $ "ababacac", and $s' = $ "bbcc", and $t = s + s' = $ "ababacacbbcc".