QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#637408#4273. Good Gamechenxinyang200625 ✓51ms42280kbC++204.1kb2024-10-13 12:40:262024-10-13 12:40:27

Judging History

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

  • [2024-10-13 12:40:27]
  • 评测
  • 测评结果:25
  • 用时:51ms
  • 内存:42280kb
  • [2024-10-13 12:40:26]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int n,m,k;
char s[1000005];
int a[1000005],b[1000005],c[1000005];

vector <pii> answer;
int top;
int stk[1000005];
void psh(int v){
//	printf("psh %d\n",v);
	stk[++top] = v;
}
int pick(){
	assert(top);
	return stk[top--];
}
void clr(int l,int r){
//	printf("clr [%d,%d]\n",l,r);
	assert(r > l);
	if(l % 2 == r % 2){
		answer.eb(l,3);
		r -= 3;
	}
	while(l <= r){
		answer.eb(l,2);
		r -= 2;
	}
}
struct info{
	int _l[2],_r[2];
	info(){
		_l[0] = _l[1] = inf;
		_r[0] = _r[1] = 0;
	}
}dp[1000005];

void fix(info &I,int l,int r){
	if(l > r) return;
	assert(l % 2 == r % 2);
	chkmin(I._l[l % 2],l);
	chkmax(I._r[r % 2],r);
}

int sz;
int d[1000005];
void get(info &I,int up){
	rep(i,I._l[0],min(up,I._r[0])) if(i % 2 == 0) d[++sz] = i;
	rep(i,I._l[1],min(up,I._r[1])) if(i % 2) d[++sz] = i;
}

int chk(info &I,int p){
	return I._l[p % 2] <= p && p <= I._r[p % 2];
}

int valid(int p,int l,int r){
	return (p % 2 == l % 2 && l <= p && p <= r);
}

void dbg(info &I){
	printf("even range [%d,%d] odd range [%d,%d]\n",I._l[0],I._r[0],I._l[1],I._r[1]);
}

