Rewind Parade

Time limit: 4000 msMemory limit: 256 MB

A parade of robots moves on a square grid in synchronized beats. Every robot has a recorded route consisting of $B+1$ grid squares:

$P_{i,0}, P_{i,1}, \ldots, P_{i,B}.$

Consecutive squares in a route are horizontally or vertically adjacent. Before the parade begins, robot $i$ must choose exactly one of the following playback directions for its entire route:

Forward: at beat $t$ , it occupies $P_{i,t}$ .
Reverse: at beat $t$ , it occupies $P_{i,B-t}$ .

Thus, between consecutive beats, every robot travels along one grid street segment. A street segment is considered the same resource in both directions.

The parade is safe only if both of these rules hold:

At every beat $t$ satisfying $0 \le t \le B$ , no two robots occupy the same grid square.
During every interval from beat $t$ to beat $t+1$ , where , no two robots travel along the same street segment. This rule also forbids using that segment simultaneously in opposite directions.

Determine whether playback directions can be chosen for all robots so that the parade is safe.

Input

The first line contains two integers $N$ and $B$ , the number of robots and the number of moves in each recorded route, respectively. They satisfy $1 \le N \le 10^5$ , $0 \leq B \leq 10^{5}$ , and .

Output

Print POSSIBLE if every robot can be assigned a playback direction so that the performance obeys both safety rules. Otherwise, print IMPOSSIBLE.

Samples

Sample 1

Input

2 2
0 0 1 0 2 0
2 0 2 1 2 2

Output

POSSIBLE

Both robots can play their routes forward. They occupy distinct squares at every beat and use different street segments during both moves.

Sample 2

Input

2 1
0 0 1 0
1 0 0 0

Output

IMPOSSIBLE

Each robot uses the same street segment during the only move, regardless of its playback direction.

Rewind Parade

Input

Output

Samples

Sample 1

Sample 2

Submit

Submissions