QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#792168#9279. Matrix 4bulijiojiodibuliduo#AC ✓12ms3996kbC++173.2kb2024-11-29 03:03:372024-11-29 03:03:37

Judging History

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

  • [2024-11-29 03:03:37]
  • 评测
  • 测评结果:AC
  • 用时:12ms
  • 内存:3996kb
  • [2024-11-29 03:03:37]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

array<ll,2> operator + (array<ll,2> a,array<ll,2> b) {
	return {a[0]+b[0],a[1]+b[1]};
}
array<ll,2> operator - (array<ll,2> a,array<ll,2> b) {
	return {a[0]-b[0],a[1]-b[1]};
}
array<ll,2> operator * (array<ll,2> a,ll c) {
	return {a[0]*c,a[1]*c};
}
ll p,q,r,s;
int M=1000000000;
bool solve() {
	scanf("%lld%lld%lld%lld",&p,&q,&r,&s);
	if (p*s-q*r!=1) return false;
	if ((p-1)%4!=0||(s-1)%4!=0) return false;
	if (q%2!=0||r%2!=0) return false;
	array<ll,2> a{p,r},b{q,s};
	vector<string> opr;
	auto opB=[&](int tt=1){
		a=a+b*(2*tt);
		if (tt==1) opr.pb("B");
		else opr.pb("(B)"+to_string(tt));
	};
	auto opA=[&](int tt=1){
		b=b+a*(2*tt);
		if (tt==1) opr.pb("A");
		else opr.pb("(A)"+to_string(tt));
	};
	auto opa=[&](int tt=1){
		b=b-a*(2*tt);
		if (tt==1) opr.pb("a");
		else opr.pb("(a)"+to_string(tt));
	};
	auto opb=[&](int tt=1){
		a=a-b*(2*tt);
		if (tt==1) opr.pb("b");
		else opr.pb("(b)"+to_string(tt));
	};
	auto sgn=[&](ll a) {
		return a>0?1:(a==0?0:-1);
	};
	auto gaoop=[&](string a,ll t) {
		if (t<=M) opr.pb("("+a+")"+to_string(t));
		else {
			string v1="(("+a+")"+to_string(M)+")"+to_string(t/M);
			if (t%M!=0) v1+="("+a+")"+to_string(t%M);
		}
	};
	while (b[0]!=0) {
		//printf("! %lld,%lld %lld,%lld\n",a[0],a[1],b[0],b[1]);
		if (abs(a[0])>abs(b[0])) {
			if (sgn(a[0])==sgn(b[0])) {
				if (abs(a[0])>=2*abs(b[0])) {
					opb(abs(a[0])/(2*abs(b[0])));
				} else if (abs(a[0])>=4*abs(a[0]-b[0])) {
					auto dt=a-b;
					ll t=abs(a[0])/abs(a[0]-b[0])/4;
					gaoop("AbAb",t);
					a=a-dt*t*4; b=b-dt*t*4;
				} else {
					opb();
				}
			} else {
				if (abs(a[0])>=2*abs(b[0])) {
					opB(abs(a[0])/(2*abs(b[0])));
				} else {
					opB();
				}
			}
		} else {
			if (sgn(a[0])==sgn(b[0])) {
				if (abs(b[0])>=2*abs(a[0])) {
					opa(abs(b[0])/(2*abs(a[0])));
				} else if (abs(b[0])>=4*abs(b[0]-a[0])) {
					auto dt=b-a;
					ll t=abs(b[0])/abs(b[0]-a[0])/4;
					gaoop("BaBa",t);
					a=a-dt*t*4; b=b-dt*t*4;
				} else {
					opa();
				}
			} else {
				if (abs(b[0])>=2*abs(a[0])) {
					opA(abs(b[0])/(2*abs(a[0])));
				} else {
					opA();
				}
			}
		}
	}
	assert(a[0]==1&&b[1]==1);
	if (a[1]>0) {
		gaoop("b",a[1]/2);
	} else if (a[1]<0) {
		gaoop("B",-a[1]/2);
	}
	reverse(all(opr));
	string s;
	for (auto o:opr) s+=o;
	puts(s.c_str());
	// [p,r], [q,s]
	return true;
}

