Maintain an ordered multiset and answer predecessor and successor queries.

Input

The first line contains n and the n initial integers. The next line contains q. A query is 1 x (insert), 2 x (erase one if present), 3 x (smallest value at least x), or 4 x (largest value at most x).

Array and query counts are between $1$ and $10^5$. Integer values are between $-10^9$ and $10^9$. Deleting a missing multiset value has no effect.

Output

For every type 3 or 4 query, print the requested value, or -1 when it does not exist.

Example

Input

5
5 3 8 6 7
6
3 5
3 9
4 5
1 4
3 4
2 3

Output

5
-1
5
4