#include using namespace std; // 全ての合法な操作を列挙し、盤面全体に対して F_2 上の掃き出し法を行う。 // 操作数 Q = N(N-1)(N-2)/6、ベクトルの次元 D = N^2。 // 最悪計算量は O(Q D^2) = O(N^7)。大きな入力では TLE を想定する。 // ベクトルは非零成分の添字を昇順に保持し、密行列の一括確保を避ける。 // メモリ計算量の最悪上界は、復元用の記録を含めて O(D^2) = O(N^4)。 struct Operation { int k, r, c; }; struct BasisRecord { vector cells; Operation operation; vector dependencies; }; vector xor_vectors(const vector& a, const vector& b) { vector result; result.reserve(a.size() + b.size()); set_symmetric_difference(a.begin(), a.end(), b.begin(), b.end(), back_inserter(result)); return result; } class LinearBasis { vector pivot; vector records; public: explicit LinearBasis(int dimension) : pivot(dimension, -1) {} void add(vector cells, Operation operation) { vector dependencies; while (!cells.empty()) { int position = cells.front(); int id = pivot[position]; if (id == -1) { pivot[position] = static_cast(records.size()); records.push_back({move(cells), operation, move(dependencies)}); return; } cells = xor_vectors(cells, records[id].cells); dependencies.push_back(id); } } bool solve(vector target, vector& answer) const { vector selected(records.size(), 0); while (!target.empty()) { int id = pivot[target.front()]; if (id == -1) return false; target = xor_vectors(target, records[id].cells); selected[id] ^= 1; } // 各基底は、追加時の元の操作と、それ以前の基底の XOR である。 // 逆順に展開して、実際に行う操作を復元する。 for (int id = static_cast(records.size()) - 1; id >= 0; --id) { if (!selected[id]) continue; answer.push_back(records[id].operation); for (int dependency : records[id].dependencies) { selected[dependency] ^= 1; } } return true; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; if (!(cin >> n)) return 0; vector target; for (int r = 0; r < n; ++r) { string row; cin >> row; for (int c = 0; c < n; ++c) { if (row[c] == '#') target.push_back(r * n + c); } } LinearBasis basis(n * n); for (int k = 1; k <= (n - 1) / 2; ++k) { for (int r = k; r < n - k; ++r) { for (int c = k; c < n - k; ++c) { vector cells; cells.reserve(4 * k + 1); for (int i = -k; i <= k; ++i) { cells.push_back((r + i) * n + c + i); if (i != 0) cells.push_back((r + i) * n + c - i); } sort(cells.begin(), cells.end()); basis.add(move(cells), {k, r + 1, c + 1}); } } } vector answer; if (!basis.solve(move(target), answer)) { cout << -1 << '\n'; return 0; } // 元の操作のうち、独立なものだけを各1回以下使うため、 // 操作数は高々 N^2 <= 250000 で、出力上限を満たす。 cout << answer.size() << '\n'; for (const Operation& operation : answer) { cout << operation.k << ' ' << operation.r << ' ' << operation.c << '\n'; } }