Problem Statement

Little Petya likes computer games a lot. He is currently playing the last level
of a game. The level is a rectangular grid with N rows by M columns of cells.
The cells have coordinates between (0,0) and (N-1,M-1), inclusive. Each cell is
either empty or occupied by a wall. You will be given the layout of the level.
(The precise format is specified at the end of this statement.)  At the
beginning of the game Petya's character appears in the cell (r1,c1) with E
units of energy. His task is to find a sequence of valid actions (described
below) that takes his character from the cell (r1,c1) to the cell (r2,c2).  The
rules for the actions are as follows: In each action, Petya can do one of two
things:

* If his character's energy is still positive, he can decrease it by 1.

* He can make the character jump by exactly K cells in one of the four cardinal
  directions, where K is the character's current energy. The target cell has to
  be on the board and it has to be free (not a wall). Note that the cells between
  the current cell and the target cell may contain walls. Also note that jumping
  does not decrease the character's energy.

Petya wins the game if he finds a finite sequence of actions that will bring
his character to the desired destination cell.  You are given the grid in the
format described below, Petya's character starting position, ending position
and initial level of energy. Determine whether Petya can win the game or not.
Return "Possible" (without quotes) if Petya can do that and "Impossible"
otherwise. 

In order to keep the input size small, the grid should be pseudo-randomly
generated. You are given a int[] p. The following pseudocode describes how to
obtain the configuration of the grid.

64bit_integer x = N + 2 * M + 3 * r1 + 4 * c1 + 5 * r2 + 6 * c2;

for(i = 0; i < N; i++){
        for(j = 0; j < M; j++){
                grid[i][j] = Empty;
        }
}

for(i = 0; i < length(p); i += 5){
        for(j = p[i]; j <= p[i + 2]; j++){
                for(k = p[i + 1]; k <= p[i + 3]; k++){
                        x = (x * 1103515245 + 12345) % (64bit_integer)2147483648;
                        if(x < p[i + 4]){
                                grid[j][k] = Wall;
                        } else {
                                grid[j][k] = Empty;
                        }
                }
        }
}

grid[r1][c1] = Empty;
grid[r2][c2] = Empty;



Method signature: String isReachable(int N, int M, int[] p, int r1, int c1, int r2, int c2, int E)
Time limit (s): 4.000
Memory limit (MB): 512


Constraints

- N and M will be between 1 and 2000, inclusive.
- p will contain between 1 and 50 elements, inclusive.
- The number of elements in p will be divisible by 5.
- p[i] will be between 0 and N-1, inclusive for all valid i such that i mod 5 = 0.
- p[i] will be between 0 and M-1, inclusive for all valid i such that i mod 5 = 1.
- p[i] will be between p[i-2] and N-1, inclusive for all valid i such that i mod 5 = 2.
- p[i] will be between p[i-2] and M-1, inclusive for all valid i such that i mod 5 = 3.
- p[i] will be between 0 and 2,147,483,647, inclusive for all valid i such that i mod 5 = 4.
- r1 and r2 will be between 0 and N-1, inclusive.
- c1 and c2 will be between 0 and M-1, inclusive.
- E will be between 1 and max(N, M), inclusive.


Examples

0)

2
2
{1,0,1,0,2140000000}
0
0
1
1
1
Returns: "Possible"

In this case the grid looks like this ('0' stands for empty cells and '1' stands for cells occupied by walls):

00
10


1)

2
2
{0,0,1,1,2147000000}
0
0
1
1
1
Returns: "Impossible"

Here the grid looks like this:

01
10

2)

5
4
{0,0,3,3,1500000000,2,2,4,3,12857676,0,2,4,3,1500000000}
0
1
3
3
3
Returns: "Possible"

Here is how the grid looks like in this test case:

1001
1110
1111
1010
0001


3)

3
10
{0,0,0,9,2147000000,0,4,2,9,2147000000,1,0,1,9,2147000001}
0
0
2
9
10
Returns: "Impossible"

Here is how the grid looks like in this test case:

0111111111
1111111111
0000111110

It's impossible to reach the target cell with any initial amount of energy.


4)

2000
2000
{1000,1000,1001,1001,0}
386
111
1948
635
2000
Returns: "Possible"

Here the grid is completely free of walls.


5)

2000
2000
{0,0,1999,1999,2147319343,804,426,1187,1358,1501333603,900,774,1543,1815,745495001,334,301,1285,863,1797586332,500,280,1764,343,698919580,
320,17,906,607,660127261,194,1364,1007,1693,1166180009,446,1365,1403,1465,204638230,197,1283,421,1486,418539195,508,322,1443,1819,1056189843}
1075
446
364
1216
72
Returns: "Impossible"

In this test case we need at least 73 units of energy to reach the target cell.

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.