You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

 ——「叽米先生，请与『黑塔女士全肯定bot』一起歌颂黑塔女士吧！」
——「好…好的……」
——「黑塔女士天下无双！」
——「黑塔女士智慧女王！！」
——「黑塔女士美丽健康！！！」
——「黑塔女士…呃…啊…爱吃便当？」
——「「「什么乱七八糟的，炖了他。」」」

总所周知大黑塔的帽子是尖尖的

给定一个大小为$n$的数组表示大黑塔帽子尖尖的长度

有三种不同的操作

$1：$增加一个帽子尖尖长度为 p的帽子

$2：$删除一个帽子尖尖长度为 p的帽子

$3：$计算帽子尖尖的长度在$[l,r]$之中的帽子，他们的尖尖的长度之和是多少？

$q$次操作，每操作分别输入

$1$ $p$ 或者 $2$ $p$或者$3$ $l$ $r$

你需要回答操作3的答案

Input Format

第一行输入一个数字$n$表示最开始大黑塔有$n$个帽子 $(1<n<=200000)$

第二行输入$n$个数字,第$i$ 个数字$a_{i}$表示第$i$个帽子尖尖的长度$(0<a_{i}<10 ^ {9})$

第三行输入一个数字 $q$ ，表示有q次操作$(1<q<=200000)$

接下来$q$行分别表示每次操作$( p< 10^{9} , 0<l<r<10^{9})$

Output Format

对于第三种操作输出答案$ans$

Sample

输入 #1

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

输出 #1

15
24
18