まず、不変量を見つけましょう。

• 各列 \(j\) に対し、その列の黒マスの数の偶奇を \(p_j\) とします。これは不変量です。
• 各行 \(i\) に対し、\(s_i\) を以下のように定めます。\(s_i\) は長さ \(3\) の文字列で、その各文字は 0 か 1 です。\(k\) 文字目は \((i, k), (i, k+3), (i, k+6), \cdots\) のうちの黒マスの数の偶奇を表します。すると、この行に関与する操作を行うたびに、\(s_i\) の三文字全てが反転します。したがって、例えば、\(s_i\) がはじめ 010 であるなら、101 には変えられますが、他の文字列には変えられません。

上記の「不変量」が十分であることが証明できます。すなわち、これらが等しいような二つの状態（グリッド内の黒マスの集合）があるとき、一方をもう一方に変換することができます。なぜなら、サイズ \(999999999 \times 999999998\) の部分長方形内の色を一致させることが（適切な順番で一マスずつ色を揃えることで）常に可能であり、上記の不変量から残りのマスの色が一意に定まるからです。

次に、\(p_j\) と \(s_i\) の値が与えられたときに、黒マスの数として可能な最小値を求めましょう。

• \(t_k (1 \leq k \leq 3)\) を \(p_k, p_{k+3}, p_{k+6}, \cdots\) のうちの奇数の個数とし、\(S_k (1 \leq k \leq 3)\) を全ての \(i\) に対する \(s_{i,k}\) の和とします。このとき、\(t_k\) と \(S_k\) の偶奇は一致しなければなりません（そうでないと矛盾します）。偶奇が全て一致するなら、最適な黒マスの数は \(\sum \max \{ S_k, t_k \} \) です。

\(t_k\) の値は入力で与えられているため、行うべきことは \(S_k\) の値を（例えば 010 から 101 に）変えることで上記の値を最小化することです。

まとめると、

• \(3\) 次元空間内の何本かのベクトルが与えられます。これらはそれぞれ \((0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0)\) のいずれかです。
• これらに対し、\((0, 0, 0) \rightarrow (1, 1, 1), (0, 0, 1) \rightarrow (1, 1, 0), (0, 1, 0) \rightarrow (1, 0, 1), (1, 0, 0) \rightarrow (0, 1, 1)\) という変更を行うことができます。
• 三つの定数 \(x, y, z\) が与えられます。
• 変更を行った後の全てのベクトルの和を \((X, Y, Z)\) とします。このとき、\(x \equiv X, y \equiv Y, z \equiv Z \pmod{2}\) を満たしつつ \(\max \{ x, X \} + \max \{ y, Y \} + \max \{ z, Z \}\) を最小化してください。

この問題を解くには、まず各種類の変更を行う回数の偶奇を固定します（もし奇数回の変更を行うことにするなら、ここで一度行います）。すると、これ以降は二種類以上の操作を行うのは決して最適とならないことに注意して、一種類以下の操作を行う場合を全て試せます。