A relay-race ledger records, for each of the n legs of a long-distance relay, the name of the runner holding the baton at the end of that leg. A scoring-booth malfunction left some legs unrecorded; those legs are written using the reserved placeholder token MISSING. Officials know the baton is never reset mid-race, so whenever a leg's holder is missing, the true holder for that leg is the same runner who held the baton at the closest earlier leg whose holder was actually recorded. The very first leg is always guaranteed to have been recorded. Reconstruct the complete ledger.

Input format

Line 1: an integer n — the number of legs. Line 2: n space-separated tokens. Each token is either a runner's name (1 to 20 characters, using only uppercase letters, lowercase letters, and digits, and never equal to the literal text MISSING) or the placeholder token MISSING. The first token is guaranteed not to be MISSING.

Output format

n space-separated tokens: the reconstructed ledger, where every MISSING has been replaced by the name of the runner holding the baton at the nearest earlier recorded leg.

Constraints

1 <= n <= 100000.

6
Alex MISSING MISSING Bri MISSING Cee

Alex Alex Alex Bri Bri Cee

1
Solo

Solo