ヒント → https://atcoder.jp/contests/arc153/editorial/5482

[1] 1 次元の問題への帰着

本問題の操作には，次の特徴があります：

• 同じ行にある \(2\) つの文字は，操作後でも同じ行にある
• 同じ列にある \(2\) つの文字は，操作後でも同じ列にある

したがって，本問は各 \(i, j\) に対して次を計算することによって解くことができます．

• 最初に \(i\) 行目にあった文字が，操作後にどの行に移ったか
• 最初に \(j\) 列目にあった文字が，操作後にどの列に移ったか

これら行・列の問題はそれぞれ独立に解くことができます．

本問は元々は \(2\) 次元のグリッドの問題ですが，行・列の問題は次のような \(1\) 次元配列の問題です：

1 次元の問題

長さ \(N\) の \(1\) 次元配列 \(A = (1, 2, \ldots, N)\) がある．

次の操作を \(Q\) 回行う：\(1\leq a \leq N-1\) を満たす \(a\) が与えられるので，\(A\) の先頭 \(a\) 項および末尾 \(N-a\) 項を逆順に並べ替える．

操作後の配列の状態を求めよ．

以下ではこの問題を解く方法を解説します．

[2] 操作によって得られる数列の特徴

\((1, 2, \ldots, N)\) に対して，「先頭 \(a\) 項，末尾 \(N-a\) 項を逆順に並べ替える」操作を繰り返すことで得られる数列は，（単に \(1, 2, \ldots, N\) の並べ替えであるという以上に）特殊なものに限られます．これは，操作の次の性質から示すことができます：

長さ \(N\) の \(1\) 次元配列について，通常の隣接関係に加えて左端と右端も「隣接している」と考えることにする．このとき，操作前に隣接していた \(2\) 項は操作後にも隣接している．

証明は容易なので省略します．したがって，\((1, 2, \ldots, N)\) に対して操作を繰り返した結果は，\((1, 2, \ldots, N)\) やその逆順を巡回シフトして得られる高々 \(2N\) 通りに限定されます．

例えば \(N=5\) ならば，次の \(10\) 通りのいずれかです：

\[(1,2,3,4,5),\qquad (2,3,4,5,1),\qquad(3,4,5,1,2),\qquad(4,5,1,2,3),\qquad(5,1,2,3,4),\]

\[(1,5,4,3,2),\qquad (2,1,5,4,3),\qquad(3,2,1,5,4),\qquad(4,3,2,1,5),\qquad(5,4,3,2,1).\]

また，これらの数列について，例えば \(1\) と \(2\) の位置が分かれば全ての要素の位置を復元することが可能です．

したがって，「\(1\) 次元の問題」は，各操作において \(1, 2\) が何番目に移されるかを順に計算していくことで，\(O(N+Q)\) 時間で解くことができます．元の問題は \(O(HW+Q)\) 時間で解くことができます．