Black Box

In this problem, you are given a "Black Box" which initially is empty and maintains an integer array along with a special variable $i$, initially $0$. The Black Box processes a sequence of two types of commands:

1. ADD(x): Insert the integer $x$ into the Black Box.
2. GET: Increment $i$ by $1$, and output the $i^\text{th}$ smallest element in the box (i.e. the element that would appear in the sorted order of the box's contents).

The commands are given indirectly by two arrays:

• An array $a_1,a_2,\ldots,a_m$, representing the elements to be added in order via the ADD commands.
• An array $u_1,u_2,\ldots,u_n$, where each $u_j$ indicates that a GET command is executed immediately after the $u_j^{th}$ ADD command.

For example, consider the following command sequence:

$$\begin{array}{|c|c|c|c|c|} \hline \text{Index} & \text{Operation} & i & \text{Black Box Content} & \text{Output}\\ \hline 1 & ADD(3) & 0 & [3] & - \\ \hline 2 & GET & 1 & [3] & 3 \\ \hline 3 & ADD(1) & 1 & [1,3] & - \\ \hline 4 & GET & 2 & [1,3] & 3 \\ \hline 5 & ADD(-4) & 2 & [-4,1,3] & - \\ \hline 6 & ADD(2) & 2 & [-4,1,2,3] & - \\ \hline 7 & ADD(8) & 2 & [-4,1,2,3,8] & - \\ \hline 8 & ADD(-1000) & 2 & [-1000,-4,1,2,3,8] & - \\ \hline 9 & GET & 3 & [-1000,-4,1,2,3,8] & 1 \\ \hline 10 & GET & 4 & [-1000,-4,1,2,3,8] & 2 \\ \hline 11 & ADD(2) & 4 & [-1000,-4,1,2,2,3,8] & - \\ \hline \end{array}$$

This corresponds to $a = [3,1,-4,2,8,-1000,2]$ and $u = [1,2,6,6]$. Your task is to process the commands in an optimal way so that the GET operations return the correct $i^\text{th}$ smallest number from the Black Box at that moment.

A common efficient solution is to maintain two heaps: a max-heap for the lower half of numbers (to easily retrieve the $i^\text{th}$ smallest element) and a min-heap for the rest. Each GET operation ensures that the max-heap size equals the number of GETs performed so far. Then, the top of the max-heap is the desired result.

Input constraints: The input is guaranteed to be valid.

Good luck!

inputFormat

The first line contains two integers $m$ and $n$, where $m$ is the number of ADD commands and $n$ is the number of GET commands.
The second line contains $m$ integers $a_1,a_2,\ldots,a_m$, the elements to be added to the Black Box.
The third line contains $n$ integers $u_1,u_2,\ldots,u_n$, indicating that after the $u_i^{th}$ ADD command, a GET command is executed.

outputFormat

Output $n$ lines, each containing the result of a GET command in the order they are executed.

sample

7 4
3 1 -4 2 8 -1000 2
1 2 6 6

3
3
1
2

</p>