#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cassert>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<29)
#define MAX 500
using namespace std;

/*
手が壁から離れた -> 手の方向に向きを変える
目の前が壁　　　 -> 手の方向と逆に向きを変える
 */

int W,H,N,xS,yS,xG,yG;
char G[MAX][MAX];
int dx2[2][2] = {{-1,+1},{0,0}};
int dy2[2][2] = {{0,0},{+1,-1}};
/*
int dx[] = {-1,0,1,0};
int dy[] = {0,-1,0,1};
*/
int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};

void print()
{
  cout << "print---" << endl;
  rep(i,2*H+3)
    {
      rep(j,2*W+3)
	{
	  cout << G[i][j];
	}
      cout << endl;
    }
  cout << endl;
}


void initGraph()
{
  rep(i,MAX)rep(j,MAX)G[i][j] = 'x';
  rep(i,2*H+1)
    {
      for(int j=(i%2?0:1);j<2*W+1;j+=2)
	{
	  char c = (i%2?'|':'-');
	  if(i == 0 || j == 0 || i == 2*H || j == 2*W)
	  G[i][j] = c;
	  rep(k,2)
	    {
	      int nx = j + dx2[i%2][k];
	      int ny = i + dy2[i%2][k];
	      if(!(0 <= nx && nx < 2*W+1 && 0 <= ny && ny < 2*H+1))continue;
	      if(nx == 0 || ny == 0 || nx == 2*W || ny == 2*H)
		G[ny][nx] = 'o';
	    }
	}
    }

}


void drawO(int x,int y)
{
  //cout << "draw " << x << "," << y << endl;
  rep(k,2)
    {
      int nx = x + dx2[y%2][k];
      int ny = y + dy2[y%2][k];
      if(!(0 <= nx && nx < 2*W+1 && 0 <= ny && ny < 2*H+1))continue;
	G[ny][nx] = 'o';
    }
}

void makeGraph()
{
  int x1,y1,x2,y2;
  rep(i,N)
    {
      cin >> x1 >> y1 >> x2 >> y2;
      //cout << "from " << x1 << "," << y1 << " " << x2 << "," << y2 << endl;
      if(x1 == x2)
	{
	  if(y1 > y2)swap(y1,y2);
	  x1 *= 2, y1 = y1*2+1, y2 = y2*2+1;
      //cout << x1 << "," << y1 << " " << x2 << "," << y2 << endl;
	  for(int y=y1;y<y2;y+=2)
	    {
	      G[y][x1] = '|';
	      drawO(x1,y);
	    }
	}
      else if(y1 == y2)
	{
	  if(x1 > x2)swap(x1,x2);
	  x1 = x1*2+1, x2 = x2*2+1, y1 = y1*2;
	//cout << x1 << "," << y1 << " " << x2 << "," << y2 << endl;
	  for(int x=x1;x<x2;x+=2)
	    {
	      G[y1][x] = '-';
	      drawO(x,y1);
	    }
	}
      else assert(false);
      //print();
    }

  int x1E,y1E,x2E,y2E;
  cin >> x1E >> y1E >> x2E >> y2E >> xG >> yG;

  
  if(x1E == x2E)
    {
      if(y1E > y2E)swap(y1E,y2E);
      x1E *= 2, y1E = y1E*2 + 1, y2E = y2E*2 + 1;
      G[y1E][x1E] = 'x';
      //for(int y=y1E;y<y2E;y+=2)G[y][x1E] = 'x';
    }
  else if(y1E == y2E)
    {
      if(x1E > x2E)swap(x1E,x2E);
      y1E *= 2, x1E = x1E*2 + 1, x2E = x2E*2 + 1;
      G[y1E][x1E] = 'x';
      //for(int x=x1E;x<x2E;x+=2)G[y1E][x] = 'x';
    }
  
  xS = x1E, yS = y1E;

}

