QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#390998#2223. Mad Diamondbear0131AC ✓5ms24688kbC++143.7kb2024-04-16 10:40:232024-04-16 10:40:23

Judging History

你现在查看的是最新测评结果

  • [2024-04-16 10:40:23]
  • 评测
  • 测评结果:AC
  • 用时:5ms
  • 内存:24688kb
  • [2024-04-16 10:40:23]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef array<int, 3> ai3;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const int Mod = 1e9 + 7;
inline int sign(int a){ return (a&1) ? (Mod-1) : 1; }
inline void uadd(int &a, int b){ a += b-Mod; a += (a>>31) & Mod; }
inline void usub(int &a, int b){ a -= b, a += (a>>31) & Mod; }
inline void umul(int &a, int b){ a = (int)(1ll * a * b % Mod); }
inline int add(int a, int b){ a += b-Mod; a += (a>>31) & Mod; return a; }
inline int sub(int a, int b){ a -= b, a += (a>>31) & Mod; return a; }
inline int mul(int a, int b){ a = (int)(1ll * a * b % Mod); return a; }
int qpow(int b, ll p){ int ret = 1; while(p){ if(p&1) umul(ret, b); umul(b, b), p >>= 1; } return ret; }
const int fN = 111;
int fact[fN], invfact[fN], pw2[fN], invpw2[fN], inv[fN];
void initfact(int n){
	pw2[0] = 1; for(int i = 1; i <= n; ++i) pw2[i] = mul(pw2[i-1], 2);
	invpw2[0] = 1; for(int i = 1; i <= n; ++i) invpw2[i] = mul(invpw2[i-1], (Mod+1) / 2);
	fact[0] = 1; for(int i = 1; i <= n; ++i) fact[i] = mul(fact[i-1], i);
	invfact[n] = qpow(fact[n], Mod-2); for(int i = n; i > 0; --i) invfact[i-1] = mul(invfact[i], i);
	for(int i = 1; i <= n; ++i) inv[i] = mul(invfact[i], fact[i-1]);
}
int binom(int n, int m){ return (m < 0 || m > n) ? 0 : mul(fact[n], mul(invfact[m], invfact[n-m])); }
const double pi = acos(-1);
inline void chmax(int &a, int b){ (b>a) ? (a=b) : 0; }
inline void chmin(int &a, int b){ (b<a) ? (a=b) : 0; }

int n;
const int L = 360;
const int p8[] = {0, 45, 90, 135, 180, 225, 270, 315, 360};

typedef array<int, 2> ai2;

bool hor[7272], ver[7272];
inline int pack(ai2 p){ return p[0] * L + p[1]; }
inline ai2 unpack(int x){ return {x / L, x % L}; }

