Hints: https://atcoder.jp/contests/arc176/editorial/9845

Let \(S_k\) be the set of cells \((i,j)\) such that \(i + j = k \bmod N\). Now, if we select \(M\) distinct cells from \(S_k\) and write \(1\) in those cells, the row sums and the column sums will be \(M\).

All that remains is to include \(S_{A_i + B_i \bmod N}\) for each \(i\), which can be easily achieved. Note that if there are duplicates among \(A_i + B_i \bmod N\), it is necessary to add \(S_k\) accordingly.

Sample Implementation