int _;
int main() {
	for (scanf("%d",&_);_;_--) {
		if (!solve()) {
			puts("Impossible");
		}
	}
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
-7 4 -2 1
25 12 -48 -23
-1 0 0 1

output:

(a)2B
(B)1(a)6b
Impossible

result:

ok ok

Test #2:

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

input:

10
1 8 0 1
-7 2 -4 1
1 10 0 1
1 8 0 1
1 6 0 1
-7 2 -4 1
1 8 0 1
-3 2 -2 1
9 2 4 1
5 2 2 1

output:

(a)4
aBB
(a)5
(a)4
(a)3
aBB
(a)4
aB
a(b)2
ab

result:

ok ok

Test #3:

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

input:

10
-7 -4 6 5
9 -8 8 9
-3 4 -10 -3
-3 -4 0 -7
5 -2 8 -7
9 6 10 5
-11 8 2 -3
1 8 -10 1
-7 4 -4 5
1 10 0 -3

output:

Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible

result:

ok ok

Test #4:

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

input:

10
-5 7 2 -3
-7 1 -1 0
-4 -7 1 2
-8 -1 -1 0
3 -10 -1 3
-1 6 0 -1
6 -1 -1 0
-7 8 -1 1
-1 9 0 -1
3 -5 1 -2

output:

Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible

result:

ok ok

Test #5:

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

input:

10
4 -3 0 -5
-9 -9 -3 -10
-3 -8 1 -4
2 5 -3 -2
5 -1 -7 -3
-7 6 6 9
-5 -2 6 -7
2 -6 2 2
0 4 1 0
-2 -3 0 7

output:

Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible

result:

ok ok

Test #6:

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

input:

100
997 998 -998 -999
997 998 -998 -999
-999 -998 998 997
997 -998 998 -999
-999 -998 998 997
-999 998 -998 997
-999 -998 998 997
-999 998 -998 997
-999 -998 998 997
-999 -998 998 997
-999 -998 998 997
997 -998 998 -999
997 998 -998 -999
-999 998 -998 997
-999 998 -998 997
997 998 -998 -999
-999 -99...

output:

(B)1a(BaBa)249
(B)1a(BaBa)249
Ab(AbAb)249
(b)1(AbAb)249A
Ab(AbAb)249
a(BaBa)249B
Ab(AbAb)249
a(BaBa)249B
Ab(AbAb)249
Ab(AbAb)249
Ab(AbAb)249
(b)1(AbAb)249A
(B)1a(BaBa)249
a(BaBa)249B
a(BaBa)249B
(B)1a(BaBa)249
Ab(AbAb)249
(b)1(AbAb)249A
Ab(AbAb)249
a(BaBa)249B
(B)1a(BaBa)249
(b)1(AbAb)249A
a(BaBa)24...

result:

ok ok

Test #7:

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

input:

100
997 998 -998 -999
465 -464 -466 465
-215 -214 -216 -215
-999 1000 998 -999
-999 998 -998 997
-999 998 -998 997
-999 998 -998 997
-999 -1000 -998 -999
-571 -572 572 573
997 998 -998 -999
-331 332 -994 997
749 750 -750 -751
997 -998 998 -999
-995 998 -332 333
997 998 -998 -999
-851 -608 -844 -603
...

output:

(B)1a(BaBa)249
(BaBa)116B
(b)1Ab(AbAb)53
Ab(AbAb)249A
a(BaBa)249B
a(BaBa)249B
a(BaBa)249B
(b)1(BaBa)250
(BaBa)143
(B)1a(BaBa)249
(b)2Ab(AbAb)82A
(B)1a(BaBa)187
(b)1(AbAb)249A
abAb(AbAb)82A
(B)1a(BaBa)249
a(BaBa)30bAb
(b)1(BaBa)250
(b)1(AbAb)249A
(AbAb)42AAb
(b)1Ab(AbAb)249
abAb(AbAb)82
a(BaBa)249B
A...

result:

ok ok

Test #8:

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

input:

100
-207 -206 620 617
997 994 -332 -331
-999 998 1000 -999
-999 -998 998 997
-999 -992 428 425
825 824 826 825
-231 230 232 -231
997 998 -998 -999
-999 998 1000 -999
-999 -998 -1000 -999
-207 208 -208 209
417 -416 416 -415
989 996 -424 -427
941 944 -314 -315
-999 -998 998 997
765 -764 -766 765
-999 ...

output:

(B)1Ab(AbAb)51
A(AbAb)83
(B)1a(BaBa)249B
Ab(AbAb)249
ABAb(AbAb)35
(b)1(AbAb)206
(B)1a(BaBa)57B
(B)1a(BaBa)249
(B)1a(BaBa)249B
(b)1Ab(AbAb)249
(b)1Ab(AbAb)51A
(b)1(BaBa)104B
A(B)2a(BaBa)35
ABa(BaBa)78
Ab(AbAb)249
(BaBa)191B
Ab(AbAb)249
A(AbAb)20A
A(AbAb)83A
a(BaBa)15ba
(A)2Ba(BaBa)49
(B)1(AbAb)83
(a)...

result:

ok ok

Test #9:

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

input:

6561
0 0 0 0
1 0 0 0
-1 0 0 0
0 0 0 1
0 0 0 -1
0 0 1 0
0 0 -1 0
0 1 0 0
0 -1 0 0
1 0 0 1
1 0 0 -1
-1 0 0 1
-1 0 0 -1
0 0 1 1
0 0 1 -1
0 0 -1 1
0 0 -1 -1
0 1 1 0
0 1 -1 0
0 -1 1 0
0 -1 -1 0
1 1 0 0
1 -1 0 0
-1 1 0 0
-1 -1 0 0
1 0 1 0
1 0 -1 0
-1 0 1 0
-1 0 -1 0
0 1 0 1
0 1 0 -1
0 -1 0 1
0 -1 0 -1
1 0...

output:

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
Im...

result:

ok ok

Test #10:

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

input:

10000
0 0 0 0
1 0 0 0
-1 0 0 0
0 0 0 1
0 0 0 -1
0 0 1 0
0 0 -1 0
0 1 0 0
0 -1 0 0
1 0 0 1
1 0 0 -1
-1 0 0 1
-1 0 0 -1
0 0 1 1
0 0 1 -1
0 0 -1 1
0 0 -1 -1
0 1 1 0
0 1 -1 0
0 -1 1 0
0 -1 -1 0
1 1 0 0
1 -1 0 0
-1 1 0 0
-1 -1 0 0
1 0 1 0
1 0 -1 0
-1 0 1 0
-1 0 -1 0
0 1 0 1
0 1 0 -1
0 -1 0 1
0 -1 0 -1
1 ...

output:

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
Im...

result:

ok ok

Test #11:

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

input:

10000
10 10 10 10
10 10 10 -10
10 10 -10 10
10 10 -10 -10
10 -10 10 10
10 -10 10 -10
10 -10 -10 10
10 -10 -10 -10
-10 10 10 10
-10 10 10 -10
-10 10 -10 10
-10 10 -10 -10
-10 -10 10 10
-10 -10 10 -10
-10 -10 -10 10
-10 -10 -10 -10
9 9 9 9
9 9 9 -9
9 9 -9 9
9 9 -9 -9
9 -9 9 9
9 -9 9 -9
9 -9 -9 9
9 -9 ...

output:

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
Imp...

result:

ok ok

Test #12:

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

input:

10000
-7 10 2 -3
5 2 2 1
1 2 0 1
-11 6 -2 1
9 2 4 1
1 6 0 1
1 10 0 1
1 2 0 1
-11 6 -2 1
1 0 0 1
-7 4 -2 1
1 0 0 1
5 2 2 1
1 2 0 1
1 8 0 1
5 2 2 1
-3 2 -2 1
9 4 2 1
1 8 0 1
5 2 2 1
1 4 0 1
-3 2 -2 1
5 8 -2 -3
1 2 0 1
-7 2 -4 1
9 2 4 1
-7 2 -4 1
1 2 0 1
5 2 2 1
-3 2 -2 1
-3 2 -2 1
1 8 0 1
-11 2 -6 1
5...

output:

(A)2bA
ab
a
(a)3B
a(b)2
(a)3
(a)5
a
(a)3B

(a)2B

ab
a
(a)4
ab
aB
(a)2b
(a)4
ab
(a)2
aB
ABa
a
aBB
a(b)2
aBB
a
ab
aB
aB
(a)4
aB(B)2
ab
aB
(a)5
ABa
(a)2B

(a)2B
(a)3B
(a)3
(a)2B
ABaB
a(b)2
(a)3B

(a)3
aB(B)2
(a)3
a
a(b)2
(a)2b
aB
(a)3
ABaB
(a)2B
ab
ABaB
a
a
ab
(a)2B
ABa
(a)5
aBB
(a)3
(a)2B
aBB
(a)4
aB...

result:

ok ok

Test #13:

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

input:

10000
-7 8 -6 -3
-3 6 8 -3
9 -10 -8 5
5 2 -4 5
1 -2 10 -3
9 -2 2 1
-3 -6 -4 -11
1 6 10 1
-3 -4 0 -3
9 10 0 -11
-3 6 2 -3
-7 -4 -6 -3
5 4 4 -7
5 6 10 -3
5 0 -10 1
5 4 2 -11
1 10 -2 -3
1 -8 -10 5
-7 4 -10 1
-11 -2 -10 9
-7 -10 -10 1
-7 6 -8 1
1 2 -10 9
5 -2 -4 1
-7 -6 4 -3
9 -2 8 -7
-7 -10 -4 9
5 4 8 ...

output:

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
Imp...

result:

ok ok

Test #14:

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

input:

10000
5 6 -1 -1
-8 -3 -3 -1
1 -7 0 -1
7 1 -1 0
9 7 -4 -3
-7 4 -2 1
3 10 -1 -3
-1 -4 0 1
8 9 -1 -1
-6 -5 1 1
-5 1 -1 0
-1 5 0 -1
2 -7 -1 3
5 -1 -1 0
-1 9 0 -1
5 7 2 3
4 -1 -1 0
10 -7 -3 2
-1 2 -1 1
4 -7 1 -2
-5 4 1 -1
1 5 0 1
-4 7 1 -2
5 -1 -1 0
-4 -7 1 2
-5 2 -3 1
-9 -2 4 1
-3 8 1 -3
-8 9 -1 1
7 -4 ...

output:

Impossible
Impossible
Impossible
Impossible
Impossible
(a)2B
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossib...

result:

ok ok

Test #15:

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

input:

10000
9 5 7 5
-1 -8 3 -8
-2 3 0 0
3 -2 2 -5
-8 10 -5 -4
0 5 10 -2
5 -6 9 0
-9 -4 -8 -6
8 -8 -8 6
4 9 -9 -6
2 8 4 2
-6 10 -8 3
4 -1 -8 10
-9 4 -9 6
3 6 -6 -3
-8 8 -9 1
6 -4 -4 6
-8 -8 3 -5
-3 10 -8 7
3 -5 4 3
-8 2 4 6
2 -7 -3 -8
9 -4 -10 5
-8 4 -7 10
-9 -1 9 10
0 -10 -6 -8
-5 -8 1 -1
5 10 -8 -4
1 1 -...

output:

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
Imp...

result:

ok ok

Test #16:

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

input:

10000
-35 96 4 -11
-23 40 4 -7
97 74 38 29
21 26 4 5
41 44 -14 -15
-43 36 -6 5
73 22 -10 -3
-43 32 4 -3
-11 80 -4 29
5 32 2 13
-39 20 -2 1
1 24 0 1
-43 78 -16 29
-75 68 -32 29
-59 44 4 -3
1 86 0 1
17 32 -8 -15
-55 62 -8 9
-27 14 -2 1
-55 32 12 -7
53 16 -10 -3
89 64 -32 -23
-23 40 4 -7
-63 8 -8 1
-43...

output:

(A)4BaBA
(A)3bbA
abAA(AbAb)1
(a)3(BaBa)1
ABa(BaBa)3
(a)4(BaBa)1B
(A)3(AbAb)1b
(A)5BaB
abAbA(A)3
ab(a)3
(a)10B
(a)12
abAb(b)2A
aba(BaBa)2B
(A)7BaB
(a)43
A(B)4a
(a)3bAb(AbAb)1A
(a)7B
(A)2BaaB
(A)2(AbAb)1b
A(BaBa)1bAb
(A)3bbA
(a)4B(B)3
(a)2(BaBa)3B
a(b)3(AbAb)1
(a)8B
(a)12(b)2
(A)2BaBB
(A)2bA(A)2
(A)3b...

result:

ok ok

Test #17:

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

input:

10000
5 40 -94 61
-19 -72 84 -67
69 18 -26 -79
-35 14 76 5
21 -6 84 -91
-59 -90 -12 -27
81 -6 66 9
-7 -48 -38 53
77 30 -70 -71
89 98 -34 -55
-87 -38 46 65
-39 -90 -86 -47
-15 68 64 -87
-55 20 -90 69
61 66 -54 65
73 -30 100 9
-47 -32 -50 53
-71 -94 -16 69
-43 48 82 33
-19 -52 -86 -79
69 26 -38 -7
73 ...

output:

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
Imp...

result:

ok ok

Test #18:

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

input:

10000
81 20 4 1
-15 -56 4 15
3 2 1 1
-4 -99 1 25
-89 36 42 -17
-13 10 -4 3
-37 -49 3 4
-64 -89 23 32
53 60 15 17
-37 29 14 -11
68 39 -7 -4
-5 48 -2 19
-14 71 -1 5
-15 82 2 -11
35 -24 16 -11
-92 27 17 -5
71 84 -11 -13
-67 -58 15 13
99 14 7 1
-82 49 5 -3
19 77 -1 -4
52 19 -11 -4
21 80 -5 -19
14 -61 -3...

output:

(a)10(b)2
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
(A)4bA(A)2
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impo...

result:

ok ok

Test #19:

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

input:

10000
29 40 -92 50
-4 92 35 46
-55 49 -55 5
70 -75 56 -14
59 -53 5 -30
77 24 -24 5
-88 -51 61 -54
58 -93 59 -64
63 -13 4 87
90 -79 -1 -6
-20 -50 13 55
-26 -35 96 -38
77 91 41 94
-51 -91 -94 -2
77 -81 60 70
-59 15 52 -30
-61 30 -91 -29
-79 63 19 73
64 91 -92 -12
-30 39 -86 -13
-73 78 82 94
-17 6 16 3...

output:

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
Imp...

result:

ok ok

Test #20:

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

input:

10000
100 100 100 100
100 100 100 -100
100 100 -100 100
100 100 -100 -100
100 -100 100 100
100 -100 100 -100
100 -100 -100 100
100 -100 -100 -100
-100 100 100 100
-100 100 100 -100
-100 100 -100 100
-100 100 -100 -100
-100 -100 100 100
-100 -100 100 -100
-100 -100 -100 100
-100 -100 -100 -100
99 99 ...

output:

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
Imp...

result:

ok ok

Test #21:

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

input:

9853
1 0 0 1
1 -2 0 1
1 0 -2 1
1 2 0 1
1 0 2 1
1 -2 2 -3
-3 -2 2 1
1 2 -2 -3
-3 2 -2 1
1 -4 0 1
1 0 -4 1
1 4 0 1
1 0 4 1
1 -2 -2 5
5 -2 -2 1
5 2 2 1
1 2 2 5
1 -6 0 1
1 0 -6 1
1 6 0 1
1 0 6 1
1 -2 4 -7
-7 -2 4 1
1 4 -2 -7
-7 4 -2 1
-7 2 -4 1
1 2 -4 -7
-7 -4 2 1
1 -4 2 -7
1 -8 0 1
1 0 -8 1
1 8 0 1
1 0...

output:


A
(B)1
a
(b)1
(b)1A
Ab
(B)1a
aB
(A)2
(B)2
(a)2
(b)2
(B)1A
AB
ab
(b)1a
(A)3
(B)3
(a)3
(b)3
(b)2A
Abb
(B)1(a)2
(a)2B
aBB
(B)2a
(A)2b
(b)1(A)2
(A)4
(B)4
(a)4
(b)4
Aba
abA
(b)1aB
(B)1ab
ABa
aBA
(b)1AB
(B)1Ab
(B)2A
A(B)2
(B)1(A)2
(A)2B
a(b)2
(b)2a
(a)2b
(b)1(a)2
(A)5
(B)5
(a)5
(b)5
(b)1(BaBa)1a
(a)2Ba
(...

result:

ok ok

Test #22:

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

input:

10000
-43 -128 42 125
125 -128 42 -43
-43 42 -128 125
125 42 -128 -43
125 128 -42 -43
-43 128 -42 125
125 -42 128 -43
-43 -42 128 125
41 -124 42 -127
-127 -124 42 41
41 42 -124 -127
-127 42 -124 41
-127 124 -42 41
41 124 -42 -127
-127 -42 124 41
41 -42 124 -127
41 -122 -42 125
125 -122 -42 41
41 -42...

output:

Ab(AbAb)10a
ab(AbAb)10A
(b)1a(BaBa)10B
(B)1a(BaBa)10b
ABa(BaBa)10
a(BaBa)10BA
(b)1(AbAb)10AB
(B)1Ab(AbAb)10
(b)1(AbAb)10AA
(A)2b(AbAb)10
(B)2a(BaBa)10
a(BaBa)10BB
(a)2(BaBa)10B
(B)1a(BaBa)10a
Ab(AbAb)10b
(b)2(AbAb)10A
(BaBa)10BA
A(BaBa)10B
(B)1(AbAb)10A
(AbAb)10AB
ab(AbAb)10
(b)1(AbAb)10a
a(BaBa)10b...

result:

ok ok

Test #23:

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

input:

10000
9565 1614 1286 217
8693 1644 -3400 -643
9057 3602 958 381
7741 6150 832 661
6981 4970 -2246 -1599
4621 5368 266 309
-4647 6974 -1328 1993
3113 9234 -504 -1495
-79 1468 12 -223
-4799 1814 918 -347
281 4338 -16 -247
-2639 3814 694 -1003
-5139 4946 -1784 1717
8961 2458 1214 333
7641 2462 -3386 -1...

output:

(a)4BaabA(A)6b(b)2
ABaab(AbAb)2A(AbAb)1(b)2
(a)5Ba(a)2B(B)8ab
(a)5BaBBA(B)3(AbAb)1
(A)2b(AbAb)2(b)2(AbAb)2bAb
(a)9Bab(a)3Ba(BaBa)1
(a)2Ba(a)165bA
(A)3(B)3ab(AbAb)7a
(A)3BaaB(A)9
(A)2(AbAb)1AAb(a)2bAB
(A)9b(a)2Ba(a)7
(A)2b(b)2Ab(AbAb)3A(A)2bA
abAb(AbAb)1AAba(BaBa)6B
(a)4BabA(BaBa)1BAbb
A(B)2a(a)4BAb(...

result:

ok ok

Test #24:

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

input:

10000
-7403 8318 -7884 1721
-7291 -4042 644 -8099
209 -1932 9956 -9923
8077 986 4742 1953
1345 -6556 2630 6905
8201 5150 -9098 5073
3861 -7984 -9228 -8439
-9367 -7108 7950 -3755
-8575 7052 -8794 9105
-159 -122 7318 7325
1421 1298 4180 9765
9961 -7682 -6384 -1027
-679 -5110 -2090 -7739
4501 -1640 574...

output:

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
Imp...

result:

ok ok

Test #25:

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

input:

10000
5005 9171 -2416 -4427
-7419 -7570 3341 3409
9705 -8657 1102 -983
-4727 5522 -220 257
-3087 -6509 -986 -2079
-5873 -6751 -796 -915
-1301 -4020 -278 -859
-6534 -7919 1387 1681
-9629 2403 -1699 424
4921 543 145 16
-5014 2805 -1977 1106
9289 -5175 2215 -1234
-7023 -4147 -3133 -1850
-1451 -6424 447...

output:

Impossible
Impossible
Impossible
(a)11Ba(a)8b(AbAb)1A
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impo...

result:

ok ok

Test #26:

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

input:

10000
233 1668 9955 -5209
2471 8724 7711 9452
-5398 3151 6199 -7717
5443 -6348 -6717 -5463
-9174 6934 -7132 5030
2168 -7442 -9975 8880
1008 -4070 -7446 1115
-5774 7707 5528 -5837
4828 1564 -490 -2402
4097 -6092 3586 7443
6691 451 -4330 8779
-4798 6397 -6164 583
3531 3120 -3445 -5385
-6258 -1701 -248...

output:

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
Imp...

result:

ok ok

Test #27:

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

input:

10000
3333 -10000 -3332 9997
9997 -10000 -3332 3333
3333 -3332 -10000 9997
9997 -3332 -10000 3333
9997 10000 3332 3333
3333 10000 3332 9997
9997 3332 10000 3333
3333 3332 10000 9997
3333 -9998 3332 -9995
-9995 -9998 3332 3333
3333 3332 -9998 -9995
-9995 3332 -9998 3333
-9995 9998 -3332 3333
3333 999...

output:

(AbAb)833AA
A(AbAb)833A
(B)1(BaBa)833B
(BaBa)833BB
(a)2(BaBa)833
a(BaBa)833a
(b)1(AbAb)833b
(b)2(AbAb)833
(b)1(BaBa)833BA
A(BaBa)833
(B)1(AbAb)833
(b)1Ab(AbAb)832AB
abAb(AbAb)832A
(AbAb)833a
(BaBa)833b
(b)2(BaBa)833B
(BaBa)833a
(a)2Ba(BaBa)832B
(b)2Ab(AbAb)832A
(AbAb)833b
A(AbAb)833
(b)1Ab(AbAb)832A...

result:

ok ok

Test #28:

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

input:

10000
-798847 806212 -314224 317121
-474507 934672 -75004 147741
-54967 71846 26798 -35027
322169 437656 131284 178345
-103739 680156 14340 -94019
-29623 215850 4184 -30487
462197 925374 -12734 -25495
868589 290872 102022 34165
-604063 486962 -300404 242169
-530083 416044 -97144 76245
-966923 562062...

output:

abA(A)2BABAb(AbAb)1A(AbAb)27A
(a)3(b)2Ab(AbAb)3AB(AbAb)3(b)16A
A(B)10a(b)2a(BaBa)2(b)2AbA
ab(a)2b(AbAb)3A(B)7(A)2bbaBa
(A)3(AbAb)1AABaBAb(AbAb)3(a)2B(A)3
(A)3(AbAb)3A(AbAb)6bAbA(A)3
(A)18(B)2aBAb(b)235a
(a)4bA(A)8BaBB(BaBa)18b
a(b)46(a)2Ba(a)2BaB(B)2(BaBa)1B
(a)3Ba(a)2(b)2AAbAB(A)3baBaB
(a)3B(A)6(Ab...

result:

ok ok

Test #29:

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

input:

10000
627205 700970 -468742 -630643
505397 658906 -978638 -231079
-120471 171952 533554 925937
310013 -612476 113372 923181
664513 -352048 -725218 -262675
-464443 961896 -128164 689685
-627643 250084 -227754 302589
769837 -200132 -588566 788581
874337 -203330 359452 -218319
-21143 -547222 -680924 44...

output:

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
Imp...

result:

ok ok

Test #30:

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

input:

10000
589589 927046 11353 17851
-346093 489774 157345 -222667
-123839 943091 15226 -115953
420237 909965 -120542 -261017
-669014 -498333 -310889 -231574
-390419 116516 -107322 32029
220983 788204 75073 267771
-562888 311153 -185081 102309
-792073 166396 -94913 19939
724401 87715 149984 18161
793429 ...

output:

Impossible
Impossible
Impossible
Impossible
Impossible
(a)2B(AbAb)1(b)2abAbbA(A)2BaBB
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impos...

result:

ok ok

Test #31:

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

input:

10000
-626246 343019 972428 -632022
343790 -475249 99963 -260863
829636 391605 702588 -336408
-31530 980510 204287 370578
-82302 618391 -914026 449683
-689348 573872 216107 -372945
739670 72663 381226 -813564
-185656 -592612 -732631 490311
-98864 580673 689720 -509816
-468846 803972 -913967 -864410
...

output:

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
Imp...

result:

ok ok

Test #32:

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

input:

10000
999997 999998 999996 999997
-999999 -1000000 -999998 -999999
999997 999998 -999998 -999999
-999999 -999998 999998 999997
999993 999992 999994 999993
-999995 -999994 -999996 -999995
999993 -999994 999994 -999995
-999995 999994 -999994 999993
999989 999990 999988 999989
-999991 -999992 -999990 -...

output:

a(BaBa)249999
(b)1(BaBa)250000
(B)1a(BaBa)249999
Ab(AbAb)249999
(b)1(AbAb)249998
(b)1Ab(AbAb)249998
(b)1(AbAb)249998A
a(BaBa)249998B
a(BaBa)249997
(b)1(BaBa)249998
(B)1a(BaBa)249997
Ab(AbAb)249997
(b)1(AbAb)249996
(b)1Ab(AbAb)249996
(b)1(AbAb)249996A
a(BaBa)249996B
a(BaBa)249995
(b)1(BaBa)249996
(B)...

result:

ok ok

Test #33:

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

input:

10000
999997 -999998 999998 -999999
-999999 -999998 999998 999997
-999999 999998 -999998 999997
-999999 -999998 999998 999997
-999999 999998 -999998 999997
999997 -999998 999998 -999999
999997 -999998 999998 -999999
999997 999998 -999998 -999999
-999999 999998 -999998 999997
-999999 -999998 999998 9...

output:

(b)1(AbAb)249999A
Ab(AbAb)249999
a(BaBa)249999B
Ab(AbAb)249999
a(BaBa)249999B
(b)1(AbAb)249999A
(b)1(AbAb)249999A
(B)1a(BaBa)249999
a(BaBa)249999B
Ab(AbAb)249999
(B)1a(BaBa)249999
a(BaBa)249999B
(B)1a(BaBa)249999
a(BaBa)249999B
a(BaBa)249999B
Ab(AbAb)249999
a(BaBa)249999B
Ab(AbAb)249999
a(BaBa)24999...

result:

ok ok

Test #34:

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

input:

10000
999997 -999994 333332 -333331
-999999 999998 1000000 -999999
-687795 -687796 -687794 -687795
769197 769196 769198 769197
775893 857566 -775912 -857587
-333331 333332 -999994 999997
-779659 -779660 -779658 -779659
-678179 678178 -678178 678177
-999999 999998 -999998 999997
-999999 999998 -99999...

output:

(a)2Ba(BaBa)83332B
(B)1a(BaBa)249999B
(b)1(BaBa)171949
(b)1(AbAb)192299
(BaBa)10209BBa(BaBa)2
(b)2Ab(AbAb)83332A
(b)1(BaBa)194915
a(BaBa)169544B
a(BaBa)249999B
a(BaBa)249999B
(b)1(AbAb)249999A
(B)1(AbAb)83333
a(BaBa)249999B
A(BaBa)83333
(B)1a(BaBa)249999B
a(BaBa)249999B
(AbAb)54267A
Ab(AbAb)23522A(B...

result:

ok ok

Test #35:

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

input:

10000
-982967 982964 327656 -327655
967521 967520 -967520 -967519
601393 601396 200464 200465
-999999 999998 -999998 999997
-999999 1000000 999998 -999999
-176907 -530720 176906 530717
-333331 333332 999992 -999995
-606075 -606076 606076 606077
-999999 999998 1000000 -999999
999997 -999994 333332 -3...

output:

ABa(BaBa)81913B
(AbAb)241880
(a)2(BaBa)50116
a(BaBa)249999B
Ab(AbAb)249999A
Ab(AbAb)44226a
(B)1Ab(AbAb)83332A
(BaBa)151519
(B)1a(BaBa)249999B
(a)2Ba(BaBa)83332B
(b)1(BaBa)250000
(b)1Ab(AbAb)249999
A(AbAb)83333
(B)1a(BaBa)115415B
(B)3a(BaBa)49999
(b)1(BaBa)250000
(B)1(BaBa)83333
(b)1(BaBa)250000
Ab(A...

result:

ok ok

Test #36:

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

input:

10000
333333 -1000000 -333332 999997
999997 -1000000 -333332 333333
333333 -333332 -1000000 999997
999997 -333332 -1000000 333333
999997 1000000 333332 333333
333333 1000000 333332 999997
999997 333332 1000000 333333
333333 333332 1000000 999997
333333 -999998 333332 -999995
-999995 -999998 333332 3...

output:

(AbAb)83333AA
A(AbAb)83333A
(B)1(BaBa)83333B
(BaBa)83333BB
(a)2(BaBa)83333
a(BaBa)83333a
(b)1(AbAb)83333b
(b)2(AbAb)83333
(b)1(BaBa)83333BA
A(BaBa)83333
(B)1(AbAb)83333
(b)1Ab(AbAb)83332AB
abAb(AbAb)83332A
(AbAb)83333a
(BaBa)83333b
(b)2(BaBa)83333B
(BaBa)83333a
(a)2Ba(BaBa)83332B
(b)2Ab(AbAb)83332A
...

result:

ok ok

Extra Test:

score: 0
Extra Test Passed