考虑把这个队列分为3段： 在队列头部插入的数据，在之前操作后已经被排序了的数据，在队列尾部插入的数据。

对于第一种与第二种操作，把元素插入到第一段或者第三段即可。

对于排序操作，我们把队头和队尾插入的数据更新到已排序的段然后清空它们。

在分为三个段之后，我们在队列上的查询就被转换成了在这三个段上的区间查询。

题目内容

2333要求你维护一个双端队列$q$。其一开始为空，接下来有若干个操作。操作分以下几类:

1.push_front(x) , 即向$q$的首部加入一个元素$x$

2.push_back(x) , 即向$q$的尾部加入一个元素$x$

3.sort() , 即将$q$ 的所有元素升序排序。

4.sum(q[l:r+1]) , 即求和$q$的下标属于$[l,r]$ 的所有元素 。 (下标从$1$ 开始)

输入描述

第一行一个整数$n$ , 代表操作次数.

接下来$n$行，每行一个操作。操作的个数如下：

$1\ x$

$2\ x$

$3$

$4\ l\ r$

分别对应于题面中的四类操作

输出描述

对于每一个操作$4$ , 输出一个整数代表答案

数据范围说明

对于全部数据，加入队列的所有元素均满足$1 \leq x \leq 10^9$

样例1

输入

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

输出

12
7

解释

• 第一行输入 6，表示有6个操作。
• 第二行输入 1 3，表示执行 push_front(3) 操作，队列变为 [3]。
• 第三行输入 2 4，表示执行 push_back(4) 操作，队列变为 [3, 4]。
• 第四行输入 2 5，表示执行 push_back(5) 操作，队列变为 [3, 4, 5]。
• 第五行输入 3，表示执行 sort() 操作，队列变为 [3, 4, 5]（已经是升序）。
• 第六行输入 4 1 3，表示执行 sum(q[1:3+1]) 操作，计算队列中下标从1到3的元素之和，结果为 12。
• 第七行输入 4 1 2，表示执行 sum(q[1:2+1]) 操作，计算队列中下标从1到2的元素之和，结果为 7。