本問は多倍長整数とビット演算を用いると簡単に実装することができます。

（ヒント）

• 入力を \(2\) 進法と思って受け取ります
• \(2\) 次元なので、（\(2\) 進法で表された）整数がいくつかあると考えることもできますが
• 上下方向もビットシフトで表すと、全体でひとつの整数とみることができます（少し余裕をもって、例えば下に一段下りると \(2^{20}\) 倍にするなど）
• 「いずれかが黒のとき黒」というのは、ビット演算の or に対応します
• 上下・左右の平行移動はビットシフトに対応します
• 「平行移動して一致する」ことの判定は、適当なビットシフトを施して一致するかどうかを判定すれば良いです
• あるいは（\(2\) 進法における）末尾の \(0\) を消したもの同士で判定すると、計算量・実装量ともに小さくできます
• a の末尾の \(0\) を消したものは a // (a & -a) で計算できます

AC コード（PyPy 3）