void compute()
{
  int dir = inf;
  rep(i,4)
    {
      int nx = xS + dx[i];
      int ny = yS + dy[i];
      if(!(0 <= nx && nx < 2*W+1 && 0 <= ny && ny < 2*H+1))continue;
      if(G[ny][nx] != 'x')continue;
      dir = i;
    }

  xG = xG*2 + 1;
  yG = yG*2 + 1;
  //cout << "goal = " << xG << "," << yG << endl;
  int cnt = 0;
  bool used[4][2*H+1][2*W+1];
  rep(i,4)rep(j,2*H+1)rep(k,2*W+1)used[i][j][k] = false;

  int x = xS, y = yS;

  while(true)
    {
      //cout << x << "," << y << " " << dir << " " << used[dir][y][x]<< endl;
      if(x == xG && y == yG)
	{
	  cout << cnt << endl;
	  return;
	}
      if(used[dir][y][x])
	{
	  cout << "Impossible" << endl;
	  return;
	}
      used[dir][y][x] = true;

      int nx = x + dx[dir];
      int ny = y + dy[dir];
      int lx = nx + dx[(dir+1)%4];
      int ly = ny + dy[(dir+1)%4];
      //cout << "n = " << nx << "," << ny << " dir = " << dir << endl;
      //cout << "l = " << lx << "," << ly << endl;
      if(!(0 <= nx && nx < 2*W+1 && 0 <= ny && ny < 2*H+1))
	{
	  cout << "Impossible" << endl;
	  return;
	}
      if(G[ny][nx] != 'x')
	{
	  //cout << "in1" << endl;
	  dir = (dir + 3)%4;
	}
      else if(G[ly][lx] == 'x')
	{
	  //cout << "in2" << endl;
	  dir = (dir + 1)%4;
	  x = nx, y = ny;
	  cnt++;
	}
      else 
	{
	  //cout << "in3" << endl;
	  if(G[ly][lx] != 'o')cnt++;
	  x = nx;
	  y = ny;
	}

      /*
      char pc,ppc;
      pc = G[y][x];
      int llx = x + dx[(dir+1)%4];
      int lly = y + dy[(dir+1)%4];

      ppc = G[lly][llx];
      
      G[y][x] = 'B';
      G[lly][llx] = 'H';
      print();
      G[y][x] = pc;
      G[lly][llx] = ppc;
      */
      //cout <<"next -> " << x << "," << y << endl;
    }

}


int main()
{
  while(cin >> W >> H >> N,W|H|N)
    {
      initGraph();
      makeGraph();
      //print();
      compute();
      //cout << xG <<" " << yG  <<endl;
    }
  return 0;
} 
### Prompt

In cpp, your task is to solve the following problem:

The left-hand rule, which is also known as the wall follower, is a well-known strategy that solves a two- dimensional maze. The strategy can be stated as follows: once you have entered the maze, walk around with keeping your left hand in contact with the wall until you reach the goal. In fact, it is proven that this strategy solves some kind of mazes.

Your task is to write a program that determines whether the given maze is solvable by using the left-hand rule and (if the maze is solvable) the number of steps to reach the exit. Moving to a cell from the entrance or the adjacent (north, south, east or west) cell is counted as a step.

In this problem, the maze is represented by a collection of walls placed on the two-dimensional grid. We use an ordinary Cartesian coordinate system; the positive x-axis points right and the positive y-axis points up. Each wall is represented by a line segment which is parallel to the x-axis or the y-axis, such that both ends of each wall are located on integer coordinates. The size of the maze is given by W and H that indicate the width and the height of the maze, respectively. A rectangle whose vertices are on (0, 0), (W, 0), (W, H) and (0, H) forms the outside boundary of the maze. The outside of the maze is always surrounded by walls except for the entrance of the maze. The entrance is represented by a line segment whose ends are (xE, yE) and (xE', yE'). The entrance has a unit length and is located somewhere on one edge of the boundary. The exit is a unit square whose bottom left corner is located on (xX, yX).

