Byteasar 拥有一个养着许多金鱼的池塘。目前池塘里有 $n$ 条金鱼，编号从 $1$ 到 $n$。第 $i$ 条鱼的重量为 $w_i$。Byteasar 很爱他的金鱼，但他担心会有邪恶的梭子鱼袭击他的池塘（梭子鱼是大鱼，有时被称为“水之王”，就像狮子被称为“丛林之王”一样）。

Byteasar 想知道他的金鱼在这些捕食者的攻击下有多脆弱。他很了解梭子鱼的生物学特性和习性，虽然它们既凶猛又邪恶，但它们也非常聪明，而且总是每次只攻击一条鱼。每条梭子鱼都可以用两个整数 $s$ 和 $k$ 来描述，分别表示它当前的重量和它想要达到（或超过）的目标重量。

当梭子鱼出现在池塘中时，它开始吃池塘里的金鱼。当且仅当梭子鱼的重量严格大于某条金鱼的重量时，它才能吃掉这条金鱼。吃掉金鱼后，梭子鱼的重量会增加被吃掉金鱼的重量，这在理论上可能使它能够吃掉更多的金鱼。梭子鱼的聪明之处在于，它们总是以最少的金鱼数量达到目标重量。

Byteasar 想要考虑许多可能的攻击场景。每个场景都描述了一条攻击池塘的梭子鱼。对于每一个场景，Byteasar 都想知道，如果梭子鱼能够达到其目标重量，它会吃掉多少条金鱼。如果它无法达到目标重量，它就会放弃攻击。所有这些考虑实际上都是假设性的场景，不会影响池塘中金鱼的状态。

此外，有时会有新的金鱼被放入池塘，有时金鱼也会因为去寻找更大的池塘而离开。Byteasar 需要更新所有这些信息，以便考虑他脑海中不断涌现的攻击场景。请帮助他编写一个程序，告诉他所有攻击场景的结果！

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 300\,000$)，表示 Byteasar 池塘中金鱼的数量。

第二行包含 $n$ 个整数 $w_1, \dots, w_n$ ($1 \le w_i \le 10^{12}$)，表示金鱼的重量。

第三行包含一个整数 $q$ ($1 \le q \le 100\,000$)，表示将要发生的事件数量。

接下来的 $q$ 行包含上述事件。事件分为三种类型：

• $1 \ s \ k$ —— Byteasar 考虑一条重量为 $s$ 的梭子鱼，它想要达到至少 $k$ 的重量 ($1 \le s, k \le 10^{18}$)。
• $2 \ w$ —— 向池塘中加入一条重量为 $w$ 的金鱼 ($1 \le w \le 10^{12}$)。
• $3 \ w$ —— 从池塘中移除一条重量为 $w$ 的金鱼。你可以假设在操作前池塘中至少有一条该重量的金鱼。

至少存在一个第一类型的事件。

输出格式

对于每一个第一类型的事件，输出一行，表示在相应场景中被吃掉的金鱼数量；如果梭子鱼无法达到目标重量，则输出 $-1$。

样例

样例输入 1

4
1 4 8 1
15
1 2 3
1 2 4
1 2 5
1 3 3
1 3 5
1 3 16
1 4 16
1 8 17
1 100 101
1 100 115
1 3 9
2 2
1 3 9
3 4
1 3 9

样例输出 1

1
2
-1
0
2
4
3
2
1
-1
3
2
-1