Latin Square

Observation 1: the matrix is secretly a set of 3D points

The whole trick is to stop staring at the matrix like it owes you money.

For each cell, use zero-based coordinates and define a point $(x,y,z),$ where:

• $x$ = row index,
• $y$ = column index,
• $z = a_{x,y}-1$.

So the matrix becomes a set of $n^2$ points in $[0,n-1]^3$.

Why is this useful? Because the Latin square condition says:

• in each row, every value appears exactly once,
• in each column, every value appears exactly once.

So if you know any two of the three coordinates in the right way, the third is uniquely determined. That’s exactly why the inverse operations behave so cleanly.

---

Observation 2: every operation is just a shift or a swap of coordinates

Let’s write the six operations on a single point $(x,y,z)$.

Simple shifts

These are immediate: $R:(x,y,z) \to (x,y+1,z),$ $L:(x,y,z) \to (x,y-1,z),$ $D:(x,y,z) \to (x+1,y,z),$ $U:(x,y,z) \to (x-1,y,z),$ all modulo $n$.

Row inverse: I

If originally in row $x$ we have value $z$ at column $y$, then after replacing that row permutation by its inverse, the new row has value $y$ at column $z$.

So: $I:(x,y,z) \to (x,z,y).$

That is, I simply swaps column and value.

Column inverse: C

If originally in column $y$ we have value $z$ at row $x$, then after inverting that column permutation, the new column has value $x$ at row $z$.

So: $C:(x,y,z) \to (z,y,x).$

That is, C swaps row and value.

---

Observation 3: after any prefix, the transformation has a tiny state

Since every operation is only:

• shifting one current coordinate by $\pm1$, or
• swapping two current coordinates,

we never get anything complicated like $x+y$ or $2z-x$.

After any prefix of operations, each current coordinate is still of the form $\text{current coordinate} = \text{one original coordinate} + \text{constant} \pmod n.$

So we maintain:

• a permutation $p$ of $\{0,1,2\}$,
• an offset array $add[3]$,

such that for an original point $orig = (orig_0,orig_1,orig_2) = (x,y,z),$ its current coordinates are $cur_k = orig_{p_k} + add_k \pmod n \qquad (k=0,1,2).$

Here:

• $k=0$ means current row,
• $k=1$ means current column,
• $k=2$ means current value.

Initially, $p = [0,1,2], \qquad add = [0,0,0].$

---

Observation 4: updating the state is trivial

Now process the operation string left to right.

Shifts

They modify the corresponding current axis:

• R: increment $add[1]$
• L: decrement $add[1]$
• D: increment $add[0]$
• U: decrement $add[0]$

all modulo $n$.

Swaps

Since I swaps current column and current value, we do: $swap(p_1,p_2), \quad swap(add_1,add_2).$

Since C swaps current row and current value, we do: $swap(p_0,p_2), \quad swap(add_0,add_2).$

That second part — swapping the offsets too — is the subtle bit. If you forget it, the solution explodes in a totally predictable and embarrassing way.

---

Why this invariant is correct

Induction, nice and clean.

Assume after some prefix we have $cur_k = orig_{p_k} + add_k \pmod n.$

• A shift like R changes only current column by $+1$, so only $add[1]$ changes.
• A swap like I exchanges the meaning of current column and current value, so the formulas for coordinates $1$ and $2$ are exchanged. That means both $p$ and $add$ swap in those positions.

So the same form is preserved after every operation. End of story.

---

Reconstruction

After processing all $m$ operations, we know the final transform.

For every original cell $(i,j)$ with value $a_{i,j}$, set $orig = (i, j, a_{i,j}-1).$ Then compute: $d_k = orig_{p_k} + add_k \pmod n \,\,\text{for } k=0,1,2.$

Now $(d_0,d_1,d_2)$ is the final row, column, and value of that entry, so: $ans[d_0][d_1] = d_2 + 1.$

Because the transformation is bijective, every final cell gets filled exactly once.

---

Complexity

For each test case:

• processing the string: $O(m)$,
• rebuilding the answer: $O(n^2)$.

So total complexity is $O(n^2 + m)$ per test case, with memory $O(n^2).$

Given the constraints, this is easily fast enough.

---

Final takeaway

This problem looks like cursed matrix simulation, but it’s really just coordinate geometry over $\mathbb{Z}_n$.

You’re composing operations from $S_3 \ltimes (\mathbb{Z}_n)^3,$ which sounds fancy, but the code is just:

• keep a permutation of 3 axes,
• keep 3 offsets,
• rebuild once at the end.

That’s the whole scam.