JAG-channel

時間制限 : 8 sec, メモリ制限 : 131072 KB

JAG-channel

ネイサン・O・デイビスはJAG-channelという電子掲示板を運営している. 彼は現在,スレッドビューという新機能の追加に取り組んでいる.

他の多くの電子掲示板と同じように,JAG-channelはスレッドベースである. ここで,スレッドとは,一連の投稿からなる一つの会話のまとまりを指す. 投稿には,以下の2種類が存在する.

  • 新しいスレッドを作る最初の投稿
  • すでにあるスレッドの過去の投稿への返信

スレッドビューは,投稿間の返信・被返信関係による論理的な構造を表す,ツリー状のビューである. それぞれの投稿はツリーのノードとなり,その投稿に対する返信を子ノードとして持つ. ある投稿に対する直接・間接の返信が,全体として部分木となることに注意してほしい.

例を見てみよう.例えば, "hoge"という最初の投稿に対して "fuga"と"piyo"という2つの返信が付き, "fuga"に対してさらに"foobar"と"jagjag"という返信が付き, "jagjag"に対して"zigzag"という返信が付いたとする. このスレッドのツリーは次のようになる.

hoge
├─fuga
│ ├─foobar
│ └─jagjag
│   └─zigzag
└─piyo

ネイサン・O・デイビスはプログラマーを雇って機能を実装させていたが,このプログラマーが最後の段階で失踪してしまった. このプログラマーは,スレッドのツリーを作り,それを簡易フォーマットで表示するところまで完成させている. この簡易フォーマットでは,返信の深さが '.' (半角ドット) で表され,ある投稿に対する返信は,元の投稿より1つ多くの '.' が左につく.また,ある投稿に対する返信は必ず元の投稿よりも下に来る.返信元の投稿と返信の間には,返信元の投稿に対する他の返信 (および,それに対する直接・間接の返信) が現れることがあるが,それ以外の投稿が両者の間に現れることはない. 上のツリーの簡易フォーマット表示は次のようになる.

hoge
.fuga
..foobar
..jagjag
...zigzag
.piyo

あなたの仕事は,この簡易フォーマット表示を受け取り,見やすく整形することである. すなわち,

  • 各投稿のすぐ左の '.' (各投稿の左についた '.' のうち,もっとも右のもの) を '+' (半角プラス),
  • 同じ投稿に対する直接の返信について,それぞれのすぐ左にある '+' の間に位置する '.' を '|' (半角縦線),
  • それ以外の '.' は ' ' (半角スペース)

に置き換えて欲しい.

上の簡易フォーマット表示に対する整形済みの表示は次のようになる.

hoge
+fuga
|+foobar
|+jagjag
| +zigzag
+piyo

Input

入力は複数のデータセットから構成される.各データセットの形式は次の通りである.

$n$
$s_1$
$s_2$
...
$s_n$

$n$ は簡易フォーマット表示の行数を表す整数であり,$1$ 以上 $1{,}000$ 以下と仮定してよい. 続く $n$ 行にはスレッドツリーの簡易フォーマット表示が記載されている. $s_i$ は簡易フォーマット表示の $i$ 行目を表し,いくつかの '.' と,それに続く $1$ 文字以上 $50$ 文字以下のアルファベット小文字で構成された文字列からなる. $s_1$ はスレッドの最初の投稿であり,'.' を含まない. $s_2$, ..., $s_n$ はそのスレッドでの返信であり,必ず1つ以上の '.' を含む.

$n=0$ は入力の終わりを示す.これはデータセットには含めない.

Output

各データセットに対する整形済みの表示を各 $n$ 行で出力せよ.

Sample Input

6
hoge
.fuga
..foobar
..jagjag
...zigzag
.piyo
8
jagjag
.hogehoge
..fugafuga
...ponyoponyo
....evaeva
....pokemon
...nowawa
.buhihi
8
hello
.goodmorning
..howareyou
.goodafternoon
..letshavealunch
.goodevening
.goodnight
..gotobed
3
caution
.themessagelengthislessthanorequaltofifty
..sothelengthoftheentirelinecanexceedfiftycharacters
0

Output for Sample Input

hoge
+fuga
|+foobar
|+jagjag
| +zigzag
+piyo
jagjag
+hogehoge
|+fugafuga
| +ponyoponyo
| |+evaeva
| |+pokemon
| +nowawa
+buhihi
hello
+goodmorning
|+howareyou
+goodafternoon
|+letshavealunch
+goodevening
+goodnight
 +gotobed
caution
+themessagelengthislessthanorequaltofifty
 +sothelengthoftheentirelinecanexceedfiftycharacters

Source: ACM International Collegiate Programming Contest , ACM-ICPC Japan Alumni Group Practice Contest for Japan Domestic 2014, 2014-07-06
http://acm-icpc.aitea.net/