题目内容

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。