この問題は，ランダムアクセスが定数時間で可能な deque（両端キュー）を用いることで，問題文の通りにシミュレーションして解くことができます．

具体的には，次のような処理を行います．

• deque として \(\mathrm{dq}\) を用意する．（\(\mathrm{dq}\) の先頭から \(i\) 番目の要素を，以後\(\mathrm{dq}[i]\) と表記する）
• まず，\(\mathrm{dq}\) の後ろに \(A_1, A_2, \dots, A_N\) をこの順に追加する．
• 各種クエリに対しては，次のように処理する．
  • \(T=1\) のクエリに対しては，\(\mathrm{dq}[x]\) と \(\mathrm{dq}[y]\) を入れ替える．
  • \(T=2\) のクエリに対しては，\(\mathrm{dq}\) の一番後ろの要素を削除し，それを一番先頭に追加する．
  • \(T=3\) のクエリに対しては，\(\mathrm{dq}[x]\) の値を出力する．

この方法を用いると，各クエリにすべて定数時間で答えられるので，全体での計算量は \(O(N+Q)\) となります．

ランダムアクセスが定数時間で可能な deque は，deque を配列の形で保持し，リングバッファなどの手法を用いることで実装できます．さらに，C++ では，標準で実装されている deque におけるランダムアクセスが \(O(1)\) で可能なので，標準ライブラリをそのまま用いることができます．

実装例（C++）