006 - 品質管理

会津タカダ市が生産販売する布製コースターは、対称なデザインでとても美しいことで知られている。会津タカダ市では品質管理の一環として、製造ラインにカメラを設置し、各コースターを撮影して得られた画像が対称になっているかを自動で検証している。各コースターはN×Nピクセルの正方形の白黒画像として表される。各ピクセルは白または黒の画像に対応して、0または1の値をとる。
この度、生産ラインの機器更新にともなって、画像解析システムのソフトウェアを更新することになった。新システムでは、通信データ量を削減する工夫がなされ、以下の方法でカメラから解析システムにデータが送られてくる。

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

課題

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

入力

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

C N
p11 p12…p1N
p21 p22…p2N
:
pN1 pN2…pNN

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

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

D
r1 c1
r2 c2
:
rD cD

１行目に変化したピクセルの数D(0≦D≦100)が与えられる。続くD行に変化したピクセルの行と列の番号をそれぞれ表すr_iとc_i(1≦r_i,c_i≦N)が与えられる。diff_iの中に、同じ位置は２回以上与えられない。

時間制限

入力に対して、実行時間が５秒を超えてはならない。

出力

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

入出力例

入力例１

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

出力例１

3

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

入力例２

1 6
000000
000000
010010
010010
000000
000000

出力例２

1

入力例３

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

出力例３

2