50004. Final Prob. 4: 序列操作

I'm a slow walker, but I never walk backwards.

現在有一個$1$到$N$的排列$a_1,a_2,\cdots,a_N$,調皮的彥仁接下來會依序做$Q$件事,每件都是下列兩種的其中之一:

(1) 將這個排列的某兩段連續區間交換

(2) 問你某個數字的左邊或右邊是多少

當然彥仁十分調皮,所以他有可能會問你最左邊的數的左邊是多少,或者最右邊的數的右邊是多少,這時候你就必須meow一下來滿足他。請你寫一個程式來回答彥仁的問題。

Input

輸入的第一列為一個正整數$T$,代表接下來有 $T$ 筆測資。

每筆測資的第一列為一個正整數$N$,第二列為 $N$ 個由空白隔開的正整數 $a_1,a_2,\cdots ,a_N$,第三列為一個正整數 $Q$,接下來的 $Q$ 列為以下兩種格式中的其一:

(1) $1\ x_1\ y_1\ x_2\ y_2$ 代表彥仁將某兩段連續區間交換,其中左邊的是從數字 $x_1$ 到數字 $y_1$,右邊的區間是從數字 $x_2$ 到數字 $y_2$。

(保證輸入都是合法的,即若用 $pos(z)$ 表示 $z$ 是從左數來第 $pos(z)$ 個,則有 $pos(x_1)\leq pos(y_1)\lt pos(x_2)\leq pos(x_2)$。)

(2) $2\ x\ d$ 代表彥仁問你數字 $x$ 的左邊或右邊的數字是多少, $d=0$ 代表 問左邊, $d=1$ 代表問右邊。

Output

對於彥仁問你的每個問題,輸出一個佔一列的正整數,代表這個問題的答案。

(如果 $d=0$ 但 $x$ 是最左邊的數,或者 $d=1$ 但 $x$ 是最右邊的數,請輸出一列 meow)。

Subtasks/Constraints

對於所有測資,$1\leq T\leq 5, 1\leq Q\leq10^ 6, 2\leq N\leq 10^ 6$。

Subtask 1 ( 5 分) : 彥仁不會做交換區間這個動作。

Subtask 2 ( 5 分) : 彥仁每次只會交換兩個只有一數的區間,即 $x_1=y_1, x_2=y_2$。

Subtask 3 ( 5 分) : $N,Q\leq 1000$

Subtask 4 (10 分) : 沒有額外限制條件

Sample Input

2
6
3 1 4 2 5 6
6
2 4 0
1 3 4 5 6
1 6 6 3 1
2 5 1
2 2 0
2 6 1
5
1 2 3 5 4
6
1 1 2 3 5
1 1 1 4 4
2 3 1
1 3 4 2 1
2 1 0
2 2 0

Sample Output

1
3
1
4
5
2
meow

Discussion