p01747 Snake_28803
Sunake is in the form of a polygonal line consisting of n vertices (without self-intersection). First, Sunake-kun's i-th vertex is at (xi, yi). You can move continuously by translating or rotating, but you cannot deform (change the length of the polygonal line or the angle between the two line segments). y = 0 is the wall, and there is a small hole at (0, 0). Determine if you can move through this hole so that the whole thing meets y <0.

Constraints

* 2 ≤ n ≤ 1000
* 0 ≤ xi ≤ 109
* 1 ≤ yi ≤ 109
* Lines do not have self-intersections
* None of the three points are on the same straight line
* (xi, yi) ≠ (xi + 1, yi + 1)
* All inputs are integers

Input


n
x1 y1
.. ..
xn yn


Output

Output "Possible" if you can move through the hole, and "Impossible" if you can't.

Examples

Input

4
0 1
1 1
1 2
2 2


Output

Possible


Input

11
63 106
87 143
102 132
115 169
74 145
41 177
56 130
28 141
19 124
0 156
22 183


Output

Impossible
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


struct Point{
	Point(double arg_x,double arg_y){
		x = arg_x;
		y = arg_y;
	}

	Point(){
		x = y = 0.0;
	}

	Point operator + (Point p){ return Point(x+p.x,y+p.y); }
	Point operator - (Point p){ return Point(x-p.x,y-p.y);}
	Point operator * (double a){ return Point(a*x,a*y); }
	Point operator / (double a){ return Point(x/a,y/a); }

	double abs(){ return sqrt(norm()); }
	double norm(){ return x*x + y*y; }

	bool operator<(const Point &p) const{
		return x != p.x? x < p.x: y < p.y;
	}

	bool operator == (const Point &p) const{
		return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS;
	}

	double x,y;
};

typedef Point Vector;
typedef vector<Point> Polygon;

double cross(Vector a,Vector b){
    return a.x*b.y-a.y*b.x;
}

bool calcGaiseki(Point left,Point base, Point right){
	double gaiseki = (left.x-base.x)*(right.y - base.y)-(left.y-base.y)*(right.x-base.x);
	if(gaiseki < -0.00000001)return false;
	else{
		return true;
	}
}

double calc_S(Polygon g){

	int N = g.size();
	double ret = 0;

	for(int i = 0; i < g.size(); i++){
		ret += cross(g[i],g[(i+1)%N]);
	}
	return ret/2.0;
}

double dot(Vector a,Vector b){
    return a.x*b.x + a.y*b.y;
}

static const int COUNTER_CLOCKWISE = 1;
static const int CLOCKWISE = -1;
static const int ONLINE_BACK = 2;
static const int ONLINE_FRONT = -1;
static const int ON_SEGMENT = 0;

int ccw(Point p0,Point p1,Point p2){

	Vector a = p1 - p0;
	Vector b = p2 - p0;

	if(cross(a,b) > EPS)return COUNTER_CLOCKWISE;
	if(cross(a,b) < -EPS)return CLOCKWISE;
	if(dot(a,b) < -EPS)return ONLINE_BACK;
	if(a.norm() < b.norm())return ONLINE_FRONT;

	return ON_SEGMENT;
}

//http://www.prefield.com/algorithm/geometry/convex_hull.html
Polygon ConvexHull(Polygon V)
{
  int N = V.size(), k = 0;

  sort(V.begin(), V.end());

  Polygon ret(2*N);
  for (int i = 0; i < N; ret[k++] = V[i++]) // lower-hull
  while (k >= 2 && ccw(ret[k-2], ret[k-1], V[i]) <= 0) --k;
  for (int i = N-2, t = k+1; i >= 0; ret[k++] = V[i--]) // upper-hull
    while (k >= t && ccw(ret[k-2], ret[k-1], V[i]) <= 0) --k;

  ret.resize(k-1);

  return ret;
}

bool is_ok(Polygon p){

	double pre_S = -1.0,tmp_S;

	for(int i = 0; i < p.size(); i++){
		if(i < 2)continue;

		Polygon p2;
		for(int k = 0; k <= i; k++){
			p2.push_back(p[k]);
		}

		p2 = ConvexHull(p2);

		tmp_S = calc_S(p2);

		if(fabs(tmp_S-pre_S) < EPS){
			return false;
		}
		pre_S = tmp_S;
	}
	return true;
}


