arrayqueries

You are given an initial array X of size N, where X_i denotes the i^th element.

You must perform Q operations. Each operation consists of:

• Output the maximum element currently in the array.
• Remove that maximum element from the array. If the array is empty, output -1 and do not remove anything.
• Insert a given integer A into the array.

Input Format

The first line contains two integers, N and Q.

The second line contains N integers representing the initial elements.

The next Q lines each contain a single integer A.

Output Format

For each operation, output the maximum element before insertion. If the array is empty, output -1.

Constraints

• 1 ≤ N, Q ≤ 10⁶
• -10⁹ ≤ X_i, A ≤ 10⁹

Sample Test Case

Input:
2 3
1 3
5
2
4

Output:
3
5
2

Explanation:
Start with [1, 3]
Operation 1 (x = 5): output 3, remove it, insert 5 → [1, 5]
Operation 2 (x = 2): output 5, remove it, insert 2 → [1, 2]
Operation 3 (x = 4): output 2, remove it, insert 4 → [1, 4]