题目背景

中考的时候好像是没什么实感的，随随便便就考上了cdqz，考前几天晚上还在偷偷用itouch看修仙小说。

考上cdqz之后，我就天天去听OI课了，虽然不太听得懂，但反正也没事干。

当时听于神介绍数据结构，他大概是这么写的：

初级：树状数组，线段树

中级：平衡树，可并堆，莫队

高级：主席树，动态树

前沿：动态仙人掌

感觉有好多听起来就好厉害的树，还有“仙人掌”?数据结构真的是太厉害了（伏笔）！

那一年cdqz突然决定搞一个竞赛实验班，专门搞竞赛，由于挺不喜欢文化课的，所以我决定去参加。

想去竞赛班要经过一个学科夏令营的选拔，当时有个朋友f321dd觉得很毒瘤就跑路了，我还不太能理解，现在一定程度上能理解了。

这个学科夏令营大概就是每天请不同学科的竞赛老师来讲课，数学，物理都不太感兴趣，所以上课就很无聊，无所事事的，经常偷偷跑去机房写点代码。

仔细想想，我当时也对未来没什么打算，也谈不上有多热爱竞赛，也谈不上有多讨厌文化课，只是听说这个实验班好，可以上好大学，就去了，感觉和听到“学计算机挣钱多”而选择去计算机系的人差不多。

不过大家不都是这样的吗。

我最后进入了竞赛实验班，也认识了将要一起学习两年oi的大家，同时还进行了一次摸底考试，当时好像zms拿了350第一，我拿了310第二，记得我还用“动态spfa”水了个最短路题，看到AC的时候开心地叫了出来。

当时的竞赛组：

zms：初中同学，之前有提到，大家都叫他“小白”，感觉是一个挺稳重的人，是公认的我们那届OI最强选手，和yjq关系很好，被当时的我视为目标。

f321dd：初中同学，朋友，初中经常一起逃课打牌（自己搞了个叫化学杀的东西），感觉是个有趣的人。

grh：四中来的，高高瘦瘦的，喜欢看本子和动画片。

ziliuziliu：四中来的，瘦瘦的，喜欢玩坦克世界，练了KV3这条线，天天AP打不穿WZ111，水平不错。

cyz：喜欢玩坦克世界，印象中第一次看到他玩是在玩四号防空车，然后我觉得好玩也入坑了，水平挺高的，感觉经常无法理解他在想什么。

Flaze：女oier，感觉挺可爱的。

zyx：外地生，没学过oi。

cx：胖胖的，会写oj。

zqq：和Flaze一个初中的，感觉挺踏实的（最开始是这样的），什么知识点都会去学。

学长：

yjq：特别强，天天比赛早早做完AK。

Karl_duan：感觉一直在学习，很踏实努力。

zcy：特别会乱搞，平时也经常乱搞过题，NOIP暴力拿了600。

mhy：集训队学长，瘦瘦的。

写下这个回忆录的时候我还是挺有感触的，回忆起当时的事情让我很开心~

学oi的那一阵子虽然我很菜，天天被吊打，但无疑还是快乐的。

【记得配图，内容oj7】

由于这是Ynoi，不是出题人拿来写怀旧的文字的地方，所以你需要做一个数据结构题：

题目描述

有一个长度为 $n$ 的数组 $A$。下标从 $1$ 开始标号。有 $m$ 个操作需要处理，操作有如下四种：

1. 在数组 $A$ 的末尾添加一个数 $x$。
2. 输出 $\sum_{i=l}^{r}A_i$。
3. 将数组 $A$ 中的每个数 $A_i$ 都改为 $A_i\oplus x$。（$\oplus$ 表示异或操作）。
4. 将数组 $A$ 从小到大排序。

输入格式

第一行一个数 $n$ 表示 $A$ 的初始大小。
接下来一行 $n$ 个非负整数 $A_i$，表示 $A$ 的中的每个元素。
接下来一行一个数 表示询问的数量。
接下来 $m$ 行，每行表示一个操作：

• 1 x： 表示第一种操作，在末尾插入数 $x$。
• 2 l r：表示第二种操作，询问 $\sum_{i=l}^{r}A_i$。保证有 $1\le l\le r\le n'$，其中 $n'$ 为操作时刻序列的长度。
• 3 x：表示第三种操作，给每个数 $\oplus$ 上 $x$。
• 4：表示第四种操作，将数组 $A$ 排序。

输出格式

对于每个第二种操作，输出答案。

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

15
23

提示

Idea：WJMZBMR，Solution：WJMZBMR，Code：WJMZBMR，Data：WJMZBMR

$1\le n,\,m\le 10^5, 0\le x,A_i\le 10^9$