int main(){

	int N;
	scanf("%d",&N);

	Polygon p;
	double tmp_x,tmp_y;

	for(int loop = 0; loop < N; loop++){
		scanf("%lf %lf",&tmp_x,&tmp_y);
		p.push_back(Point(tmp_x,tmp_y));
	}

	if(!is_ok(p)){
		printf("Impossible\n");
		return 0;
	}

	reverse(p.begin(),p.end());

	if(!is_ok(p)){
		printf("Impossible\n");
		return 0;
	}

	printf("Possible\n");

	return 0;
}


4
0 1
1 1
1 2
2 2 11
63 106
87 143
102 132
115 169
74 145
41 177
56 130
28 141
19 124
0 156
22 183 4
0 1
1 1
1 2
3 2 11
63 106
87 143
102 132
115 169
74 145
41 177
56 130
28 102
19 124
0 156
22 183 4
0 2
1 1
1 2
3 2 11
63 106
87 143
102 132
115 169
74 145
41 177
56 130
28 102
19 124
0 294
22 183 4
0 2
1 1
2 2
3 2 11
63 106
87 143
102 132
115 169
74 145
41 177
84 130
28 102
19 124
0 294
22 183 11
63 106
87 143
102 132
115 44
74 145
41 177
84 130
28 102
19 124
0 294
22 183 11
63 106
87 143
102 132
115 44
74 145
41 340
84 130
28 102
19 124
0 294
22 183 11
63 106
87 143
102 132
115 44
74 145
11 340
84 130
28 102
19 124
0 294
22 183 11
63 106
87 143
102 132
115 44
86 145
11 340
84 130
28 102
19 124
0 294
22 183 11
63 106
87 143
144 132
115 44
86 145
11 340
84 130
28 102
19 124
0 294
22 183 11
63 106
87 143
144 132
177 44
86 145
11 340
84 130
28 102
19 124
0 294
22 183 11
63 106
87 143
144 132
177 44
86 52
11 340
84 130
28 102
19 124
0 294
22 183 11
63 106
87 143
144 132
177 57
86 52
11 340
84 130
28 102
19 124
0 294
22 183 11
63 106
87 143
144 132
177 57
136 52
11 340
84 130
28 102
19 124
0 294
22 183 11
63 106
87 143
203 132
177 57
136 52
11 340
84 130
28 102
19 124
0 294
22 183 11
63 106
87 143
203 167
177 57
136 52
11 340
84 130
28 102
19 124
0 294
22 183 11
63 141
87 143
203 167
177 57
136 52
11 340
84 130
28 102
19 124
0 294
22 183 11
63 141
87 143
125 167
177 57
136 52
11 340
84 130
28 102
19 124
0 294
22 183 11
63 141
87 143
125 167
177 57
136 52
11 340
84 130
28 102
19 124
0 294
29 183 11
63 141
89 143
125 167
177 57
136 52
11 340
84 130
28 102
19 124
0 294
29 183 11
63 141
89 143
125 145
177 57
136 52
11 340
84 130
28 102
19 124
0 294
29 183 11
63 141
11 143
125 145
177 57
136 52
11 340
84 130
28 102
19 124
0 294
29 183 11
63 141
11 143
125 145
177 57
136 52
11 340
84 130
28 102
19 179
0 294
29 183 11
63 141
11 143
125 145
130 57
136 52
11 340
84 130
28 102
19 179
0 294
29 183 11
63 141
11 143
125 145
130 57
136 52
2 340
84 130
28 102
19 179
0 294
29 183 11
63 141
11 143
125 145
130 57
136 52
2 340
84 130
28 75
19 179
0 294
29 183 11
63 141
11 143
125 145
130 57
136 52
2 340
84 143
28 75
19 179
0 294
29 183 11
63 141
11 143
125 145
130 57
136 52
2 340
84 143
28 75
37 179
0 294
29 183 11
63 141
11 143
242 145
130 57
136 52
2 340
84 143
28 75
37 179
0 294
29 183 11
63 141
11 143
242 145
130 44
136 52
2 340
84 143
28 75
37 179
0 294
29 183 11
63 141
11 143
242 145
130 44
136 52
0 340
84 143
28 75
37 179
0 294
29 183 11
63 141
11 143
242 145
130 44
136 52
0 340
84 25
28 75
37 179
0 294
29 183 11
63 141
11 143
242 145
130 44
136 52
0 340
84 25
28 75
37 179
0 294
2 183 11
63 141
11 143
242 145
130 44
136 52
0 340
84 29
28 75
37 179
0 294
2 183 11
63 141
11 143
242 145
130 44
136 52
0 340
84 29
28 75
37 44
0 294
2 183 11
63 141
11 143
242 162
130 44
136 52
0 340
84 29
28 75
37 44
0 294
2 183 11
63 141
11 143
242 162
130 53
136 52
0 340
84 29
28 75
37 44
0 294
2 183 11
63 141
11 143
242 162
130 53
136 52
0 340
149 29
28 75
37 44
0 294
2 183 11
63 141
11 143
242 162
130 53
136 50
0 340
149 29
28 75
37 44
0 294
2 183 11
63 141
11 143
242 162
130 53
136 50
-1 340
149 29
28 75
37 44
0 294
2 183 11
63 141
6 143
242 162
130 53
136 50
-1 340
149 29
28 75
37 44
0 294
2 183 11
65 141
6 143
242 162
130 53
136 50
-1 340
149 29
28 75
37 44
0 294
2 183 11
65 141
6 143
242 162
130 76
136 50
-1 340
149 29
28 75
37 44
0 294
2 183 11
65 141
6 143
242 200
130 76
136 50
-1 340
149 29
28 75
37 44
0 294
2 183 11
65 141
6 143
242 200
130 76
177 50
-1 340
149 29
28 75
37 44
0 294
2 183 11
65 141
6 143
242 200
130 76
321 50
-1 340
149 29
28 75
37 44
0 294
2 183 11
65 141
6 143
242 200
130 76
321 50
-1 340
149 29
28 75
37 53
0 294
2 183 11
124 141
6 143
242 200
130 76
321 50
-1 340
149 29
28 75
37 53
0 294
2 183 11
124 141
6 143
242 341
130 76
321 50
-1 340
149 29
28 75
37 53
0 294
2 183 11
124 141
6 143
242 341
130 76
321 50
-1 340
149 29
28 70
37 53
0 294
2 183 11
124 141
6 143
242 341
130 76
321 50
-1 340
149 29
28 10
37 53
0 294
2 183 11
124 141
6 143
242 341
130 76
321 50
-1 340
149 29
56 10
37 53
0 294
2 183 11
124 141
6 143
242 341
130 76
371 50
-1 340
149 29
56 10
37 53
0 294
2 183 11
124 141
6 143
242 341
130 76
371 50
-1 340
149 34
56 10
37 53
0 294
2 183 11
124 141
6 143
242 341
130 76
371 50
-1 340
149 34
56 10
37 53
0 294
2 145 11
124 141
6 143
242 341
130 76
371 50
-1 340
149 34
56 10
37 0
0 294
2 145 11
124 141
6 143
242 341
130 76
371 50
-1 340
149 34
56 10
37 0
0 294
1 145 11
124 141
6 143
242 341
130 76
371 50
-1 340
128 34
56 10
37 0
0 294
1 145 11
124 141
6 143
242 341
130 76
371 50
-1 340
128 34
28 10
37 0
0 294
1 145 11
124 141
8 143
242 341
130 76
371 50
-1 340
128 34
28 10
37 0
0 294
1 145 11
124 141
8 143
242 341
130 76
371 50
-1 340
128 34
28 10
37 0
1 294
1 145 11
124 141
8 143
242 341
130 76
371 50
-2 340
128 34
28 10
37 0
1 294
1 145 11
124 141
8 143
242 341
130 76
224 50
-2 340
128 34
28 10
37 0
1 294
1 145 11
124 141
8 143
242 341
130 76
224 50
-2 340
128 62
28 10
37 0
1 294
1 145 11
124 141
8 143
242 341
130 76
224 50
-2 340
128 62
11 10
37 0
1 294
1 145 11
124 141
8 143
242 341
130 76
224 50
-2 340
128 62
11 10
37 0
1 294
1 30 11
124 141
8 143
242 341
130 76
224 50
-2 340
154 62
11 10
37 0
1 294
1 30 11
124 141
8 143
242 341
130 76
224 50
-2 561
154 62
11 10
37 0
1 294
1 30 11
124 141
8 143
242 341
130 147
224 50
-2 561
154 62
11 10
37 0
1 294
1 30 11
124 141
8 143
242 341
130 147
224 50
-2 561
154 66
11 10
37 0
1 294
1 30 11
124 141
8 143
6 341
130 147
224 50
-2 561
154 66
11 10
37 0
1 294
1 30 11
124 141
8 143
6 341
130 147
224 50
-2 561
154 66
11 19
37 0
1 294
1 30 11
124 186
8 143
6 341
130 147
224 50
-2 561
154 66
11 19
37 0
1 294
1 30 11
124 186
8 143
6 341
10 147
224 50
-2 561
154 66
11 19
37 0
1 294
1 30 11
124 186
8 143
6 341
10 147
224 50
-2 561
154 66
12 19
37 0
1 294
1 30 11
124 186
8 143
6 341
10 147
224 50
-3 561
154 66
12 19
37 0
1 294
1 30 11
124 186
8 143
6 675
10 147
224 50
-3 561
154 66
12 19
37 0
1 294
1 30 11
124 186
8 143
6 675
10 147
248 50
-3 561
154 66
12 19
37 0
1 294
1 30 11
124 186
8 143
6 675
10 147
248 50
-3 561
154 66
13 19
37 0
1 294
1 30 11
124 186
8 143
6 675
10 186
248 50
-3 561
154 66
13 19
37 0
1 294
1 30 11
124 186
8 143
6 675
0 186
248 50
-3 561
154 66
13 19
37 0
1 294
1 30 11
124 186
8 143
6 675
0 186
248 50
-3 561
154 66
13 19
51 0
1 294
1 30 11
124 186
0 143
6 675
0 186
248 50
-3 561
154 66
13 19
51 0
1 294
1 30 11
124 186
0 143
6 675
-1 186
248 50
-3 561
154 66
13 19
51 0
1 294
1 30 11
124 186
-1 143
6 675
-1 186
248 50
-3 561
154 66
13 19
51 0
1 294
1 30 11
124 186
-1 143
6 675
-1 186
248 50
-3 561
154 66
13 11
51 0
1 294
1 30 11
124 186
-1 143
6 675
-1 186
248 50
-3 561
154 66
13 4
51 0
1 294
1 30 11
124 186
-1 143
6 675
-1 186
248 50
-3 561
154 66
13 4
80 0
1 294
1 30 11
124 186
-1 143
6 130
-1 186
248 50
-3 561
154 66
13 4
80 0
1 294
1 30 11
124 186
-1 143
6 130
-1 186
248 47
-3 561
154 66
13 4
80 0
1 294
1 30 11
124 186
-1 143
6 130
-1 186
248 47
-3 561
154 66
13 4
80 0
1 294
2 30 11
68 186
-1 143
6 130
-1 186
248 47
-3 561
154 66
13 4
80 0
1 294
2 30 11
68 186
-1 118
6 130
-1 186
248 47
-3 561
154 66
13 4
80 0
1 294
2 30 11
68 186
-1 118
6 130
-1 186
248 30
-3 561
154 66
13 4
80 0
1 294
2 30 11
68 186
-1 118
6 130
-1 186
248 30
-3 561
154 66
18 4
80 0
1 294
2 30 11
68 186
-1 118
6 130
-1 186
248 30
-3 561
154 66
18 4
80 0
1 294
1 30 11
68 186
-1 118
6 130
-1 186
248 30
-3 561
154 66
18 4
80 0
1 129
1 30 11
68 186
-1 118
6 130
-1 186
248 30
-3 561
154 26
18 4
80 0
1 129
1 30 11
68 186
-1 118
6 130
-1 186
248 30
-3 561
154 26
18 4
82 0
1 129
1 30
Possible Impossible Possible
 Impossible
 Possible
 Impossible
 Possible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
 Impossible
