Quality Management

Time Limit : 2 sec, Memory Limit : 262144 KB

品質管理

会津タカダ市が生産販売する布製コースターは、対称なデザインでとても美しいことで知られている。会津タカダ市では品質管理の一環として、製造ラインにカメラを設置し、各コースターを撮影して得られた画像が対称になっているかを自動で検証している。各コースターは N × N ピクセルの正方形の白黒画像として表される。各ピクセルは白または黒の画像に対応して、0 または 1 の値をとる。

この度、生産ラインの機器更新にともなって、画像解析システムのソフトウェアを更新することになった。新システムでは、通信データ量を削減する工夫がなされ、以下の方法でカメラから解析システムにデータが送られてくる。

  • ラインに流れてくる最初のコースターの情報は、N × N ピクセルの画像としてシステムに送られてくる。
  • 2枚目以降のコースターの情報は、1つ前に送られた画像との差分だけが送られてくる。差分は、「0 から 1 」または「1 から 0 」へと変化したピクセルの位置の集合として与えられる。

C 枚のコースターについて、1枚目の画像のピクセル情報と続く C - 1 枚分の差分情報を入力し、上下対称かつ左右対称となっているコースターの枚数を報告するプログラムを作成せよ。

Input

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

C N
p11p12...p1N
p21p22...p2N
:
pN1pN2...pNN
diff1
diff2
:
diffC−1

1行目にコースターの枚数 C (1 ≤ C ≤ 10000) と画像の縦と横のピクセル数 N (2 ≤ N ≤ 1000 かつ N は偶数) が与えられる。2行目から N + 1 行目に最初のコースターの画像のピクセルを表す N行 × N 列の数字 pij (pij は 0 または 1)が与えられる。

N + 2 行目以降に、2枚目以降のコースターの情報を表す差分 diffi が次の形式で与えられる。

D
r1 c1
r2 c2
:
rD cD

1行目に変化したピクセルの数 D (0 ≤ D ≤ 100) が与えられる。続くD 行に変化したピクセルの行と列の番号をそれぞれ表す rici (1 ≤ ri, ciN) が与えられる。diffi の中に、同じ位置は2回以上与えられない。

Output

上下対称かつ左右対称となっているコースターの枚数を1行に出力する。

Sample Input 1

7 8
00100000
00011000
10111101
01100110
01000110
10111101
00011000
00100100
2
5 3
1 6
1
6 8
3
6 8
3 3
3 6
2
6 3
6 6
0
2
3 8
6 8

Sample Output 1

3

入力例1のコースターの画像を以下に示す。この場合、2枚目、5枚目、6枚目のコースターが上下対称かつ左右対称となるため、3と報告する。


Sample Input 2

1 6
000000
000000
010010
010010
000000
000000

Sample Output 2

1

Sample Input 3

2 2
00
00
4
1 1
1 2
2 1
2 2

Sample Output 3

2

Source: PC Koshien 2015 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2015-9-12
http://web-ext.u-aizu.ac.jp/pc-concours/