Idiot Sort

Program time limit: 1 second

Program memory limit: 512 MB

Cyril is sorting an array! However, instead of using a standard algorithm like bubble sort, they decided to experiment with a new sorting algorithm: Fool Sort.

Fool Sort operates by swapping any two elements in the array, but it must adhere to strict rules. A state of the array is considered valid if the concatenation of all its elements forms an odd number. For example, the array [1, 5, 3, 2, 41, 0] concatenates to the number 1532410, which is even (and therefore invalid).

The rules of Fool Sort are as follows:

Valid Swaps: In a single step (timestamp), the algorithm swaps exactly two elements(two elements can be any two numbers of this array). After the swap, the resulting array must be a valid state (its concatenated number must be odd).
No Repetition: All array states visited during the sorting process must be unique. You cannot swap elements to form an array that has already appeared in a previous step (including the initial state).
Halting Condition: Like all sorting algorithms, Fool Sort stops when the array becomes sorted in non-decreasing order. Once sorted, no further swaps are required, and the array remains in its current state for all future timestamps.

Cyril is given Q queries, each containing a timestamp t. For each query, your task is to determine if there exists at least one valid sequence of swaps such that the algorithm is in a valid state at exactly timestamp t (either by actively swapping t times, or by reaching a sorted valid state at some step ≤t and halting).

If such a sequence exists, output Possible. If all possible sequences violate the rules or get stuck before timestamp t, output Impossible.

Input

The first line contains two numbers, N and Q, which is the length of the array and the number of queries.
The following N lines contains an integers each, which are the elements of this array.
The following Q lines contains an integers each, which is the query time stamp.

You should read from standard input.

Constraints

For all test cases:

$1 \le N \le 10^5$.
$1 \le Q \le 10^5$.
$1 \le t \le 10^{18}$.
$1 \le A_i \le 10^{9}$.

Additionally:

For Subtask 1 (50% of points): $1 \leq N,Q,t \leq 1000$.
For Subtask 2 (50% of points): there are no additional constraints.

Output

For each time stamp output if it is possible the constraint of fool sort can be satisfied at that time stamp.

You should write to standard output.

Sample Input 1

3 5
1
3
5
1
21
25
30
1000000000000000

Sample Output 1

Possible
Possible
Possible
Possible
Possible

Explanation 1

The contents of the array is [1,3,5], already sorted and 135 is odd, so every time stamp in the future, no swap is needed and the constraint is satisfied.

Sample Input 2

3 5
2
4
6
1
21
25
30
1000000000000000

Sample Output 2

Impossible
Impossible
Impossible
Impossible
Impossible

Sample Input 3

3 5
1
2
1
1
21
25
30
1000000000000000

Sample Output 3

Possible
Impossible
Impossible
Impossible
Impossible

Explanation 3

The initial array is [1, 2, 1].

Timestamp 1: We can swap the first and second elements to create [2, 1, 1]. This state has not been visited, and its concatenation 211 is odd, making it Possible.
Timestamp 21: From [2, 1, 1], we must make another swap since the array is not sorted. Swapping back to [1, 2, 1] is invalid because that state was already visited. Swapping the outer elements results in [1, 1, 2]. While [1, 1, 2] is unvisited and sorted, its concatenation is 112, which is even (an invalid state). Since no valid sequence of swaps can progress beyond the first step, it is Impossible for all future timestamps.

Scoring

For each subtask (worth 50% and 50% of points, as per the Constraints section), your program will be run on multiple secret test cases one after another, and if it produces the correct output for all test cases, it solves that subtask. Your program will receive the points for each subtask it solves. Recall that your final score on the task is the score of your highest scoring submission.

Submit unofficially

The contest ended at 8:45 p.m. AEST on Tuesday 7th April. All submissions will be unofficial officially.