Description

Given a sequence $S=\{a_1,a_2,a_3,…,a_n\}$, if there exists $P=\{a_{x_1},a_{x_2},a_{x_3},…,a_{x_m}\}$ such that $(x_1<x_2<…<x_m)$ and $(a_{x_1}<a_{x_2}<…<a_{x_m})$, then $P$ is called an increasing subsequence of $S$. If multiple $P$ satisfy the conditions, we want the lexicographically smallest one.

Task:

Given the sequence $S$ and several queries. For the $i$-th query, find an increasing subsequence of length $L_i$. If there are multiple, choose the lexicographically smallest one (i.e., first minimize $x_1$; if it is not unique, then minimize $x_2$, and so on). If no increasing subsequence of length $L_i$ exists, print Impossible.

Input Format

• The first line contains an integer $N$, the number of elements in the sequence.
• The second line contains $N$ integers: $a_1, a_2 , \cdots , a_n$.
• The third line contains an integer $M$, the number of queries. Each of the next $M$ lines contains one integer $L$, asking for an increasing subsequence of length $L$.

Output Format

For each query:

• If a valid subsequence exists, output the chosen subsequence’s elements $a_{x_1}, a_{x_2}, \dots, a_{x_L}$ on one line, separated by single spaces.
• Otherwise, print Impossible.

6
3 4 1 2 3 6
3
6
4
5

Impossible
1 2 3 6
Impossible

6
6 7 1 2 3 4
1
2

6 7

Hint

Constraints: $N \le 10000$, $M \le 1000$. The testdata are random.

Translated by ChatGPT 5