theater

注意

入出力の量が多くなることがあるため、高速な入出力を行うことを推奨します。
例:

• python
• c++

問題文

あなたは、とある劇場の観客の座席割り当てを決定する仕事を行っています。
劇場は $H$ 行 $W$ 列の座席からなり、今回の公演には $N$ 人の観客が訪れます。 観客 $i$ の身長は $A_i$ です。

観客が「快適に観る」ことができるのは、次の条件を満たすとき、かつそのときに限ります：

• 同じ列において、自分より前の行にいる任意の観客の身長が自分より低い。

あなたは、それぞれの観客をいずれかの座席に割り当てるとき、「快適に観る」ことのできる人数を最大化したいと考えています。 そのときの「快適に観る」ことのできる人数と、座席表の一例を出力してください。 ( $N$ 人の観客全員をいずれかの座席に割り当てる必要があります。)

座席表は次の形式で表されます：

• 前から $i$ 行目、左から $j$ 列目の座席を $S_{i,j}$ とする。
• $S_{i,j} = -1$ なら空席、$S_{i,j} = k$ なら観客 $k$ をその座席に割り当てたことを表す。

答えが複数考えられる場合、どれを出力しても正解とみなされます。

制約

• $1 \leq H \leq 2 \times 10^5$
• $1 \leq W \leq 2 \times 10^5$
• $1 \leq HW \leq 2 \times 10^5$
• $1 \leq N \leq HW$
• $1 \leq A_i \leq 10^9 \, (1 \leq i \leq N)$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

出力

1 行目に「快適に観る」ことのできる人数を出力してください。 続く $H$ 行に座席表を以下の形式で出力してください。

入力例 1

2 2
3
1 5 2

出力例 1

3
1 3
2 -1

このように割り当てることで $3$ 人全員が「快適に観る」ことができます。

入力例 2

3 2
6
1 1 1 1 1 1

出力例 2

2
5 4
6 3
2 1

どのように割り当てても $3$ 人以上が「快適に観る」ことはできません。

入力例 3

3 1
1
1000000000

出力例 3

1
-1
-1
1