레이팅 미적용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\times1\) bricks and also a few \(1\times1\) 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\times1\) bricks, Fred noticed that this might have been a bad idea...
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\times1\) 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.
The input consists of:
- One line with two integers \(w\) and \(h\) (\(1\leq w\leq2\cdot10^5\), \(1\leq h\leq10^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 "possible" if Fred can complete his wall and "impossible" otherwise.
3 3
0 0 1
possible
6 3
1 0 1 1 0 1
possible
6 2
1 0 1 1 0 1
impossible
5 2
1 2 3 2 2
impossible