Hints → https://atcoder.jp/contests/arc153/editorial/5524

[1] Reduction to a single dimension

The operation in the problem has the following characteristics:

• two characters in the same row will remain in the same row;
• two characters in the same column will remain in the same column.

Thus, one can solve the problem by computing the following for each \(i\) and \(j\).

• To which row will the characters that start in the \(i\)-th row go?
• To which column will the characters that start in the \(j\)-th column go?

These two problems can be solved separately.

Although the problem takes place in a two-dimensional grid, each of these two problems deals with a one-dimensional array, as follows.

1D problem

We have a 1D array of length \(N\): \(A = (1, 2, \ldots, N)\).

We perform the following operation \(Q\) times: given \(a\) such that \(1\leq a \leq N-1\), reverse the first \(a\) terms of \(A\) and the last \(N-a\) terms of \(A\).

Find the array after the operations.

Let us explain how to solve this problem.

[2] The characteristics of the obtained sequence

From \((1, 2, \ldots, N)\), one can only obtain some particular sequences (not all permutations of \(1, 2, \ldots, N\)) by repeatedly reversing the first \(a\) terms and the last \(N-a\) terms. This can be shown using the following property of the operation:

For the 1D array of length \(N\), let us consider that the leftmost and rightmost terms are also adjacent, in addition to the usual adjacency. Then, two terms that are adjacent before the operation will also be adjacent after the operation.

The proof is easy and omitted. From this, there are only \(2N\) arrays that can result from repeating the operation: the circular shifts of \((1, 2, \ldots, N)\) and its reversal.

For instance, if \(N=5\), the following \(10\) arrays can be obtained:

\[(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).\]

For these sequences, one can restore the positions of all elements from, for example, the positions of \(1\) and \(2\).

Therefore, the 1D problem can be solved in \(O(N+Q)\) time by tracing the positions of \(1\) and \(2\) through the operations. The original problem can be solved in \(O(HW+Q)\) time.