P1801 Black Box

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). | No. | Operation | $i$ | Database | Output | | :--: | :--- | :------: | ------ | :----: | | 1 | `ADD(3)` | $0$ | $3$ | / | | 2 | `GET` | $1$ | $3$ | $3$ | | 3 | `ADD(1)` | $1$ | $1,3$ | / | | 4 | `GET` | $2$ | $1,3$ | $3$ | | 5 | `ADD(-4)` | $2$ | $-4,1,3$ | / | | 6 | `ADD(2)` | $2$ | $-4,1,2,3$ | / | | 7 | `ADD(8)` | $2$ | $-4,1,2,3,8$ | / | | 8 | `ADD(-1000)` | $2$ | $-1000,-4,1,2,3,8$ | / | | 9 | `GET` | $3$ | $-1000,-4,1,2,3,8$ | $1$ | | 10 | `GET` | $4$ | $-1000,-4,1,2,3,8$ | $2$ | | 11 | `ADD(2)` | $4$ | $-1000,-4,1,2,2,3,8$ | / | 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.

- 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 the sequence produced by the Black Box according to the command sequence, one number per line.

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