A few examples of mazes are illustrated in the figure below. They correspond to the datasets in the sample input.

<image>

Figure 1: Example Mazes (shaded squares indicate the exits)



Input

The input consists of multiple datasets.

Each dataset is formatted as follows:


W H N
x1 y1 x1' y1'
x2 y2 x2' y2'
...
xN yN xN' yN'
xE yE xE' yE' xX yX


W and H (0 < W, H ≤ 100) indicate the size of the maze. N is the number of walls inside the maze. The next N lines give the positions of the walls, where (xi, yi) and (xi', yi') denote two ends of each wall (1 ≤ i ≤ N). The last line gives the positions of the entrance and the exit. You can assume that all the coordinates given in the input are integer coordinates and located inside the boundary of the maze. You can also assume that the wall description is not redundant, i.e. an endpoint of a wall is not shared by any other wall that is parallel to it.

The input is terminated by a line with three zeros.

Output

For each dataset, print a line that contains the number of steps required to reach the exit. If the given maze is unsolvable, print “Impossible” instead of the number of steps.

Example

Input

3 3 3
1 0 1 2
1 2 2 2
2 2 2 1
0 0 1 0 1 1
3 3 4
1 0 1 2
1 2 2 2
2 2 2 1
2 1 1 1
0 0 1 0 1 1
3 3 0
0 0 1 0 1 1
0 0 0


Output

9
Impossible
Impossible

### Response

