#1342. 异或双端队列

在这题你需要维护一个支持异或变换操作的双端队列。

我们定义队列中第$i+1$个元素为$a_i$，队首位置为$a_0$，队尾位置为$a_{n-1}$。你将读取并执行以下六种操作：

$\text{1 x}$: 在队首插入整数$x$，换句话说，队列将变成$x,a_0,a_1,\dots,a_{n-1}$

$\text{2}$: 输出并弹出队首，换句话说，你需要输出$a_0$，然后将队列置为$a_1,a_2,\dots,a_{n-1}$。保证$n \geq 1$。

$\text{3 x}$: 在队尾插入整数$x$，换句话说，队列将变成$a_0,a_1,\dots,a_{n-1},x$

$\text{4}$: 输出并弹出队尾，换句话说，你需要输出$a_{n-1}$，然后将队列置为$a_0,a_1,\dots,a_{n-2}$。保证$n \geq 1$。

$\text{5 x}$: 输出$a_x$，保证$0 \leq x < n$。

$\text{6 x}$: 对队列进行$x$异或变换。$x$异或变换定义为，设原队列为$a$，变换后队列为$b$，则$b_i=a_{i \oplus x}$。其中，$\oplus$为异或运算，保证对于输入的$x$，变换后的序列也是合法的，即$\forall 0 \leq i < n,0 \leq x \oplus i < n$。

第一行一个正整数$q$ $(1 \leq q \leq 5 \times 10^5)$，为操作次数。

下面 $q$ 行，每行有若干个整数，含义如题意所述。

对于所有操作，保证$0 \leq x \leq 10^9$。

对于每一个操作2、4和5，输出答案。

样例输入

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

样例输出

1
3
1
2
3

每轮操作完毕的队列情况：

$\text{6 6}$: $[]$

$\text{1 2}$: $[2]$

$\text{3 1}$: $[2,1]$

$\text{1 3}$: $[3,2,1]$

$\text{3 4}$: $[3,2,1,4]$

$\text{6 2}$: $[1,2,3,4]$

$\text{2}$: $[2,3,4]$

$\text{4}$: $[2,3]$

$\text{6 1}$: $[3,2]$