Declining Sequences

Consider an integer sequence $a_1, a_2, \ldots, a_n$. A strictly increasing sequence of indices $c_1, c_2, \ldots, c_p$ (with $1 \le c_i \le n$) is called declining if the values at those positions strictly decrease, that is $a_{c_1} > a_{c_2} > \cdots > a_{c_p}$.

A sequence of indices $c_1, c_2, \ldots, c_p$ is lexicographically smaller than a sequence $d_1, d_2, \ldots, d_p$ if there is some position $k \in [1, p]$ such that $c_i = d_i$ for every $i \in [1, k-1]$ and $c_k < d_k$.

Answer several queries of the form: find the lexicographically $k$-th smallest declining sequence of indices. Every declining sequence considered has length exactly $p$.

The first line contains three integers $n$, $p$, and $q$ ($1 \le n, q \le 100\,000$, $1 \le p \le 10$): the length of the sequence, the length of the declining sequences to consider, and the number of queries. The second line contains $n$ integers $a_i$ ($-10^9 \le a_i \le 10^9$). Each of the next $q$ lines contains one integer $k_j$ ($1 \le k_j \le 10^{18}$).

Print $q$ lines. The $j$-th line contains the $k_j$-th smallest declining sequence of indices, written as its $p$ index values separated by single spaces, or a single number $-1$ if that declining sequence does not exist.

For the first example ($n=5$ and the sequence $-1\ 6\ 5\ 2\ 1$), the declining sequences of indices of length $3$, in lexicographic order, are $(2, 3, 4)$, $(2, 3, 5)$, $(2, 4, 5)$, and $(3, 4, 5)$.