Bajtazar is the owner of a fish pond. Currently, there are $n$ sprats living in it, numbered for convenience from $1$ to $n$. The weight of the $i$-th sprat is $w_i$ grams. Bajtazar loves his sprats and is very afraid that his pond will be attacked by wild pike.

Bajtazar would like to know how much his sprats might suffer during a predator attack. He knows the biology and psychology of pike exactly. He knows that despite their innate wildness, they are very intelligent creatures that always attack one by one. Each pike can be described by two integers, $s$ and $k$, which represent the pike's current weight and the weight it would like to reach (or exceed), respectively.

A pike introduced into the pond will eat the sprats living in it. It can only eat a sprat if its weight is strictly greater than the weight of that sprat. After eating, its weight increases by the weight of its prey, which may allow it to eat specimens previously unavailable to it. The aforementioned intelligence manifests in the fact that the pike will always eat the minimum number of sprats that will allow it to reach its desired weight.

Bajtazar wants to consider various attack scenarios. Each scenario is a description of a pike attacking the pond. For each such scenario, Bajtazar would like to know how many sprats the attacking pike would eat, or that the aggressor will not be able to reach its goal at all, which will likely cause it to abandon the offensive. All these scenarios are just Bajtazar's conjectures, so they do not affect the actual state of the fauna in the pond.

Additionally, sometimes new sprats are added to the pond. Sometimes, sprats also disappear from it. Bajtazar must therefore be able to update the state of his pond to take it into account when considering attack scenarios that might come to his mind in the future. Help him and write a program that will help him manage the situation in his pond!

Input

The first line of input contains a single integer $n$ ($1 \le n \le 300\,000$), representing the number of sprats living in Bajtazar's pond.

The second line contains a sequence of $n$ integers $w_1, \dots, w_n$ ($1 \le w_i \le 10^{12}$), representing the weights of the sprats.

The third line contains a single integer $q$ ($1 \le q \le 100\,000$), representing the number of events for which Bajtazar needs help. The following $q$ lines contain descriptions of individual events. They can be one of three types:

• $1 \ s \ k$ – Bajtazar considers an attack by a pike with weight $s$ grams, which wants to reach a weight of at least $k$ grams ($1 \le s, k \le 10^{18}$).
• $2 \ w$ – A single sprat with a weight of $w$ grams is added to the pond ($1 \le w \le 10^{12}$).
• $3 \ w$ – A single sprat with a weight of $w$ grams is removed from the pond ($1 \le w \le 10^{12}$). It can be assumed that during such an event, there is at least one sprat of that weight in the pond.

There will be at least one event of the first type in the input.

Output

For each event of the first type, output how many sprats the attacking pike would eat, or $-1$ if it would not be able to reach (or exceed) its desired weight at all.

Examples

Input 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

Output 1

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

Subtasks

In some test groups, the events are exclusively of the first type.