012 - 星座を探して

問題

ニッシンカン天文台では、イヅア地方で観測できる星座を分類することにした。それぞれの星座は、星座を構成する星を表す座標平面上の点の集合で表されている。これらの星座のうち、以下の３種類の操作を、それぞれ任意の回数組み合わせて行うことで一致させることができる星座は、同じ種類の星座と考えることにした。

• 平行移動
• 原点を中心とした回転
• 原点を中心として、正の係数を倍率とした拡大・縮小

ニッシンカン天文台の分類業務のために、あなたはそれぞれの星座について、同じ種類の星座がどのくらいあるのかをリストにまとめることにした。

星座の情報が与えられたとき、各星座について同じ種類の星座がいくつあり、何番目の星座が同じ種類の星座かを求めるプログラムを作成せよ。

入力

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

$N$ $M$
$con_1$
$con_2$
:
$con_N$

１行目に星座の数$N$ ($1 \leq N \leq 1,000$)と各星座を構成する点の数$M$ ($1 \leq M \leq 1,000$)が与えられる。続く$N$行に、各星座の情報$con_i$が、以下の形式で与えられる。

$x_1$ $y_1$ $x_2$ $y_2$ ... $x_M$ $y_M$

$x_i,y_i$ ($-1,000 \leq x_i,y_i \leq 1,000$)は、この星座を構成する$i$番目の点のx,y座標である。ただし、各星座について、同じ座標をもつ点は与えられない($i \ne j$について、$x_i \ne x_j$または$y_i\ne y_j$）。

出力

出力は$N$行である。星座$i$について、同じ種類の星座の数と、同じ種類の星座の番号を$i$行目に出力する。ただし、同じ種類の星座が複数ある場合、番号は昇順で出力する。

入出力例

入力例

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

出力例

2 3 4
0
2 1 4
2 1 3