QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#81724#5575. Knight's Tour ReduxCrysfly🌈AC ✓24ms9736kbC++173.8kb2023-02-26 10:03:552023-02-26 10:06:02

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-26 10:06:02]
  • Judged
  • Verdict: AC
  • Time: 24ms
  • Memory: 9736kb
  • [2023-02-26 10:03:55]
  • Submitted

answer

// what is matter? never mind.
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define int long long
using namespace std;
inline int read()
{
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	if(f)x=-x;return x;
}

#define mod 998244353
struct modint{
	int x;
	modint(int o=0){x=o;}
	modint &operator = (int o){return x=o,*this;}
	modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
	modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
	modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
	modint &operator ^=(int b){
		modint a=*this,c=1;
		for(;b;b>>=1,a*=a)if(b&1)c*=a;
		return x=c.x,*this;
	}
	modint &operator /=(modint o){return *this *=o^=mod-2;}
	friend modint operator +(modint a,modint b){return a+=b;}
	friend modint operator -(modint a,modint b){return a-=b;}
	friend modint operator *(modint a,modint b){return a*=b;}
	friend modint operator /(modint a,modint b){return a/=b;}
	friend modint operator ^(modint a,int b){return a^=b;}
	friend bool operator ==(modint a,int b){return a.x==b;}
	friend bool operator !=(modint a,int b){return a.x!=b;}
	bool operator ! () {return !x;}
	modint operator - () {return x?mod-x:0;}
	bool operator <(const modint&b)const{return x<b.x;}
};
inline modint qpow(modint x,int y){return x^y;}

vector<modint> fac,ifac,iv;
inline void initC(int n)
{
	if(iv.empty())fac=ifac=iv=vector<modint>(2,1);
	int m=iv.size(); ++n;
	if(m>=n)return;
	iv.resize(n),fac.resize(n),ifac.resize(n);
	For(i,m,n-1){
		iv[i]=iv[mod%i]*(mod-mod/i);
		fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*iv[i];
	}
}
inline modint C(int n,int m){
	if(m<0||n<m)return 0;
	return initC(n),fac[n]*ifac[m]*ifac[n-m];
}
inline modint sign(int n){return (n&1)?(mod-1):(1);}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 2000005
#define inf 0x3f3f3f3f

int n,bo;
pii res[maxn];
int m;

void wk(int x,int y){
	++m;
	res[m]=mkp(res[m-1].fi+x,res[m-1].se+y);
}

int pre[maxn];
bool f[maxn];

namespace B{


int p[maxn],q[maxn];

int e[233][233];
bool chk(int dx,int dy){
	dx=abs(dx),dy=abs(dy);
	return (dx==3&&dy==1)||(dx==1&&dy==3);
}

void main()
{
	For(i,1,n)p[i]=i;
	int tim=0;
	do{
		++tim;
	//	if(tim%100==0)cout<<tim<<"\n";
		For(i,1,n)q[i]=i;
		For(i,1,n)For(j,1,n)e[i][j]=chk(i-j,p[i]-p[j]);
		do{
			bool ok=1;
			For(i,1,n-1) if(!e[q[i]][q[i+1]]){
				ok=0;
				break;
			}
			if(ok){
				For(i,1,n) cout<<q[i]<<" "<<p[q[i]]<<"\n";
				exit(0);
			}
		}while(next_permutation(q+1,q+n+1)); 
	}while(next_permutation(p+1,p+n+1));
}	

}

signed main()
{
	n=read();
	if(n>=2 && n<=4){
		puts("IMPOSSIBLE");
		exit(0);
	}
	puts("POSSIBLE");
	if(n==1){
		puts("1 1");
		exit(0);
	}
	f[1]=1;
	for(int x:{6,8,9}){
		For(i,x+1,100000){
			if(f[i-x] && !f[i])
				f[i]=1,pre[i]=x;
		}
	}
	if(n<=6) B::main();
	res[m=1]=mkp(1,1);
	int add=0;
	if(!f[n]){
		if(f[n+1])++n,++add;
		else if(f[n+2])n+=2,add+=2;
		else assert(0);
	}
	while(n!=1){
		int x=pre[n];
		n-=x;
		if(x==6){
			wk(1,3),wk(3,1),wk(1,-3);
			wk(-3,1),wk(1,3),wk(3,1);
		}
		if(x==8){
			wk(1,3),wk(1,3),wk(3,1);
			wk(-1,-3),wk(-1,-3),wk(3,1);
			wk(1,3),wk(1,3);
		}
		if(x==9){
			wk(1,3);
			wk(3,-1);
			wk(3,-1);
			wk(-1,3);
			wk(-3,1);
			wk(-1,3);
			wk(3,-1);
			wk(3,-1);
			wk(1,3);
		}
	}
	if(add==1)--m,--add;
	if(add==2){
		For(i,2,m-1)cout<<res[i].fi-1<<" "<<res[i].se-1<<"\n";
	}else{
		For(i,1,m) cout<<res[i].fi<<" "<<res[i].se<<"\n";
	}
	return 0;
}

