QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#140975#5440. P-P-Palindromemendicillin2AC ✓43ms43544kbC++142.1kb2023-08-17 02:42:012023-08-17 02:42:02

Judging History

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

  • [2023-08-17 02:42:02]
  • 评测
  • 测评结果:AC
  • 用时:43ms
  • 内存:43544kb
  • [2023-08-17 02:42:01]
  • 提交

answer

#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = int(a); i < int(b); i++)
#define trav(a, x) for (auto& a : x)
#define per(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()

template <class T> using vc = vector<T>;
template <class T> using vvc = vc<vc<T>>;

using ll = int64_t;
using vi = vc<int>;
using pii = pair<int, int>;

// Author: maroonrk (modified)
// https://codeforces.com/contest/1738/submission/174140231
template<class S>
struct eertree{
	struct N{
		int suf,l,r;
		int len(){return r-l;}
		//map<int,int> ch;
		array<int,26> ch;
	};
	vc<N> x;
	int dist(int v){
		if(x[v].suf<=0)return -1;
		return x[v].len()-x[x[v].suf].len();
	}
	int c;
	S s;
	eertree(){
		x.push_back({-1,1,0,{}});
		x.push_back({0,0,0,{}});
		c=1;
	}
	void reset() {
		c = 1;
		s.clear();
	}
	void reserve(int n) {
		s.reserve(n+5);
		x.reserve(n+5);
	}
	bool chk(int v,int i){
		int l=i-x[v].len();
		return l>0&&s[l-1]==s[i];
	}
	template<class t>
		int extend(t z){
			int i=sz(s);
			s.push_back(z);

			while(!chk(c,i))c=x[c].suf;
			if(x[c].ch[s[i]]==0){
				int d=x[c].suf;
				if(d!=-1)while(!chk(d,i))d=x[d].suf;
				int e=d==-1?1:x[d].ch[s[i]];
				x[c].ch[s[i]]=sz(x);
				x.push_back({e,i-x[c].len()-1,i+1,{}});
			}
			return c=x[c].ch[s[i]];
		}
	N& operator[](int i){
		return x[i];
	}
};

int main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	cout << fixed << setprecision(20);

	int N;
	cin >> N;
	eertree<vector<int>> et;
	et.reserve(1000000);
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		const int L = int(s.size());
		et.reset();
		for (int j = 0; j < L; j++) {
			int x = int(s[j] - 'a');
			et.extend(x);
		}
	}

	ll ans = 0;
	const int num = int(et.x.size());
	for (int v = 2; v < num; v++) {
		int period = et.dist(v);
		int len = et[v].len();
		if (period == -1 || len % period) {
			ans++;
		} else {
			ans += 2 * (len/period) - 1;
		}
	}
	cout << ans << '\n';
}


详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3584kb

input:

2
aaaa
aaa

output:

16

result:

ok 1 number(s): "16"

Test #2:

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

input:

3
abaaa
abbbba
bbbaba

output:

28

result:

ok 1 number(s): "28"

Test #3:

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

input:

1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab

output:

15130

result:

ok 1 number(s): "15130"

Test #4:

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

input:

3
aaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbb
bababababababaabababababa

output:

1282

result:

ok 1 number(s): "1282"

Test #5:

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

input:

5
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...

output:

3600000000

result:

ok 1 number(s): "3600000000"

Test #6:

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

input:

5
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...

output:

3600000000

result:

ok 1 number(s): "3600000000"

Test #7:

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

input:

3
abbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbab...

output:

133586

result:

ok 1 number(s): "133586"

Test #8:

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

input:

3
abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbabab...

output:

118967

result:

ok 1 number(s): "118967"

Test #9:

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

input:

3
bbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabb...

output:

114444

result:

ok 1 number(s): "114444"

Test #10:

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

input:

3
abbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbabab...

output:

115321

result:

ok 1 number(s): "115321"

Test #11:

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

input:

3
azzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazaz...

output:

131825

result:

ok 1 number(s): "131825"

Test #12:

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

input:

3
yazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbyb...

output:

6

result:

ok 1 number(s): "6"

