P1022 Mission 1 - V : Back to Home

Difficulty: \(\color{brown}650\)

Problem Background

Radar solves the problem Cui2010 gave him, and wins. So he went back to the RAO (The Republic of AOCode). Seeing him okay is so awesome, so we decided to give Radar a surprise. But Radar don’t want the surprise and wants to give it to you, but you have to solve his problem first.

So, can you solve Radar’s problem?

Problem Statement

There’s a sequence \(A\) with \(n\) numbers in it. Radar will give you \(q\) queries, and there are \(3\) kinds:

• \(1\ x\)

  This means you have to push the number \(x\) to the back of \(A\).

• \(2\)

  This lets you sort the sequence.

• \(3\ a\)

  This makes you erase all elements of value \(a\) in \(A\).

  Note that if there’s no \(a\)’s, do nothing.

• \(4\)

  This makes you print the smallest element in \(A\), then pop it.

  Note that if there’s no element in \(A\) right then, print \(-1\).

Could you make it and get the gift?

Input

\(n\)

\(A_1\ A_2\ A_3\ \cdots A_n\)

\(q\)

\(\text{query}_1\)

\(\text{query}_2\)

\(\text{query}_3\)

\(\ \ \ \ \ \vdots\)

\(\text{query}_q\)

\(\text{query}_i(1 \le i \le n)\) is one of below:

• \(1\ x\)

• \(2\)

• \(3\ a\)

• \(4\)

Output

Output \(k\) lines (\(k\) is the number of the \(4^{\rm th}\) kind of queries), each line contains the answer of one of the queries. (One by One)

Samples

Input 1

3
3 2 1
4
1 3
3 4
1 3
4

Output 1

1

Input 2

3
782 474 293
4
1 777
2
3 293
4

Output 2

474

Input 3

2
999 999
3
2
3 999
4

Output 3

-1

Constraints

• \(1 \le n \le 10^3\)
• \(1 \le A_i \le 10^6\)
• \(1 \le q \le 10^2\)
• For all available \(x\)'s, \(1 \le x \le 10^6\).
• For all available \(a\)'s, \(1 \le a \le 10^6\).