Description

给定包含n个整数的数列，接下来进行Q次操作，每次操作为下列三项操作之一： 操作一：1 x 表示将整数x加入到数列中 操作二：2 flag x 表示将数列中的每个整数都加上或减去x，flag为0 表示加上x flag为1 表示减去x。 操作三：3表示删除数列中一个最大的整数（如果数列为空，则操作三无效）对于每个有效的操作三，输出你删除的整数。

Format

Input

第一行包含一个整数n； 第二行包含n个整数a₁，a₂...，a_n，整数之间以一个空格隔开。 第三行包含一个整数Q，表示操作次数； 接下来Q行，每行包含一次操作，操作的具体内容如题所示。

Output

若干行，每行包含一个整数，表示按照输入顺序每个有效的操作三输出的整数。

Samples

5
7 5 1 3 9
6
1 11
2 0 5
1 8
2 1 3
3
3

13
11

Limitation

数据范围： 测试点1~10:1<=n,Q<=10⁵,-10⁹<=a_i,X<=10⁹。