Test #13:

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

input:

3
azbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazby...

output:

6

result:

ok 1 number(s): "6"

Test #14:

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

input:

3
byazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyaz...

output:

6

result:

ok 1 number(s): "6"

Test #15:

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

input:

1
abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabba...

output:

113382

result:

ok 1 number(s): "113382"

Test #16:

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

input:

5
rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr...

output:

123447499

result:

ok 1 number(s): "123447499"

Test #17:

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

input:

5
tttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt...

output:

25319820

result:

ok 1 number(s): "25319820"

Test #18:

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

input:

5
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...

output:

2746507

result:

ok 1 number(s): "2746507"

Test #19:

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

input:

3
oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo...

output:

1912677071

result:

ok 1 number(s): "1912677071"

Test #20:

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

input:

3
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxcxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

111259628

result:

ok 1 number(s): "111259628"

Test #21:

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

input:

3
cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...

output:

13754174

result:

ok 1 number(s): "13754174"

Test #22:

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

input:

3
dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd...

output:

1867151

result:

ok 1 number(s): "1867151"

Test #23:

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

input:

1
jjqjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjvjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj...

output:

1856484

result:

ok 1 number(s): "1856484"

Test #24:

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

input:

1
vvvvvvvvvvvvvvvvvvvvvvvvvvvqvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvsvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvnvvvvvvvvvvvvvvvvvvvv...

output:

190722

result:

ok 1 number(s): "190722"

Test #25:

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

input:

1
txxxxxxxxxxxxxxxxxxxxxxxxxxxxhxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxrxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxhxxxxxtxlxxxxxxxxxktxxxxxxxxxxxxxxxxxexxxxxxxxxxxxxxgxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxjxxxxxxxxxxxxxxxxxxxvxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzqxxjxxxxxxxxxxxxxxx...

output:

76004

result:

ok 1 number(s): "76004"

Test #26:

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

input:

1
gggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg...

output:

81149988

result:

ok 1 number(s): "81149988"

Test #27:

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

input:

1
llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...

output:

1272080790

result:

ok 1 number(s): "1272080790"

Test #28:

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

input:

1
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee...

output:

12890286923

result:

ok 1 number(s): "12890286923"

Test #29:

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

input:

5
dgasxxawfuzttbnrniddspiplejfqzzoadnogyemjktjqqjtkjmeygondaozzqfjelpipsddinrnbttzufwaxxsagdvkrreghjrkkrjhgerrkvdgasxxawfuzttbnrniddspiplejfqzzoadnogyemjktjqqjtkjmeygondaozzqfjelpipsddinrnbttzufwaxxsagdvkrreghjrkkrjhgerrkvdgasxxawfuzttbnrniddspiplejfqzzoadnogyemjktjqqjtkjmeygondaozzqfjelpipsddinrnbt...

output:

652993

result:

ok 1 number(s): "652993"

Test #30:

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

input:

5
jlpzojmatlmawicowbaazzfyzqdjodsyngoqfnxbshbjywkgafhdarnchbwcskosqxpdjffjdpxqsokscwbhcnradhfagkwyjbhsbxnfqognysdojdqzyfzzaabwociwamltamjozpljjlpzojmatlmawicowbaazzfyzqdjodsyngoqfnxbshbjywkgafhdarnchbwcskosqxpdjffjdpxqsokscwbhcnradhfagkwyjbhsbxnfqognysdojdqzyfzzaabwociwamltamjozpljjlpzojmatlmawicowb...

output:

425510

result:

ok 1 number(s): "425510"

Test #31:

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

input:

5
zwzxfvwcwglyetqbpgxubiqntaydeqmdpassapdmqedyatnqibuxgpbqteylgwcwvfxzwzjeiveeviejzwzxfvwcwglyetqbpgxubiqntaydeqmdpassapdmqedyatnqibuxgpbqteylgwcwvfxzwzjeiveeviejzwzxfvwcwglyetqbpgxubiqntaydeqmdpassapdmqedyatnqibuxgpbqteylgwcwvfxzwzjeiveeviejzwzxfvwcwglyetqbpgxubiqntaydeqmdpassapdmqedyatnqibuxgpbqte...