/*
1 1
2 4
5 3
8 2
7 5
4 6
3 9
6 8
9 7
10 10
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1

output:

POSSIBLE
1 1

result:

ok answer = 1

Test #2:

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

input:

2

output:

IMPOSSIBLE

result:

ok answer = 0

Test #3:

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

input:

3

output:

IMPOSSIBLE

result:

ok answer = 0

Test #4:

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

input:

4

output:

IMPOSSIBLE

result:

ok answer = 0

Test #5:

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

input:

5

output:

POSSIBLE
3 5
4 2
1 1
2 4
5 3

result:

ok answer = 1

Test #6:

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

input:

6

output:

POSSIBLE
1 1
2 4
5 5
6 2
3 3
4 6

result:

ok answer = 1

Test #7:

score: 0
Accepted
time: 1ms
memory: 7428kb

input:

7

output:

POSSIBLE
1 1
2 4
5 5
6 2
3 3
4 6
7 7

result:

ok answer = 1

Test #8:

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

input:

8

output:

POSSIBLE
1 1
2 4
3 7
6 8
5 5
4 2
7 3
8 6

result:

ok answer = 1

Test #9:

score: 0
Accepted
time: 1ms
memory: 7488kb

input:

9

output:

POSSIBLE
1 1
2 4
3 7
6 8
5 5
4 2
7 3
8 6
9 9

result:

ok answer = 1

Test #10:

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

input:

10

output:

POSSIBLE
1 1
2 4
5 3
8 2
7 5
4 6
3 9
6 8
9 7
10 10

result:

ok answer = 1

Test #11:

score: 0
Accepted
time: 1ms
memory: 7976kb

input:

11

output:

POSSIBLE
1 3
4 4
5 1
2 2
3 5
6 6
7 9
10 10
11 7
8 8
9 11

result:

ok answer = 1

Test #12:

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

input:

12

output:

POSSIBLE
1 1
2 4
5 5
6 2
3 3
4 6
7 7
8 10
11 11
12 8
9 9
10 12

result:

ok answer = 1

Test #13:

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

input:

13

output:

POSSIBLE
1 1
2 4
5 5
6 2
3 3
4 6
7 7
8 10
11 11
12 8
9 9
10 12
13 13

result:

ok answer = 1

Test #14:

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

input:

14

output:

POSSIBLE
1 1
2 4
3 7
6 8
5 5
4 2
7 3
8 6
9 9
10 12
13 13
14 10
11 11
12 14

result:

ok answer = 1

Test #15:

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

input:

15

output:

POSSIBLE
1 1
2 4
3 7
6 8
5 5
4 2
7 3
8 6
9 9
10 12
13 13
14 10
11 11
12 14
15 15

result:

ok answer = 1

Test #16:

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

input:

16

output:

POSSIBLE
1 1
2 4
5 3
8 2
7 5
4 6
3 9
6 8
9 7
10 10
11 13
14 14
15 11
12 12
13 15
16 16

result:

ok answer = 1

Test #17:

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

input:

17

output:

POSSIBLE
1 1
2 4
3 7
6 8
5 5
4 2
7 3
8 6
9 9
10 12
11 15
14 16
13 13
12 10
15 11
16 14
17 17

result:

ok answer = 1

Test #18:

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

input:

18

output:

POSSIBLE
1 1
2 4
5 3
8 2
7 5
4 6
3 9
6 8
9 7
10 10
11 13
12 16
15 17
14 14
13 11
16 12
17 15
18 18

result:

ok answer = 1

Test #19:

score: 0
Accepted
time: 1ms
memory: 7936kb

input:

19

output:

POSSIBLE
1 1
2 4
5 5
6 2
3 3
4 6
7 7
8 10
11 11
12 8
9 9
10 12
13 13
14 16
17 17
18 14
15 15
16 18
19 19

result:

ok answer = 1

Test #20:

score: 0
Accepted
time: 1ms
memory: 7632kb

input:

20

output:

POSSIBLE
1 1
2 4
3 7
6 8
5 5
4 2
7 3
8 6
9 9
10 12
13 13
14 10
11 11
12 14
15 15
16 18
19 19
20 16
17 17
18 20

result:

ok answer = 1

Test #21:

score: 0
Accepted
time: 16ms
memory: 9116kb

input:

99990

output:

POSSIBLE
1 1
2 4
5 3
8 2
7 5
4 6
3 9
6 8
9 7
10 10
11 13
12 16
15 17
14 14
13 11
16 12
17 15
18 18
19 21
22 22
23 19
20 20
21 23
24 24
25 27
28 28
29 25
26 26
27 29
30 30
31 33
34 34
35 31
32 32
33 35
36 36
37 39
40 40
41 37
38 38
39 41
42 42
43 45
46 46
47 43
44 44
45 47
48 48
49 51
52 52
53 49
50 ...

result:

ok answer = 1

Test #22:

score: 0
Accepted
time: 12ms
memory: 9224kb

input:

99991

output:

POSSIBLE
1 1
2 4
5 5
6 2
3 3
4 6
7 7
8 10
11 11
12 8
9 9
10 12
13 13
14 16
17 17
18 14
15 15
16 18
19 19
20 22
23 23
24 20
21 21
22 24
25 25
26 28
29 29
30 26
27 27
28 30
31 31
32 34
35 35
36 32
33 33
34 36
37 37
38 40
41 41
42 38
39 39
40 42
43 43
44 46
47 47
48 44
45 45
46 48
49 49
50 52
53 53
54 ...

result:

ok answer = 1

Test #23:

score: 0
Accepted
time: 24ms
memory: 9164kb

input:

99992

output:

POSSIBLE
1 1
2 4
5 3
8 2
7 5
4 6
3 9
6 8
9 7
10 10
11 13
12 16
15 17
14 14
13 11
16 12
17 15
18 18
19 21
20 24
23 25
22 22
21 19
24 20
25 23
26 26
27 29
30 30
31 27
28 28
29 31
32 32
33 35
36 36
37 33
34 34
35 37
38 38
39 41
42 42
43 39
40 40
41 43
44 44
45 47
48 48
49 45
46 46
47 49
50 50
51 53
54 ...

result:

ok answer = 1

Test #24:

score: 0
Accepted
time: 21ms
memory: 9156kb

input:

99993

output:

POSSIBLE
1 1
2 4
3 7
6 8
5 5
4 2
7 3
8 6
9 9
10 12
13 13
14 10
11 11
12 14
15 15
16 18
19 19
20 16
17 17
18 20
21 21
22 24
25 25
26 22
23 23
24 26
27 27
28 30
31 31
32 28
29 29
30 32
33 33
34 36
37 37
38 34
35 35
36 38
39 39
40 42
43 43
44 40
41 41
42 44
45 45
46 48
49 49
50 46
47 47
48 50
51 51
52 ...

result:

ok answer = 1

Test #25:

score: 0
Accepted
time: 22ms
memory: 9736kb

input:

99994

output:

POSSIBLE
1 1
2 4
5 3
8 2
7 5
4 6
3 9
6 8
9 7
10 10
11 13
14 14
15 11
12 12
13 15
16 16
17 19
20 20
21 17
18 18
19 21
22 22
23 25
26 26
27 23
24 24
25 27
28 28
29 31
32 32
33 29
30 30
31 33
34 34
35 37
38 38
39 35
36 36
37 39
40 40
41 43
44 44
45 41
42 42
43 45
46 46
47 49
50 50
51 47
48 48
49 51
52 ...

result:

ok answer = 1

Test #26:

score: 0
Accepted
time: 20ms
memory: 9044kb

input:

99995

output:

POSSIBLE
1 1
2 4
3 7
6 8
5 5
4 2
7 3
8 6
9 9
10 12
11 15
14 16
13 13
12 10
15 11
16 14
17 17
18 20
21 21
22 18
19 19
20 22
23 23
24 26
27 27
28 24
25 25
26 28
29 29
30 32
33 33
34 30
31 31
32 34
35 35
36 38
39 39
40 36
37 37
38 40
41 41
42 44
45 45
46 42
43 43
44 46
47 47
48 50
51 51
52 48
49 49
50 ...

result:

ok answer = 1

Test #27:

score: 0
Accepted
time: 12ms
memory: 9040kb

input:

99996

output:

POSSIBLE
1 1
2 4
5 3
8 2
7 5
4 6
3 9
6 8
9 7
10 10
11 13
12 16
15 17
14 14
13 11
16 12
17 15
18 18
19 21
22 22
23 19
20 20
21 23
24 24
25 27
28 28
29 25
26 26
27 29
30 30
31 33
34 34
35 31
32 32
33 35
36 36
37 39
40 40
41 37
38 38
39 41
42 42
43 45
46 46
47 43
44 44
45 47
48 48
49 51
52 52
53 49
50 ...

result:

ok answer = 1

Test #28:

score: 0
Accepted
time: 11ms
memory: 9076kb

input:

99997

output:

POSSIBLE
1 1
2 4
5 5
6 2
3 3
4 6
7 7
8 10
11 11
12 8
9 9
10 12
13 13
14 16
17 17
18 14
15 15
16 18
19 19
20 22
23 23
24 20
21 21
22 24
25 25
26 28
29 29
30 26
27 27
28 30
31 31
32 34
35 35
36 32
33 33
34 36
37 37
38 40
41 41
42 38
39 39
40 42
43 43
44 46
47 47
48 44
45 45
46 48
49 49
50 52
53 53
54 ...

result:

ok answer = 1

Test #29:

score: 0
Accepted
time: 14ms
memory: 9088kb

input:

99998

output:

POSSIBLE
1 1
2 4
5 3
8 2
7 5
4 6
3 9
6 8
9 7
10 10
11 13
12 16
15 17
14 14
13 11
16 12
17 15
18 18
19 21
20 24
23 25
22 22
21 19
24 20
25 23
26 26
27 29
30 30
31 27
28 28
29 31
32 32
33 35
36 36
37 33
34 34
35 37
38 38
39 41
42 42
43 39
40 40
41 43
44 44
45 47
48 48
49 45
46 46
47 49
50 50
51 53
54 ...

result:

ok answer = 1

Test #30:

score: 0
Accepted
time: 14ms
memory: 9672kb

input:

99999

output:

POSSIBLE
1 1
2 4
3 7
6 8
5 5
4 2
7 3
8 6
9 9
10 12
13 13
14 10
11 11
12 14
15 15
16 18
19 19
20 16
17 17
18 20
21 21
22 24
25 25
26 22
23 23
24 26
27 27
28 30
31 31
32 28
29 29
30 32
33 33
34 36
37 37
38 34
35 35
36 38
39 39
40 42
43 43
44 40
41 41
42 44
45 45
46 48
49 49
50 46
47 47
48 50
51 51
52 ...

result:

ok answer = 1

Test #31:

score: 0
Accepted
time: 20ms
memory: 9476kb

input:

100000

output:

POSSIBLE
1 1
2 4
5 3
8 2
7 5
4 6
3 9
6 8
9 7
10 10
11 13
14 14
15 11
12 12
13 15
16 16
17 19
20 20
21 17
18 18
19 21
22 22
23 25
26 26
27 23
24 24
25 27
28 28
29 31
32 32
33 29
30 30
31 33
34 34
35 37
38 38
39 35
36 36
37 39
40 40
41 43
44 44
45 41
42 42
43 45
46 46
47 49
50 50
51 47
48 48
49 51
52 ...

result:

ok answer = 1

Test #32:

score: 0
Accepted
time: 4ms
memory: 9644kb

input:

74615

output:

POSSIBLE
1 1
2 4
3 7
6 8
5 5
4 2
7 3
8 6
9 9
10 12
11 15
14 16
13 13
12 10
15 11
16 14
17 17
18 20
21 21
22 18
19 19
20 22
23 23
24 26
27 27
28 24
25 25
26 28
29 29
30 32
33 33
34 30
31 31
32 34
35 35
36 38
39 39
40 36
37 37
38 40
41 41
42 44
45 45
46 42
43 43
44 46
47 47
48 50
51 51
52 48
49 49
50 ...

result:

ok answer = 1

Test #33:

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

input:

25027

output:

POSSIBLE
1 1
2 4
5 5
6 2
3 3
4 6
7 7
8 10
11 11
12 8
9 9
10 12
13 13
14 16
17 17
18 14
15 15
16 18
19 19
20 22
23 23
24 20
21 21
22 24
25 25
26 28
29 29
30 26
27 27
28 30
31 31
32 34
35 35
36 32
33 33
34 36
37 37
38 40
41 41
42 38
39 39
40 42
43 43
44 46
47 47
48 44
45 45
46 48
49 49
50 52
53 53
54 ...

result:

ok answer = 1

Test #34:

score: 0
Accepted
time: 7ms
memory: 8600kb

input:

40852

output:

POSSIBLE
1 1
2 4
5 3
8 2
7 5
4 6
3 9
6 8
9 7
10 10
11 13
14 14
15 11
12 12
13 15
16 16
17 19
20 20
21 17
18 18
19 21
22 22
23 25
26 26
27 23
24 24
25 27
28 28
29 31
32 32
33 29
30 30
31 33
34 34
35 37
38 38
39 35
36 36
37 39
40 40
41 43
44 44
45 41
42 42
43 45
46 46
47 49
50 50
51 47
48 48
49 51
52 ...

result:

ok answer = 1

Test #35:

score: 0
Accepted
time: 8ms
memory: 8148kb

input:

31411

output:

POSSIBLE
1 1
2 4
5 5
6 2
3 3
4 6
7 7
8 10
11 11
12 8
9 9
10 12
13 13
14 16
17 17
18 14
15 15
16 18
19 19
20 22
23 23
24 20
21 21
22 24
25 25
26 28
29 29
30 26
27 27
28 30
31 31
32 34
35 35
36 32
33 33
34 36
37 37
38 40
41 41
42 38
39 39
40 42
43 43
44 46
47 47
48 44
45 45
46 48
49 49
50 52
53 53
54 ...

result:

ok answer = 1

Test #36:

score: 0
Accepted
time: 9ms
memory: 8096kb

input:

37332

output:

POSSIBLE
1 1
2 4
5 3
8 2
7 5
4 6
3 9
6 8
9 7
10 10
11 13
12 16
15 17
14 14
13 11
16 12
17 15
18 18
19 21
22 22
23 19
20 20
21 23
24 24
25 27
28 28
29 25
26 26
27 29
30 30
31 33
34 34
35 31
32 32
33 35
36 36
37 39
40 40
41 37
38 38
39 41
42 42
43 45
46 46
47 43
44 44
45 47
48 48
49 51
52 52
53 49
50 ...

result:

ok answer = 1

Test #37:

score: 0
Accepted
time: 12ms
memory: 8920kb

input:

80435

output:

POSSIBLE
1 1
2 4
3 7
6 8
5 5
4 2
7 3
8 6
9 9
10 12
11 15
14 16
13 13
12 10
15 11
16 14
17 17
18 20
21 21
22 18
19 19
20 22
23 23
24 26
27 27
28 24
25 25
26 28
29 29
30 32
33 33
34 30
31 31
32 34
35 35
36 38
39 39
40 36
37 37
38 40
41 41
42 44
45 45
46 42
43 43
44 46
47 47
48 50
51 51
52 48
49 49
50 ...

result:

ok answer = 1

Test #38:

score: 0
Accepted
time: 9ms
memory: 9048kb

input:

90457

output:

POSSIBLE
1 1
2 4
5 5
6 2
3 3
4 6
7 7
8 10
11 11
12 8
9 9
10 12
13 13
14 16
17 17
18 14
15 15
16 18
19 19
20 22
23 23
24 20
21 21
22 24
25 25
26 28
29 29
30 26
27 27
28 30
31 31
32 34
35 35
36 32
33 33
34 36
37 37
38 40
41 41
42 38
39 39
40 42
43 43
44 46
47 47
48 44
45 45
46 48
49 49
50 52
53 53
54 ...

result:

ok answer = 1

Test #39:

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

input:

1796

output:

POSSIBLE
1 1
2 4
5 3
8 2
7 5
4 6
3 9
6 8
9 7
10 10
11 13
12 16
15 17
14 14
13 11
16 12
17 15
18 18
19 21
20 24
23 25
22 22
21 19
24 20
25 23
26 26
27 29
30 30
31 27
28 28
29 31
32 32
33 35
36 36
37 33
34 34
35 37
38 38
39 41
42 42
43 39
40 40
41 43
44 44
45 47
48 48
49 45
46 46
47 49
50 50
51 53
54 ...

result:

ok answer = 1

Test #40:

score: 0
Accepted
time: 9ms
memory: 8576kb

input:

55809

output:

POSSIBLE
1 1
2 4
3 7
6 8
5 5
4 2
7 3
8 6
9 9
10 12
13 13
14 10
11 11
12 14
15 15
16 18
19 19
20 16
17 17
18 20
21 21
22 24
25 25
26 22
23 23
24 26
27 27
28 30
31 31
32 28
29 29
30 32
33 33
34 36
37 37
38 34
35 35
36 38
39 39
40 42
43 43
44 40
41 41
42 44
45 45
46 48
49 49
50 46
47 47
48 50
51 51
52 ...

result:

ok answer = 1

Test #41:

score: 0
Accepted
time: 11ms
memory: 9348kb

input:

97013

output:

POSSIBLE
1 1
2 4
3 7
6 8
5 5
4 2
7 3
8 6
9 9
10 12
11 15
14 16
13 13
12 10
15 11
16 14
17 17
18 20
21 21
22 18
19 19
20 22
23 23
24 26
27 27
28 24
25 25
26 28
29 29
30 32
33 33
34 30
31 31
32 34
35 35
36 38
39 39
40 36
37 37
38 40
41 41
42 44
45 45
46 42
43 43
44 46
47 47
48 50
51 51
52 48
49 49
50 ...

result:

ok answer = 1

Test #42:

score: 0
Accepted
time: 4ms
memory: 8648kb

input:

77938

output:

POSSIBLE
1 1
2 4
5 3
8 2
7 5
4 6
3 9
6 8
9 7
10 10
11 13
14 14
15 11
12 12
13 15
16 16
17 19
20 20
21 17
18 18
19 21
22 22
23 25
26 26
27 23
24 24
25 27
28 28
29 31
32 32
33 29
30 30
31 33
34 34
35 37
38 38
39 35
36 36
37 39
40 40
41 43
44 44
45 41
42 42
43 45
46 46
47 49
50 50
51 47
48 48
49 51
52 ...

result:

ok answer = 1

Test #43:

score: 0
Accepted
time: 14ms
memory: 9476kb

input:

87884

output:

POSSIBLE
1 1
2 4
5 3
8 2
7 5
4 6
3 9
6 8
9 7
10 10
11 13
12 16
15 17
14 14
13 11
16 12
17 15
18 18
19 21
20 24
23 25
22 22
21 19
24 20
25 23
26 26
27 29
30 30
31 27
28 28
29 31
32 32
33 35
36 36
37 33
34 34
35 37
38 38
39 41
42 42
43 39
40 40
41 43
44 44
45 47
48 48
49 45
46 46
47 49
50 50
51 53
54 ...

result:

ok answer = 1

Test #44:

score: 0
Accepted
time: 14ms
memory: 8520kb

input:

61687

output:

POSSIBLE
1 1
2 4
5 5
6 2
3 3
4 6
7 7
8 10
11 11
12 8
9 9
10 12
13 13
14 16
17 17
18 14
15 15
16 18
19 19
20 22
23 23
24 20
21 21
22 24
25 25
26 28
29 29
30 26
27 27
28 30
31 31
32 34
35 35
36 32
33 33
34 36
37 37
38 40
41 41
42 38
39 39
40 42
43 43
44 46
47 47
48 44
45 45
46 48
49 49
50 52
53 53
54 ...

result:

ok answer = 1

Test #45:

score: 0
Accepted
time: 9ms
memory: 8216kb

input:

32567

output:

POSSIBLE
1 1
2 4
3 7
6 8
5 5
4 2
7 3
8 6
9 9
10 12
11 15
14 16
13 13
12 10
15 11
16 14
17 17
18 20
21 21
22 18
19 19
20 22
23 23
24 26
27 27
28 24
25 25
26 28
29 29
30 32
33 33
34 30
31 31
32 34
35 35
36 38
39 39
40 36
37 37
38 40
41 41
42 44
45 45
46 42
43 43
44 46
47 47
48 50
51 51
52 48
49 49
50 ...

result:

ok answer = 1

Test #46:

score: 0
Accepted
time: 1ms
memory: 8620kb

input:

53441

output:

POSSIBLE
1 1
2 4
3 7
6 8
5 5
4 2
7 3
8 6
9 9
10 12
11 15
14 16
13 13
12 10
15 11
16 14
17 17
18 20
21 21
22 18
19 19
20 22
23 23
24 26
27 27
28 24
25 25
26 28
29 29
30 32
33 33
34 30
31 31
32 34
35 35
36 38
39 39
40 36
37 37
38 40
41 41
42 44
45 45
46 42
43 43
44 46
47 47
48 50
51 51
52 48
49 49
50 ...

result:

ok answer = 1

Test #47:

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

input:

19197

output:

POSSIBLE
1 1
2 4
3 7
6 8
5 5
4 2
7 3
8 6
9 9
10 12
13 13
14 10
11 11
12 14
15 15
16 18
19 19
20 16
17 17
18 20
21 21
22 24
25 25
26 22
23 23
24 26
27 27
28 30
31 31
32 28
29 29
30 32
33 33
34 36
37 37
38 34
35 35
36 38
39 39
40 42
43 43
44 40
41 41
42 44
45 45
46 48
49 49
50 46
47 47
48 50
51 51
52 ...

result:

ok answer = 1

Test #48:

score: 0
Accepted
time: 17ms
memory: 8868kb

input:

77260

output:

POSSIBLE
1 1
2 4
5 3
8 2
7 5
4 6
3 9
6 8
9 7
10 10
11 13
14 14
15 11
12 12
13 15
16 16
17 19
20 20
21 17
18 18
19 21
22 22
23 25
26 26
27 23
24 24
25 27
28 28
29 31
32 32
33 29
30 30
31 33
34 34
35 37
38 38
39 35
36 36
37 39
40 40
41 43
44 44
45 41
42 42
43 45
46 46
47 49
50 50
51 47
48 48
49 51
52 ...

result:

ok answer = 1

Test #49:

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

input:

6699

output:

POSSIBLE
1 1
2 4
3 7
6 8
5 5
4 2
7 3
8 6
9 9
10 12
13 13
14 10
11 11
12 14
15 15
16 18
19 19
20 16
17 17
18 20
21 21
22 24
25 25
26 22
23 23
24 26
27 27
28 30
31 31
32 28
29 29
30 32
33 33
34 36
37 37
38 34
35 35
36 38
39 39
40 42
43 43
44 40
41 41
42 44
45 45
46 48
49 49
50 46
47 47
48 50
51 51
52 ...

result:

ok answer = 1

Test #50:

score: 0
Accepted
time: 12ms
memory: 8672kb

input:

72561

output:

POSSIBLE
1 1
2 4
3 7
6 8
5 5
4 2
7 3
8 6
9 9
10 12
13 13
14 10
11 11
12 14
15 15
16 18
19 19
20 16
17 17
18 20
21 21
22 24
25 25
26 22
23 23
24 26
27 27
28 30
31 31
32 28
29 29
30 32
33 33
34 36
37 37
38 34
35 35
36 38
39 39
40 42
43 43
44 40
41 41
42 44
45 45
46 48
49 49
50 46
47 47
48 50
51 51
52 ...

result:

ok answer = 1

Test #51:

score: 0
Accepted
time: 7ms
memory: 8732kb

input:

60412

output:

POSSIBLE
1 1
2 4
5 3
8 2
7 5
4 6
3 9
6 8
9 7
10 10
11 13
14 14
15 11
12 12
13 15
16 16
17 19
20 20
21 17
18 18
19 21
22 22
23 25
26 26
27 23
24 24
25 27
28 28
29 31
32 32
33 29
30 30
31 33
34 34
35 37
38 38
39 35
36 36
37 39
40 40
41 43
44 44
45 41
42 42
43 45
46 46
47 49
50 50
51 47
48 48
49 51
52 ...

result:

ok answer = 1

Test #52:

score: 0
Accepted
time: 6ms
memory: 8824kb

input:

78243

output:

POSSIBLE
1 1
2 4
3 7
6 8
5 5
4 2
7 3
8 6
9 9
10 12
13 13
14 10
11 11
12 14
15 15
16 18
19 19
20 16
17 17
18 20
21 21
22 24
25 25
26 22
23 23
24 26
27 27
28 30
31 31
32 28
29 29
30 32
33 33
34 36
37 37
38 34
35 35
36 38
39 39
40 42
43 43
44 40
41 41
42 44
45 45
46 48
49 49
50 46
47 47
48 50
51 51
52 ...

result:

ok answer = 1

Test #53:

score: 0
Accepted
time: 20ms
memory: 9608kb

input:

93055

output:

POSSIBLE
1 1
2 4
5 5
6 2
3 3
4 6
7 7
8 10
11 11
12 8
9 9
10 12
13 13
14 16
17 17
18 14
15 15
16 18
19 19
20 22
23 23
24 20
21 21
22 24
25 25
26 28
29 29
30 26
27 27
28 30
31 31
32 34
35 35
36 32
33 33
34 36
37 37
38 40
41 41
42 38
39 39
40 42
43 43
44 46
47 47
48 44
45 45
46 48
49 49
50 52
53 53
54 ...

result:

ok answer = 1

Test #54:

score: 0
Accepted
time: 12ms
memory: 8660kb

input:

72060

output:

POSSIBLE
1 1
2 4
5 3
8 2
7 5
4 6
3 9
6 8
9 7
10 10
11 13
12 16
15 17
14 14
13 11
16 12
17 15
18 18
19 21
22 22
23 19
20 20
21 23
24 24
25 27
28 28
29 25
26 26
27 29
30 30
31 33
34 34
35 31
32 32
33 35
36 36
37 39
40 40
41 37
38 38
39 41
42 42
43 45
46 46
47 43
44 44
45 47
48 48
49 51
52 52
53 49
50 ...

result:

ok answer = 1

Test #55:

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

input:

10561

output:

POSSIBLE
1 1
2 4
5 5
6 2
3 3
4 6
7 7
8 10
11 11
12 8
9 9
10 12
13 13
14 16
17 17
18 14
15 15
16 18
19 19
20 22
23 23
24 20
21 21
22 24
25 25
26 28
29 29
30 26
27 27
28 30
31 31
32 34
35 35
36 32
33 33
34 36
37 37
38 40
41 41
42 38
39 39
40 42
43 43
44 46
47 47
48 44
45 45
46 48
49 49
50 52
53 53
54 ...

result:

ok answer = 1

Test #56:

score: 0
Accepted
time: 13ms
memory: 8388kb

input:

56368

output:

POSSIBLE
1 1
2 4
5 3
8 2
7 5
4 6
3 9
6 8
9 7
10 10
11 13
14 14
15 11
12 12
13 15
16 16
17 19
20 20
21 17
18 18
19 21
22 22
23 25
26 26
27 23
24 24
25 27
28 28
29 31
32 32
33 29
30 30
31 33
34 34
35 37
38 38
39 35
36 36
37 39
40 40
41 43
44 44
45 41
42 42
43 45
46 46
47 49
50 50
51 47
48 48
49 51
52 ...

result:

ok answer = 1

Test #57:

score: 0
Accepted
time: 10ms
memory: 8208kb

input:

44898

output:

POSSIBLE
1 1
2 4
5 3
8 2
7 5
4 6
3 9
6 8
9 7
10 10
11 13
12 16
15 17
14 14
13 11
16 12
17 15
18 18
19 21
22 22
23 19
20 20
21 23
24 24
25 27
28 28
29 25
26 26
27 29
30 30
31 33
34 34
35 31
32 32
33 35
36 36
37 39
40 40
41 37
38 38
39 41
42 42
43 45
46 46
47 43
44 44
45 47
48 48
49 51
52 52
53 49
50 ...

result:

ok answer = 1

Test #58:

score: 0
Accepted
time: 7ms
memory: 8564kb

input:

69941

output:

POSSIBLE
1 1
2 4
3 7
6 8
5 5
4 2
7 3
8 6
9 9
10 12
11 15
14 16
13 13
12 10
15 11
16 14
17 17
18 20
21 21
22 18
19 19
20 22
23 23
24 26
27 27
28 24
25 25
26 28
29 29
30 32
33 33
34 30
31 31
32 34
35 35
36 38
39 39
40 36
37 37
38 40
41 41
42 44
45 45
46 42
43 43
44 46
47 47
48 50
51 51
52 48
49 49
50 ...

result:

ok answer = 1

Test #59:

score: 0
Accepted
time: 4ms
memory: 8008kb

input:

24192

output:

POSSIBLE
1 1
2 4
5 3
8 2
7 5
4 6
3 9
6 8
9 7
10 10
11 13
12 16
15 17
14 14
13 11
16 12
17 15
18 18
19 21
22 22
23 19
20 20
21 23
24 24
25 27
28 28
29 25
26 26
27 29
30 30
31 33
34 34
35 31
32 32
33 35
36 36
37 39
40 40
41 37
38 38
39 41
42 42
43 45
46 46
47 43
44 44
45 47
48 48
49 51
52 52
53 49
50 ...

result:

ok answer = 1

Test #60:

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

input:

13677

output:

POSSIBLE
1 1
2 4
3 7
6 8
5 5
4 2
7 3
8 6
9 9
10 12
13 13
14 10
11 11
12 14
15 15
16 18
19 19
20 16
17 17
18 20
21 21
22 24
25 25
26 22
23 23
24 26
27 27
28 30
31 31
32 28
29 29
30 32
33 33
34 36
37 37
38 34
35 35
36 38
39 39
40 42
43 43
44 40
41 41
42 44
45 45
46 48
49 49
50 46
47 47
48 50
51 51
52 ...

result:

ok answer = 1

Test #61:

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

input:

47780

output:

POSSIBLE
1 1
2 4
5 3
8 2
7 5
4 6
3 9
6 8
9 7
10 10
11 13
12 16
15 17
14 14
13 11
16 12
17 15
18 18
19 21
20 24
23 25
22 22
21 19
24 20
25 23
26 26
27 29
30 30
31 27
28 28
29 31
32 32
33 35
36 36
37 33
34 34
35 37
38 38
39 41
42 42
43 39
40 40
41 43
44 44
45 47
48 48
49 45
46 46
47 49
50 50
51 53
54 ...

result:

ok answer = 1

Test #62:

score: 0
Accepted
time: 9ms
memory: 8192kb

input:

36022

output:

POSSIBLE
1 1
2 4
5 3
8 2
7 5
4 6
3 9
6 8
9 7
10 10
11 13
14 14
15 11
12 12
13 15
16 16
17 19
20 20
21 17
18 18
19 21
22 22
23 25
26 26
27 23
24 24
25 27
28 28
29 31
32 32
33 29
30 30
31 33
34 34
35 37
38 38
39 35
36 36
37 39
40 40
41 43
44 44
45 41
42 42
43 45
46 46
47 49
50 50
51 47
48 48
49 51
52 ...

result:

ok answer = 1

Test #63:

score: 0
Accepted
time: 13ms
memory: 8400kb

input:

50675

output:

POSSIBLE
1 1
2 4
3 7
6 8
5 5
4 2
7 3
8 6
9 9
10 12
11 15
14 16
13 13
12 10
15 11
16 14
17 17
18 20
21 21
22 18
19 19
20 22
23 23
24 26
27 27
28 24
25 25
26 28
29 29
30 32
33 33
34 30
31 31
32 34
35 35
36 38
39 39
40 36
37 37
38 40
41 41
42 44
45 45
46 42
43 43
44 46
47 47
48 50
51 51
52 48
49 49
50 ...

result:

ok answer = 1

Test #64:

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

input:

26644

output:

POSSIBLE
1 1
2 4
5 3
8 2
7 5
4 6
3 9
6 8
9 7
10 10
11 13
14 14
15 11
12 12
13 15
16 16
17 19
20 20
21 17
18 18
19 21
22 22
23 25
26 26
27 23
24 24
25 27
28 28
29 31
32 32
33 29
30 30
31 33
34 34
35 37
38 38
39 35
36 36
37 39
40 40
41 43
44 44
45 41
42 42
43 45
46 46
47 49
50 50
51 47
48 48
49 51
52 ...

result:

ok answer = 1

Test #65:

score: 0
Accepted
time: 4ms
memory: 8316kb

input:

56969

output:

POSSIBLE
1 1
2 4
3 7
6 8
5 5
4 2
7 3
8 6
9 9
10 12
11 15
14 16
13 13
12 10
15 11
16 14
17 17
18 20
21 21
22 18
19 19
20 22
23 23
24 26
27 27
28 24
25 25
26 28
29 29
30 32
33 33
34 30
31 31
32 34
35 35
36 38
39 39
40 36
37 37
38 40
41 41
42 44
45 45
46 42
43 43
44 46
47 47
48 50
51 51
52 48
49 49
50 ...

result:

ok answer = 1

Test #66:

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

input:

53401

output:

POSSIBLE
1 1
2 4
5 5
6 2
3 3
4 6
7 7
8 10
11 11
12 8
9 9
10 12
13 13
14 16
17 17
18 14
15 15
16 18
19 19
20 22
23 23
24 20
21 21
22 24
25 25
26 28
29 29
30 26
27 27
28 30
31 31
32 34
35 35
36 32
33 33
34 36
37 37
38 40
41 41
42 38
39 39
40 42
43 43
44 46
47 47
48 44
45 45
46 48
49 49
50 52
53 53
54 ...

result:

ok answer = 1

Test #67:

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

input:

24772

output:

POSSIBLE
1 1
2 4
5 3
8 2
7 5
4 6
3 9
6 8
9 7
10 10
11 13
14 14
15 11
12 12
13 15
16 16
17 19
20 20
21 17
18 18
19 21
22 22
23 25
26 26
27 23
24 24
25 27
28 28
29 31
32 32
33 29
30 30
31 33
34 34
35 37
38 38
39 35
36 36
37 39
40 40
41 43
44 44
45 41
42 42
43 45
46 46
47 49
50 50
51 47
48 48
49 51
52 ...

result:

ok answer = 1

Test #68:

score: 0
Accepted
time: 9ms
memory: 8040kb

input:

35433

output:

POSSIBLE
1 1
2 4
3 7
6 8
5 5
4 2
7 3
8 6
9 9
10 12
13 13
14 10
11 11
12 14
15 15
16 18
19 19
20 16
17 17
18 20
21 21
22 24
25 25
26 22
23 23
24 26
27 27
28 30
31 31
32 28
29 29
30 32
33 33
34 36
37 37
38 34
35 35
36 38
39 39
40 42
43 43
44 40
41 41
42 44
45 45
46 48
49 49
50 46
47 47
48 50
51 51
52 ...

result:

ok answer = 1

Test #69:

score: 0
Accepted
time: 16ms
memory: 8876kb

input:

89877

output:

POSSIBLE
1 1
2 4
3 7
6 8
5 5
4 2
7 3
8 6
9 9
10 12
13 13
14 10
11 11
12 14
15 15
16 18
19 19
20 16
17 17
18 20
21 21
22 24
25 25
26 22
23 23
24 26
27 27
28 30
31 31
32 28
29 29
30 32
33 33
34 36
37 37
38 34
35 35
36 38
39 39
40 42
43 43
44 40
41 41
42 44
45 45
46 48
49 49
50 46
47 47
48 50
51 51
52 ...

result:

ok answer = 1

Test #70:

score: 0
Accepted
time: 15ms
memory: 9556kb

input:

99986

output:

POSSIBLE
1 1
2 4
5 3
8 2
7 5
4 6
3 9
6 8
9 7
10 10
11 13
12 16
15 17
14 14
13 11
16 12
17 15
18 18
19 21
20 24
23 25
22 22
21 19
24 20
25 23
26 26
27 29
30 30
31 27
28 28
29 31
32 32
33 35
36 36
37 33
34 34
35 37
38 38
39 41
42 42
43 39
40 40
41 43
44 44
45 47
48 48
49 45
46 46
47 49
50 50
51 53
54 ...

result:

ok answer = 1

Test #71:

score: 0
Accepted
time: 1ms
memory: 7820kb

input:

6094

output:

POSSIBLE
1 1
2 4
5 3
8 2
7 5
4 6
3 9
6 8
9 7
10 10
11 13
14 14
15 11
12 12
13 15
16 16
17 19
20 20
21 17
18 18
19 21
22 22
23 25
26 26
27 23
24 24
25 27
28 28
29 31
32 32
33 29
30 30
31 33
34 34
35 37
38 38
39 35
36 36
37 39
40 40
41 43
44 44
45 41
42 42
43 45
46 46
47 49
50 50
51 47
48 48
49 51
52 ...

result:

ok answer = 1