Insert Asterisk

Background

Congcong is currently learning about string manipulation. He encountered an interesting problem that requires special processing of strings.

Problem Description

Given a string, compute recursively a new string where identical chars that are adjacent in the original string are separated from each other by an "*".

Input Format

Input is given from standard input in the following format.

s

Output Format

Output is printed to standard output in the following format.

result

Sample

hello

hel*lo

xxyy

x*xy*y

aaaa

a*a*a*a

Sample Explanation

• Sample 1: For the input hello, only the two adjacent 'l's are identical, so an '*' is inserted between them, resulting in hel*lo.
• Sample 2: For the input xxyy, the two adjacent 'x's are separated by an '', and the two adjacent 'y's are separated by an '', resulting in x*xy*y.
• Sample 3: For the input aaaa, an '*' is inserted between every pair of identical adjacent 'a's, resulting in a*a*a*a.

Constraints

Time limit: 1 second. Memory limit: 1024 KiB for each test case.