Subtask 1

Suppose our array of swaps were static. How would we go about solving this? Well, we can simply take the queried swap list and apply our swaps starting from the back. So if we want to produce ~(3, 1, 2)~ and our swap list is ~((2, 3), (2, 1))~, then first we get ~(1, 3, 2)~, and then ~(1, 2, 3)~, so we output ~(1, 2, 3)~.

This simulation is sufficient for this subtask.

Let ~Q_P~ be our count of type ~3~ queries:

Time Complexity: ~\mathcal O(NQQ_P + Q)~

Subtask 2

For this subtask, we need a slightly more efficient way of producing the final array. The idea is to use a list mapping query permutation indices to output indices. When we want to add a swap to the front of the list, well, given our current mapping, we can simply swap m[x] and m[y], since we just need to swap where those elements end up.

However, for adding a swap to the end of the list, we need to pretend that items x and y have been swapped this whole time. To do that, we should swap the places in a where x and y appear. This is the same as pretending that they were always swapped. To do this, we need to maintain a pos array, containing the index in a where i appears. Implementation details are left as an exercise to the reader.

Time Complexity: ~\mathcal O(NQ_P + Q)~