各 \(1 \le i \le H\) に対して、マス \((i, j)\) が壁でない \(1 \le j \le W\) の集合を \(Rs_i\) 、各 \(1 \le j \le W\) に対して、マス \((i, j)\) が壁でない \(1 \le i \le H\) の集合を \(Cs_j\) とします。はじめは全ての集合は空です。各クエリでの操作は以下のようになります。

• \((R, C)\) が壁であるときは、\(Rs_R\) に \(C\) を追加して \(Cs_C\) に \(R\) を追加する。
• そうでないときは、その上下左右で壁がある端のマスを探します。その先がグリッドの外でなければそのマスを \((i,j)\) としたとき \(Rs_i\) に \(j\) を、\(Cs_j\) に \(i\) を追加します。端のマスは、\(Rs_R\) や \(Cs_C\) を二分探索することで探すことができます。

この解法の計算量は \(O(H+W+Q \log^2(max(H,W)))\) です。

実装例(PyPy): https://atcoder.jp/contests/abc370/submissions/57532668