QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#637330#4273. Good Gamechenxinyang200616 61ms154844kbC++203.2kb2024-10-13 12:10:202024-10-13 12:10:22

Judging History

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

  • [2024-10-13 12:10:22]
  • 评测
  • 测评结果:16
  • 用时:61ms
  • 内存:154844kb
  • [2024-10-13 12:10:20]
  • 提交

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;
	}
}
int dp[6005][6005];
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;
	}
	memset(dp,0,sizeof(dp));
	dp[0][b[0]] = 1;
	rep(i,1,k - 1){
		rep(x,0,m){
			if(!dp[i - 1][x]) continue;
			if(b[i] - x >= 0) dp[i][b[i] - x] = 1;
			rep(y,max(b[i] + 1 - x,x - (b[i] + 1)),b[i] + 1 + x) if((x + y) % 2 != b[i] % 2) dp[i][y] = 1;
		}
	}
/*	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(!dp[k - 1][b[k]]){
		printf("-1\n");
		return 0;
	}
	rep(i,1,b[k]) psh(1);
	int x = b[k],y,aa,bb,sum = n - b[k];
	per(i,k - 1,0){
		y = x;x = aa = bb = -1;
		if(i){
			rep(xx,0,m){
				if(!dp[i - 1][xx]) continue;
				if(b[i] - xx == y){
					x = xx;
					aa = x;
					bb = y;
				}
				rep(yy,max(b[i] + 1 - xx,xx - (b[i] + 1)),b[i] + 1 + xx){
					if((xx + yy) % 2 != b[i] % 2 && yy == y){
//						printf("transfer %d->%d ok\n",xx,yy);
						x = xx;
						aa = (b[i] + 1 + x - y) / 2;
						bb = (b[i] + 1 - x + y) / 2;
					}
				}
			}			
		}else{
			x = 0;
			bb = b[i];
		}
//		printf("i=%d y=%d chose x=%d bb=%d sum=%d\n",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;
}

詳細信息

Subtask #1:

score: 3
Accepted

Test #1:

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

input:

9
ABAABBBAA

output:

4
3 2
2 2
2 2
1 3

result:

ok good solution!

Test #2:

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

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: 3ms
memory: 152876kb

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: 0ms
memory: 152856kb

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: 1ms
memory: 9848kb

input:

1
B

output:

-1

result:

ok no solution

Test #6:

score: 3
Accepted
time: 11ms
memory: 150904kb

input:

2
BB

output:

1
1 2

result:

ok good solution!

Test #7:

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

input:

7
AAAABBB

output:

3
1 2
1 2
1 3

result:

ok good solution!

Test #8:

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

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: 9972kb

input:

2
AB

output:

-1

result:

ok no solution

Test #10:

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

input:

14
BAAAAAAAAAAAAA

output:

-1

result:

ok no solution

Test #11:

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

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: 7ms
memory: 152880kb

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: 152896kb

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: 151644kb

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: 8ms
memory: 150916kb

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: 152960kb

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: 4ms
memory: 150916kb

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: 152940kb

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: 11ms
memory: 150848kb

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: 12ms
memory: 153004kb

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: 4ms
memory: 152936kb

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: 150832kb

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: 150828kb

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: 3ms
memory: 150956kb

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: 8ms
memory: 150812kb

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: 4ms
memory: 153000kb

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: 7ms
memory: 152952kb

input:

15
AABABBABAABBABB

output:

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

result:

ok good solution!

Test #28:

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

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: 0ms
memory: 150776kb

input:

15
BBAABBABABABBAA

output:

-1

result:

ok no solution

Test #30:

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

input:

15
ABABBAABBAABBAB

output:

-1

result:

ok no solution

Test #31:

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

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: 150828kb

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: 4ms
memory: 150912kb

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: 4ms
memory: 152948kb

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: 152896kb

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: 4ms
memory: 152996kb

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: 152860kb

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: 152872kb

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: 3ms
memory: 152896kb

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: 8ms
memory: 152952kb

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: 4ms
memory: 152812kb

input:

14
AABABABBAABBAA

output:

-1

result:

ok no solution

Test #42:

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

input:

15
AABBBABABAABBAA

output:

-1

result:

ok no solution

Test #43:

score: 3
Accepted
time: 8ms
memory: 150836kb

input:

14
AABBAABABABBAA

output:

-1

result:

ok no solution

Test #44:

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

input:

15
BBBAABBAABABABB

output:

-1

result:

ok no solution

Test #45:

score: 3
Accepted
time: 11ms
memory: 150884kb

input:

15
BABABBBBAABBAAA

output:

-1

result:

ok no solution

Test #46:

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

input:

15
BBBABABAABBBAAA

output:

-1

result:

ok no solution

Test #47:

score: 3
Accepted
time: 8ms
memory: 150796kb

input:

15
AAABBBBAABABABB

output:

-1

result:

ok no solution

Test #48:

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

input:

15
AAAAABBAABBABAB

output:

-1

result:

ok no solution

Test #49:

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

input:

15
BAAAABBAABBBABA

output:

-1

result:

ok no solution

Test #50:

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

input:

15
BABAAABBBAAABBA

output:

-1

result:

ok no solution

Subtask #2:

score: 6
Accepted

Test #51:

score: 6
Accepted
time: 7ms
memory: 152896kb

input:

299
ABABABABABABABABABABABABABABABABABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

-1

result:

ok no solution

Test #52:

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

input:

300
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAB...

output:

-1

result:

ok no solution

Test #53:

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

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: 8ms
memory: 152956kb

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: 8ms
memory: 152952kb

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: 3ms
memory: 150924kb

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: 150968kb

input:

299
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBAABBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

149
209 2
206 2
206 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
161 2
16...

result:

ok good solution!

Test #58:

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

input:

300
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAAAABBAAAABABABABABABABABABABABABABABABABABABABABABAB...

output:

150
248 2
244 2
244 2
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
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: 7ms
memory: 150916kb

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: 7ms
memory: 150888kb

input:

298
BAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

output:

-1

result:

ok no solution

Test #61:

score: 6
Accepted
time: 11ms
memory: 150916kb

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: 3ms
memory: 150896kb

input:

300
AAAABBBBAAAABBBBBBAABBAABBBBAAAAABBBBBAAAABBBBAAAABBBBBBAABBBAAAABBBBAAAABBBBBBAAAAABBAAABBAAABBBBBAAAABBBBAAABBBBAAAAAABBBBAABBAAAABBBBAAABBBBBAAABBBBBAAAABBAAABBBAABBBAAAABBBAAAAAABBBBBBAAABBAAAAAABBBBBAAAAAABBBBAAAAABBBBAAAABBBBBBAAABBBBAAAAAAABBAAAAAAABBBBBAAAABBBBAAAAABBBAAAAABBBAAAABBBBAAA...

output:

139
140 3
140 2
137 2
137 2
137 2
133 3
133 2
133 2
133 2
129 2
129 2
129 2
129 2
127 2
127 2
125 3
125 2
121 3
121 2
121 2
115 2
115 2
115 2
115 2
111 3
111 2
111 2
108 3
108 2
108 2
104 3
104 2
104 2
100 2
100 2
100 2
100 2
100 2
95 3
95 2
95 2
95 2
95 2
92 2
92 2
92 2
90 2
90 2
87 3
87 2
87 2
87 ...

result:

ok good solution!

Test #63:

score: 6
Accepted
time: 12ms
memory: 150904kb

input:

299
BBBBBBBBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAAAAAAAAAABABABABABABABABABABABABABABABABABABABAAAAAAAAAAAAAAABABABABABABABABABABABABABABABABABABABABABABAAAAAAAAAAABABABABABABABABABABABABABABABABABABABABABBBBBBBABABABABABABABABABABABABABABABABABA...

output:

148
146 3
146 2
146 2
146 2
146 2
146 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
99 2
99 2
99 2
99 2
99 2
98 3
97 2
96 ...

result:

ok good solution!

Test #64:

score: 6
Accepted
time: 7ms
memory: 150912kb

input:

299
BABABABABABABABBBBBBBBBBABABABABABABABABABABABABABBBBBBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAAAAAAAAAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAAAAAAAAAABABABAAAAAAAAAAAAAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

148
195 2
195 2
195 2
195 2
195 2
194 2
193 2
192 2
191 2
190 2
189 3
189 2
189 2
189 2
189 2
189 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
15...

result:

ok good solution!

Test #65:

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

input:

298
ABABABABABABABABABAAAAABABABABABABABABABAAAABABABABABABABABABABABABABABABABBBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABAAAAAABABABABABABABBBBBBABABABABABABABABABABBBBBBABABABABABABABABABABABABABABABBBBBBABAAAAAABABABABABABABABBBBBBBABABABBBBBBABABABABABABABABABABABABABABABABABABABABABA

output:

146
150 2
150 2
150 2
149 2
148 2
147 2
146 2
145 2
132 2
132 2
132 2
131 2
130 2
129 2
128 2
127 2
126 2
125 3
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 3
111 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 2
98 2
97 2
96 2
95 2
9...

result:

ok good solution!

Test #66:

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

input:

298
BABABABABABABABAAAAABABABABABABABABABABABABABAAAAAABABABABABABABABABABABABABABABABABABAAAAAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBBBBABABABABABABAAAAAAAAAABBBBABABABAAAAAAAABABABABABABABAAAABABABABABABBBBBABABABABABABABABBBBABABABABABABABABABABABABABABABABABABABABABABABABABA

output:

145
169 2
169 2
169 2
169 2
169 2
168 3
168 2
167 2
166 2
151 2
151 2
151 2
150 2
149 2
148 2
147 2
146 2
145 2
144 2
143 2
142 3
141 2
140 2
139 2
138 3
138 2
138 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 3
124 2
123 2
122 2
121 2
120 2
119 2
118 2
11...

result:

ok good solution!

Test #67:

score: 6
Accepted
time: 8ms
memory: 152960kb

input:

297
BABABABABABABABABABABABAAAAAAABABABABABABABABABABABABABBABABABABABABABABABABABABABABABABABABABAAAAABABABABABABABAABBBBBBABAABABABABABABAAAAABABABABABBBBBBBABABABABABABABAAAABABABABAAAABABABBABABABABABABABABABABABABABABABABABABABABABABABBBBBBABABABABABABABABABABABABBBBBABABABAABBBBABABABABABABABAB

output:

143
149 3
149 2
149 2
148 2
147 2
146 2
145 2
144 2
143 2
136 3
136 2
135 2
134 3
133 2
132 2
131 2
130 2
129 2
128 2
127 2
126 3
126 2
125 2
123 3
122 2
121 2
115 3
115 2
115 2
113 3
112 2
111 3
111 2
110 2
109 2
108 2
107 2
106 3
105 2
104 2
103 2
102 2
101 2
100 2
95 2
95 2
95 2
94 2
93 2
92 2
91...

result:

ok good solution!

Test #68:

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

input:

297
BABABABABABABABABABABABABABABABABABABABAABABABABABBBBABABABAAAAAABABABABABABABBBBBABABABABABAAAABABABABABABABABABABABABABBABABABAAAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBABAAAAABABAAAABABAAAAAAABABABABABABAAAAAAAABABABABABAAABABABABABABABABABABABABABABABABBBABABABABABABABBA

output:

144
191 3
190 2
189 2
188 2
188 2
188 2
187 2
186 2
185 2
184 3
184 2
183 2
182 2
181 2
180 2
180 2
180 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 3
168 2
168 2
168 2
167 2
166 2
165 2
164 2
163 2
162 2
161 2
160 2
159 2
158 2
158 2
157 2
156 2
155 2
154 2
153 2
15...

result:

ok good solution!

Test #69:

score: 6
Accepted
time: 7ms
memory: 153000kb

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: 152828kb

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: 0ms
memory: 150844kb

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: 3ms
memory: 152884kb

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: 150852kb

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: 11ms
memory: 152824kb

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: 3ms
memory: 152960kb

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: 3ms
memory: 152908kb

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: 3ms
memory: 150964kb

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: 152952kb

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: 150912kb

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: 0ms
memory: 153012kb

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: 0ms
memory: 150924kb

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: 152960kb

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: 4ms
memory: 150820kb

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: 3ms
memory: 152948kb

input:

300
ABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABAABBAABBAABBAABBAABBAAABBAABBAAABBAABBAAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBBAABBAABBAABBAABB...

output:

106
103 2
100 2
99 2
99 2
98 3
97 3
96 3
95 3
94 3
93 3
92 3
91 3
90 2
90 2
89 3
88 3
87 3
86 2
86 2
85 3
84 3
83 3
82 2
82 2
81 3
80 3
79 3
78 3
77 3
76 3
75 3
74 3
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...

result:

ok good solution!

Test #85:

score: 6
Accepted
time: 11ms
memory: 150780kb

input:

299
BBABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

105
202 2
199 2
197 2
197 2
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: 3ms
memory: 152952kb

input:

299
AABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBABABABABABABABABABABABABABABABABABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBAABAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBA...

output:

105
102 2
101 3
100 3
99 3
98 3
97 3
96 3
95 3
94 3
93 3
92 3
91 3
90 3
89 3
88 3
87 3
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 3
73 3
72 3
71 3
70 3
67 2
66 2
66 2
65 3
64 3
63 3
62 3
61 3
60 3
59 3
58 3
57 3
56 2
56 2
55 3
54 3
53 2
53 2
52 3
51 3
50 3
49 3
48 3
47 3
46 ...

result:

ok good solution!

Test #87:

score: 6
Accepted
time: 7ms
memory: 150832kb

input:

299
BAABBBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAAABBAABBABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABABABABABABABABABABABABABABAB...

output:

105
266 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
135 2
133 3
131 3
129 3
126 2
126 2
124 3
122 3
120 3
118 3
116 3
113 2
113 2
111 3
109 3
10...

result:

ok good solution!

Test #88:

score: 6
Accepted
time: 11ms
memory: 153000kb

input:

300
AAABBAABBAABBAABBAABBAABBAABBAABBBAAABBAABBAABBAABBAAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

105
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: 3ms
memory: 152948kb

input:

300
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABAABBAABBAABBAABBBAABBAABBAABBAAABBAABBAABBAAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABB...

output:

106
298 2
295 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: 152940kb

input:

299
BBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBBAABAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBABABABABABABABABABABAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABB...

output:

122
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
149 3
148 3
147 3
146 3
145 3
144 3
143 2
143 2
142 3
141 3
140 3
139 3
138 3
137 3
136 3
135 3
134 3
133 3
132 3
131 3
13...

result:

ok good solution!

Test #91:

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

input:

300
ABABABABABABABABABABABABABABAABABABABABABABABABABABBAABBBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBABBAABBAABBAABBAABBAAABBAAABBAABBAABBAABBAABABABABABABABABABABABABABABABABABABABABABABAB...

output:

122
210 2
207 2
205 3
205 2
203 2
203 2
201 2
201 2
199 2
199 2
197 2
197 2
195 2
195 2
193 2
193 2
191 2
191 2
189 3
189 2
187 2
187 2
185 3
185 2
183 2
183 2
181 2
181 2
179 2
179 2
177 2
177 2
175 2
175 2
173 2
173 2
171 2
171 2
169 2
169 2
167 3
165 3
163 3
161 3
159 3
157 3
155 3
153 3
151 3
14...

result:

ok good solution!

Test #92:

score: 6
Accepted
time: 7ms
memory: 152948kb

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: 150832kb

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: 4ms
memory: 152876kb

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: 7ms
memory: 152820kb

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: 0ms
memory: 150848kb

input:

299
AABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAB...

output:

-1

result:

ok no solution

Test #97:

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

input:

300
AABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAA...

output:

-1

result:

ok no solution

Test #98:

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

input:

299
BBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

-1

result:

ok no solution

Test #99:

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

input:

300
BBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

-1

result:

ok no solution

Test #100:

score: 6
Accepted
time: 8ms
memory: 152892kb

input:

300
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAA...

output:

-1

result:

ok no solution

Test #101:

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

input:

300
BBAABBBAABBAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAABBAABBAABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAA...

output:

-1

result:

ok no solution

Subtask #3:

score: 7
Accepted

Test #102:

score: 7
Accepted
time: 8ms
memory: 153020kb

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: 3ms
memory: 150840kb

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: 0ms
memory: 150844kb

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: 15ms
memory: 152960kb

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: 150956kb

input:

5999
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2999
4197 3
4195 2
4195 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
4157 2
4...

result:

ok good solution!

Test #107:

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

input:

5998
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2998
4996 3
4994 3
4994 2
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: 3ms
memory: 148784kb

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: 11ms
memory: 152856kb

input:

6000
ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

-1

result:

ok no solution

Test #110:

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

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: 11ms
memory: 148972kb

input:

5999
BBBAAAABBAAAAAAABBBAAAAABBBBBAABBBAABBBBBAAAABBBBBAAAAABBBAAAAABBBBBAAAAAABBBBBAAAABBBBBBAAAAAAABBBBBBAAAABBBBBAAABBBAAABBBBAAAABBBBAAABBBAAAABBBBAAABBBBAAAABBAAAABBBAAAAAABBBAAABBBBBAAAAABBBBAAAABBBAAABBBAAABBAAAABBAAABBBBBAAAAAABBBBBBBAAAABBBAAABBBAABBBAAAABBAABBBBBBBAAAAAABBBBAAAAABBBBAAABBB...

output:

2806
3035 2
3031 3
3031 2
3031 2
3031 2
3027 3
3027 2
3027 2
3023 2
3023 2
3023 2
3023 2
3021 2
3021 2
3021 2
3016 3
3016 2
3016 2
3011 3
3011 2
3011 2
3011 2
3004 2
3004 2
3004 2
3004 2
3004 2
3000 3
3000 2
3000 2
2996 2
2996 2
2996 2
2996 2
2994 3
2994 2
2994 2
2992 2
2992 2
2992 2
2992 2
2986 3
2...

result:

ok good solution!

Test #112:

score: 7
Accepted
time: 16ms
memory: 152884kb

input:

6000
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

2999
3350 2
3350 2
3350 2
3350 2
3350 2
3350 2
3350 2
3350 2
3349 2
3348 2
3347 2
3346 2
3345 2
3344 2
3343 2
3342 2
3341 2
3340 2
3339 2
3338 2
3337 2
3336 2
3335 2
3334 2
3333 2
3332 2
3331 2
3330 2
3329 2
3328 2
3327 2
3326 2
3325 2
3324 2
3323 2
3322 2
3321 2
3320 2
3319 2
3318 2
3317 2
3316 2
3...

result:

ok good solution!

Test #113:

score: 7
Accepted
time: 16ms
memory: 152812kb

input:

6000
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

-1

result:

ok no solution

Test #114:

score: 7
Accepted
time: 32ms
memory: 151364kb

input:

6000
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

2998
3046 2
3046 2
3046 2
3045 2
3044 2
3043 2
3042 2
3041 2
3040 2
3039 2
3038 2
3037 2
3036 2
3035 2
3034 2
3033 2
3032 2
3031 2
3030 2
3029 2
3028 2
3027 2
3026 2
3025 2
3024 2
3023 2
3022 2
3021 2
3020 2
3019 2
3018 2
3017 2
3016 2
3015 2
3014 2
3013 2
3012 2
3011 2
3010 2
3009 2
3008 2
3007 2
3...

result:

ok good solution!

Test #115:

score: 7
Accepted
time: 31ms
memory: 153000kb

input:

5999
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2998
4412 2
4412 2
4411 2
4410 2
4409 2
4408 2
4407 2
4406 2
4405 2
4404 2
4403 2
4402 2
4401 2
4400 2
4399 2
4398 2
4397 2
4396 2
4395 2
4394 2
4393 2
4392 2
4391 2
4390 2
4389 2
4388 2
4387 2
4386 2
4385 2
4384 2
4383 2
4382 2
4381 2
4380 2
4379 2
4378 2
4377 2
4376 2
4375 2
4374 2
4373 2
4372 2
4...

result:

ok good solution!

Test #116:

score: 7
Accepted
time: 44ms
memory: 152888kb

input:

5999
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2995
3214 2
3214 2
3213 2
3212 2
3211 2
3210 2
3209 2
3208 2
3207 2
3206 2
3205 2
3204 2
3203 2
3202 2
3201 2
3200 2
3199 2
3198 2
3197 2
3196 2
3195 2
3194 2
3193 2
3192 2
3191 2
3190 2
3189 2
3188 2
3187 2
3186 2
3185 2
3184 2
3183 2
3182 2
3181 2
3180 2
3179 2
3178 2
3177 2
3176 2
3175 2
3174 2
3...

result:

ok good solution!

Test #117:

score: 7
Accepted
time: 60ms
memory: 153064kb

input:

5997
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBBABABABABABABABABABABABABABABABABABABABABABABBBBBBBBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2995
3925 2
3925 2
3925 2
3924 2
3923 2
3922 2
3921 2
3920 2
3919 2
3918 2
3917 2
3916 2
3915 2
3914 2
3913 2
3912 2
3911 2
3910 2
3909 2
3908 2
3907 2
3906 2
3905 2
3904 2
3903 2
3902 2
3901 2
3900 2
3899 2
3898 2
3897 2
3896 2
3895 2
3894 2
3893 2
3892 2
3891 2
3890 2
3889 2
3888 2
3887 2
3886 2
3...

result:

ok good solution!

Test #118:

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

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: 7ms
memory: 150988kb

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: 3ms
memory: 150984kb

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: 0ms
memory: 153012kb

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: 153004kb

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: 153004kb

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: 7ms
memory: 153072kb

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: 3ms
memory: 150968kb

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: 11ms
memory: 150984kb

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: 152984kb

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: 7ms
memory: 152220kb

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: 8ms
memory: 151024kb

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: 7ms
memory: 151028kb

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: 9ms
memory: 154844kb

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: 7ms
memory: 153024kb

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: 43ms
memory: 151156kb

input:

6000
BAABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2006
2003 2
2000 2
1999 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
1...

result:

ok good solution!

Test #134:

score: 7
Accepted
time: 28ms
memory: 150944kb

input:

5999
AABAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABB...

output:

2005
4002 2
3999 2
3997 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 #135:

score: 7
Accepted
time: 61ms
memory: 152988kb

input:

6000
BBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2006
2002 2
2001 3
2000 3
1999 3
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
1...

result:

ok good solution!

Test #136:

score: 7
Accepted
time: 49ms
memory: 150936kb

input:

6000
ABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABB...

output:

2006
5334 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 #137:

score: 7
Accepted
time: 39ms
memory: 150952kb

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: 23ms
memory: 150952kb

input:

6000
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

2006
5998 2
5995 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: 43ms
memory: 153020kb

input:

6000
BBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABB...

output:

2431
3572 2
3571 2
3570 2
3569 2
3568 2
3567 2
3566 2
3565 2
3564 2
3563 2
3562 2
3561 2
3560 2
3559 2
3558 2
3557 2
3556 2
3555 2
3554 2
3553 2
3552 2
3551 2
3550 2
3549 2
3548 2
3547 2
3546 2
3545 2
3544 2
3543 2
3542 2
3541 2
3540 2
3539 2
3538 2
3537 2
3536 2
3535 2
3534 2
3533 2
3532 2
3531 2
3...

result:

ok good solution!

Test #140:

score: 7
Accepted
time: 36ms
memory: 153016kb

input:

5999
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

2430
4144 2
4141 2
4139 3
4139 2
4137 2
4137 2
4135 2
4135 2
4133 2
4133 2
4131 2
4131 2
4129 2
4129 2
4127 2
4127 2
4125 2
4125 2
4123 2
4123 2
4121 2
4121 2
4119 2
4119 2
4117 2
4117 2
4115 2
4115 2
4113 2
4113 2
4111 2
4111 2
4109 2
4109 2
4107 2
4107 2
4105 2
4105 2
4103 2
4103 2
4101 2
4101 2
4...

result:

ok good solution!

Test #141:

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

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: 15ms
memory: 152860kb

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: 11ms
memory: 151024kb

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: 10ms
memory: 154764kb

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: 19ms
memory: 152940kb

input:

6000
BBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

-1

result:

ok no solution

Test #146:

score: 7
Accepted
time: 19ms
memory: 154368kb

input:

6000
BBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBA...

output:

-1

result:

ok no solution

Test #147:

score: 7
Accepted
time: 19ms
memory: 151212kb

input:

6000
AABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAB...

output:

-1

result:

ok no solution

Test #148:

score: 7
Accepted
time: 20ms
memory: 150804kb

input:

5999
AABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAB...

output:

-1

result:

ok no solution

Test #149:

score: 7
Accepted
time: 15ms
memory: 150836kb

input:

5999
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

-1

result:

ok no solution

Test #150:

score: 7
Accepted
time: 23ms
memory: 150844kb

input:

6000
AABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAAB...

output:

-1

result:

ok no solution

Test #151:

score: 7
Accepted
time: 11ms
memory: 151520kb

input:

6000
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

-1

result:

ok no solution

Test #152:

score: 7
Accepted
time: 18ms
memory: 151276kb

input:

5999
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

-1

result:

ok no solution

Subtask #4:

score: 0
Time Limit Exceeded

Test #153:

score: 0
Time Limit Exceeded

input:

999997
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:


result: