Letter Replacement

Time limit1sMemory limit128 MB

Summary

Replace each repeated letter in a word with a symbol assigned in the order letters first repeat, comparing case-insensitively.

Level: Easy3 of 10
Topics: String, Implementation, Hash map
Solved: No attempts yet

Problem

Mr Sythe is teaching an ESL class about letters that repeat inside English words. As an exercise, his students replace every repeated letter in a word with a symbol.

The symbols are:

* — the first repeated letter (the first letter encountered that has appeared before)
? — the second repeated letter
/ — the third repeated letter
+ — the fourth repeated letter
! — the fifth repeated letter

No word Mr Sythe uses has more than 5 repeated letters.

Letters are compared case-insensitively. The first time a letter appears it is left unchanged; every later appearance of that letter is replaced by the symbol assigned to it. Symbols are assigned in the order in which each distinct letter first becomes repeated: *, then ?, /, +, !.

For example, the word Reindeer becomes Reind**?, because e is repeated twice and r is repeated once. The repeated e comes before the repeated r, so e is assigned * and r is assigned ?. The first letter of the word is an upper case R, but it is treated as the same letter as lower case r.

Input

The input is a list of words, one per line. Each word begins with an upper case letter and contains no more than 10 letters. The last line contains just a # — do not process this line.

Output

Print one line for each input word. Each output word is the input word with its repeated letters replaced according to the rules above.

Examples2

Example 1

Input

Reindeer
Bubbles
Occurrence
#

Expected output

Reind**?
Bu**les
Oc*ur?en*/

Example 2
Input
```
Cat
#
```
Expected output
```
Cat
```