output:

1180524

result:

ok 1 number(s): "1180524"

Test #32:

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

input:

5
rmgwqmkvznpmdkqiiqkdmpnzvkmqwgmrpocxxcoprmgwqmkvznpmdkqiiqkdmpnzvkmqwgmrpocxxcoprmgwqmkvznpmdkqiiqkdmpnzvkmqwgmrpocxxcoprmgwqmkvznpmdkqiiqkdmpnzvkmqwgmrpocxxcoprmgwqmkvznpmdkqiiqkdmpnzvkmqwgmrpocxxcoprmgwqmkvznpmdkqiiqkdmpnzvkmqwgmrpocxxcoprmgwqmkvznpmdkqiiqkdmpnzvkmqwgmrpocxxcoprmgwqmkvznpmdkqiiq...

output:

4551019

result:

ok 1 number(s): "4551019"

Test #33:

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

input:

5
tnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskk...

output:

18042012

result:

ok 1 number(s): "18042012"

Test #34:

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

input:

5
wosalwxbdgvouchgnkqygjphbtpoxduzlpmpbuhhmwvgsbrfolbykyjzoukregdyxskkinjqzjeuublzpuukcaazbsggluyqlmyiallofjebbukuqcalufrqdjjkgvooretzaasgnpnztfalutzztulaftznpngsaazteroovgkjjdqrfulacqukubbejfollaiymlqyulggsbzaackuupzlbuuejzqjnikksxydgerkuozjykyblofrbsgvwmhhubpmplzudxoptbhpjgyqknghcuovgdbxwlasowovxg...

output:

61625

result:

ok 1 number(s): "61625"

Test #35:

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

input:

5
pyybsfiukgpneuwnykmxylcpaujvzpvcubdlvljkdwxkniwznzqvfblfedmydoqqrysksoobrwsqguocoxtfnisqmtbbieekshiwrzrbluflrtzfxwkvqtplcinkqqjsxogdsyucodbzhhnzaluymttfnzovqnevrqtbtqpmtgsfvnenstchzhdrequfxuasnkoxexafwpbgzqaobiicvmwugeugfgpmjvfphfojacdfhjplypqfoxzoacnfoucbhlqqnxxywfdaykxbsfkkkbwuryfwowvhecdgtnzcnp...

output:

57998

result:

ok 1 number(s): "57998"

Test #36:

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

input:

5
pndpupqzhnvxfilkpqdiabywphmclxjchfoctreacxnxwernjkhtyrgokfjpcuuqstsoserfmhfnrgdhzsioknvrhqflrjfkgkjrtoouchgeduceggstnsraurhpxgreryesioloxkcnndjdzyrfmksunizovolqltamzkmaggqftuvwjnkrhgyewthkqchdrgqrkwdfdwdoqunjulkpykaavlinxbzfuzzoqyvwrsfgmtvrzoyidesgkfwtbunicodseljtsxdzxpvpjnbaunefavrjjzhufqqsvekbpl...

output:

46840

result:

ok 1 number(s): "46840"

Test #37:

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

input:

1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

90000000000

result:

ok 1 number(s): "90000000000"

Test #38:

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

input:

5
nmnnmnnmnnmnnmmmnnmmmmmnnnnnmmnmnnnnnmmnmmmnnnmnmnmnmmmmmnnnnmnnnmnnnmmmnmnmmmmnmmnmmmnnnnmmmmmnmnnmmmnmmnmmnmmmnnnmmmnmmnnnmmmnnmnnnmnmmmnnnnmmmnmnnmnmmmmnnnnnnnmnnnmmmmnmmnnnmnnnmmmnnmmnmnmmnnmmmmnnmnnnmmmmmmnmmnnnmnnnnnmmnmnmmnmnnnmnmmnmnmmmnnmmnmnnnmnmmmmnmnnnmmmnmnmmnnnnnmmmnnmnnnnnnmmmmmmmnm...

output:

4526

result:

ok 1 number(s): "4526"

