## Chocological

令初始状态为 $S$，最终状态为 $T$，如果它们每一列的人数都相等，那么就直接做完了。

否则，考虑倒着做。操作改为：每列的人的位置可以在同一列内随便移动；如果一行中所有人都在最左/最右边，那么可以在同一行内任意重排。

枚举最后一步行操作。由于两行是等价的，所以不妨设是对第一行的操作。

- 假设 $j$ 是使得 $(1,j),(2,j)$ 都有人的最大整数，如果 $T$ 中 $(1,1),(1,2),\ldots,(1,j)$ 都有人，那么最后一步就可能是第一行左对齐操作（因为 $j$ 之后列的人可以都安排到第二行，从而 $T$ 中第一行的人是个前缀）。

最后一步是第一行右对齐的情况类似。

如果最后一步可以是任何一种对齐，那么方案可以贪心地构造：

将 $T$ 中所有最后在第二行的人按照到两边的最小距离（即 $(2,j)$ 处到两边的最小距离是 $\min(j,n-j+1)$）从大到小排序，设列号分别为 $c_1,\ldots,c_t$。那么 $S$ 只需要在第一行做对齐操作，并且依次满足 $(2,c_1),\ldots,(2,c_t)$ 的需求即可。如果当前考虑到 $(2,c_i)$ 的需求，如果 $S$ 当前在 $c_i$ 列已经有一个人，那么直接安排过去即可，否则就要先在第一行对齐到合适的角落（如果 $c_i<n/2$ 就左对齐，否则右对齐），然后将 $(1,c_i)$ 安排到 $(2,c_i)$。如果对齐之后 $(1,c_i)$ 也没有人，那么无解。