各操作はアフィン変換です。例えば直線 \(x=p\) で対称に移す変換は以下のように表すことができます。

\( \begin{pmatrix} -1 & 0 & 2p \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} x \\ y \\ 1 \end{pmatrix}= \begin{pmatrix} 2p-x \\ y \\ 1 \end{pmatrix} \)

したがって、変換行列の累積積を予め計算しておくことで、各クエリに \(O(1)\) で答えることができます。 累積積の前計算に \(O(M)\) かかるので計算量は \(O(N+M+Q)\) になります。

よりナイーブには、「各操作終了時に(0,0),(1,0),(0,1)がそれぞれどこに移ったか」という情報さえわかっていれば、任意の点に対して操作終了後の座標を \(O(1)\) で求めることができます。実際に3点に対する操作を事前にシミュレーションしておくことで、計算量は \(O(N+M+Q)\) になります。