Test #39:

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

input:

5
aaupapuupauuauapupapauauuuuuaapauuaaapppuauuppupuapappuapuuuuaupappaauupapppuppauuaauppuappaappaupaaapaapupuuapaauuuppppuaapaaauuapupuaaapppuuaaapuuuapuaupaaapupaauaapuaapaaaaupuuuupupuapaaaapaupaaaapppuapapuauauapuaauuapapuappauauappuappppuppaauapapuapuauuapupaupaauauupaauapuaupauauuapaappaapaapp...

output:

2372

result:

ok 1 number(s): "2372"

Test #40:

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

input:

5
bkdbddddvddkvkvdbkvdvbbdkkkvvkbvbvbvvbvvvkdbdkkkdvbdkdkvbbbbkbbvbkddkbdvbkkkbdvvdkkdvkbkkdvddbdvdkkdkvbkkdkkbvddddvdvvkkvbbdvkkvkbkkkkkvddbbkdkbvdkbkkdvkvvvvkbkkvkbbdvbkdbkdbkvkkkkvkvkkvvkkvkbbvbvbbbvkbvbvkkvkvkbvbdvvdkkvdbkvbdvvdkvddvvddvkdbkbbvkbvdbvvdddkbdddvbbbdvvdddvdkbdkbkkdbvbkdvdddvddbkkvk...

output:

2339

result:

ok 1 number(s): "2339"

Test #41:

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

input:

2
afffafafaa
afaafaafaf

output:

29

result:

ok 1 number(s): "29"

Test #42:

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

input:

5
wjdulwwjulujdddljudwwlddduddujljjjdluljwddjuddddljwjuujdllllljuudddjwududddudllwudluldwudddwdllldlwwwdjlwuwwlddlluluwdlldjuudujdjujddwduwwjwlluudjjujjdudlljwdwduwjdljlwdjddwddddludwuuwlddddddljddlduddwldwddllduwjwddjdulwddjwddddwujwluujjjludwjddwwdjwddulldjwljudjljljduddjlddjujdddddudduljduuuljwul...

output:

2063

result:

ok 1 number(s): "2063"

Test #43:

score: 0
Accepted
time: 33ms
memory: 3460kb

input:

1000000
i
n
l
f
q
i
s
m
u
x
r
v
v
u
b
m
o
u
s
q
k
t
t
c
n
t
y
m
x
q
k
v
h
q
s
w
o
b
o
y
n
s
f
w
d
d
y
d
l
i
e
r
c
l
e
d
h
h
c
l
x
q
f
l
v
j
q
j
p
o
e
s
l
w
u
h
q
f
j
g
l
h
v
x
k
w
t
h
o
b
e
s
x
c
m
v
r
r
p
w
d
g
r
u
g
d
j
a
a
c
w
t
u
h
x
i
l
s
o
z
i
m
p
h
j
u
p
t
g
f
p
w
x
f
o
w
u
m
a
k
p
p
q
x
n
r
...

output:

26

result:

ok 1 number(s): "26"

Test #44:

score: 0
Accepted
time: 43ms
memory: 3528kb

input:

1000000
u
i
n
f
z
i
g
y
o
t
a
t
y
q
m
g
u
z
t
j
j
s
f
r
f
z
a
e
k
s
q
u
p
e
o
l
x
g
q
b
l
w
x
c
u
x
j
e
s
e
y
r
r
v
v
i
d
p
q
e
q
q
z
a
d
i
e
y
w
p
e
x
m
n
e
f
j
l
c
y
x
i
d
a
m
k
w
q
y
j
c
u
y
h
k
l
y
j
r
e
r
b
n
i
w
r
o
i
q
m
o
r
x
d
s
u
n
i
w
r
t
g
c
i
d
h
n
a
x
h
t
c
s
h
c
j
c
i
b
z
u
z
c
b
e
k
...

output:

26

result:

ok 1 number(s): "26"

Test #45:

score: 0
Accepted
time: 37ms
memory: 3576kb

input:

