K-th Smallest Filtered Number

You are given a list of integers and a number of queries. For each query, you are required to determine the k-th smallest number among the numbers that are either odd or even based on the query. If there are fewer than k numbers with the required parity, output -1.

Formally, if you are given a list \(A\) of \(n\) integers and a list of \(q\) queries where each query is a pair \((parity, k)\) with \(parity \in \{\text{odd}, \text{even}\}\), you need to output the k-th smallest number in \(A\) that has the given parity (odd or even). If there are fewer than \(k\) such numbers, the answer for that query is \(-1\).

Note: The output for each query should be printed on a separate line.

inputFormat

The input is read from standard input (stdin) and is structured as follows:

• The first line contains a single integer \(n\) denoting the number of elements in the list.
• The second line contains \(n\) space-separated integers representing the list \(A\). If \(n = 0\), this line will be empty.
• The third line contains a single integer \(q\) denoting the number of queries.
• The following \(q\) lines each contain a query in the format: a string (odd or even) followed by an integer \(k\), separated by a space.

outputFormat

For each query, output the k-th smallest number from the list with the specified parity on a separate line. If there are fewer than \(k\) numbers with that parity, output \(-1\).

## sample

5
4 2 7 1 3
2
odd 2
even 1

3
2

</p>