Bajtazar 拥有一座鱼塘。目前塘里有 $n$ 条鲱鱼，为了方便起见，它们被编号为 $1$ 到 $n$。第 $i$ 条鲱鱼的重量为 $w_i$ 克。Bajtazar 非常喜爱他的鲱鱼，并且非常担心他的鱼塘会受到野生狗鱼的攻击。

Bajtazar 想知道，在捕食者攻击期间，他的鲱鱼可能会受到多大的伤害。他非常了解狗鱼的生物学和心理学。他知道，尽管狗鱼天性凶猛，但它们是非常聪明的生物，总是单独行动。每条狗鱼都可以用两个整数 $s$ 和 $k$ 来描述，分别表示狗鱼当前的重量以及它想要达到（或超过）的目标重量。

进入鱼塘的狗鱼会吃掉塘里的鲱鱼。只有当狗鱼的重量严格大于某条鲱鱼的重量时，它才能吃掉这条鲱鱼。吃掉鲱鱼后，狗鱼的重量会增加所吃鲱鱼的重量，这可能会使它能够吃掉之前无法捕食的猎物。上述的“聪明”体现在：狗鱼总是会吃掉最少数量的鲱鱼，以达到它想要的目标重量。

Bajtazar 想要考虑各种不同的攻击方案。每个方案都描述了一条攻击鱼塘的狗鱼。对于每一个这样的方案，Bajtazar 都想知道攻击的狗鱼会吃掉多少条鲱鱼，或者该侵略者根本无法达到其目标（在这种情况下，它可能会放弃进攻）。所有这些方案都只是 Bajtazar 的假设，因此它们不会影响鱼塘中生物的实际状态。

此外，有时会有新的鲱鱼进入鱼塘，有时鲱鱼也会消失。因此，Bajtazar 必须能够更新鱼塘的状态，以便在考虑未来可能出现的攻击方案时将其纳入考量。请帮助他编写一个程序，协助他管理鱼塘的情况！

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 300\,000$)，表示 Bajtazar 鱼塘中鲱鱼的数量。

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

第三行包含一个整数 $q$ ($1 \le q \le 100\,000$)，表示需要帮助 Bajtazar 处理的事件数量。接下来的 $q$ 行包含各个事件的描述。事件类型如下：

• $1 \ s \ k$ – Bajtazar 考虑一条重量为 $s$ 克的狗鱼，它想要达到至少 $k$ 克的重量 ($1 \le s, k \le 10^{18}$)。
• $2 \ w$ – 一条重量为 $w$ 克的鲱鱼被加入鱼塘 ($1 \le w \le 10^{12}$)。
• $3 \ w$ – 一条重量为 $w$ 克的鲱鱼从鱼塘中被移除 ($1 \le w \le 10^{12}$)。可以假设在发生此类事件时，鱼塘中至少存在一条该重量的鲱鱼。

输入中至少包含一个第一类型的事件。

输出格式

对于每个第一类型的事件，输出攻击的狗鱼会吃掉多少条鲱鱼，如果它根本无法达到（或超过）目标重量，则输出 $-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

子任务

在某些测试组中，事件仅包含第一类型。