Hide

Problem F
Freestyle Masonry

/problems/freestylemasonry/file/statement/en/img-0001.png
An interesting brick layout, photo by Bobo Boom
Fred got a simple task, he just has to build a $w\times h$ wall. To make this even easier, he was provided with enough $2\times 1$ bricks and also a few $1\times 1$ bricks to complete the wall. Knowing that this task should not be too hard, Fred went to work and started building the wall without thinking too much about the design. Only when he ran out of $1\times 1$ bricks, Fred noticed that this might have been a bad idea…
\includegraphics{sample}
Figure 1: Visualization of Sample Input $2$. The red bricks have already been placed by Fred. The blue bricks still need to be placed to complete the wall (the only possible design in this case).

Maybe he should have made a plan before starting to build the wall, but now it is too late. Fred only has a bunch of $2\times 1$ bricks left and wants to finish the wall. Can he still complete it with the remaining $2\times 1$ bricks? Note that the wall to be built should have a width of exactly $w$ units and a height of exactly $h$ units.

Input

The input consists of:

  • One line with two integers $w$ and $h$ ($1\leq w\leq 2\cdot 10^5$, $1\leq h\leq 10^6$), the width and height of the wall Fred wants to build.

  • One line with $w$ integers $h_1,\dots ,h_n$ ($0\leq h_i\leq 10^6$), where $h_i$ is the current height of the wall at position $i$.

Output

Output “possible” if Fred can complete his wall and “impossible” otherwise.

Sample Input 1 Sample Output 1
3 3
0 0 1
possible
Sample Input 2 Sample Output 2
6 3
1 0 1 1 0 1
possible
Sample Input 3 Sample Output 3
6 2
1 0 1 1 0 1
impossible
Sample Input 4 Sample Output 4
5 2
1 2 3 2 2
impossible

Please log in to submit a solution to this problem

Log in