1000000
c
c
b
c
b
b
a
c
c
b
c
b
a
a
a
a
c
b
a
c
c
c
c
b
c
a
c
c
b
a
a
a
c
c
b
b
c
a
c
a
c
c
c
c
a
b
c
b
a
b
c
a
a
a
b
c
a
c
b
c
b
a
c
b
a
b
c
c
a
c
b
c
a
b
c
c
b
a
a
a
c
b
c
a
b
b
c
b
a
a
c
c
c
b
b
a
b
a
c
b
a
b
c
b
b
b
a
b
a
a
c
a
b
b
c
a
a
c
c
b
a
a
c
b
a
b
a
b
b
b
b
b
c
a
b
b
c
a
a
a
b
a
b
b
a
c
...

output:

3

result:

ok 1 number(s): "3"

Test #46:

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

input:

1
alngdzgfsplrmhhyblurpjxyqhrxmbyyubvvxtmuwrnfimiggwhsoluetintakqfohgtmtampxljpkawolbuyrsrmdjapecfytjcfxcdcyymbfaqshkujxxypteohceukrejaveenkmsdxrmpdlapcnsnowykiiqisgdratbqcwxfzspkglkqghmcsiqwemkilaisqucgithhcrjvoydpnmtmxdwsmjfjtimsqpvesagpqucssfwyricarvcpcujfsxupluoxxkzelyjqewsptiyobhrvdatjhbcohcdfd...

output:

3195

result:

ok 1 number(s): "3195"

Test #47:

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

input:

1
ghbhcdfhccifjigghcfhejhfcaibghfhehehjichadijbiihajddhgjgbdibecjjcaagedfaafejcfjjgdaiebcjihecjicadacefgbajeafccjdbafdjhjddjggbdhgdijbbiadeabbaiieacbeighagbaajgdbdajgajcabhcgfcadbadigjhehaibighhdjhaeggefhgfcfhaahhchedcjhbaedihgfgjiejeifbdieacghbghfjdjfehfgdfadeeghdjdcghibjdhiiggdchdbihfchbhchaeefccb...

output:

3395

result:

ok 1 number(s): "3395"

Test #48:

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

input:

1
fgffhhghheehgggfgghdeeeedgfdhdfehghhegeeggfhgdfhgfgedgdgdegedhegeedddefdfedhfgdhghehhggehdffdfgddhegeghefffgddedfeeggfheghhgghhhehfefhfegfgghfffdhfddgheegdgefdhhegfffefghhehgggheegdggddeggdehddhdfefgeffdgfdghefgegdhegdfggeggddhhddefghfgedhhdeghgfedhddefdhfhfdhfdghhegedfhdeefffegedddgfgefheffeeeedd...

output:

4178

result:

ok 1 number(s): "4178"

Test #49:

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

input:

100
xuxmuutatmmtxmautmmttuuaatmtamxmutxautxxttmuamtxaaumaautaaattmmmxumtxaaxmxxmmumuttmututmtmuauutuuuumtuaxmaaxattxattuuxumxtummmttmmutmmataxuuttattmatumxxatuxumatxutmtuuaaatxatutmmtutauauuuuxumataxtamauttaaxxuttaaxtauamammxumauxumuuutmuxmauxutuxuxtutmtatuxttxtummtxutxmaxuuxxtxuatuamuxaatuatuauxxmu...

output:

30276

result:

ok 1 number(s): "30276"

Test #50:

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

input:

100
wddldawddddlwwawawdwdldldldldawdwwdwaaddlddddadwladdddaddawadladlwldlalldddlddlddwdlwwddaddllwwdldddwwldddaadwadddddlddlwwdawawdwaawadadadldddwaaldadallwdwlwdlddadlddladdlddddaaddddlwwdaalddddwldaddadaddwawwalaalladdalllddadwddddadlwlddlddwldaadlwddwlldddadwwaddaaldddwwlddddddwddadddalwawddwdawd...

output:

30213

result:

ok 1 number(s): "30213"

Test #51:

score: 0
Accepted
time: 18ms
memory: 6152kb

input:

