Elliot, with the help of Dark Army, has infiltrated the back-office of E Corp. He intends to blow up the building so that they're unable to retrieve the hard copies of the backup of the data encrypted in The Hack. For this task, he needs a sequence of bombs with varying intensities of the right amount. Too powerful and he won't come out alive. Too weak and it won't be effective.
Elliot initially starts with a given sequence of bombs with intensity identified by an integer. He can perform 3 kinds of operations on the sequence:
1) He can add a bomb of intensity x to the end of the sequence created after processing some previous operation.
2) He can find the first occurrence of an unsuitable bomb of intensity x and remove it from the sequence created after processing some previous operation.
3) He evaluates the maximum and minimum intensity of the bombs in the sequence created after processing some previous operation.
Given all the operations, you need to answer the third operation for Elliot.

Input

The first line contains integers n, size of the initial sequence, and k, the total number of operations performed.
The second line contains n space separated integers denoting the initial sequence A.
The next k lines denote operations in following 3 forms:
1 q x : Bomb of intensity x is added to the end of sequence formed after the qth query.
2 q x : First occurrence of bomb of intensity x is removed from the sequence formed after qth query.
3 q : Maximum and minimum intensities of the bombs in the sequence formed after the qth query is printed. If the sequence is empty, output “0 0”.

Output

Print 1 line corresponding to every query of third kind containing two space separated integers denoting the maximum followed by the minimum intensities of the bombs.

Constraints

1 ≤ n, k ≤ 1000000
0 ≤ q ≤ 1000000
1 ≤ x, B[i] ≤ 10⁹
For ith query, q is strictly less than i.