int main(){
//	freopen("test.in","r",stdin);
	scanf("%d",&n);
	scanf("%s",s + 1);
	for(int l = 1,r;l <= n;l = r + 1){
		r = l;
		while(r < n && s[r] == s[r + 1]) r++;
		a[++m] = r - l + 1;
	}

	k = 0;
	rep(i,1,m){
		if(a[i] == 1) b[k]++;
		else c[++k] = a[i];
	}
	if(!k){
		printf("-1\n");
		return 0;
	}
	fix(dp[0],b[0],b[0]);
	rep(i,1,k - 1){
		get(dp[i - 1],b[i]);
		while(sz){
			fix(dp[i],b[i] - d[sz],b[i] - d[sz]);
			fix(dp[i],abs(d[sz] - (b[i] + 1)),d[sz] + (b[i] + 1));
			sz--;
		}
		rep(p,0,1){
			int tl = max(b[i] + 1,dp[i - 1]._l[p]),tr = dp[i - 1]._r[p];
			while(tl % 2 != p) tl++;
			if(tl > tr) continue;
			fix(dp[i],tl - (b[i] + 1),tr + (b[i] + 1));
		}
//		dbg(dp[i]);
	}
/*	rep(i,1,m) printf("%d ",a[i]);
	printf("\n");
	rep(i,0,k) printf("%d ",b[i]);
	printf("\n");
	rep(i,1,k) printf("%d ",c[i]);
	printf("\n");*/
	if(!chk(dp[k - 1],b[k])){
		printf("-1\n");
		return 0;
	}
	rep(i,1,b[k]) psh(1);
	int x = b[k],y,bb,sum = n - b[k];
	per(i,k - 1,0){
		y = x;x = bb = -1;
		if(i){
			get(dp[i - 1],b[i]);
			while(sz){
				if(b[i] - d[sz] == y) x = d[sz];
				if(valid(y,abs(d[sz] - (b[i] + 1)),d[sz] + (b[i] + 1))) x = d[sz];
				sz--;
			}
//			printf("x=%d\n",x);
			rep(p,0,1){
				int tl = max(b[i] + 1,dp[i - 1]._l[p]),tr = dp[i - 1]._r[p];
				while(tl % 2 != p) tl++;
				if(tl > tr || (p + (b[i] + 1)) % 2 != y % 2) continue;
				chkmax(tl,y - (b[i] + 1));
				chkmin(tr,y + (b[i] + 1));
				if(tl <= tr) x = tl;
			}		
			assert(x != -1);
			bb = (b[i] + 1 - x + y) / 2;
		}else{
			x = 0;
			bb = b[i];
		}
//		printf("i=%d bi=%d y=%d chose x=%d bb=%d sum=%d\n",i,b[i],y,x,bb,sum);
		assert(x != -1);
		assert(bb <= b[i] + 1);
		sum -= c[i + 1];
		psh(c[i + 1]);
		rep(kk,1,bb){
			clr(sum + 1,sum + pick());
			if(kk != b[i] + 1){
				stk[top]++;
				sum--;
			}else{
				sum -= c[i];
				c[i] += pick();
				sum += c[i];
			}
		}
		rep(kk,1,b[i] - bb){
			psh(1);
			sum--;
		}
	}
	while(top) clr(1,stk[top--]);
	printf("%d\n",SZ(answer));
	for(pii I:answer) printf("%d %d\n",I.first,I.second);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 3
Accepted

Test #1:

score: 3
Accepted
time: 5ms
memory: 28380kb

input:

9
ABAABBBAA

output:

4
3 2
2 2
2 2
1 3

result:

ok good solution!

Test #2:

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

input:

13
ABABBABABBABA

output:

6
9 2
8 2
4 2
3 2
2 3
1 2

result:

ok good solution!

Test #3:

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

input:

15
AABABAABABAABAB

output:

7
11 2
10 2
6 2
5 2
4 3
1 2
1 2

result:

ok good solution!

Test #4:

score: 3
Accepted
time: 4ms
memory: 30476kb

input:

15
ABAABBBABAABBAB

output:

7
12 2
10 3
3 2
2 2
2 2
1 2
1 2

result:

ok good solution!

Test #5:

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

input:

1
B

output:

-1

result:

ok no solution

Test #6:

score: 3
Accepted
time: 3ms
memory: 24404kb

input:

2
BB

output:

1
1 2

result:

ok good solution!

Test #7:

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

input:

7
AAAABBB

output:

3
1 2
1 2
1 3

result:

ok good solution!

Test #8:

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

input:

11
BBBBBBAAAAA

output:

5
1 2
1 2
1 2
1 3
1 2

result:

ok good solution!

Test #9:

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

input:

2
AB

output:

-1

result:

ok no solution

Test #10:

score: 3
Accepted
time: 3ms
memory: 26404kb

input:

14
BAAAAAAAAAAAAA

output:

-1

result:

ok no solution

Test #11:

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

input:

14
ABBABAABBABBAB

output:

7
11 2
8 2
6 2
6 2
2 2
1 2
1 2

result:

ok good solution!

Test #12:

score: 3
Accepted
time: 3ms
memory: 26464kb

input:

15
BAABABABBABBAAB

output:

6
8 2
7 2
6 3
5 3
2 2
1 3

result:

ok good solution!

Test #13:

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

input:

14
BABBBBBBBBBBAB

output:

7
3 2
3 2
3 2
3 2
3 2
2 2
1 2

result:

ok good solution!

Test #14:

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

input:

15
BABAAAAAAAAABAB

output:

7
4 3
4 2
4 2
4 2
3 2
2 2
1 2

result:

ok good solution!

Test #15:

score: 3
Accepted
time: 4ms
memory: 26468kb

input:

14
BBBABAAAAAAABA

output:

6
6 3
6 2
6 2
5 2
1 3
1 2

result:

ok good solution!

Test #16:

score: 3
Accepted
time: 4ms
memory: 26372kb

input:

15
AAAABABAAAAABAB

output:

7
8 3
8 2
7 2
6 2
1 2
1 2
1 2

result:

ok good solution!

Test #17:

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

input:

14
BAAABABAAAABAB

output:

6
8 2
8 2
7 2
6 2
2 3
1 3

result:

ok good solution!

Test #18:

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

input:

15
ABAAAABABBBBABA

output:

7
9 2
9 2
8 2
3 2
3 2
2 3
1 2

result:

ok good solution!

Test #19:

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

input:

14
BABAAABAAAABAB

output:

6
8 2
8 2
4 3
3 3
2 2
1 2

result:

ok good solution!

Test #20:

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

input:

15
BABBABABBBBBBAB

output:

7
8 2
8 2
8 2
7 2
3 2
2 2
1 3

result:

ok good solution!

Test #21:

score: 3
Accepted
time: 2ms
memory: 30564kb

input:

14
BABAAAABABBBAB

output:

6
10 3
4 2
4 2
3 2
2 3
1 2

result:

ok good solution!

Test #22:

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

input:

15
BABAAAAAABABAAB

output:

7
13 2
4 2
4 2
4 2
3 2
2 2
1 3

result:

ok good solution!

Test #23:

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

input:

14
BABBBBBABAAAAA

output:

6
3 3
3 2
2 2
1 2
1 3
1 2

result:

ok good solution!

Test #24:

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

input:

15
BABAAAABABAAAAA

output:

7
4 2
4 2
3 2
2 2
1 2
1 3
1 2

result:

ok good solution!

Test #25:

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

input:

15
BAABABAABAABBAA

output:

7
10 2
7 2
6 2
6 2
2 2
1 2
1 3

result:

ok good solution!

Test #26:

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

input:

15
AABAABBAABAABAB

output:

7
11 2
8 2
6 2
6 2
4 3
1 2
1 2

result:

ok good solution!

Test #27:

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

input:

15
AABABBABAABBABB

output:

7
11 2
9 3
5 2
4 2
1 2
1 2
1 2

result:

ok good solution!

Test #28:

score: 3
Accepted
time: 4ms
memory: 30600kb

input:

15
BAABBABBAABABBA

output:

6
13 2
9 2
7 3
2 2
1 3
1 3

result:

ok good solution!

Test #29:

score: 3
Accepted
time: 2ms
memory: 28448kb

input:

15
BBAABBABABABBAA

output:

-1

result:

ok no solution

Test #30:

score: 3
Accepted
time: 2ms
memory: 30496kb

input:

15
ABABBAABBAABBAB

output:

-1

result:

ok no solution

Test #31:

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

input:

14
AAABAAAAABAAAB

output:

5
11 3
5 3
5 2
1 3
1 3

result:

ok good solution!

Test #32:

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

input:

15
ABBBBABBBBBABBB

output:

6
7 3
7 2
2 2
2 2
1 3
1 3

result:

ok good solution!

Test #33:

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

input:

14
BBBBABBABAAABA

output:

6
10 3
9 2
6 2
1 2
1 2
1 3

result:

ok good solution!

Test #34:

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

input:

15
AAAAABABBBABBAB

output:

6
12 2
8 3
7 3
1 3
1 2
1 2

result:

ok good solution!

Test #35:

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

input:

14
AABABBBBABAAAB

output:

6
11 3
5 2
5 2
4 2
1 2
1 3

result:

ok good solution!

Test #36:

score: 3
Accepted
time: 5ms
memory: 30476kb

input:

15
BAABAAAABABBBBA

output:

7
11 2
11 2
5 2
5 2
2 2
1 3
1 2

result:

ok good solution!

Test #37:

score: 3
Accepted
time: 4ms
memory: 28496kb

input:

14
ABBBABAAABAAAB

output:

5
11 3
7 3
2 3
1 2
1 3

result:

ok good solution!

Test #38:

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

input:

15
BAAABABBBBABAAA

output:

6
7 2
7 2
6 2
2 3
1 3
1 3

result:

ok good solution!

Test #39:

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

input:

14
BABBABBBBABAAA

output:

6
6 2
6 2
3 2
2 3
1 2
1 3

result:

ok good solution!

Test #40:

score: 3
Accepted
time: 4ms
memory: 30500kb

input:

15
ABAAABABBBABBBB

output:

6
8 3
3 3
2 2
1 3
1 2
1 2

result:

ok good solution!

Test #41:

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

input:

14
AABABABBAABBAA

output:

-1

result:

ok no solution

Test #42:

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

input:

15
AABBBABABAABBAA

output:

-1

result:

ok no solution

Test #43:

score: 3
Accepted
time: 4ms
memory: 28436kb

input:

14
AABBAABABABBAA

output:

-1

result:

ok no solution

Test #44:

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

input:

15
BBBAABBAABABABB

output:

-1

result:

ok no solution

Test #45:

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

input:

15
BABABBBBAABBAAA

output:

-1

result:

ok no solution

Test #46:

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

input:

15
BBBABABAABBBAAA

output:

-1

result:

ok no solution

Test #47:

score: 3
Accepted
time: 2ms
memory: 28452kb

input:

15
AAABBBBAABABABB

output:

-1

result:

ok no solution

Test #48:

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

input:

15
AAAAABBAABBABAB

output:

-1

result:

ok no solution

Test #49:

score: 3
Accepted
time: 4ms
memory: 26440kb

input:

15
BAAAABBAABBBABA

output:

-1

result:

ok no solution

Test #50:

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

input:

15
BABAAABBBAAABBA

output:

-1

result:

ok no solution

Subtask #2:

score: 6
Accepted

Test #51:

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

input:

299
ABABABABABABABABABABABABABABABABABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

-1

result:

ok no solution

Test #52:

score: 6
Accepted
time: 3ms
memory: 30496kb

input:

300
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAB...

output:

-1

result:

ok no solution

Test #53:

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

input:

299
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

149
199 2
199 2
199 2
198 2
197 2
196 2
195 2
194 2
193 2
192 2
191 2
190 2
189 2
188 2
187 2
186 2
185 2
184 2
183 2
182 2
181 2
180 2
179 2
178 2
177 2
176 2
175 2
174 2
173 2
172 2
171 2
170 2
169 2
168 2
167 2
166 2
165 2
164 2
163 2
162 2
161 2
160 2
159 2
158 2
157 2
156 2
155 2
154 2
153 2
15...

result:

ok good solution!

Test #54:

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

input:

299
BBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

148
200 3
200 2
199 2
198 2
197 2
196 2
195 2
194 2
193 2
192 2
191 2
190 2
189 2
188 2
187 2
186 2
185 2
184 2
183 2
182 2
181 2
180 2
179 2
178 2
177 2
176 2
175 2
174 2
173 2
172 2
171 2
170 2
169 2
168 2
167 2
166 2
165 2
164 2
163 2
162 2
161 2
160 2
159 2
158 2
157 2
156 2
155 2
154 2
153 2
10...

result:

ok good solution!

Test #55:

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

input:

297
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA

output:

148
224 2
222 3
221 2
220 2
219 2
218 2
217 2
216 2
215 2
214 2
213 2
212 2
211 2
210 2
209 2
208 2
207 2
206 2
205 2
204 2
203 2
202 2
201 2
200 2
199 2
198 2
197 2
196 2
195 2
194 2
193 2
192 2
191 2
190 2
189 2
188 2
187 2
186 2
185 2
184 2
183 2
182 2
181 2
180 2
179 2
178 2
177 2
176 2
175 2
17...

result:

ok good solution!

Test #56:

score: 6
Accepted
time: 4ms
memory: 28380kb

input:

300
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABAAAABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBAAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

149
209 3
208 2
208 2
207 2
206 2
205 2
204 2
203 2
202 2
201 2
200 2
199 2
198 2
197 2
196 2
195 2
194 2
193 2
192 2
191 2
190 2
189 2
188 2
187 2
186 2
185 2
184 2
183 2
182 2
181 2
180 2
179 2
178 2
177 2
176 2
175 2
174 2
173 2
172 2
171 2
170 2
169 2
168 2
167 2
166 2
165 2
164 2
163 2
162 2
16...

result:

ok good solution!

Test #57:

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

input:

299
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBAABBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

148
211 3
206 3
205 2
205 2
204 2
203 2
202 2
201 2
200 2
199 2
198 2
197 2
196 2
195 2
194 2
193 2
192 2
191 2
190 2
189 2
188 2
187 2
186 2
185 2
184 2
183 2
182 2
181 2
180 2
179 2
178 2
177 2
176 2
175 2
174 2
173 2
172 2
171 2
170 2
169 2
168 2
167 2
166 2
165 2
164 2
163 2
162 2
161 2
160 2
15...

result:

ok good solution!

Test #58:

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

input:

300
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAAAABBAAAABABABABABABABABABABABABABABABABABABABABABAB...

output:

150
250 2
250 2
244 2
244 2
243 2
243 2
242 2
241 2
240 2
239 2
238 2
237 2
236 2
235 2
234 2
233 2
232 2
231 2
230 2
229 2
228 2
227 2
226 2
225 2
224 2
223 2
222 2
221 2
220 2
219 2
218 2
217 2
216 2
215 2
214 2
213 2
212 2
211 2
210 2
209 2
208 2
207 2
206 2
205 2
204 2
203 2
202 2
201 2
200 2
19...

result:

ok good solution!

Test #59:

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

input:

298
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB

output:

149
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
...

result:

ok good solution!

Test #60:

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

input:

298
BAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

output:

-1

result:

ok no solution

Test #61:

score: 6
Accepted
time: 3ms
memory: 26472kb

input:

297
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

output:

148
1 3
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
...

result:

ok good solution!

Test #62:

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

input:

300
AAAABBBBAAAABBBBBBAABBAABBBBAAAAABBBBBAAAABBBBAAAABBBBBBAABBBAAAABBBBAAAABBBBBBAAAAABBAAABBAAABBBBBAAAABBBBAAABBBBAAAAAABBBBAABBAAAABBBBAAABBBBBAAABBBBBAAAABBAAABBBAABBBAAAABBBAAAAAABBBBBBAAABBAAAAAABBBBBAAAAAABBBBAAAAABBBBAAAABBBBBBAAABBBBAAAAAAABBAAAAAAABBBBBAAAABBBBAAAAABBBAAAAABBBAAAABBBBAAA...

output:

142
286 2
286 2
278 3
278 2
270 3
270 2
262 2
262 2
250 3
250 2
250 2
241 3
241 2
241 2
234 3
224 2
224 2
215 3
215 2
205 2
205 2
205 2
194 2
194 2
194 2
189 3
177 2
177 2
177 2
170 2
170 2
165 2
159 3
153 2
153 2
145 3
137 3
129 2
129 2
125 2
115 2
115 2
115 2
108 3
100 2
100 2
92 3
87 3
80 3
80 2
...

result:

ok good solution!

Test #63:

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

input:

299
BBBBBBBBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAAAAAAAAAABABABABABABABABABABABABABABABABABABABAAAAAAAAAAAAAAABABABABABABABABABABABABABABABABABABABABABABAAAAAAAAAAABABABABABABABABABABABABABABABABABABABABABBBBBBBABABABABABABABABABABABABABABABABABA...

output:

147
255 3
255 2
255 2
254 2
253 2
252 2
251 2
250 2
249 2
248 2
247 2
246 2
245 2
244 2
243 2
242 2
241 2
240 2
239 2
238 2
237 2
204 3
204 2
204 2
204 2
204 2
203 2
202 2
201 2
200 2
199 2
198 2
197 2
196 2
195 2
194 2
193 2
192 2
191 2
190 2
189 2
188 2
187 2
99 2
99 2
99 2
99 2
99 2
98 2
97 2
96 ...

result:

ok good solution!

Test #64:

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

input:

299
BABABABABABABABBBBBBBBBBABABABABABABABABABABABABABBBBBBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAAAAAAAAAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAAAAAAAAAABABABAAAAAAAAAAAAAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

148
210 2
210 2
210 2
210 2
210 2
210 2
210 2
209 2
208 2
207 2
206 2
205 2
195 3
195 2
195 2
195 2
195 2
194 2
193 2
192 2
191 2
190 2
189 2
188 2
187 2
186 2
185 2
184 2
183 2
182 2
181 2
180 2
179 2
178 2
177 2
176 2
175 2
174 2
173 2
172 2
171 2
170 2
169 2
168 2
167 2
166 2
165 2
164 2
163 2
16...

result:

ok good solution!

Test #65:

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

input:

298
ABABABABABABABABABAAAAABABABABABABABABABAAAABABABABABABABABABABABABABABABABBBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABAAAAAABABABABABABABBBBBBABABABABABABABABABABBBBBBABABABABABABABABABABABABABABABBBBBBABAAAAAABABABABABABABABBBBBBBABABABBBBBBABABABABABABABABABABABABABABABABABABABABABA

output:

144
250 2
250 2
250 2
249 2
248 2
247 2
246 2
245 2
238 2
238 2
238 2
238 2
237 2
236 2
235 2
234 2
233 2
232 2
231 2
230 2
229 2
228 2
227 2
226 2
225 2
224 2
218 3
218 2
218 2
217 2
216 2
210 3
210 2
210 2
209 2
208 2
207 2
206 2
205 2
204 2
203 2
202 2
175 2
175 2
175 2
174 2
173 2
172 2
171 2
17...

result:

ok good solution!

Test #66:

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

input:

298
BABABABABABABABAAAAABABABABABABABABABABABABABAAAAAABABABABABABABABABABABABABABABABABABAAAAAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBBBBABABABABABABAAAAAAAAAABBBBABABABAAAAAAAABABABABABABABAAAABABABABABABBBBBABABABABABABABABBBBABABABABABABABABABABABABABABABABABABABABABABABABABA

output:

145
244 2
244 2
243 2
242 2
241 2
240 2
239 2
238 2
237 2
236 2
235 2
234 2
233 2
232 2
231 2
230 2
229 2
224 2
224 2
224 2
223 2
222 2
221 2
220 2
219 2
218 2
217 2
216 2
215 2
214 2
210 3
210 2
209 2
208 2
207 2
206 2
205 2
204 2
203 2
202 2
201 2
200 2
199 2
189 2
189 2
189 2
189 2
188 2
187 3
18...

result:

ok good solution!

Test #67:

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

input:

297
BABABABABABABABABABABABAAAAAAABABABABABABABABABABABABABBABABABABABABABABABABABABABABABABABABABAAAAABABABABABABABAABBBBBBABAABABABABABABAAAAABABABABABBBBBBBABABABABABABABAAAABABABABAAAABABABBABABABABABABABABABABABABABABABABABABABABABABABBBBBBABABABABABABABABABABABABBBBBABABABAABBBBABABABABABABABAB

output:

143
278 2
278 2
276 3
275 2
274 2
273 2
272 2
271 2
270 2
265 2
265 2
265 2
264 2
263 2
262 2
236 2
236 2
236 2
235 2
234 2
233 2
232 2
231 2
230 2
229 2
228 2
227 2
226 2
225 2
189 2
188 2
187 2
186 2
185 2
181 3
181 2
180 2
179 2
178 2
177 2
176 2
175 2
174 2
170 3
170 2
169 2
168 2
167 2
166 2
16...

result:

ok good solution!

Test #68:

score: 6
Accepted
time: 4ms
memory: 28432kb

input:

297
BABABABABABABABABABABABABABABABABABABABAABABABABABBBBABABABAAAAAABABABABABABABBBBBABABABABABAAAABABABABABABABABABABABABABBABABABAAAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBABAAAAABABAAAABABAAAAAAABABABABABABAAAAAAAABABABABABAAABABABABABABABABABABABABABABABABBBABABABABABABABBA

output:

142
279 3
278 2
277 2
276 2
275 2
274 2
273 2
246 3
245 2
244 2
243 2
242 2
241 2
240 2
239 2
238 2
237 2
229 3
229 2
229 2
229 2
228 2
227 2
226 2
225 2
224 2
223 2
222 2
221 2
220 2
219 2
211 3
211 2
211 2
210 3
209 2
208 2
204 2
204 2
204 2
203 2
202 2
201 2
196 2
196 2
196 2
195 2
191 3
190 3
18...

result:

ok good solution!

Test #69:

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

input:

299
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

149
149 3
148 2
147 2
146 2
145 2
144 2
143 2
142 2
141 2
140 2
139 2
138 2
137 2
136 2
135 2
134 2
133 2
132 2
131 2
130 2
129 2
128 2
127 2
126 2
125 2
124 2
123 2
122 2
121 2
120 2
119 2
118 2
117 2
116 2
115 2
114 2
113 2
112 2
111 2
110 2
109 2
108 2
107 2
106 2
105 2
104 2
103 2
102 2
101 2
10...

result:

ok good solution!

Test #70:

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

input:

300
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

150
150 2
149 2
148 2
147 2
146 2
145 2
144 2
143 2
142 2
141 2
140 2
139 2
138 2
137 2
136 2
135 2
134 2
133 2
132 2
131 2
130 2
129 2
128 2
127 2
126 2
125 2
124 2
123 2
122 2
121 2
120 2
119 2
118 2
117 2
116 2
115 2
114 2
113 2
112 2
111 2
110 2
109 2
108 2
107 2
106 2
105 2
104 2
103 2
102 2
10...

result:

ok good solution!

Test #71:

score: 6
Accepted
time: 3ms
memory: 28516kb

input:

300
AABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAAAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

150
150 2
150 2
149 2
148 2
147 2
146 2
145 2
144 2
143 2
142 2
141 2
140 2
139 2
138 2
137 2
136 2
135 2
134 2
133 2
132 2
131 2
130 2
129 2
128 2
127 2
126 2
125 2
124 2
123 2
122 2
121 2
120 2
119 2
118 2
117 2
116 2
115 2
114 2
113 2
112 2
111 2
110 2
109 2
108 2
107 2
106 2
105 2
104 2
103 2
10...

result:

ok good solution!

Test #72:

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

input:

300
ABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

150
152 2
151 2
150 2
149 2
148 2
147 2
146 2
145 2
144 2
143 2
142 2
141 2
140 2
139 2
138 2
137 2
136 2
135 2
134 2
133 2
132 2
131 2
130 2
129 2
128 2
127 2
126 2
125 2
124 2
123 2
122 2
121 2
120 2
119 2
118 2
117 2
116 2
115 2
114 2
113 2
112 2
111 2
110 2
109 2
108 2
107 2
106 2
105 2
104 2
10...

result:

ok good solution!

Test #73:

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

input:

300
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

149
211 3
210 2
209 2
208 2
207 2
206 2
205 2
204 2
203 2
202 2
201 2
200 2
199 2
198 2
197 2
196 2
195 2
194 2
193 2
192 2
191 2
190 2
189 2
188 2
187 2
186 2
185 2
184 2
183 2
182 2
181 2
180 2
179 2
178 2
177 2
176 2
175 2
174 2
173 2
172 2
171 2
170 2
169 2
168 2
167 2
166 2
165 2
164 2
163 2
16...

result:

ok good solution!

Test #74:

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

input:

300
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABABABABABABABABABABABAB...

output:

150
272 2
271 2
270 2
269 2
268 2
267 2
266 2
265 2
264 2
263 2
262 2
261 2
260 2
259 2
258 2
257 2
256 2
255 2
254 2
253 2
252 2
251 2
250 2
249 2
248 2
247 2
246 2
122 2
121 2
120 2
119 2
118 2
117 2
116 2
115 2
114 2
113 2
112 2
111 2
110 2
109 2
108 2
107 2
106 2
105 2
104 2
103 2
102 2
101 2
10...

result:

ok good solution!

Test #75:

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

input:

300
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

150
298 2
148 2
147 2
146 2
145 2
144 2
143 2
142 2
141 2
140 2
139 2
138 2
137 2
136 2
135 2
134 2
133 2
132 2
131 2
130 2
129 2
128 2
127 2
126 2
125 2
124 2
123 2
122 2
121 2
120 2
119 2
118 2
117 2
116 2
115 2
114 2
113 2
112 2
111 2
110 2
109 2
108 2
107 2
106 2
105 2
104 2
103 2
102 2
101 2
10...

result:

ok good solution!

Test #76:

score: 6
Accepted
time: 2ms
memory: 28564kb

input:

299
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

149
148 3
147 2
146 2
145 2
144 2
143 2
142 2
141 2
140 2
139 2
138 2
137 2
136 2
135 2
134 2
133 2
132 2
131 2
130 2
129 2
128 2
127 2
126 2
125 2
124 2
123 2
122 2
121 2
120 2
119 2
118 2
117 2
116 2
115 2
114 2
113 2
112 2
111 2
110 2
109 2
108 2
107 2
106 2
105 2
104 2
103 2
102 2
101 2
100 2
99...

result:

ok good solution!

Test #77:

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

input:

299
BAAAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

149
152 2
151 2
150 2
149 2
148 2
147 2
146 2
145 2
144 2
143 2
142 2
141 2
140 2
139 2
138 2
137 2
136 2
135 2
134 2
133 2
132 2
131 2
130 2
129 2
128 2
127 2
126 2
125 2
124 2
123 2
122 2
121 2
120 2
119 2
118 2
117 2
116 2
115 2
114 2
113 2
112 2
111 2
110 2
109 2
108 2
107 2
106 2
105 2
104 2
10...

result:

ok good solution!

Test #78:

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

input:

299
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAAAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

149
212 2
211 2
210 2
209 2
208 2
207 2
206 2
205 2
204 2
203 2
202 2
201 2
200 2
199 2
198 2
197 2
196 2
195 2
194 2
193 2
192 2
191 2
190 2
189 2
188 2
187 2
186 2
185 2
184 2
183 2
182 2
181 2
180 2
179 2
178 2
177 2
176 2
175 2
174 2
173 2
172 2
171 2
170 2
169 2
168 2
167 2
166 2
165 2
164 2
16...

result:

ok good solution!

Test #79:

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

input:

297
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAAB

output:

148
295 2
147 2
146 2
145 2
144 2
143 2
142 2
141 2
140 2
139 2
138 2
137 2
136 2
135 2
134 2
133 2
132 2
131 2
130 2
129 2
128 2
127 2
126 2
125 2
124 2
123 2
122 2
121 2
120 2
119 2
118 2
117 2
116 2
115 2
114 2
113 2
112 2
111 2
110 2
109 2
108 2
107 2
106 2
105 2
104 2
103 2
102 2
101 2
100 2
99...

result:

ok good solution!

Test #80:

score: 6
Accepted
time: 3ms
memory: 28564kb

input:

297
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA

output:

148
235 2
147 2
146 2
145 2
144 2
143 2
142 2
141 2
140 2
139 2
138 2
137 2
136 2
135 2
134 2
133 2
132 2
131 2
130 2
129 2
128 2
127 2
126 2
125 2
124 2
123 2
122 2
121 2
120 2
119 2
118 2
117 2
116 2
115 2
114 2
113 2
112 2
111 2
110 2
109 2
108 2
107 2
106 2
105 2
104 2
103 2
102 2
101 2
100 2
99...

result:

ok good solution!

Test #81:

score: 6
Accepted
time: 4ms
memory: 30564kb

input:

297
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA

output:

148
150 2
147 2
146 3
145 2
144 2
143 2
142 2
141 2
140 2
139 2
138 2
137 2
136 2
135 2
134 2
133 2
132 2
131 2
130 2
129 2
128 2
127 2
126 2
125 2
124 2
123 2
122 2
121 2
120 2
119 2
118 2
117 2
116 2
115 2
114 2
113 2
112 2
111 2
110 2
109 2
108 2
107 2
106 2
105 2
104 2
103 2
102 2
101 2
100 2
99...

result:

ok good solution!

Test #82:

score: 6
Accepted
time: 3ms
memory: 26336kb

input:

298
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA

output:

148
150 3
149 2
148 2
147 2
146 2
145 2
144 2
143 2
142 2
141 2
140 2
139 2
138 2
137 2
136 2
135 2
134 2
133 2
132 2
131 2
130 2
129 2
128 2
127 2
126 2
125 2
124 2
123 2
122 2
121 2
120 2
119 2
118 2
117 2
116 2
115 2
114 2
113 2
112 2
111 2
110 2
109 2
108 2
107 2
106 2
105 2
104 2
103 2
102 2
10...

result:

ok good solution!

Test #83:

score: 6
Accepted
time: 2ms
memory: 28512kb

input:

300
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

149
210 2
210 2
209 2
208 2
207 2
206 2
205 2
204 2
203 2
202 2
201 2
200 2
199 2
198 2
197 2
196 2
195 2
194 2
193 2
192 2
191 2
190 2
189 2
188 2
187 2
186 2
185 2
184 2
183 2
182 2
181 2
180 2
179 2
178 2
177 2
176 2
175 2
174 2
173 2
172 2
171 2
170 2
169 2
168 2
167 2
166 2
165 2
164 2
163 2
16...

result:

ok good solution!

Test #84:

score: 6
Accepted
time: 4ms
memory: 26372kb

input:

300
ABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABAABBAABBAABBAABBAABBAAABBAABBAAABBAABBAAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBBAABBAABBAABBAABB...

output:

106
295 2
100 2
99 2
98 3
97 3
96 3
95 3
94 3
93 3
92 3
91 3
90 3
89 3
88 2
88 2
87 3
86 3
85 3
84 2
84 2
83 3
82 3
81 3
80 2
80 2
79 3
78 3
77 3
76 3
75 3
74 3
73 3
72 3
71 3
70 3
69 2
69 2
68 3
67 3
66 3
65 3
64 3
63 3
62 3
61 3
60 3
59 3
58 3
57 3
56 3
55 3
54 3
53 3
52 3
51 3
50 3
49 3
48 3
47 3...

result:

ok good solution!

Test #85:

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

input:

299
BBABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

105
202 2
201 2
199 3
197 3
195 3
193 3
191 3
189 3
187 3
184 2
184 2
182 3
180 3
178 3
176 3
174 3
172 3
170 3
168 3
166 3
164 3
162 3
159 2
159 2
157 3
155 3
153 3
151 3
149 3
147 3
145 3
143 3
141 3
139 3
137 3
135 3
133 3
131 3
129 3
127 3
125 3
123 3
121 3
119 3
117 3
115 3
113 3
111 3
109 3
10...

result:

ok good solution!

Test #86:

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

input:

299
AABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBABABABABABABABABABABABABABABABABABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBAABAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBA...

output:

133
294 2
290 2
286 2
281 3
277 2
273 2
269 2
265 2
261 2
257 2
253 2
249 2
245 2
240 3
236 2
231 2
229 3
225 2
221 2
217 2
213 2
209 2
205 2
201 2
196 3
192 2
187 2
183 2
179 2
175 2
171 2
167 2
163 2
67 2
66 2
65 2
64 2
63 2
62 2
61 2
60 2
59 2
58 2
57 2
56 2
55 2
54 2
53 2
52 2
51 2
50 2
49 2
48 ...

result:

ok good solution!

Test #87:

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

input:

299
BAABBBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAAABBAABBABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABABABABABABABABABABABABABABAB...

output:

120
266 2
265 2
264 2
263 2
262 2
261 2
260 2
259 2
258 2
257 2
256 2
255 2
254 2
253 2
252 2
251 2
200 2
198 3
196 3
194 3
192 3
190 3
188 3
186 3
184 3
182 3
180 3
178 3
176 3
174 3
172 3
170 3
168 3
166 3
164 3
162 3
160 3
158 3
156 3
154 3
152 3
150 3
148 3
146 3
144 3
142 3
140 3
138 3
136 3
13...

result:

ok good solution!

Test #88:

score: 6
Accepted
time: 4ms
memory: 28372kb

input:

300
AAABBAABBAABBAABBAABBAABBAABBAABBBAAABBAABBAABBAABBAAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

106
296 2
295 2
198 2
197 2
195 3
193 3
191 3
189 3
187 3
185 3
183 3
181 3
179 3
177 3
175 3
173 3
171 3
169 3
167 3
165 3
163 3
161 3
159 3
157 3
155 3
153 3
151 3
149 3
147 3
145 3
143 3
141 3
139 3
137 3
135 3
133 3
131 3
129 3
127 3
125 3
123 3
121 3
119 3
117 3
115 3
113 3
111 3
109 3
107 3
10...

result:

ok good solution!

Test #89:

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

input:

300
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABAABBAABBAABBAABBBAABBAABBAABBAAABBAABBAABBAAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABB...

output:

106
298 2
291 2
96 2
95 2
94 3
93 3
92 3
91 3
90 3
89 3
88 3
87 2
87 2
86 3
85 3
84 3
83 3
82 3
81 3
80 2
80 2
79 3
78 3
77 3
76 3
75 3
74 2
74 2
73 3
72 3
71 2
71 2
70 3
69 3
68 3
67 3
66 3
65 3
64 3
63 3
62 3
61 3
60 3
59 3
58 3
57 3
56 3
55 3
54 3
53 3
52 3
51 3
50 3
49 3
48 3
47 3
46 3
45 3
44 3...

result:

ok good solution!

Test #90:

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

input:

299
BBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBBAABAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBABABABABABABABABABABAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABB...

output:

123
293 2
289 2
285 2
281 2
277 2
273 2
269 2
265 2
261 2
257 2
253 2
249 2
245 2
241 2
237 2
233 2
228 3
224 2
220 2
216 2
178 2
177 2
176 2
175 2
174 2
173 2
172 2
171 2
170 2
169 2
168 2
167 2
166 2
165 2
164 2
163 2
162 2
161 2
160 2
159 2
158 2
157 3
156 3
155 3
154 3
153 3
152 3
151 3
150 3
15...

result:

ok good solution!

Test #91:

score: 6
Accepted
time: 3ms
memory: 26460kb

input:

300
ABABABABABABABABABABABABABABAABABABABABABABABABABABBAABBBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBABBAABBAABBAABBAABBAAABBAAABBAABBAABBAABBAABABABABABABABABABABABABABABABABABABABABABABAB...

output:

123
250 2
248 3
246 3
244 3
242 3
240 3
238 3
236 3
233 2
233 2
231 3
228 2
228 2
226 3
224 3
222 3
220 3
218 3
216 3
214 3
212 3
210 3
209 2
207 3
205 3
203 3
201 3
199 3
197 3
195 3
193 3
191 3
189 3
187 3
185 3
183 3
181 3
179 3
177 3
175 3
173 3
171 3
169 3
167 3
165 3
163 3
161 3
159 3
157 3
15...

result:

ok good solution!

Test #92:

score: 6
Accepted
time: 4ms
memory: 30560kb

input:

298
ABABABABABABABABABABABABABABABABAABABABABABABABABAAAAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAAAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB

output:

148
198 2
198 2
197 2
196 2
195 2
194 2
193 2
192 2
191 2
190 2
189 2
188 2
187 2
186 2
185 2
184 2
183 2
182 2
181 2
180 2
179 2
178 2
177 2
176 2
175 2
174 2
173 2
172 2
171 2
170 2
169 2
168 2
167 2
166 2
165 2
164 2
163 2
162 2
161 2
160 2
159 2
158 2
157 2
156 2
155 2
154 2
153 2
152 2
151 2
15...

result:

ok good solution!

Test #93:

score: 6
Accepted
time: 3ms
memory: 28520kb

input:

300
ABABABABABABABABABABABABABABABABABABABABABABABABAAAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAAAAABABABABABABABABABABABABABABABABABBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

149
233 2
233 2
196 3
196 2
195 2
194 2
193 2
192 2
191 2
190 2
189 2
188 2
187 2
186 2
185 2
184 2
183 2
182 2
181 2
180 2
179 2
178 2
177 2
176 2
175 2
174 2
173 2
172 2
171 2
170 2
169 2
168 2
167 2
166 2
165 2
164 3
163 2
162 2
161 2
160 2
159 2
158 2
157 2
156 2
155 2
154 2
153 2
152 2
151 2
15...

result:

ok good solution!

Test #94:

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

input:

298
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAAAAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB

output:

147
211 3
210 2
209 2
208 2
207 2
206 2
205 2
204 2
203 2
202 2
201 2
200 2
199 2
198 2
197 2
196 2
195 2
194 2
193 2
192 2
191 2
190 2
189 2
188 2
187 2
186 2
185 2
184 2
183 2
182 2
181 2
180 2
179 2
178 2
177 2
176 2
175 2
174 2
173 2
172 2
171 2
170 2
169 2
168 2
167 2
166 2
165 2
164 2
163 2
16...

result:

ok good solution!

Test #95:

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

input:

300
ABABABABABABABABABABABABABABABBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAAAAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAAAAABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

148
239 3
239 2
238 2
237 2
236 2
235 2
234 2
233 2
232 2
231 2
230 2
229 2
228 2
227 2
226 2
225 2
224 2
223 2
222 2
221 2
220 2
219 2
218 2
217 2
216 2
215 2
214 2
213 2
212 2
211 2
210 2
209 2
208 2
207 2
206 2
205 2
204 2
203 2
202 2
201 2
200 2
199 2
198 2
197 2
196 2
195 2
194 2
193 2
192 2
19...

result:

ok good solution!

Test #96:

score: 6
Accepted
time: 3ms
memory: 30356kb

input:

299
AABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAB...

output:

-1

result:

ok no solution

Test #97:

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

input:

300
AABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAA...

output:

-1

result:

ok no solution

Test #98:

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

input:

299
BBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

-1

result:

ok no solution

Test #99:

score: 6
Accepted
time: 4ms
memory: 30536kb

input:

300
BBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

-1

result:

ok no solution

Test #100:

score: 6
Accepted
time: 3ms
memory: 28452kb

input:

300
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAA...

output:

-1

result:

ok no solution

Test #101:

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

input:

300
BBAABBBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAA...

output:

-1

result:

ok no solution

Subtask #3:

score: 7
Accepted

Test #102:

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

input:

5998
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

2998
3995 3
3995 2
3995 2
3995 2
3994 2
3993 2
3992 2
3991 2
3990 2
3989 2
3988 2
3987 2
3986 2
3985 2
3984 2
3983 2
3982 2
3981 2
3980 2
3979 2
3978 2
3977 2
3976 2
3975 2
3974 2
3973 2
3972 2
3971 2
3970 2
3969 2
3968 2
3967 2
3966 2
3965 2
3964 2
3963 2
3962 2
3961 2
3960 2
3959 2
3958 2
3957 2
3...

result:

ok good solution!

Test #103:

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

input:

5999
BBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

2998
4000 3
4000 2
3999 2
3998 2
3997 2
3996 2
3995 2
3994 2
3993 2
3992 2
3991 2
3990 2
3989 2
3988 2
3987 2
3986 2
3985 2
3984 2
3983 2
3982 2
3981 2
3980 2
3979 2
3978 2
3977 2
3976 2
3975 2
3974 2
3973 2
3972 2
3971 2
3970 2
3969 2
3968 2
3967 2
3966 2
3965 2
3964 2
3963 2
3962 2
3961 2
3960 2
3...

result:

ok good solution!

Test #104:

score: 7
Accepted
time: 4ms
memory: 30536kb

input:

5998
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2998
4500 2
4497 2
4497 2
4496 2
4495 2
4494 2
4493 2
4492 2
4491 2
4490 2
4489 2
4488 2
4487 2
4486 2
4485 2
4484 2
4483 2
4482 2
4481 2
4480 2
4479 2
4478 2
4477 2
4476 2
4475 2
4474 2
4473 2
4472 2
4471 2
4470 2
4469 2
4468 2
4467 2
4466 2
4465 2
4464 2
4463 2
4462 2
4461 2
4460 2
4459 2
4458 2
4...

result:

ok good solution!

Test #105:

score: 7
Accepted
time: 2ms
memory: 28568kb

input:

5998
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2999
4198 2
4197 2
4197 2
4196 2
4195 2
4194 2
4193 2
4192 2
4191 2
4190 2
4189 2
4188 2
4187 2
4186 2
4185 2
4184 2
4183 2
4182 2
4181 2
4180 2
4179 2
4178 2
4177 2
4176 2
4175 2
4174 2
4173 2
4172 2
4171 2
4170 2
4169 2
4168 2
4167 2
4166 2
4165 2
4164 2
4163 2
4162 2
4161 2
4160 2
4159 2
4158 2
4...

result:

ok good solution!

Test #106:

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

input:

5999
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2999
4200 2
4200 2
4195 2
4194 3
4194 2
4193 2
4192 2
4191 2
4190 2
4189 2
4188 2
4187 2
4186 2
4185 2
4184 2
4183 2
4182 2
4181 2
4180 2
4179 2
4178 2
4177 2
4176 2
4175 2
4174 2
4173 2
4172 2
4171 2
4170 2
4169 2
4168 2
4167 2
4166 2
4165 2
4164 2
4163 2
4162 2
4161 2
4160 2
4159 2
4158 2
4157 2
4...

result:

ok good solution!

Test #107:

score: 7
Accepted
time: 4ms
memory: 30660kb

input:

5998
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2998
4999 3
4994 2
4993 3
4993 2
4992 2
4991 2
4990 2
4989 2
4988 2
4987 2
4986 2
4985 2
4984 2
4983 2
4982 2
4981 2
4980 2
4979 2
4978 2
4977 2
4976 2
4975 2
4974 2
4973 2
4972 2
4971 2
4970 2
4969 2
4968 2
4967 2
4966 2
4965 2
4964 2
4963 2
4962 2
4961 2
4960 2
4959 2
4958 2
4957 2
4956 2
4955 2
4...

result:

ok good solution!

Test #108:

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

input:

5997
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

2998
1 3
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2...

result:

ok good solution!

Test #109:

score: 7
Accepted
time: 4ms
memory: 30436kb

input:

6000
ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

-1

result:

ok no solution

Test #110:

score: 7
Accepted
time: 3ms
memory: 24484kb

input:

5999
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

2999
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2...

result:

ok good solution!

Test #111:

score: 7
Accepted
time: 3ms
memory: 24464kb

input:

5999
BBBAAAABBAAAAAAABBBAAAAABBBBBAABBBAABBBBBAAAABBBBBAAAAABBBAAAAABBBBBAAAAAABBBBBAAAABBBBBBAAAAAAABBBBBBAAAABBBBBAAABBBAAABBBBAAAABBBBAAABBBAAAABBBBAAABBBBAAAABBAAAABBBAAAAAABBBAAABBBBBAAAAABBBBAAAABBBAAABBBAAABBAAAABBAAABBBBBAAAAAABBBBBBBAAAABBBAAABBBAABBBAAAABBAABBBBBBBAAAAAABBBBAAAAABBBBAAABBB...

output:

2818
5988 2
5988 2
5981 2
5981 2
5970 3
5970 2
5970 2
5965 2
5957 3
5957 2
5947 3
5947 2
5942 3
5933 2
5933 2
5924 3
5924 2
5919 2
5912 2
5899 2
5899 2
5899 2
5899 2
5893 2
5885 3
5878 3
5870 3
5870 2
5864 3
5856 2
5856 2
5850 2
5842 2
5842 2
5835 3
5829 3
5824 3
5818 2
5808 2
5808 2
5796 3
5796 2
5...

result:

ok good solution!

Test #112:

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

input:

6000
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

2997
5188 3
5188 2
5188 2
5187 2
5186 2
5185 2
5184 2
5183 2
5182 2
5181 2
5180 2
5179 2
5178 2
5177 2
5176 2
5175 2
5174 2
5173 2
5172 2
5171 2
5170 2
5169 2
5168 2
5167 2
5166 2
5165 2
5164 2
5163 2
5162 2
5161 2
5160 2
5159 2
5158 2
5157 2
5156 2
5155 2
5154 2
5153 2
5152 2
5151 2
5150 2
5149 2
5...

result:

ok good solution!

Test #113:

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

input:

6000
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

-1

result:

ok no solution

Test #114:

score: 7
Accepted
time: 2ms
memory: 28580kb

input:

6000
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

2995
4656 2
4656 2
4656 2
4655 2
4654 2
4653 2
4652 2
4651 2
4650 2
4649 2
4648 2
4647 2
4646 2
4645 2
4644 2
4643 2
4642 2
4641 2
4640 2
4639 2
4638 2
4637 2
4636 2
4635 2
4634 2
4633 2
4632 2
4631 2
4630 2
4629 2
4628 2
4627 2
4626 2
4625 2
4624 2
4623 2
4622 2
4621 2
4620 2
4619 2
4618 2
4617 2
4...

result:

ok good solution!

Test #115:

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

input:

5999
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2994
5620 2
5620 2
5619 2
5618 2
5617 2
5616 2
5615 2
5614 2
5613 2
5612 2
5611 2
5610 2
5609 2
5608 2
5607 2
5606 2
5605 2
5604 2
5603 2
5602 2
5601 2
5600 2
5599 2
5598 2
5597 2
5596 2
5595 2
5594 2
5593 2
5592 2
5591 2
5590 2
5589 2
5588 2
5587 2
5586 2
5585 2
5584 2
5583 2
5582 2
5581 2
5580 2
5...

result:

ok good solution!

Test #116:

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

input:

5999
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2991
5676 2
5676 2
5676 2
5675 2
5674 2
5673 2
5672 2
5671 2
5670 2
5669 2
5668 2
5667 2
5666 2
5665 2
5664 2
5663 2
5662 2
5661 2
5660 2
5659 2
5658 2
5657 2
5656 2
5655 2
5654 2
5653 2
5652 2
5651 2
5650 2
5649 2
5648 2
5647 2
5646 2
5645 2
5644 2
5643 2
5642 2
5641 2
5640 2
5639 2
5638 2
5637 2
5...

result:

ok good solution!

Test #117:

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

input:

5997
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBBABABABABABABABABABABABABABABABABABABABABABABBBBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2991
5837 2
5837 2
5836 2
5835 2
5834 2
5833 2
5832 2
5831 2
5830 2
5829 2
5828 2
5827 2
5826 2
5825 2
5824 2
5823 2
5822 2
5821 2
5820 2
5819 2
5818 2
5817 2
5816 2
5815 2
5814 2
5813 2
5812 2
5811 2
5810 2
5809 2
5808 2
5807 2
5806 2
5805 2
5804 2
5803 2
5802 2
5801 2
5800 2
5799 2
5798 2
5797 2
5...

result:

ok good solution!

Test #118:

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

input:

6000
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

3000
2999 2
2999 2
2998 2
2997 2
2996 2
2995 2
2994 2
2993 2
2992 2
2991 2
2990 2
2989 2
2988 2
2987 2
2986 2
2985 2
2984 2
2983 2
2982 2
2981 2
2980 2
2979 2
2978 2
2977 2
2976 2
2975 2
2974 2
2973 2
2972 2
2971 2
2970 2
2969 2
2968 2
2967 2
2966 2
2965 2
2964 2
2963 2
2962 2
2961 2
2960 2
2959 2
2...

result:

ok good solution!

Test #119:

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

input:

6000
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

3000
3000 2
2999 2
2998 2
2997 2
2996 2
2995 2
2994 2
2993 2
2992 2
2991 2
2990 2
2989 2
2988 2
2987 2
2986 2
2985 2
2984 2
2983 2
2982 2
2981 2
2980 2
2979 2
2978 2
2977 2
2976 2
2975 2
2974 2
2973 2
2972 2
2971 2
2970 2
2969 2
2968 2
2967 2
2966 2
2965 2
2964 2
2963 2
2962 2
2961 2
2960 2
2959 2
2...

result:

ok good solution!

Test #120:

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

input:

5999
AAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2999
3001 2
3000 2
2999 2
2998 2
2997 2
2996 2
2995 2
2994 2
2993 2
2992 2
2991 2
2990 2
2989 2
2988 2
2987 2
2986 2
2985 2
2984 2
2983 2
2982 2
2981 2
2980 2
2979 2
2978 2
2977 2
2976 2
2975 2
2974 2
2973 2
2972 2
2971 2
2970 2
2969 2
2968 2
2967 2
2966 2
2965 2
2964 2
2963 2
2962 2
2961 2
2960 2
2...

result:

ok good solution!

Test #121:

score: 7
Accepted
time: 5ms
memory: 26528kb

input:

6000
ABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

3000
3002 2
3001 2
3000 2
2999 2
2998 2
2997 2
2996 2
2995 2
2994 2
2993 2
2992 2
2991 2
2990 2
2989 2
2988 2
2987 2
2986 2
2985 2
2984 2
2983 2
2982 2
2981 2
2980 2
2979 2
2978 2
2977 2
2976 2
2975 2
2974 2
2973 2
2972 2
2971 2
2970 2
2969 2
2968 2
2967 2
2966 2
2965 2
2964 2
2963 2
2962 2
2961 2
2...

result:

ok good solution!

Test #122:

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

input:

6000
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

2999
4201 3
4200 2
4199 2
4198 2
4197 2
4196 2
4195 2
4194 2
4193 2
4192 2
4191 2
4190 2
4189 2
4188 2
4187 2
4186 2
4185 2
4184 2
4183 2
4182 2
4181 2
4180 2
4179 2
4178 2
4177 2
4176 2
4175 2
4174 2
4173 2
4172 2
4171 2
4170 2
4169 2
4168 2
4167 2
4166 2
4165 2
4164 2
4163 2
4162 2
4161 2
4160 2
4...

result:

ok good solution!

Test #123:

score: 7
Accepted
time: 4ms
memory: 28556kb

input:

6000
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

3000
5402 2
5401 2
5400 2
5399 2
5398 2
5397 2
5396 2
5395 2
5394 2
5393 2
5392 2
5391 2
5390 2
5389 2
5388 2
5387 2
5386 2
5385 2
5384 2
5383 2
5382 2
5381 2
5380 2
5379 2
5378 2
5377 2
5376 2
5375 2
5374 2
5373 2
5372 2
5371 2
5370 2
5369 2
5368 2
5367 2
5366 2
5365 2
5364 2
5363 2
5362 2
5361 2
5...

result:

ok good solution!

Test #124:

score: 7
Accepted
time: 4ms
memory: 28516kb

input:

6000
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

3000
5998 2
2998 2
2997 2
2996 2
2995 2
2994 2
2993 2
2992 2
2991 2
2990 2
2989 2
2988 2
2987 2
2986 2
2985 2
2984 2
2983 2
2982 2
2981 2
2980 2
2979 2
2978 2
2977 2
2976 2
2975 2
2974 2
2973 2
2972 2
2971 2
2970 2
2969 2
2968 2
2967 2
2966 2
2965 2
2964 2
2963 2
2962 2
2961 2
2960 2
2959 2
2958 2
2...

result:

ok good solution!

Test #125:

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

input:

6000
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2999
2998 3
2997 2
2996 2
2995 2
2994 2
2993 2
2992 2
2991 2
2990 2
2989 2
2988 2
2987 2
2986 2
2985 2
2984 2
2983 2
2982 2
2981 2
2980 2
2979 2
2978 2
2977 2
2976 2
2975 2
2974 2
2973 2
2972 2
2971 2
2970 2
2969 2
2968 2
2967 2
2966 2
2965 2
2964 2
2963 2
2962 2
2961 2
2960 2
2959 2
2958 2
2957 2
2...

result:

ok good solution!

Test #126:

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

input:

6000
BAAAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2999
3002 3
3001 2
3000 2
2999 2
2998 2
2997 2
2996 2
2995 2
2994 2
2993 2
2992 2
2991 2
2990 2
2989 2
2988 2
2987 2
2986 2
2985 2
2984 2
2983 2
2982 2
2981 2
2980 2
2979 2
2978 2
2977 2
2976 2
2975 2
2974 2
2973 2
2972 2
2971 2
2970 2
2969 2
2968 2
2967 2
2966 2
2965 2
2964 2
2963 2
2962 2
2961 2
2...

result:

ok good solution!

Test #127:

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

input:

5999
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2999
4202 2
4201 2
4200 2
4199 2
4198 2
4197 2
4196 2
4195 2
4194 2
4193 2
4192 2
4191 2
4190 2
4189 2
4188 2
4187 2
4186 2
4185 2
4184 2
4183 2
4182 2
4181 2
4180 2
4179 2
4178 2
4177 2
4176 2
4175 2
4174 2
4173 2
4172 2
4171 2
4170 2
4169 2
4168 2
4167 2
4166 2
4165 2
4164 2
4163 2
4162 2
4161 2
4...

result:

ok good solution!

Test #128:

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

input:

5997
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

2998
5995 2
2997 2
2996 2
2995 2
2994 2
2993 2
2992 2
2991 2
2990 2
2989 2
2988 2
2987 2
2986 2
2985 2
2984 2
2983 2
2982 2
2981 2
2980 2
2979 2
2978 2
2977 2
2976 2
2975 2
2974 2
2973 2
2972 2
2971 2
2970 2
2969 2
2968 2
2967 2
2966 2
2965 2
2964 2
2963 2
2962 2
2961 2
2960 2
2959 2
2958 2
2957 2
2...

result:

ok good solution!

Test #129:

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

input:

5999
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2999
4795 2
4795 2
2997 2
2996 2
2995 2
2994 2
2993 2
2992 2
2991 2
2990 2
2989 2
2988 2
2987 2
2986 2
2985 2
2984 2
2983 2
2982 2
2981 2
2980 2
2979 2
2978 2
2977 2
2976 2
2975 2
2974 2
2973 2
2972 2
2971 2
2970 2
2969 2
2968 2
2967 2
2966 2
2965 2
2964 2
2963 2
2962 2
2961 2
2960 2
2959 2
2958 2
2...

result:

ok good solution!

Test #130:

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

input:

5998
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2998
3000 3
2997 2
2996 3
2995 2
2994 2
2993 2
2992 2
2991 2
2990 2
2989 2
2988 2
2987 2
2986 2
2985 2
2984 2
2983 2
2982 2
2981 2
2980 2
2979 2
2978 2
2977 2
2976 2
2975 2
2974 2
2973 2
2972 2
2971 2
2970 2
2969 2
2968 2
2967 2
2966 2
2965 2
2964 2
2963 2
2962 2
2961 2
2960 2
2959 2
2958 2
2957 2
2...

result:

ok good solution!

Test #131:

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

input:

5997
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2998
3000 2
2999 2
2998 2
2997 2
2996 2
2995 2
2994 2
2993 2
2992 2
2991 2
2990 2
2989 2
2988 2
2987 2
2986 2
2985 2
2984 2
2983 2
2982 2
2981 2
2980 2
2979 2
2978 2
2977 2
2976 2
2975 2
2974 2
2973 2
2972 2
2971 2
2970 2
2969 2
2968 2
2967 2
2966 2
2965 2
2964 2
2963 2
2962 2
2961 2
2960 2
2959 2
2...

result:

ok good solution!

Test #132:

score: 7
Accepted
time: 4ms
memory: 28476kb

input:

5998
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2998
4200 2
4199 2
4198 2
4197 2
4196 2
4195 2
4194 2
4193 2
4192 2
4191 2
4190 2
4189 2
4188 2
4187 2
4186 2
4185 2
4184 2
4183 2
4182 2
4181 2
4180 2
4179 2
4178 2
4177 2
4176 2
4175 2
4174 2
4173 2
4172 2
4171 2
4170 2
4169 2
4168 2
4167 2
4166 2
4165 2
4164 2
4163 2
4162 2
4161 2
4160 2
4159 2
4...

result:

ok good solution!

Test #133:

score: 7
Accepted
time: 4ms
memory: 30572kb

input:

6000
BAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2006
5995 2
2000 2
1999 2
1998 3
1997 3
1996 3
1995 3
1994 3
1993 3
1992 3
1991 3
1990 3
1989 3
1988 3
1987 3
1986 3
1985 3
1984 3
1983 3
1982 3
1981 3
1980 3
1979 3
1978 3
1977 3
1976 3
1975 3
1974 3
1973 3
1972 3
1971 3
1970 3
1969 3
1968 3
1967 3
1966 3
1965 3
1964 3
1963 3
1962 3
1961 3
1960 3
1...

result:

ok good solution!

Test #134:

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

input:

5999
AABAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABB...

output:

2005
4002 2
4001 2
3999 3
3997 3
3995 3
3993 3
3991 3
3989 3
3987 3
3985 3
3983 3
3981 3
3979 3
3977 3
3975 3
3973 3
3971 3
3969 3
3967 3
3965 3
3963 3
3961 3
3959 3
3957 3
3955 3
3953 3
3951 3
3949 3
3947 3
3945 3
3943 3
3941 3
3939 3
3937 3
3935 3
3933 3
3931 3
3929 3
3927 3
3925 3
3923 3
3921 3
3...

result:

ok good solution!

Test #135:

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

input:

6000
BBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2666
5995 2
5991 2
5987 2
5983 2
5979 2
5975 2
5971 2
5967 2
5963 2
5959 2
5955 2
5951 2
5947 2
5943 2
5939 2
5935 2
5931 2
5927 2
5923 2
5919 2
5915 2
5911 2
5907 2
5903 2
5899 2
5895 2
5891 2
5887 2
5883 2
5879 2
5875 2
5871 2
5867 2
5863 2
5859 2
5855 2
5851 2
5847 2
5843 2
5839 2
5835 2
5831 2
5...

result:

ok good solution!

Test #136:

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

input:

6000
ABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABB...

output:

2335
5334 2
5333 2
5332 2
5331 2
5330 2
5329 2
5328 2
5327 2
5326 2
5325 2
5324 2
5323 2
5322 2
5321 2
5320 2
5319 2
5318 2
5317 2
5316 2
5315 2
5314 2
5313 2
5312 2
5311 2
5310 2
5309 2
5308 2
5307 2
5306 2
5305 2
5304 2
5303 2
5302 2
5301 2
5300 2
5299 2
5298 2
5297 2
5296 2
5295 2
5294 2
5293 2
5...

result:

ok good solution!

Test #137:

score: 7
Accepted
time: 4ms
memory: 26424kb

input:

6000
BBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBA...

output:

2006
5996 2
5995 2
3998 2
3997 2
3995 3
3993 3
3991 3
3989 3
3987 3
3985 3
3983 3
3981 3
3979 3
3977 3
3975 3
3973 3
3971 3
3969 3
3967 3
3965 3
3963 3
3961 3
3959 3
3957 3
3955 3
3953 3
3951 3
3949 3
3947 3
3945 3
3943 3
3941 3
3939 3
3937 3
3935 3
3933 3
3931 3
3929 3
3927 3
3925 3
3923 3
3921 3
3...

result:

ok good solution!

Test #138:

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

input:

6000
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2006
5998 2
5991 2
1996 2
1995 2
1994 3
1993 3
1992 3
1991 3
1990 3
1989 3
1988 3
1987 3
1986 3
1985 3
1984 3
1983 3
1982 3
1981 3
1980 3
1979 3
1978 3
1977 3
1976 3
1975 3
1974 3
1973 3
1972 3
1971 3
1970 3
1969 3
1968 3
1967 3
1966 3
1965 3
1964 3
1963 3
1962 3
1961 3
1960 3
1959 3
1958 3
1957 3
1...

result:

ok good solution!

Test #139:

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

input:

6000
BBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABB...

output:

2432
5995 2
5991 2
5987 2
5983 2
5979 2
5975 2
5971 2
5967 2
5963 2
5959 2
5955 2
5951 2
5947 2
5943 2
5939 2
5935 2
5931 2
5927 2
5923 2
5919 2
5915 2
5911 2
5907 2
5903 2
5899 2
5895 2
5891 2
5887 2
5883 2
5879 2
5875 2
5871 2
5867 2
5863 2
5859 2
5855 2
5851 2
5847 2
5843 2
5839 2
5835 2
5831 2
5...

result:

ok good solution!

Test #140:

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

input:

5999
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

2431
4999 2
4997 3
4995 3
4993 3
4991 3
4989 3
4987 3
4985 3
4983 3
4981 3
4979 3
4977 3
4975 3
4973 3
4971 3
4969 3
4967 3
4965 3
4963 3
4961 3
4959 3
4957 3
4955 3
4953 3
4951 3
4949 3
4947 3
4945 3
4943 3
4941 3
4939 3
4937 3
4935 3
4933 3
4931 3
4929 3
4927 3
4925 3
4923 3
4921 3
4919 3
4917 3
4...

result:

ok good solution!

Test #141:

score: 7
Accepted
time: 4ms
memory: 26448kb

input:

5997
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2997
3998 3
3997 2
3996 2
3995 2
3994 2
3993 2
3992 2
3991 2
3990 2
3989 2
3988 2
3987 2
3986 2
3985 2
3984 2
3983 2
3982 2
3981 2
3980 2
3979 2
3978 2
3977 2
3976 2
3975 2
3974 2
3973 2
3972 2
3971 2
3970 2
3969 2
3968 2
3967 2
3966 2
3965 2
3964 2
3963 2
3962 2
3961 2
3960 2
3959 2
3958 2
3957 2
3...

result:

ok good solution!

Test #142:

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

input:

6000
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2999
4666 2
4666 2
3994 3
3994 2
3994 2
3993 2
3992 2
3991 2
3990 2
3989 2
3988 2
3987 2
3986 2
3985 2
3984 2
3983 2
3982 2
3981 2
3980 2
3979 2
3978 2
3977 2
3976 2
3975 2
3974 2
3973 2
3972 2
3971 2
3970 2
3969 2
3968 2
3967 2
3966 2
3965 2
3964 2
3963 2
3962 2
3961 2
3960 2
3959 2
3958 2
3957 2
3...

result:

ok good solution!

Test #143:

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

input:

5998
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

2998
4201 3
4200 2
4199 2
4198 2
4197 2
4196 2
4195 2
4194 2
4193 2
4192 2
4191 2
4190 2
4189 2
4188 2
4187 2
4186 2
4185 2
4184 2
4183 2
4182 2
4181 2
4180 2
4179 2
4178 2
4177 2
4176 2
4175 2
4174 2
4173 2
4172 2
4171 2
4170 2
4169 2
4168 2
4167 2
4166 2
4165 2
4164 2
4163 2
4162 2
4161 2
4160 2
4...

result:

ok good solution!

Test #144:

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

input:

5997
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

2997
4796 3
4796 2
4795 2
4794 2
4793 2
4792 2
4791 2
4790 2
4789 2
4788 2
4787 2
4786 2
4785 2
4784 2
4783 2
4782 2
4781 2
4780 2
4779 2
4778 2
4777 2
4776 2
4775 2
4774 2
4773 2
4772 2
4771 2
4770 2
4769 2
4768 2
4767 2
4766 2
4765 2
4764 2
4763 2
4762 2
4761 2
4760 2
4759 2
4758 2
4757 2
4756 2
4...

result:

ok good solution!

Test #145:

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

input:

6000
BBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

-1

result:

ok no solution

Test #146:

score: 7
Accepted
time: 4ms
memory: 26324kb

input:

6000
BBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBA...

output:

-1

result:

ok no solution

Test #147:

score: 7
Accepted
time: 4ms
memory: 30536kb

input:

6000
AABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAB...

output:

-1

result:

ok no solution

Test #148:

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

input:

5999
AABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAB...

output:

-1

result:

ok no solution

Test #149:

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

input:

5999
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

-1

result:

ok no solution

Test #150:

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

input:

6000
AABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAB...

output:

-1

result:

ok no solution

Test #151:

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

input:

6000
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

-1

result:

ok no solution

Test #152:

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

input:

5999
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

-1

result:

ok no solution

Subtask #4:

score: 9
Accepted

Test #153:

score: 9
Accepted
time: 41ms
memory: 39196kb

input:

999997
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

499998
666661 2
666661 2
666661 2
666661 2
666661 2
666660 2
666659 2
666658 2
666657 2
666656 2
666655 2
666654 2
666653 2
666652 2
666651 2
666650 2
666649 2
666648 2
666647 2
666646 2
666645 2
666644 2
666643 2
666642 2
666641 2
666640 2
666639 2
666638 2
666637 2
666636 2
666635 2
666634 2
66663...

result:

ok good solution!

Test #154:

score: 9
Accepted
time: 37ms
memory: 37948kb

input:

999998
BBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

499998
666667 3
666667 2
666666 2
666665 2
666664 2
666663 2
666662 2
666661 2
666660 2
666659 2
666658 2
666657 2
666656 2
666655 2
666654 2
666653 2
666652 2
666651 2
666650 2
666649 2
666648 2
666647 2
666646 2
666645 2
666644 2
666643 2
666642 2
666641 2
666640 2
666639 2
666638 2
666637 2
66663...

result:

ok good solution!

Test #155:

score: 9
Accepted
time: 34ms
memory: 37780kb

input:

999997
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

499998
749999 2
749997 3
749996 2
749995 2
749994 2
749993 2
749992 2
749991 2
749990 2
749989 2
749988 2
749987 2
749986 2
749985 2
749984 2
749983 2
749982 2
749981 2
749980 2
749979 2
749978 2
749977 2
749976 2
749975 2
749974 2
749973 2
749972 2
749971 2
749970 2
749969 2
749968 2
749967 2
74996...

result:

ok good solution!

Test #156:

score: 9
Accepted
time: 42ms
memory: 39712kb

input:

999998
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

499998
699998 3
699997 3
699996 2
699995 2
699994 2
699993 2
699992 2
699991 2
699990 2
699989 2
699988 2
699987 2
699986 2
699985 2
699984 2
699983 2
699982 2
699981 2
699980 2
699979 2
699978 2
699977 2
699976 2
699975 2
699974 2
699973 2
699972 2
699971 2
699970 2
699969 2
699968 2
699967 2
69996...

result:

ok good solution!

Test #157:

score: 9
Accepted
time: 42ms
memory: 36268kb

input:

999999
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

499999
700002 2
699997 3
699996 2
699996 2
699995 2
699994 2
699993 2
699992 2
699991 2
699990 2
699989 2
699988 2
699987 2
699986 2
699985 2
699984 2
699983 2
699982 2
699981 2
699980 2
699979 2
699978 2
699977 2
699976 2
699975 2
699974 2
699973 2
699972 2
699971 2
699970 2
699969 2
699968 2
69996...

result:

ok good solution!

Test #158:

score: 9
Accepted
time: 42ms
memory: 36856kb

input:

999997
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

499998
833332 2
833327 2
833326 3
833326 2
833325 2
833324 2
833323 2
833322 2
833321 2
833320 2
833319 2
833318 2
833317 2
833316 2
833315 2
833314 2
833313 2
833312 2
833311 2
833310 2
833309 2
833308 2
833307 2
833306 2
833305 2
833304 2
833303 2
833302 2
833301 2
833300 2
833299 2
833298 2
83329...

result:

ok good solution!

Test #159:

score: 9
Accepted
time: 29ms
memory: 30132kb

input:

999999
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

499999
1 3
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1...

result:

ok good solution!

Test #160:

score: 9
Accepted
time: 7ms
memory: 27424kb

input:

999998
BAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

-1

result:

ok no solution

Test #161:

score: 9
Accepted
time: 37ms
memory: 33288kb

input:

999998
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

499999
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1...

result:

ok good solution!

Test #162:

score: 9
Accepted
time: 44ms
memory: 31600kb

input:

999998
AAAAAAAABBBBAAAAAABBAAAABBBAAAAAABBBBBBAAAAABBBBBBAAAABBBAAABBBAAAAAABBBAAABBBBBAABBBBBBAAABBAAAAAAABBBAAAAAAABBBAAAAAABBBBAAABBBAAABBBBBBAAAABBBAAABBBAAAABBBBAABBBBAAAAABBBBBBAAAAAABBBBBAABBBBBBAAABBBBAABBAAAABBAABBBBAABBBBBBAAAAABBBBBBAAAAABBBBAAAAABBAAAAAAAABBAAAABBBBAAABBBBAAAABBBBBAAAABB...

output:

469429
999989 3
999974 2
999974 2
999974 2
999965 2
999965 2
999957 3
999949 3
999939 3
999939 2
999935 2
999930 3
999922 3
999922 2
999912 3
999912 2
999902 3
999902 2
999902 2
999893 2
999893 2
999893 2
999881 2
999881 2
999871 2
999871 2
999871 2
999865 3
999856 3
999856 2
999848 3
999836 3
99983...

result:

ok good solution!

Test #163:

score: 9
Accepted
time: 12ms
memory: 33768kb

input:

999997
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

-1

result:

ok no solution

Test #164:

score: 9
Accepted
time: 45ms
memory: 39160kb

input:

1000000
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

499999
827654 2
827654 2
827654 2
827654 2
827654 2
827654 2
827653 2
827652 2
827651 2
827650 2
827649 2
827648 2
827647 2
827646 2
827645 2
827644 2
827643 2
827642 2
827641 2
827640 2
827639 2
827638 2
827637 2
827636 2
827635 2
827634 2
827633 2
827632 2
827631 2
827630 2
827629 2
827628 2
82762...

result:

ok good solution!

Test #165:

score: 9
Accepted
time: 46ms
memory: 39060kb

input:

999997
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

499995
842657 3
842657 2
842657 2
842657 2
842657 2
842656 2
842655 2
842654 2
842653 2
842652 2
842651 2
842650 2
842649 2
842648 2
842647 2
842646 2
842645 2
842644 2
842643 2
842642 2
842641 2
842640 2
842639 2
842638 2
842637 2
842636 2
842635 2
842634 2
842633 2
842632 2
842631 2
842630 2
84262...

result:

ok good solution!

Test #166:

score: 9
Accepted
time: 44ms
memory: 41216kb

input:

1000000
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

499995
878140 3
878140 2
878139 2
878138 2
878137 2
878136 2
878135 2
878134 2
878133 2
878132 2
878131 2
878130 2
878129 2
878128 2
878127 2
878126 2
878125 2
878124 2
878123 2
878122 2
878121 2
878120 2
878119 2
878118 2
878117 2
878116 2
878115 2
878114 2
878113 2
878112 2
878111 2
878110 2
87810...

result:

ok good solution!

Test #167:

score: 9
Accepted
time: 48ms
memory: 38436kb

input:

999999
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

499992
957343 2
957343 2
957342 2
957341 2
957340 2
957339 2
957338 2
957337 2
957336 2
957335 2
957334 2
957333 2
957332 2
957331 2
957330 2
957329 2
957328 2
957327 2
957326 2
957325 2
957324 2
957323 2
957322 2
957321 2
957320 2
957319 2
957318 2
957317 2
957316 2
957315 2
957314 2
957313 2
95731...

result:

ok good solution!

Test #168:

score: 9
Accepted
time: 51ms
memory: 40260kb

input:

999999
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

499992
984459 3
984458 2
984457 2
984456 2
984455 2
984454 2
984453 2
984452 2
984451 2
984450 2
984449 2
984448 2
984447 2
984446 2
984445 2
984444 2
984443 2
984442 2
984441 2
984440 2
984439 2
984438 2
984437 2
984436 2
984435 2
984434 2
984433 2
984432 2
984431 2
984430 2
984429 2
984428 2
98442...

result:

ok good solution!

Test #169:

score: 9
Accepted
time: 43ms
memory: 37252kb

input:

999999
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

499999
499999 3
499998 2
499997 2
499996 2
499995 2
499994 2
499993 2
499992 2
499991 2
499990 2
499989 2
499988 2
499987 2
499986 2
499985 2
499984 2
499983 2
499982 2
499981 2
499980 2
499979 2
499978 2
499977 2
499976 2
499975 2
499974 2
499973 2
499972 2
499971 2
499970 2
499969 2
499968 2
49996...

result:

ok good solution!

Test #170:

score: 9
Accepted
time: 46ms
memory: 35740kb

input:

1000000
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

500000
500000 2
499999 2
499998 2
499997 2
499996 2
499995 2
499994 2
499993 2
499992 2
499991 2
499990 2
499989 2
499988 2
499987 2
499986 2
499985 2
499984 2
499983 2
499982 2
499981 2
499980 2
499979 2
499978 2
499977 2
499976 2
499975 2
499974 2
499973 2
499972 2
499971 2
499970 2
499969 2
49996...

result:

ok good solution!

Test #171:

score: 9
Accepted
time: 47ms
memory: 37264kb

input:

1000000
AAAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

500000
500002 2
500001 2
500000 2
499999 2
499998 2
499997 2
499996 2
499995 2
499994 2
499993 2
499992 2
499991 2
499990 2
499989 2
499988 2
499987 2
499986 2
499985 2
499984 2
499983 2
499982 2
499981 2
499980 2
499979 2
499978 2
499977 2
499976 2
499975 2
499974 2
499973 2
499972 2
499971 2
49997...

result:

ok good solution!

Test #172:

score: 9
Accepted
time: 39ms
memory: 37300kb

input:

1000000
BAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

500000
500002 2
500001 2
500000 2
499999 2
499998 2
499997 2
499996 2
499995 2
499994 2
499993 2
499992 2
499991 2
499990 2
499989 2
499988 2
499987 2
499986 2
499985 2
499984 2
499983 2
499982 2
499981 2
499980 2
499979 2
499978 2
499977 2
499976 2
499975 2
499974 2
499973 2
499972 2
499971 2
49997...

result:

ok good solution!

Test #173:

score: 9
Accepted
time: 43ms
memory: 36584kb

input:

1000000
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

500000
700000 2
700000 2
699999 2
699998 2
699997 2
699996 2
699995 2
699994 2
699993 2
699992 2
699991 2
699990 2
699989 2
699988 2
699987 2
699986 2
699985 2
699984 2
699983 2
699982 2
699981 2
699980 2
699979 2
699978 2
699977 2
699976 2
699975 2
699974 2
699973 2
699972 2
699971 2
699970 2
69996...

result:

ok good solution!

Test #174:

score: 9
Accepted
time: 42ms
memory: 37644kb

input:

1000000
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

500000
900002 2
900001 2
900000 2
899999 2
899998 2
899997 2
899996 2
899995 2
899994 2
899993 2
899992 2
899991 2
899990 2
899989 2
899988 2
899987 2
899986 2
899985 2
899984 2
899983 2
899982 2
899981 2
899980 2
899979 2
899978 2
899977 2
899976 2
899975 2
899974 2
899973 2
899972 2
899971 2
89997...

result:

ok good solution!

Test #175:

score: 9
Accepted
time: 39ms
memory: 38668kb

input:

1000000
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

500000
999998 2
499998 2
499997 2
499996 2
499995 2
499994 2
499993 2
499992 2
499991 2
499990 2
499989 2
499988 2
499987 2
499986 2
499985 2
499984 2
499983 2
499982 2
499981 2
499980 2
499979 2
499978 2
499977 2
499976 2
499975 2
499974 2
499973 2
499972 2
499971 2
499970 2
499969 2
499968 2
49996...

result:

ok good solution!

Test #176:

score: 9
Accepted
time: 42ms
memory: 36300kb

input:

1000000
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

500000
499998 2
499998 2
499997 2
499996 2
499995 2
499994 2
499993 2
499992 2
499991 2
499990 2
499989 2
499988 2
499987 2
499986 2
499985 2
499984 2
499983 2
499982 2
499981 2
499980 2
499979 2
499978 2
499977 2
499976 2
499975 2
499974 2
499973 2
499972 2
499971 2
499970 2
499969 2
499968 2
49996...

result:

ok good solution!

Test #177:

score: 9
Accepted
time: 45ms
memory: 38204kb

input:

1000000
BAAAAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

499999
500003 2
500002 2
500001 2
500000 2
499999 2
499998 2
499997 2
499996 2
499995 2
499994 2
499993 2
499992 2
499991 2
499990 2
499989 2
499988 2
499987 2
499986 2
499985 2
499984 2
499983 2
499982 2
499981 2
499980 2
499979 2
499978 2
499977 2
499976 2
499975 2
499974 2
499973 2
499972 2
49997...

result:

ok good solution!

Test #178:

score: 9
Accepted
time: 42ms
memory: 37288kb

input:

999998
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

499998
700001 2
700000 2
699999 2
699998 2
699997 2
699996 2
699995 2
699994 2
699993 2
699992 2
699991 2
699990 2
699989 2
699988 2
699987 2
699986 2
699985 2
699984 2
699983 2
699982 2
699981 2
699980 2
699979 2
699978 2
699977 2
699976 2
699975 2
699974 2
699973 2
699972 2
699971 2
699970 2
69996...

result:

ok good solution!

Test #179:

score: 9
Accepted
time: 35ms
memory: 37508kb

input:

999999
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

499998
999996 3
499997 3
499996 2
499995 2
499994 2
499993 2
499992 2
499991 2
499990 2
499989 2
499988 2
499987 2
499986 2
499985 2
499984 2
499983 2
499982 2
499981 2
499980 2
499979 2
499978 2
499977 2
499976 2
499975 2
499974 2
499973 2
499972 2
499971 2
499970 2
499969 2
499968 2
499967 2
49996...

result:

ok good solution!

Test #180:

score: 9
Accepted
time: 40ms
memory: 40860kb

input:

999999
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

499998
799996 3
499997 3
499996 2
499995 2
499994 2
499993 2
499992 2
499991 2
499990 2
499989 2
499988 2
499987 2
499986 2
499985 2
499984 2
499983 2
499982 2
499981 2
499980 2
499979 2
499978 2
499977 2
499976 2
499975 2
499974 2
499973 2
499972 2
499971 2
499970 2
499969 2
499968 2
499967 2
49996...

result:

ok good solution!

Test #181:

score: 9
Accepted
time: 46ms
memory: 40468kb

input:

999997
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

499998
500000 2
499997 2
499996 3
499995 2
499994 2
499993 2
499992 2
499991 2
499990 2
499989 2
499988 2
499987 2
499986 2
499985 2
499984 2
499983 2
499982 2
499981 2
499980 2
499979 2
499978 2
499977 2
499976 2
499975 2
499974 2
499973 2
499972 2
499971 2
499970 2
499969 2
499968 2
499967 2
49996...

result:

ok good solution!

Test #182:

score: 9
Accepted
time: 38ms
memory: 36524kb

input:

999998
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

499998
500000 3
499999 2
499998 2
499997 2
499996 2
499995 2
499994 2
499993 2
499992 2
499991 2
499990 2
499989 2
499988 2
499987 2
499986 2
499985 2
499984 2
499983 2
499982 2
499981 2
499980 2
499979 2
499978 2
499977 2
499976 2
499975 2
499974 2
499973 2
499972 2
499971 2
499970 2
499969 2
49996...

result:

ok good solution!

Test #183:

score: 9
Accepted
time: 38ms
memory: 36104kb

input:

999999
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

499999
699999 2
699999 2
699998 2
699997 2
699996 2
699995 2
699994 2
699993 2
699992 2
699991 2
699990 2
699989 2
699988 2
699987 2
699986 2
699985 2
699984 2
699983 2
699982 2
699981 2
699980 2
699979 2
699978 2
699977 2
699976 2
699975 2
699974 2
699973 2
699972 2
699971 2
699970 2
699969 2
69996...

result:

ok good solution!

Test #184:

score: 9
Accepted
time: 35ms
memory: 39736kb

input:

999999
ABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

333339
999994 2
333333 2
333332 2
333331 3
333330 3
333329 3
333328 3
333327 3
333326 3
333325 3
333324 3
333323 3
333322 3
333321 3
333320 3
333319 3
333318 3
333317 3
333316 3
333315 3
333314 3
333313 3
333312 3
333311 3
333310 3
333309 3
333308 3
333307 3
333306 3
333305 3
333304 3
333303 3
33330...

result:

ok good solution!

Test #185:

score: 9
Accepted
time: 41ms
memory: 39576kb

input:

1000000
BBABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAB...

output:

333340
666670 2
666669 2
666667 3
666665 3
666663 3
666661 3
666659 3
666657 3
666655 3
666653 3
666651 3
666649 3
666647 3
666645 3
666643 3
666641 3
666639 3
666637 3
666635 3
666633 3
666631 3
666629 3
666627 3
666625 3
666623 3
666621 3
666619 3
666617 3
666615 3
666613 3
666611 3
666609 3
66660...

result:

ok good solution!

Test #186:

score: 9
Accepted
time: 47ms
memory: 35060kb

input:

999999
AABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

444446
999994 2
999990 2
999986 2
999982 2
999978 2
999974 2
999970 2
999966 2
999962 2
999958 2
999954 2
999950 2
999946 2
999942 2
999938 2
999934 2
999930 2
999926 2
999922 2
999918 2
999914 2
999910 2
999906 2
999902 2
999898 2
999894 2
999890 2
999886 2
999882 2
999878 2
999874 2
999870 2
99986...

result:

ok good solution!

Test #187:

score: 9
Accepted
time: 43ms
memory: 38384kb

input:

1000000
ABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBA...

output:

388893
888889 2
888888 2
888887 2
888886 2
888885 2
888884 2
888883 2
888882 2
888881 2
888880 2
888879 2
888878 2
888877 2
888876 2
888875 2
888874 2
888873 2
888872 2
888871 2
888870 2
888869 2
888868 2
888867 2
888866 2
888865 2
888864 2
888863 2
888862 2
888861 2
888860 2
888859 2
888858 2
88885...

result:

ok good solution!

Test #188:

score: 9
Accepted
time: 32ms
memory: 39892kb

input:

1000000
BBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAA...

output:

333340
999996 2
999995 2
666665 2
666664 2
666662 3
666660 3
666658 3
666656 3
666654 3
666652 3
666650 3
666648 3
666646 3
666644 3
666642 3
666640 3
666638 3
666636 3
666634 3
666632 3
666630 3
666628 3
666626 3
666624 3
666622 3
666620 3
666618 3
666616 3
666614 3
666612 3
666610 3
666608 3
66660...

result:

ok good solution!

Test #189:

score: 9
Accepted
time: 42ms
memory: 41936kb

input:

1000000
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

333340
999998 2
999991 2
333329 2
333328 2
333327 3
333326 3
333325 3
333324 3
333323 3
333322 3
333321 3
333320 3
333319 3
333318 3
333317 3
333316 3
333315 3
333314 3
333313 3
333312 3
333311 3
333310 3
333309 3
333308 3
333307 3
333306 3
333305 3
333304 3
333303 3
333302 3
333301 3
333300 3
33329...

result:

ok good solution!

Test #190:

score: 9
Accepted
time: 35ms
memory: 38088kb

input:

999999
BBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAB...

output:

404764
999994 2
999990 2
999986 2
999982 2
999978 2
999974 2
999970 2
999966 2
999962 2
999958 2
999954 2
999950 2
999946 2
999942 2
999938 2
999934 2
999930 2
999926 2
999922 2
999918 2
999914 2
999910 2
999906 2
999902 2
999898 2
999894 2
999890 2
999886 2
999882 2
999878 2
999874 2
999870 2
99986...

result:

ok good solution!

Test #191:

score: 9
Accepted
time: 42ms
memory: 42280kb

input:

999999
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

404763
833332 2
833330 3
833328 3
833326 3
833324 3
833322 3
833320 3
833318 3
833316 3
833314 3
833312 3
833310 3
833308 3
833306 3
833304 3
833302 3
833300 3
833298 3
833296 3
833294 3
833292 3
833290 3
833288 3
833286 3
833284 3
833282 3
833280 3
833278 3
833276 3
833274 3
833272 3
833270 3
83326...

result:

ok good solution!

Test #192:

score: 9
Accepted
time: 35ms
memory: 38408kb

input:

999997
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

499998
666664 2
666664 2
666663 2
666662 2
666661 2
666660 2
666659 2
666658 2
666657 2
666656 2
666655 2
666654 2
666653 2
666652 2
666651 2
666650 2
666649 2
666648 2
666647 2
666646 2
666645 2
666644 2
666643 2
666642 2
666641 2
666640 2
666639 2
666638 2
666637 2
666636 2
666635 2
666634 2
66663...

result:

ok good solution!

Test #193:

score: 9
Accepted
time: 39ms
memory: 37392kb

input:

999999
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

499999
777777 2
777777 2
666661 2
666661 2
666661 2
666660 2
666659 2
666658 2
666657 2
666656 2
666655 2
666654 2
666653 2
666652 2
666651 2
666650 2
666649 2
666648 2
666647 2
666646 2
666645 2
666644 2
666643 2
666642 2
666641 2
666640 2
666639 2
666638 2
666637 2
666636 2
666635 2
666634 2
66663...

result:

ok good solution!

Test #194:

score: 9
Accepted
time: 40ms
memory: 40320kb

input:

999998
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

499998
700000 2
700000 2
699999 2
699998 2
699997 2
699996 2
699995 2
699994 2
699993 2
699992 2
699991 2
699990 2
699989 2
699988 2
699987 2
699986 2
699985 2
699984 2
699983 2
699982 2
699981 2
699980 2
699979 2
699978 2
699977 2
699976 2
699975 2
699974 2
699973 2
699972 2
699971 2
699970 2
69996...

result:

ok good solution!

Test #195:

score: 9
Accepted
time: 46ms
memory: 36132kb

input:

999999
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

499998
799999 2
799999 2
799998 2
799997 2
799996 2
799995 2
799994 2
799993 2
799992 2
799991 2
799990 2
799989 2
799988 2
799987 2
799986 2
799985 2
799984 2
799983 2
799982 2
799981 2
799980 2
799979 2
799978 2
799977 2
799976 2
799975 2
799974 2
799973 2
799972 2
799971 2
799970 2
799969 2
79996...

result:

ok good solution!

Test #196:

score: 9
Accepted
time: 4ms
memory: 31472kb

input:

1000000
BBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

-1

result:

ok no solution

Test #197:

score: 9
Accepted
time: 11ms
memory: 35496kb

input:

999999
BBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAB...

output:

-1

result:

ok no solution

Test #198:

score: 9
Accepted
time: 10ms
memory: 33600kb

input:

1000000
BBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAA...

output:

-1

result:

ok no solution

Test #199:

score: 9
Accepted
time: 8ms
memory: 32756kb

input:

999999
AABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBA...

output:

-1

result:

ok no solution

Test #200:

score: 9
Accepted
time: 8ms
memory: 31476kb

input:

1000000
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

-1

result:

ok no solution

Test #201:

score: 9
Accepted
time: 9ms
memory: 35816kb

input:

999999
AABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBA...

output:

-1

result:

ok no solution

Test #202:

score: 9
Accepted
time: 4ms
memory: 31452kb

input:

1000000
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

-1

result:

ok no solution

Test #203:

score: 9
Accepted
time: 8ms
memory: 33504kb

input:

1000000
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

-1

result:

ok no solution

Extra Test:

score: 0
Extra Test Passed