Big sorting — Eolymp

Input

The first line contains the size $n (n \leq 1 0^{6})$ n~(n \le 10^6) of array and the number of queries $q (q \leq 1 0^{5})$ q~(q \le 10^5).

The second line contains the array elements $a_{1}, a_{2}, ..., a_{n}$ a_1, a_2, ..., a_n.

Each of the following $q$ lines contains a query: one integer $k (1 \leq k \leq n)$ k~(1 \le k \le n).

For each query print $a_{k}$ a_k on a separate line: the $k$ -th number in the sorted array.

Sort the numbers in the given sample:

The answers to the queries are: $a_{4} = 5, a_{5} = 6, a_{1} = 1, a_{7} = 7, a_{2} = 1$ a_4 = 5, a_5 = 6, a_1 = 1, a_7 = 7, a_2 = 1.

Example 1

Loading