100
ygripyrkwoyooyykfppktyktktikoyyogttiorfyptgtogkygrtkiwgyoipkpkkiiikypgftggfpktrwoygfwptwpwfyptpwrwyigyokwprkfpkfkfwpfykrfygoyykkgfigyktyryrfpkfwoipoipotypiifpyooykkpokgopooykywyiwgoypwtwygfikorpoirptfffkwirriyyyypfpkiwrpyfgtwrtfyfotpttfrwpfoprftpyigfrtggpwifypwyfpowpripgtfrgkyirkrorfgrorwpopioig...

output:

16720

result:

ok 1 number(s): "16720"

Test #52:

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

input:

100
ywwcynkynntwwqtcyjcnkjtkwctnqwcttnnqwqjjqjjwykwwyjwnywkwqwnjytqkyyjwqwwycyycjtqyqyjyqqynqwwtnwcjwjckjnnywjwwjntnwwjywywwwkwwtcqnkqqjqqwkknnykjcynwnyyqwjwyjckkcnqyqwkywyykkwcwwwkcknkwttnqyqytnttyjqtwwywqyytywkcwyqnqwywwwtwywjwqjwcwcqwkqcqnywkkwyncjwtkcwqtjycywtjkywyknyjqcwqwtywqjktwytkcwykwknnwyj...

output:

346933

result:

ok 1 number(s): "346933"

Test #53:

score: 0
Accepted
time: 27ms
memory: 43544kb

input:

100
nmxxmmvdyyfnmmvmmunvmfmvrnddnryrmdrvuurmuvnmudnnrrmyvmvuvdxvyxvmumnnrxummffuvdrmxnydfxnxfnxmnvmyfnmuyxruxfymyryunrmfmdmmxmufnmmmmmryrnfmrrvrfvfdxumymxmmxmxxmnfyddmmurvfvumfmxrmvfmnxnmnrvmyxfyrvnyfyyvvrmryynruyxmfmvmxxmrxrvmxudyvfxndrnvunvmnyxvyfvvxrndmffdvrfvfmmufdumxdvmumvmmxnmxdudyyfrdvmrxvyyx...

output:

354764

result:

ok 1 number(s): "354764"

Test #54:

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

input:

100
hohohoohoohhoohhhhhhohohhhooohhohoooohohhhoooohohhhoohhooohhhooohhoooohooooooohohhhoohohohhhohoohhohhohhoohohhhohohoohhhohooooooohoooohhooohhhooohhoohhhohoooohhhohoooohohhooohhhohohhhhhhoohhoohoohohohhohhoohohhhohohoohhhohooooooohoooohhooohhhooohhoohhhohoooohhhohoooohohhooohhhohohhhhhhoohhoohooh...

output:

400202791

result:

ok 1 number(s): "400202791"

Test #55:

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

input:

100
yyyyyjyyjjjyyjjjjjyjyyyjyyjyyjyyyjyyyyjjyyjjjyyyjyyyyjjjyyyjjyjyyyyyyyyyjjjyyjjyjjjyyyyjjjyyyyjyyyyyyyyyyjyyyyjjjyyyyjjjyjjyyjjjyyyyyyyyyjyjjyyyjjjyyyyjyyyjjjyyjjyyyyjyyyjyyjyyjyyyjyjjjjjyyjjjyyjyyyyyyyyyyjyyjjjyyjjjjjyjyyyjyyjyyjyyyjyyyyjjyyjjjyyyjyyyyjjjyyyjjyjyyyyyyyyyjjjyyjjyjjjyyyyjjjyyyyjy...

output:

200209587

result:

ok 1 number(s): "200209587"

Test #56:

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

input:

100
coppocpcpccpccppocopcooccopopccopccocccpocooccocpcppccocoppcocoppcoocoopopoooopppopppoccppccpcppccoccoccppcpccppccopppopppoooopopoocoocppococppococcppcpcoccoocopcccoccpoccpopoccoocpocoppccpccpcpcoppoccoccppcpccppccopppopppoooopopoocoocppococppococcppcpcoccoocopcccoccpoccpopoccoocpocoppccpccpcpco...

output:

203651

result:

ok 1 number(s): "203651"