Background

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 a "*".

Format

Input

Output

Samples

hello

"hel*lo"

xxyy

"x*xy*y"

aaaa

"a*a*a*a"

Limitation

1s, 1024KiB for each test case.