```cpp
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cassert>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<29)
#define MAX 500
using namespace std;

/*
手が壁から離れた -> 手の方向に向きを変える
目の前が壁　　　 -> 手の方向と逆に向きを変える
 */

int W,H,N,xS,yS,xG,yG;
char G[MAX][MAX];
int dx2[2][2] = {{-1,+1},{0,0}};
int dy2[2][2] = {{0,0},{+1,-1}};
/*
int dx[] = {-1,0,1,0};
int dy[] = {0,-1,0,1};
*/
int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};

void print()
{
  cout << "print---" << endl;
  rep(i,2*H+3)
    {
      rep(j,2*W+3)
	{
	  cout << G[i][j];
	}
      cout << endl;
    }
  cout << endl;
}


void initGraph()
{
  rep(i,MAX)rep(j,MAX)G[i][j] = 'x';
  rep(i,2*H+1)
    {
      for(int j=(i%2?0:1);j<2*W+1;j+=2)
	{
	  char c = (i%2?'|':'-');
	  if(i == 0 || j == 0 || i == 2*H || j == 2*W)
	  G[i][j] = c;
	  rep(k,2)
	    {
	      int nx = j + dx2[i%2][k];
	      int ny = i + dy2[i%2][k];
	      if(!(0 <= nx && nx < 2*W+1 && 0 <= ny && ny < 2*H+1))continue;
	      if(nx == 0 || ny == 0 || nx == 2*W || ny == 2*H)
		G[ny][nx] = 'o';
	    }
	}
    }

}


void drawO(int x,int y)
{
  //cout << "draw " << x << "," << y << endl;
  rep(k,2)
    {
      int nx = x + dx2[y%2][k];
      int ny = y + dy2[y%2][k];
      if(!(0 <= nx && nx < 2*W+1 && 0 <= ny && ny < 2*H+1))continue;
	G[ny][nx] = 'o';
    }
}

void makeGraph()
{
  int x1,y1,x2,y2;
  rep(i,N)
    {
      cin >> x1 >> y1 >> x2 >> y2;
      //cout << "from " << x1 << "," << y1 << " " << x2 << "," << y2 << endl;
      if(x1 == x2)
	{
	  if(y1 > y2)swap(y1,y2);
	  x1 *= 2, y1 = y1*2+1, y2 = y2*2+1;
      //cout << x1 << "," << y1 << " " << x2 << "," << y2 << endl;
	  for(int y=y1;y<y2;y+=2)
	    {
	      G[y][x1] = '|';
	      drawO(x1,y);
	    }
	}
      else if(y1 == y2)
	{
	  if(x1 > x2)swap(x1,x2);
	  x1 = x1*2+1, x2 = x2*2+1, y1 = y1*2;
	//cout << x1 << "," << y1 << " " << x2 << "," << y2 << endl;
	  for(int x=x1;x<x2;x+=2)
	    {
	      G[y1][x] = '-';
	      drawO(x,y1);
	    }
	}
      else assert(false);
      //print();
    }

  int x1E,y1E,x2E,y2E;
  cin >> x1E >> y1E >> x2E >> y2E >> xG >> yG;

  
  if(x1E == x2E)
    {
      if(y1E > y2E)swap(y1E,y2E);
      x1E *= 2, y1E = y1E*2 + 1, y2E = y2E*2 + 1;
      G[y1E][x1E] = 'x';
      //for(int y=y1E;y<y2E;y+=2)G[y][x1E] = 'x';
    }
  else if(y1E == y2E)
    {
      if(x1E > x2E)swap(x1E,x2E);
      y1E *= 2, x1E = x1E*2 + 1, x2E = x2E*2 + 1;
      G[y1E][x1E] = 'x';
      //for(int x=x1E;x<x2E;x+=2)G[y1E][x] = 'x';
    }
  
  xS = x1E, yS = y1E;

}

void compute()
{
  int dir = inf;
  rep(i,4)
    {
      int nx = xS + dx[i];
      int ny = yS + dy[i];
      if(!(0 <= nx && nx < 2*W+1 && 0 <= ny && ny < 2*H+1))continue;
      if(G[ny][nx] != 'x')continue;
      dir = i;
    }

  xG = xG*2 + 1;
  yG = yG*2 + 1;
  //cout << "goal = " << xG << "," << yG << endl;
  int cnt = 0;
  bool used[4][2*H+1][2*W+1];
  rep(i,4)rep(j,2*H+1)rep(k,2*W+1)used[i][j][k] = false;

  int x = xS, y = yS;

  while(true)
    {
      //cout << x << "," << y << " " << dir << " " << used[dir][y][x]<< endl;
      if(x == xG && y == yG)
	{
	  cout << cnt << endl;
	  return;
	}
      if(used[dir][y][x])
	{
	  cout << "Impossible" << endl;
	  return;
	}
      used[dir][y][x] = true;

      int nx = x + dx[dir];
      int ny = y + dy[dir];
      int lx = nx + dx[(dir+1)%4];
      int ly = ny + dy[(dir+1)%4];
      //cout << "n = " << nx << "," << ny << " dir = " << dir << endl;
      //cout << "l = " << lx << "," << ly << endl;
      if(!(0 <= nx && nx < 2*W+1 && 0 <= ny && ny < 2*H+1))
	{
	  cout << "Impossible" << endl;
	  return;
	}
      if(G[ny][nx] != 'x')
	{
	  //cout << "in1" << endl;
	  dir = (dir + 3)%4;
	}
      else if(G[ly][lx] == 'x')
	{
	  //cout << "in2" << endl;
	  dir = (dir + 1)%4;
	  x = nx, y = ny;
	  cnt++;
	}
      else 
	{
	  //cout << "in3" << endl;
	  if(G[ly][lx] != 'o')cnt++;
	  x = nx;
	  y = ny;
	}

      /*
      char pc,ppc;
      pc = G[y][x];
      int llx = x + dx[(dir+1)%4];
      int lly = y + dy[(dir+1)%4];

      ppc = G[lly][llx];
      
      G[y][x] = 'B';
      G[lly][llx] = 'H';
      print();
      G[y][x] = pc;
      G[lly][llx] = ppc;
      */
      //cout <<"next -> " << x << "," << y << endl;
    }

}


int main()
{
  while(cin >> W >> H >> N,W|H|N)
    {
      initGraph();
      makeGraph();
      //print();
      compute();
      //cout << xG <<" " << yG  <<endl;
    }
  return 0;
} 
```