Tournament Cards

問題文

$2^N$人が参加するトーナメントがあります。このトーナメントでは以下の形式で試合を行います。

• 第 1 ラウンドでは、1 と 2、3 と 4、…　が試合を行う。
• 第 2 ラウンドでは、(1 と 2 の勝者) と (3 と 4 の勝者), (5 と 6 の勝者) と (7 と 8 の勝者), …　が試合を行う。
• 第 3 ラウンドでは、((1 と 2 の勝者) と (3 と 4 の勝者) の勝者) と ((5 と 6 の勝者) と (7 と 8 の勝者) の勝者), ((9 と 10 の勝者) と (11 と 12 の勝者) の勝者) と ((13 と 14 の勝者) と (15 と 16 の勝者) の勝者), …　が試合を行う。
• 以下同様に第 $N$ ラウンドまで行う。

はじめ、人 $i(1 \leq i \leq 2^N)$ は $A_i$ が書かれたカードを持っています。$X$が書かれたカードを持っている人 $i$ と$Y$が書かれたカードを持っている人 $j$ が対戦し、人 $i$ が勝利した場合、以下のことを実行します。

• 現在人 $i$ と人 $j$ が持っているカードを処分する。
• 人 $i$ は $(2X+Y) \ \mathrm{mod} \ M$が書かれたカードをもらう。

これ以外にカードの受け渡しをすることはできません。

$1 \leq i \leq 2^N$ について、人 $i$が優勝したとき、人 $i$ が持っている可能性のあるカードの数をすべて求めてください。

制約

• $1 \leq N \leq 12$
• $1 \leq M \leq 100$
• $0 \leq A_i < M$
• 入力される値はすべて整数

入力

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

出力

$i$ 行目に人 $i$ が持っている可能性のあるカードの数の種類数 $C_i$ とカードに書かれた数 $B_{i,j}$ を空白区切りで出力せよ。$B_{i,j}$は昇順で出力すること。

サンプル 1

入力

2 39
2 24 0 15

出力

2 8 32
2 13 37
2 2 19
2 10 32

下図のようにトーナメントが進行した場合、人1は8のカードを持っています。

サンプル 2

入力

5 5
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4

出力

4 0 1 3 4
4 0 1 3 4
4 0 1 3 4
4 0 1 3 4
4 0 1 3 4
4 0 1 3 4
4 0 1 3 4
4 0 1 3 4
3 0 3 4
3 0 3 4
3 0 3 4
3 0 3 4
2 3 4
2 3 4
1 4
1 1
4 0 1 3 4
4 0 1 3 4
4 0 1 3 4
4 0 1 3 4
4 0 1 3 4
4 0 1 3 4
4 0 1 3 4
4 0 1 3 4
4 0 1 3 4
4 0 1 3 4
4 0 1 3 4
4 0 1 3 4
4 0 1 3 4
4 0 1 3 4
4 0 1 3 4
4 0 1 3 4

サンプル 3

入力

5 5
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4

出力

1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2