Description

Black Box is a primitive database. It can store an integer array and a special variable $i$. Initially, the Black Box is empty and $i = 0$. This Black Box needs to process a sequence of commands.

There are only two types of commands:

• ADD(x): insert element $x$ into the Black Box;
• GET: increase $i$ by $1$, then output the $i$-th smallest number in the Black Box.

Remember: the $i$-th smallest number is the $i$-th element in the Black Box when its numbers are sorted in ascending order.

Let’s demonstrate a sequence of 11 commands (as shown in the table below).

Now you are asked to determine the outputs for a given command sequence. There are $m$ ADD commands and $n$ GET commands. The command sequence is represented by two integer arrays:

1. $a_1, a_2, \cdots, a_m$: the sequence of elements to be inserted into the Black Box. For example, in the above example $a = [3, 1, -4, 2, 8, -1000, 2]$.
2. $u_1, u_2, \cdots, u_n$: after the $u_i$-th element has been inserted into the Black Box, a GET command appears. For example, in the above example $u = [1, 2, 6, 6]$. You do not need to validate the input.

Input Format

• The first line contains two integers $m$ and $n$, the number of elements and the number of GET commands.
• The second line contains $m$ integers. From left to right, the $i$-th integer is $a_i$, separated by spaces.
• The third line contains $n$ integers. From left to right, the $i$-th integer is $u_i$, separated by spaces.

Output Format

Output the sequence produced by the Black Box according to the command sequence, one number per line.

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

3
3
1
2

Hint

Constraints

• For $30\%$ of the testdata, $1 \leq n, m \leq 10^{4}$.
• For $50\%$ of the testdata, $1 \leq n, m \leq 10^{5}$.
• For $100\%$ of the testdata, $1 \leq n, m \leq 2 \times 10^{5}$, $|a_i| \leq 2 \times 10^{9}$, and the sequence $u$ is non-decreasing.

Translated by ChatGPT 5