I - CR LF Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

右下方向に無限に広がるグリッド状のテキストエディタがあります。テキストエディタの上から i 行目、左から j 列目のマスを (i, j) と呼びます。各マスは文字が書かれている状態か何も書かれていない状態のいずれかです。初期状態ではどのマスにも文字は書かれていません。
また、文字の入力位置を示す カーソル と呼ばれるマークがあります。カーソルははじめ (1, 1) にあります。

あなたは Q 個のクエリを与えられた順に処理します。
クエリは次の 3 種類のいずれかです。

  • 1 c : カーソルのあるマスに文字 c を挿入する。厳密に説明すると、次の一連の操作を行う。
    • まず、現在カーソルのあるマスに書かれている文字および同じ行内でそのマスより右にある文字が存在すれば、それらを全て同時に右に 1 マス動かす。
    • 次に、現在カーソルのあるマスに文字 c を書きこむ。
    • 最後に、カーソルを右に 1 マス動かす。
  • 2 : カーソルを今いる行の左端に動かす。
  • 3 : カーソルを今いる 1 つ下の行の左端に動かす。

クエリを全て処理した後のテキストエディタの状態を出力してください。

制約

  • 1 \leq Q \leq 1.5 \times 10^6
  • c は英小文字

入力

入力は以下の形式で標準入力から与えられる。ここで \mathrm{query}_i は i 番目のクエリを意味する。

Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

出力

  • クエリを全て処理した時点でのカーソルのあるマスを (H, W)
  • 上から i 行目に書かれている文字の個数を C_i
  • マス (i, j) に書かれている文字を S_{i, j}

として、以下の形式で H + 1 行出力せよ。(C_i = 0 である行が存在する可能性があることに注意せよ。)
2 行目以降は行頭に # および半角スペースを付ける必要がある点に注意せよ。

H W
# S_{1, 1}S_{1, 2} \dots S_{1, C_1}
# S_{2, 1}S_{2, 2} \dots S_{2, C_2}
\vdots
# S_{H, 1}S_{H, 2} \dots S_{H, C_H}

入力例 1

8
1 b
1 c
1 d
2
1 a
3
3
1 e

出力例 1

3 2
# abcd
# 
# e

クエリを処理する手順を説明すると次のようになります。

  • 1 番目のクエリでは、(1, 1) に b を書きこみカーソルを (1, 2) に動かします。
  • 2 番目のクエリでは、(1, 2) に c を書きこみカーソルを (1, 3) に動かします。
  • 3 番目のクエリでは、(1, 3) に d を書きこみカーソルを (1, 4) に動かします。
  • 4 番目のクエリでは、(1, 1) にカーソルを動かします。
  • 5 番目のクエリでは、はじめに (1, 1) に書かれた b と (1, 2) に書かれた c と (1, 3) に書かれた d を全て同時に右に 1 マス動かします。そして、(1, 1) に a を書きこみカーソルを (1, 2) に動かします。
  • 6 番目のクエリでは、(2, 1) にカーソルを動かします。
  • 7 番目のクエリでは、(3, 1) にカーソルを動かします。
  • 8 番目のクエリでは、(3, 1) に e を書きこみカーソルを (3, 2) に動かします。

image

Problem Statement

There is a text editor that can be regarded as a grid extending infinitely toward right and downward. The cell in the i-th row from the top and j-th column from the left of the editor is denoted by (i, j). Each cell can have a character written on it, or be empty; initially, all cells are empty.
The editor also has a marker called a cursor, which indicates the position where a character is inserted. The cursor is initially located at (1, 1).

You are to process Q queries in given order.
Each query is one of the following three types.

  • 1 c: Insert the character c at the current position of the cursor. Formally, perform the following procedure.
    • First, move all characters in the current cell of the cursor or in any cell to the right within the same row, one cell to the right, if any.
    • Next, write the character c onto the cell where the cursor is currently located at.
    • Finally, move the cursor one cell to the right.
  • 2: Move the cursor to the leftmost cell of the current row.
  • 3: Move the cursor to the leftmost cell of the row right below the current row.

Print the state of the editor after processing all the queries.

Constraints

  • 1 \leq Q \leq 1.5 \times 10^6
  • c is a lowercase English character.

Input

The input is given from Standard Input in the following format, where \mathrm{query}_i denotes the i-th query:

Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Output

  • Let cell (H, W) be the position of the cursor when all the queries are processed.
  • Let C_i be the number of characters in the i-th row from the top.
  • Let S_{i, j} be the character written on cell (i, j).

Print (H+1) lines in the following format. (Note that C_i = 0 may apply for some rows.)
Beware that the second and succeeding lines must be preceded by # and a space.

H W
# S_{1, 1}S_{1, 2} \dots S_{1, C_1}
# S_{2, 1}S_{2, 2} \dots S_{2, C_2}
\vdots
# S_{H, 1}S_{H, 2} \dots S_{H, C_H}

Sample Input 1

8
1 b
1 c
1 d
2
1 a
3
3
1 e

Sample Output 1

3 2
# abcd
# 
# e

The query is processed as follows.

  • In the 1-st query, write b onto (1, 1), and move the cursor to (1, 2).
  • In the 2-nd query, write c onto (1, 2), and move the cursor to (1, 3).
  • In the 3-rd query, write d onto (1, 3), and move the cursor to (1, 4).
  • In the 4-th query, move the cursor to (1, 1).
  • In the 5-th query, simultaneously move the following characters one cell to the right: b written on (1, 1), c written on (1, 2), and d written on (1, 3). Then, write a onto (1, 1), and move the cursor to (1, 2).
  • In the 6-th query, move the cursor to (2, 1).
  • In the 7-th query, move the cursor to (3, 1).
  • In the 8-th query, write e onto (3, 1), and move the cursor to (3, 2).

image