int nxt[366][7272], dis[366][7272];
int getnxt(int x, int u){
	if(nxt[x][u] >= 0) return nxt[x][u];
	ai2 p = unpack(u);
	int d = (p[1] - x + L) % L;
	bool canver = (d > p8[2] && d < p8[6] && ver[pack({p[0], p[1]})]);
	canver |= (p[0] && (d < p8[2] || d > p8[6]) && ver[pack({p[0] - 1, p[1]})]);
	bool canhor = d && ((d < p8[4] && hor[pack({p[0], p[1]})]) || (d > p8[4] && hor[pack({p[0], (p[1] + L - 1) % L})]));
	if(canver && canhor)
		(((d > p8[1] && d < p8[3]) || (d > p8[5] && d < p8[7])) ? canver : canhor) = 0;
	if(canver){
		nxt[x][u] = getnxt(x, (d > p8[2] && d < p8[6]) ? pack({p[0] + 1, p[1]}) : pack({p[0] - 1, p[1]}));
	} else if(canhor){
		nxt[x][u] = getnxt(x, (d < p8[4]) ? pack({p[0], (p[1] + 1) % L}) : pack({p[0], (p[1] + L - 1) % L}));
	} else {
		nxt[x][u] = u;
	}
	//cout << "nxt " << x << " " << u << "(" << p[0] << " " << d << ")" << " = " << nxt[x][u] << endl;
	return nxt[x][u];
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	rep(i, n){
		int K;
		cin >> K;
		while(K--){
			int l, r;
			cin >> l >> r;
			for(int j = l; j != r; j = (j+1) % L) hor[pack({i, j})] = 1;
		}
		cin >> K;
		while(K--){
			int x;
			cin >> x;
			ver[pack({i, x})] = 1;
		}
	}

	memset(nxt, -1, sizeof(nxt));

	ai2 S, T;
	cin >> S[0] >> S[1] >> T[0] >> T[1];
	S = unpack(getnxt(0, pack(S)));

	memset(dis, 0x3f, sizeof(dis));
	dis[0][pack(S)] = 0;
	queue< pii > q;
	q.push(make_pair(0, pack(S)));
	while(!q.empty()){
		int x = q.front().first, u = q.front().second; q.pop(); int d = dis[x][u];
		assert(nxt[x][u] == u);
		if(u == pack(T)){
			cout << d << "\n";
			return 0;
		}
		auto go = [&](int nx){
			int nu = getnxt(nx, u);
			if(d + 1 < dis[nx][nu])
				dis[nx][nu] = d + 1, q.push(make_pair(nx, nu));
		};
		go((x + 1) % L), go((x + L - 1) % L);
	}

	cout << "Impossible\n";

	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 24480kb

input:

2
2 10 170 190 350
4 15 140 195 345
2 320 40 130 220
0
0 191
0 90

output:

Impossible

result:

ok single line: 'Impossible'

Test #2:

score: 0
Accepted
time: 0ms
memory: 24340kb

input:

9
1 225 180
4 45 180 270 315
5 330 0 20 135 150 230 250 290 315 315
8 0 70 150 210 250 270 315 330
8 0 50 70 70 90 150 180 210 230 250 270 270 290 315 330 330
9 0 70 110 230 250 270 290 315 330
9 0 0 10 80 100 110 120 230 240 260 270 280 290 290 315 325 330 350
13 0 80 90 110 120 135 195 240 260 290...

output:

Impossible

result:

ok single line: 'Impossible'

Test #3:

score: 0
Accepted
time: 0ms
memory: 24376kb

input:

2
1 0 90
1 45
1 0 90
0
1 0
0 90

output:

Impossible

result:

ok single line: 'Impossible'

Test #4:

score: 0
Accepted
time: 0ms
memory: 24436kb

input:

2
1 0 90
1 47
1 0 90
0
1 0
1 90

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 5ms
memory: 24412kb

input:

2
2 10 170 190 350
4 15 165 195 345
2 320 40 130 220
0
0 191
1 132

output:

78

result:

ok single line: '78'

Test #6:

score: 0
Accepted
time: 0ms
memory: 24608kb

input:

3
1 180 0
1 180
1 90 0
1 0
2 90 180 270 0
0
1 0
1 0

output:

0

result:

ok single line: '0'

Test #7:

score: 0
Accepted
time: 2ms
memory: 24376kb

input:

3
1 180 0
1 180
1 90 270
2 270 0
2 90 180 270 0
0
0 0
2 0

output:

182

result:

ok single line: '182'

Test #8:

score: 0
Accepted
time: 0ms
memory: 24376kb

input:

3
1 0 180
2 0 180
1 90 180
2 270 90
2 90 180 270 0
0
0 0
2 0

output:

Impossible

result:

ok single line: 'Impossible'

Test #9:

score: 0
Accepted
time: 0ms
memory: 24456kb

input:

3
1 180 0
1 180
2 180 270 0 90
2 270 0
2 90 180 270 0
0
1 0
1 0

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 0ms
memory: 24392kb

input:

4
0
2 0 180
1 270 180
2 270 90
2 90 135 180 45
1 135
2 45 180 225 0
0
3 0
3 0

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 0ms
memory: 24412kb

input:

4
0
2 0 180
1 90 270
3 270 0 90
3 45 90 135 225 315 0
3 225 270 0
2 45 180 225 0
0
3 0
3 0

output:

91

result:

ok single line: '91'

Test #12:

score: 0
Accepted
time: 0ms
memory: 24384kb

input:

4
1 0 180
2 0 180
1 0 90
3 270 0 180
1 45 270
2 315 0
2 45 180 225 0
0
0 0
3 0

output:

180

result:

ok single line: '180'

Test #13:

score: 0
Accepted
time: 0ms
memory: 24420kb

input:

4
1 0 180
1 180
1 270 180
2 90 180
2 45 90 135 0
1 45
2 45 180 225 0
0
0 0
3 0

output:

Impossible

result:

ok single line: 'Impossible'

Test #14:

score: 0
Accepted
time: 0ms
memory: 24380kb

input:

5
1 180 0
1 180
2 90 180 270 0
2 0 180
2 90 315 0 45
5 270 0 90 135 180
4 22 112 203 225 248 292 315 0
4 203 315 112 157
2 22 180 203 0
0
2 0
4 0

output:

270

result:

ok single line: '270'

Test #15:

score: 0
Accepted
time: 0ms
memory: 24376kb

input:

5
1 180 0
1 180
2 90 180 270 0
2 0 180
3 45 180 225 270 315 0
7 225 270 315 0 45 90 180
4 22 45 90 112 157 225 292 315
6 248 292 337 67 90 135
2 22 180 203 0
0
2 0
4 0

output:

362

result:

ok single line: '362'

Test #16:

score: 0
Accepted
time: 0ms
memory: 24440kb

input:

5
0
2 0 180
1 90 270
3 270 0 90
3 90 135 225 315 0 45
6 225 315 0 45 135 180
5 45 90 112 157 203 225 248 292 315 337
5 292 22 67 112 180
2 22 180 203 0
0
2 0
4 0

output:

Impossible

result:

ok single line: 'Impossible'

Test #17:

score: 0
Accepted
time: 0ms
memory: 24448kb

input:

5
1 180 0
1 180
2 180 270 0 90
3 270 0 180
2 90 180 315 45
5 225 270 315 45 135
4 135 157 180 225 248 315 337 112
2 225 135
2 22 180 203 0
0
2 0
3 2

output:

268

result:

ok single line: '268'

Test #18:

score: 0
Accepted
time: 0ms
memory: 24384kb

input:

6
0
2 0 180
2 180 270 0 90
3 270 90 180
2 45 135 270 0
7 225 270 0 45 90 135 180
5 90 112 135 180 203 248 292 337 0 22
7 203 248 270 315 22 67 180
4 22 157 225 248 270 315 337 0
3 203 337 157
2 22 180 203 0
0
4 0
1 0

output:

Impossible

result:

ok single line: 'Impossible'

Test #19:

score: 0
Accepted
time: 0ms
memory: 24440kb

input:

6
0
2 0 180
1 180 90
2 270 90
2 90 225 270 0
4 225 0 45 180
3 45 157 180 203 225 337
9 248 315 0 22 45 67 112 157 180
3 203 225 270 292 337 22
6 203 270 315 45 90 135
2 22 180 203 0
0
4 0
1 0

output:

Impossible

result:

ok single line: 'Impossible'

Test #20:

score: 0
Accepted
time: 2ms
memory: 24444kb

input:

6
1 180 0
1 180
1 90 0
2 270 90
2 270 315 0 135
6 225 315 0 90 135 180
4 67 90 135 157 203 225 248 337
11 203 248 292 337 0 22 45 67 112 157 180
4 45 67 90 112 135 157 203 248
6 270 315 0 22 112 180
2 22 180 203 0
0
2 4
2 4

output:

Impossible

result:

ok single line: 'Impossible'

Test #21:

score: 0
Accepted
time: 2ms
memory: 24644kb

input:

6
1 180 0
1 180
2 180 270 0 90
3 270 0 180
3 90 180 270 315 0 45
6 225 270 315 0 45 135
5 22 112 135 157 180 225 248 292 315 337
7 203 248 315 0 67 112 180
3 112 180 225 270 337 22
5 292 315 22 45 90
2 22 180 203 0
0
2 4
2 4

output:

Impossible

result:

ok single line: 'Impossible'

Test #22:

score: 0
Accepted
time: 3ms
memory: 24612kb

input:

7
1 0 180
1 180
2 180 270 0 90
3 270 0 90
2 90 225 270 0
6 225 270 0 45 90 180
5 22 67 112 157 225 248 270 292 337 0
8 203 248 292 315 22 90 112 157
3 157 225 248 270 337 67
12 203 225 248 270 292 315 337 45 67 90 112 135
8 33 56 67 78 101 112 123 146 157 203 225 237 303 337 348 22
8 214 259 281 292...

output:

Impossible

result:

ok single line: 'Impossible'

Test #23:

score: 0
Accepted
time: 0ms
memory: 24384kb

input:

7
1 0 180
1 180
1 270 90
3 270 90 180
3 135 180 225 315 0 90
4 315 0 135 180
4 45 135 180 270 292 315 0 22
6 270 337 0 45 112 157
5 22 45 67 112 135 180 203 292 315 0
10 270 292 315 337 22 45 67 90 135 180
7 33 45 90 101 112 146 168 259 303 326 337 348 0 22
7 259 281 326 0 56 78 157
2 11 180 192 0
0...

output:

Impossible

result:

ok single line: 'Impossible'

Test #24:

score: 0
Accepted
time: 5ms
memory: 24384kb

input:

7
1 180 0
1 180
2 90 180 270 0
4 270 0 90 180
3 45 90 225 270 315 0
5 225 270 90 135 180
5 67 112 135 157 203 225 270 292 315 45
9 225 248 292 337 22 112 135 157 180
3 180 203 248 315 0 112
11 203 225 292 315 337 0 45 90 135 157 180
10 11 33 45 56 78 101 112 135 146 157 168 180 214 225 237 281 315 3...

output:

176

result:

ok single line: '176'

Test #25:

score: 0
Accepted
time: 0ms
memory: 24444kb

input:

7
1 0 180
1 180
1 90 270
3 270 0 90
2 135 180 225 45
3 45 90 180
2 67 135 157 22
6 225 315 22 45 135 157
5 45 67 90 135 180 203 225 248 0 22
12 225 248 270 292 315 337 22 67 112 135 157 180
9 22 56 67 78 101 112 135 146 157 168 192 225 248 281 292 303 315 11
7 237 292 56 67 90 123 180
2 11 180 192 0...

output:

Impossible

result:

ok single line: 'Impossible'

Test #26:

score: 0
Accepted
time: 0ms
memory: 24336kb

input:

8
1 0 180
1 180
1 270 90
3 0 90 180
1 135 0
4 225 0 45 135
4 22 45 67 135 157 225 248 337
5 248 315 22 90 157
4 112 157 203 248 270 292 337 67
11 203 248 270 292 337 22 45 90 112 157 180
9 45 78 101 123 146 157 180 203 214 237 248 259 292 303 315 337 348 11
19 203 214 237 248 270 281 292 315 337 348...

output:

Impossible

result:

ok single line: 'Impossible'

Test #27:

score: 0
Accepted
time: 2ms
memory: 24684kb

input:

8
1 180 0
1 180
2 90 180 270 0
2 0 180
2 45 135 180 315
6 225 315 0 90 135 180
4 67 90 157 180 225 292 337 45
7 203 315 337 67 112 135 180
4 90 112 135 157 225 292 0 67
12 203 225 270 292 315 337 0 67 90 135 157 180
10 11 56 78 90 101 135 146 157 168 192 203 225 237 248 259 270 303 326 348 0
15 203 ...

output:

Impossible

result:

ok single line: 'Impossible'

Test #28:

score: 0
Accepted
time: 2ms
memory: 24416kb

input:

8
0
2 0 180
1 180 0
3 0 90 180
2 90 135 225 315
7 225 270 0 45 90 135 180
6 22 45 67 90 112 135 157 203 225 248 292 0
6 203 270 337 0 45 90
5 45 67 90 180 203 248 270 315 0 22
10 225 248 270 315 337 22 67 112 157 180
9 22 56 67 90 101 123 135 146 180 214 248 259 270 281 303 315 326 348
19 214 225 23...

output:

184

result:

ok single line: '184'

Test #29:

score: 0
Accepted
time: 2ms
memory: 24616kb

input:

8
0
2 0 180
1 180 90
1 180
2 90 135 225 45
5 225 0 90 135 180
5 22 90 135 157 180 203 225 270 292 337
8 203 225 270 315 337 67 112 135
3 135 180 270 292 337 112
8 203 248 270 0 90 112 157 180
8 22 56 78 90 112 135 146 157 180 192 203 248 259 270 281 11
14 192 237 259 292 11 33 56 67 78 101 112 135 1...

output:

183

result:

ok single line: '183'

Test #30:

score: 0
Accepted
time: 0ms
memory: 24460kb

input:

9
0
2 0 180
1 270 90
3 0 90 180
2 135 270 315 45
5 270 315 90 135 180
6 67 112 135 157 180 203 225 248 292 315 337 22
8 203 225 270 315 0 45 67 180
4 22 45 90 157 248 270 315 0
12 203 225 248 292 337 0 22 45 67 90 135 157
10 11 22 45 56 67 78 90 112 135 146 157 192 214 237 248 292 303 315 326 337
16...

output:

Impossible

result:

ok single line: 'Impossible'

Test #31:

score: 0
Accepted
time: 5ms
memory: 24388kb

input:

9
1 180 0
1 180
1 90 270
3 0 90 180
2 135 225 270 45
4 225 270 45 90
7 67 112 135 157 180 203 225 248 270 292 315 337 0 45
8 203 225 248 292 337 45 112 157
4 45 90 112 180 248 270 315 22
9 203 225 270 292 315 22 67 112 180
9 33 45 56 67 78 112 123 168 192 214 225 248 270 281 292 315 337 11
15 192 21...

output:

Impossible

result:

ok single line: 'Impossible'

Test #32:

score: 0
Accepted
time: 5ms
memory: 24396kb

input:

9
1 0 180
1 180
1 180 0
3 270 90 180
3 135 180 270 315 0 90
5 225 315 0 135 180
5 45 135 157 180 225 270 292 315 337 22
8 203 225 270 315 337 90 135 157
4 90 112 180 203 248 292 337 67
10 225 248 292 315 45 67 112 135 157 180
10 33 45 56 90 101 123 146 168 180 192 203 225 248 259 270 281 303 348 0 2...

output:

Impossible

result:

ok single line: 'Impossible'

Test #33:

score: 0
Accepted
time: 0ms
memory: 24448kb

input:

9
1 180 0
1 180
2 180 270 0 90
3 270 0 180
1 315 135
6 225 270 315 90 135 180
5 67 112 157 203 225 248 270 292 337 45
6 225 270 315 337 45 112
4 45 90 112 157 180 225 248 270
12 225 248 292 315 337 0 22 45 90 112 157 180
10 22 45 56 78 90 101 112 123 146 192 203 214 237 259 281 303 315 326 348 11
15...

output:

Impossible

result:

ok single line: 'Impossible'

Test #34:

score: 0
Accepted
time: 2ms
memory: 24396kb

input:

10
1 0 180
1 180
2 90 180 270 0
3 270 90 180
2 180 270 315 90
6 225 270 315 45 135 180
4 22 45 67 157 270 292 337 0
10 203 225 248 292 315 0 67 90 157 180
3 248 270 315 337 0 67
11 203 248 270 292 337 0 45 90 112 135 157
6 22 56 78 101 123 135 146 248 281 303 348 0
16 225 259 270 281 315 326 337 348...

output:

Impossible

result:

ok single line: 'Impossible'

Test #35:

score: 0
Accepted
time: 0ms
memory: 24620kb

input:

10
0
2 0 180
1 0 270
2 0 180
2 45 135 270 315
7 225 270 315 0 45 135 180
5 22 67 112 135 157 203 225 270 315 0
5 203 292 0 45 90
4 45 67 90 180 225 315 0 22
8 203 248 315 337 22 67 112 180
8 22 56 67 123 135 157 168 192 203 259 270 303 315 348 0 11
15 203 259 281 303 315 348 0 33 45 67 123 135 157 1...

output:

Impossible

result:

ok single line: 'Impossible'

Test #36:

score: 0
Accepted
time: 2ms
memory: 24384kb

input:

10
1 0 180
1 180
1 90 0
2 270 90
2 225 270 0 135
4 315 0 90 180
3 22 67 112 157 180 337
7 225 270 337 0 22 112 180
4 22 45 67 180 270 292 315 337
10 203 225 248 270 292 337 0 45 67 180
9 33 45 56 78 90 168 180 192 225 237 259 270 292 315 337 348 0 22
14 203 214 225 237 248 281 292 326 348 22 45 78 9...

output:

Impossible

result:

ok single line: 'Impossible'

Test #37:

score: 0
Accepted
time: 0ms
memory: 24384kb

input:

10
1 0 180
1 180
1 180 0
3 0 90 180
2 45 225 270 315
5 270 315 0 45 135
3 67 112 157 270 292 337
7 270 0 22 45 67 112 157
3 112 180 203 248 292 0
9 203 270 292 315 22 45 90 135 180
6 33 123 168 203 214 259 281 292 326 348 0 22
12 214 270 303 315 326 348 22 78 112 135 146 157
8 22 67 90 112 123 146 1...

output:

Impossible

result:

ok single line: 'Impossible'

Test #38:

score: 0
Accepted
time: 0ms
memory: 24460kb

input:

11
1 180 0
2 0 180
1 90 180
2 270 0
2 225 270 315 180
4 225 270 315 180
2 180 225 337 157
8 203 248 270 292 315 337 135 157
4 157 180 225 248 270 292 337 90
8 248 292 315 337 90 112 157 180
8 11 67 78 90 101 146 168 248 259 270 281 292 303 326 337 348
13 225 248 259 281 0 22 56 67 78 101 123 146 157...

output:

254

result:

ok single line: '254'

Test #39:

score: 0
Accepted
time: 2ms
memory: 24392kb

input:

11
1 180 0
1 180
1 0 270
2 270 0
3 90 180 225 270 315 0
6 270 315 0 45 90 180
5 67 90 112 157 203 248 270 292 337 22
11 203 248 292 315 337 22 45 67 112 157 180
3 90 135 180 203 248 292
7 225 315 337 0 45 90 157
4 112 123 135 315 326 348 0 101
6 248 0 101 123 135 157
4 101 112 168 214 225 237 259 78...

output:

Impossible

result:

ok single line: 'Impossible'

Test #40:

score: 0
Accepted
time: 0ms
memory: 24492kb

input:

11
0
2 0 180
1 0 270
1 0
1 45 315
5 225 270 315 0 45
3 22 45 67 203 315 337
7 203 225 248 292 0 67 180
3 67 90 112 157 248 45
10 203 225 248 270 315 0 45 67 112 157
11 11 33 56 67 78 112 123 135 146 157 168 214 237 259 270 281 292 303 326 337 348 0
15 225 237 270 292 315 326 348 22 45 56 78 112 123 ...

output:

Impossible

result:

ok single line: 'Impossible'

Test #41:

score: 0
Accepted
time: 0ms
memory: 24684kb

input:

11
1 180 0
2 0 180
1 0 90
2 270 180
2 45 180 270 0
6 225 270 315 0 90 180
6 67 90 112 135 157 180 225 270 315 337 0 45
8 203 248 292 337 45 90 135 180
6 45 67 90 112 135 180 203 225 270 315 0 22
10 225 248 270 315 337 0 45 90 112 180
8 22 56 67 101 112 168 180 225 259 270 281 303 326 337 0 11
14 225...

output:

546

result:

ok single line: '546'

Test #42:

score: 0
Accepted
time: 0ms
memory: 24676kb

input:

4
0
2 0 180
1 0 270
2 270 0
3 45 180 225 270 315 0
2 225 90
2 45 180 225 0
0
0 0
2 0

output:

180

result:

ok single line: '180'

Test #43:

score: 0
Accepted
time: 0ms
memory: 24396kb

input:

15
1 180 0
1 180
1 270 180
2 270 0
3 135 180 225 270 315 90
4 0 45 90 135
6 22 67 112 135 157 180 203 225 248 270 337 0
12 203 225 248 270 292 315 337 0 45 90 135 157
5 22 45 67 90 112 135 157 180 270 292
9 225 248 315 0 45 67 112 135 157
9 22 33 45 56 78 90 123 135 157 214 248 259 270 281 315 337 0...

output:

Impossible

result:

ok single line: 'Impossible'

Test #44:

score: 0
Accepted
time: 0ms
memory: 24392kb

input:

15
0
2 0 180
1 0 270
2 270 90
2 135 225 270 0
6 225 315 45 90 135 180
5 112 135 180 203 225 270 292 315 337 67
8 225 270 292 45 67 90 157 180
4 90 157 203 225 292 337 0 22
11 225 248 270 315 337 22 45 67 90 157 180
8 11 33 56 67 78 101 112 146 168 214 237 259 270 303 337 0
15 214 248 270 303 315 326...

output:

Impossible

result:

ok single line: 'Impossible'

Test #45:

score: 0
Accepted
time: 0ms
memory: 24616kb

input:

15
1 180 0
2 0 180
1 270 90
2 270 180
2 45 135 225 315
3 315 0 45
4 22 135 157 248 270 292 315 0
9 203 248 292 337 22 67 112 135 157
4 67 90 180 203 225 292 337 45
3 292 315 337
8 33 45 78 135 146 168 180 192 225 237 248 259 270 281 326 337
23 192 203 214 237 259 281 292 303 315 326 348 0 11 22 33 5...

output:

Impossible

result:

ok single line: 'Impossible'

Test #46:

score: 0
Accepted
time: 0ms
memory: 24392kb

input:

15
1 180 0
1 180
2 90 180 270 0
2 0 180
3 90 135 180 270 315 45
4 270 315 45 135
4 112 135 180 248 270 315 337 90
7 248 292 337 22 112 157 180
3 67 203 270 315 0 45
7 203 225 315 22 67 135 157
7 56 78 90 123 135 146 157 180 225 270 281 303 337 33
17 192 214 225 281 303 315 326 337 11 33 45 67 90 112...

output:

Impossible

result:

ok single line: 'Impossible'

Test #47:

score: 0
Accepted
time: 2ms
memory: 24688kb

input:

15
1 180 0
1 180
1 270 180
2 270 90
3 45 90 135 180 225 315
6 270 315 0 45 135 180
5 45 112 135 157 180 225 248 270 337 0
9 270 292 315 337 0 22 45 90 135
4 22 67 90 157 180 248 292 337
7 248 270 292 315 337 112 180
8 22 56 67 90 101 203 214 237 259 270 281 292 326 337 348 11
16 192 203 214 270 292 ...

output:

387

result:

ok single line: '387'

Test #48:

score: 0
Accepted
time: 0ms
memory: 24444kb

input:

20
0
2 0 180
1 180 0
2 0 90
2 225 270 0 180
4 270 315 90 135
4 22 45 90 112 157 292 337 0
7 225 292 315 337 22 67 135
3 90 157 203 270 292 67
9 225 292 315 337 45 67 112 157 180
9 11 22 33 56 67 90 123 135 168 180 214 259 270 281 303 326 337 0
18 192 203 225 248 270 292 315 337 348 22 33 67 101 123 ...

output:

764

result:

ok single line: '764'

Test #49:

score: 0
Accepted
time: 0ms
memory: 24424kb

input:

20
1 0 180
1 180
2 90 180 270 0
2 0 180
1 180 45
5 225 45 90 135 180
4 22 112 157 180 225 248 270 0
5 203 270 22 135 180
3 67 157 225 337 0 22
8 203 225 292 337 0 45 157 180
8 33 146 157 168 192 225 237 270 292 303 315 326 337 348 0 22
15 225 237 259 270 281 303 326 348 0 22 45 112 146 168 180
7 22 ...

output:

Impossible

result:

ok single line: 'Impossible'

Test #50:

score: 0
Accepted
time: 5ms
memory: 24388kb

input:

20
1 180 0
2 0 180
1 90 270
2 90 180
2 135 270 315 45
2 270 315
3 67 157 225 270 315 45
10 203 248 292 315 22 67 90 112 157 180
2 22 45 135 0
1 225
9 11 56 67 123 135 146 157 168 225 248 281 292 303 315 326 337 348 0
20 192 203 214 237 259 270 281 303 326 348 11 22 33 45 90 112 123 146 168 180
8 45 ...

output:

Impossible

result:

ok single line: 'Impossible'

Test #51:

score: 0
Accepted
time: 2ms
memory: 24388kb

input:

20
1 180 0
1 180
1 0 180
2 270 0
3 90 180 270 315 0 45
4 225 315 0 90
2 22 225 248 0
5 203 292 337 112 135
5 22 45 67 112 203 225 270 315 337 0
9 225 248 270 292 22 45 90 157 180
10 45 67 78 90 101 123 135 146 157 180 225 237 248 270 292 303 315 326 337 22
16 192 203 214 225 270 281 326 348 11 22 33...

output:

Impossible

result:

ok single line: 'Impossible'

Test #52:

score: 0
Accepted
time: 0ms
memory: 24388kb

input:

20
1 180 0
1 180
1 0 180
3 270 0 180
2 135 180 225 90
3 270 315 180
3 67 135 270 292 337 45
10 203 225 248 270 337 0 22 45 135 157
4 45 67 90 157 203 225 292 337
11 203 248 270 292 315 337 45 67 112 135 180
9 45 56 90 112 123 146 168 180 203 225 248 259 292 303 315 326 0 33
17 192 214 237 259 270 28...

output:

Impossible

result:

ok single line: 'Impossible'