QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#324964#8234. Period of a Stringucup-team008#AC ✓1000ms25280kbC++2312.6kb2024-02-11 02:25:072024-02-11 02:25:08

Judging History

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

  • [2024-02-11 02:25:08]
  • 评测
  • 测评结果:AC
  • 用时:1000ms
  • 内存:25280kb
  • [2024-02-11 02:25:07]
  • 提交

answer

// {{{ y0105w49 template 22M14
// hi mom
#ifndef NULL
#ifdef __GNUC__
#ifndef __clang__
// #include <bits/stdc++.h>
#include <bits/extc++.h>
#include <tr2/dynamic_bitset>
#define EXTS
#else
#ifdef ARST
#include <bits/clang++.h>
#else
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
// #include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
// #include <cuchar>
#endif
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#if __cplusplus >= 201402L
#include <shared_mutex>
#endif
#if __cplusplus >= 201703L
#include <any>
#include <charconv>
// #include <execution>
#include <filesystem>
#include <optional>
// #include <memory_resource>
#include <string_view>
#include <variant>
#endif
#if __cplusplus >= 202002L
#include <barrier>
#include <bit>
#include <compare>
#include <concepts>
#if __cpp_impl_coroutine
# include <coroutine>
#endif
#include <latch>
#include <numbers>
#include <ranges>
#include <span>
// #include <stop_token>
#include <semaphore>
// #include <source_location>
// #include <syncstream>
#include <version>
#endif
#if __cplusplus > 202002L
// #include <expected>
// #include <spanstream>
#if __has_include(<stacktrace>)
# include <stacktrace>
#endif
#include <stdatomic.h>
#endif
#endif
#endif
#else
#error "unsupported"
#endif
#endif
using namespace std;
#ifdef ARST
#define JO 1
#define OJ 0
#else
#define JO 0
#define OJ 1
#endif
#define STR(x) #x
#define GCCDIAG(s) _Pragma(STR(GCC diagnostic s)) static_assert(true)
#define Wsave GCCDIAG(push)
#define Wpop GCCDIAG(pop)
#define Wsupp(w) GCCDIAG(ignored "-W" w)
#define Wpush(w) Wsave; Wsupp(w)
#define typeof __typeof__
namespace gbd_ns {
	template<typename C>
	struct is_iterable {
		template<class T> static long check(...);
		template<class T> static char check(int,typename T::const_iterator = C().end());
		enum {
			value = sizeof(check<C>(0)) == sizeof(char),
			neg_value = sizeof(check<C>(0)) != sizeof(char)
		};
	};
	template<class T> struct _gbd3C;
	template<class T> ostream &_gbd3(ostream &os,const T &x) { return _gbd3C<T>::call(os,x); }
	template<> ostream &_gbd3(ostream &os,const string &x) { return os<<'"'<<x<<'"'; }
	template<> ostream &_gbd3(ostream &os,char *const &x) { return os<<'"'<<x<<'"'; }
	template<class T> ostream &_gbd3_5(ostream &os,const T &x) { return _gbd3(os,x); }
	template<class A,class B>
	ostream &_gbd4(ostream &os,const pair<A,B> &p) {
		_gbd3(os<<'(',p.first);
		_gbd3(os<<',',p.second);
		return os<<')';
	}
	template<class T,size_t N> struct _gbd4_tupleC {
		static void call(ostream &os,const T &t) {
			_gbd4_tupleC<T,N-1>::call(os,t);
			os<<','<<get<N-1>(t);
		}
	};
	template<class T> struct _gbd4_tupleC<T,1> {
		static void call(ostream &os,const T &t) {
			os<<get<0>(t);
		}
	};
	template<typename... Types>
	ostream &_gbd4(ostream &os,const tuple<Types...> &t) {
		os<<'(';
		_gbd4_tupleC<tuple<Types...>,sizeof...(Types)>::call(os,t);
		return os<<')';
	}
	template<>
	ostream &_gbd4(ostream &os,const tuple<> &t) { (void)t; return os<<"()"; }
	template<class T> ostream &_gbd4(ostream &os,const T &x) {
		return os<<x;
	}
	template<class T> struct _gbd3C {
		template<class U=T>
		static ostream &call(ostream &os,enable_if_t<is_iterable<U>::value,const T> &V) {
			os<<"{";
			bool ff=0;
			for(const auto &E:V) _gbd3_5<decltype(E)>(ff?os<<",":os,E), ff=1;
			return os<<"}";
		}
		template<class U=T>
		static ostream &call(ostream &os,enable_if_t<is_iterable<U>::neg_value,const T> &x) {
			return _gbd4(os,x);
		}
	};
	template<class T,typename... Args> ostream &_gbd2(ostream &os,bool,vector<string>::iterator nm,const T &x,Args&&... args);
	ostream &_gbd2(ostream &os,bool,vector<string>::iterator) { return os; }
	template<typename... Args>
	ostream &_gbd2(ostream &os,bool fi,vector<string>::iterator nm,const char *x,Args&&... args) {
		return _gbd2(os<<(fi?"":"  ")<<x,0,nm+1,args...);
	}
	template<class T,typename... Args>
	ostream &_gbd2(ostream &os,bool fi,vector<string>::iterator nm,const T &x,Args&&... args) {
		return _gbd2(_gbd3<T>(os<<(fi?"":"  ")<<*nm<<"=",x),0,nm+1,args...);
	}
	vector<string> split(string s) {
		vector<string> Z;
		string z="";
		s+=',';
		int dep=0;
		for(char c:s) {
			if(c==',' && !dep) Z.push_back(z),z="";
			else z+=c;
			if(c=='(' || c=='{' || c=='[') ++dep;
			if(c==')' || c=='}' || c==']') --dep;
		}
		return Z;
	}
	template<typename... Args> ostream &_gbd1(ostream &os,const string &nm,Args&&... args) {
		return _gbd2(os,1,split(nm).begin(),args...);
	}
	template<typename... Args> string _gbd1(const string &nm,Args&&... args) {
		ostringstream oss;
		_gbd2(oss,1,split(nm).begin(),args...);
		return oss.str();
	}
}
bool DBG=1,EMACS=0;
#define dbg(...) (JO&&DBG?gbd_ns::_gbd1(cerr<<"\033[38;5;5m"<<__FILE__<<":"<<__LINE__<<(EMACS?":note: ":": "),#__VA_ARGS__,__VA_ARGS__)<<"\033[0m"<<endl:cerr)
#define dbgt(...) dbg(fmt_time(),__VA_ARGS__)
#define fmt(...) gbd_ns::_gbd1(#__VA_ARGS__,__VA_ARGS__)
template<class Fun> struct _y_combinator_result {
	Fun _fun;
	template<class T> explicit _y_combinator_result(T &&fun) : _fun(forward<T>(fun)) {}
	template<typename... Args> decltype(auto) operator()(Args &&... args) {
		return _fun(ref(*this),forward<Args>(args)...);
	}
};
template<class Fun> [[nodiscard]] decltype(auto) fix(Fun &&fun) {
	return _y_combinator_result<decay_t<Fun>>(forward<Fun>(fun));
}
#define nop void()
#define sz(x) (int((x).size()))
#define all(v) (v).begin(),(v).end()
#define sortu(v) (sort(all(v)), (v).resize(unique(all(v))-begin(v)))
#define forenum(i,...) for(int i:{-1}) for(__VA_ARGS__) if(++i,0) assert(0); else
#define forenumll(i,...) for(long long i:{-1}) for(__VA_ARGS__) if(++i,0) assert(0); else
#define forbs(k,i,bs) for(ptrdiff_t k=0,i=(bs)._Find_first();i<(ptrdiff_t)(bs).size();i=(bs)._Find_next(i),++k)
#define fordbs(k,i,bs) for(ptrdiff_t k=0,i=(bs).find_first();i<(ptrdiff_t)(bs).size();i=(bs).find_next(i),++k)
#define get(x,i) get<i>(x)
template<class T> bool inb(const T &x,const T &l,const T &r) { return l<=x&&x<=r; }
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#ifdef EXTS
template<class S,class T> using omap=__gnu_pbds::tree<S,T,less<S>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
template<class T> using oset=omap<T,__gnu_pbds::null_type>;
template<class T> using rope=__gnu_cxx::rope<T>;
using dbitset=tr2::dynamic_bitset<>;
#endif
constexpr int e0=1, e1=10, e2=100, e3=1000;
constexpr int e4=10*e3, e5=100*e3, e6=1000*e3;
constexpr int e7=10*e6, e8=100*e6, e9=1000*e6;
constexpr long long e10=10LL*e9, e11=100LL*e9, e12=1000LL*e9;
constexpr long long e13=10*e12, e14=100*e12, e15=1000*e12;
constexpr long long e16=10*e15, e17=100*e15, e18=1000*e15;
constexpr __int128_t e21=__int128_t(e3)*e18, e24=__int128_t(e6)*e18, e27=__int128_t(e9)*e18;
constexpr __int128_t e30=e3*e27, e33=e6*e27, e36=e9*e27;
using ulll=__uint128_t;
using lll=__int128_t;
using ull=unsigned long long;
using ll=long long;
using ld=long double;
#ifdef EXTS
using lld=__float128;
#endif
long long START_TIME=chrono::duration_cast<chrono::microseconds>(chrono::steady_clock::now().time_since_epoch()).count();
inline long long now_U_03BC_s() { return chrono::duration_cast<chrono::microseconds>(chrono::steady_clock::now().time_since_epoch()).count()-START_TIME; }
const char *fmt_time(long long U_03BC_s=now_U_03BC_s()) { static char dur[20]; sprintf(dur,"%llu.%03llus",U_03BC_s/e6,(U_03BC_s%e6)/e3); return dur; }
#define timed(cb) do { dbg("timed "#cb" ..."); unsigned long long start=now_U_03BC_s(); cb; dbg("timed "#cb" took",fmt_time(now_U_03BC_s()-start)); } while(0)
int arg1; bool inp; vector<string> args;
unsigned seed=unsigned(JO&&getenv("sd")?atoi(getenv("sd")):OJ?START_TIME:START_TIME%e5);
mt19937 igen(seed<<1),gen(seed<<1|1);
#define irand(...) _rand(igen,__VA_ARGS__)
#define rand(...) _rand(gen,__VA_ARGS__)
template<class T> enable_if_t<numeric_limits<T>::is_integer,T> _rand(mt19937 &g,T l,T r) { return uniform_int_distribution<T>(l,r)(g); }
template<class T> enable_if_t<numeric_limits<T>::is_integer,T> _rand(mt19937 &g,T n) { return _rand(g,T(1),n); }
[[deprecated]] int _rand(mt19937 &g) { return _rand(g,0,numeric_limits<int>::max()); }
template<class T> enable_if_t<numeric_limits<T>::is_iec559,T> _rand(mt19937 &g,T l,T r) { return uniform_real_distribution<T>(l,r)(g); }
bool _rand(mt19937 &g,double p) { return bernoulli_distribution(p)(g); }
template<class T> T _rand(mt19937 &g,initializer_list<T> il) { return *(il.begin()+_rand(g,0,(int)il.size()-1)); }
template<class T> T _rand(mt19937 &g,double p,T a,T b) { return _rand(g,p)?a:b; }
template<class T> T _rand(mt19937 &g,initializer_list<T> il,initializer_list<double> wt) { assert(il.size()==wt.size()); return *(il.begin()+discrete_distribution<int>(wt)(g)); }
#define random_shuffle(...) static_assert(false,"random_shuffle deprecated, use shuffle")
#define ine(x,e) (inp?cin>>(x),nop:((x)=(e),nop))
#define inr(x,...) ine(x,irand(__VA_ARGS__))
#define endl '\n'
string garb;
void exit0() { DBG=1; dbgt("gg (early)"); exit(0); }
#ifndef MAIN
#define MAIN _main
#endif
void MAIN();
int32_t main([[maybe_unused]]int argc,[[maybe_unused]]char *argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(0); cin.exceptions(ios_base::failbit | ios_base::badbit);
	arg1=0,args={argv,argv+argc};
	if(sz(args)>1) {
		if(args[1][0]=='i') freopen((string(__FILE__).substr(0,string(__FILE__).find('.'))+"."+args[1].substr(1)+".in").c_str(),"r",stdin);
		else if(args[1][0]=='I') freopen(args[1].substr(1).c_str(),"r",stdin);
		else arg1=stoi(args[1]);
	}
	inp=!arg1;
	if(JO && getenv("EMACS")) EMACS=1;
	dbgt(arg1,seed,args);
	#ifdef QUIET
	DBG=0;
	#endif
	MAIN();
	DBG=1;
	dbgt("gg;wp");
	return 0;
}
constexpr int inf=e9+99;
constexpr ll linf=1LL*e9*e9+99;
#if __cplusplus >= 202002L
constexpr long double U_03C4__ld=2*numbers::pi_v<long double>;
#else
const long double U_03C4__ld=2*acosl(-1);
#endif
#define U_03C4_ ((flt)U_03C4__ld)
constexpr long double U_03B5__ld=1e-8l;
#define U_03B5_ ((flt)U_03B5__ld)
// }}}
using flt=double; //CARE
constexpr int P=e9+7;//998'244'353;

void fail() { cout<<"NO"<<endl; }

using va=valarray<int>;
const va MT=va(0,26);


void _m() {
	int n; cin>>n;
	static string s[100<<10];
	for(int i=1;i<=n;i++) cin>>s[i];

	s[n+1]="";
	map<int,va> prv;
	prv[0]=MT;
	for(int i=n;i>=1;i--) {
		va tot(0,26); for(char c:s[i]) ++tot[c-'a'];
		int p=sz(s[i]);
		map<int,va> nxt;
		for(auto [jj,x]:prv) {
			int j=jj;
			x-=tot*(j/p);
			j%=p;
			if((x<0).max()) return fail();
			if(!nxt.count(j)) nxt[j]=x;
			else if((nxt[j]!=x).max()) return fail();
		}
		nxt[p]=tot;
		va x=MT;
		for(auto [jj,y]:nxt) {
			if((y<x).max()) return fail();
			x=y;
		}
		prv=nxt;
	}

	cout<<"YES"<<endl;
	string z="";
	va y=MT;
	for(auto [jj,x]:prv) {
		x-=y;
		y+=x;
		for(int c=0;c<26;c++) for(;x[c]--;) z+=char('a'+c);
	}
	dbg(z);
	assert(sz(z)==sz(s[1]));
	for(int i=1;i<=n;i++) {
		int p=sz(s[i]);
		for(int j=0;j<p;j++) s[i][j]=z[j%sz(z)];
		z=s[i];
		cout<<z<<endl;
	}
}



void _main() { /* CURSOR START */
	int T; ine(T,5); for(;T--;) _m();
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
2
abc
abcd
4
bbcaa
cabb
acabbbb
a
3
ab
aab
bbaaaaab
3
ab
aab
bbaaaaaa

output:

NO
YES
abbca
abbc
abbcabb
a
YES
ab
aba
abaabaab
NO

result:

ok ok (4 test cases)

Test #2:

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

input:

5
1
ccecddbdbbcbbaded
3
cd
d
d
1
dcedec
2
dcec
cce
8
a
e
a
c
cc
cccccccc
c
b

output:

YES
abbbbbccccdddddee
YES
dc
d
d
YES
ccddee
YES
cced
cce
NO

result:

ok ok (5 test cases)

Test #3:

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

input:

100
147
ababbbaaaaaababbbbbaabaabbbbaaaababbbbababaabbbbaaabbabaaaaaabbbbaabbaaaaaababbbaabbabbaaabbbaabbbabaabbbbaabaabbaa
aaaaabbbbababababbbaaaaaabaaaaabbaabaabaaababbabbabbabbaabbaaabbaabbaabaababaaabbababbbbbaabaaaaabbbbaabbbbbbaaabbbbabaababbbbb
ababbabaababbbbaabbbbaaabbabaabbaaaababbbabbaaab...

output:

NO
YES
baaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbb
ba
bababababababababababababababababababababab
bababababababababababababababab
babababab
bababababbababababb
bababababbabab
baba
bababababababab
b
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
b
bbbbbbbbbbbbbb
bbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbb
bbbbbbbb...

result:

ok ok (100 test cases)

Test #4:

score: 0
Accepted
time: 86ms
memory: 8176kb

input:

100
326
decadadcaaacaaeecaddaeadeadc
aaadedcaaeaaeddddaeaceaddaaaaecccaaeadeaaedaccdddcdddaaaadddacceaaadcadaeeeadeeadccdaacadaaecaedadcaaaecdaddaeaaaeccdedaceaaaacdddcecdcdacddccecaaaeaeedacaeaadaaacdadedae
acaecaaaedcdaceaaddddaaeaddccdaeaadaeedaecdacaadeeaadeceadacdadaccdaaedaddccaceea
ddccacdcea...

output:

NO
YES
ebccdeabb
ebccde
ebccd
ebccdebccdebccdebccd
ebccde
e
eeeeeeeeeeeeeeeee
eeeeeeeeeeee
eeeeeee
eeeeeeeeeeeee
eee
eeeeeeeeeeeeeeee
eeeeeeeeeeeeee
eeeeeeeeeeeeeeeeeeee
eeeeeeeeeee
eeeeeeeeeeeeeeeeeeeee
eeeeeeeeeeeeeeeeeee
eeeeeeeeeeee
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee
eeeeeeeeee
eee...

result:

ok ok (100 test cases)

Test #5:

score: 0
Accepted
time: 76ms
memory: 8404kb

input:

100
1114
mmiceajjcjdemdhf
c
ccccccc
cccccc
cccccccccccccccccccccccccccccccccccccccc
ccccccccc
ccccccccc
ccccccccccccccc
ccccccccccccccccccccccccc
cccccccccc
ccc
ccccccccccc
ccccccccccccccccccccccccccccccc
ccccccccc
cccccc
ccccccccccccccccccccccc
ccccccccccccc
ccc
ccccccccccc
ccccccccc
cccccccccccccc...

output:

NO
NO
YES
acgbacmikmfaaddehiibfjkacaaaaaabbbbbbcccccccccdddddeeeeeeeeeeeeefffffffgggggggghhhhhhiiiiiiiiijjjjjjjjkkkkkkklllllllmmmmm
acgbacmikmfaaddehiibfjkac
acgbacmikmfaaddehiibfjkacacgbacmikmfaaddehiibfjkacacgbacmikmfaaddehiibfjkacacgbacm
acgbacmikmfaaddehiibfjkacacgbacmikmfaaddehiibfjkacacgbacmik...

result:

ok ok (100 test cases)

Test #6:

score: 0
Accepted
time: 95ms
memory: 8180kb

input:

100
512
tecvaycvrbprboqldxlzjmlbfxaseuomtjxenfyoxkmjqkifjpacqytpxmbxleryljfxeoghwfhcnhvimgkvdwjcwatlppmwbbygdbiyzvlrfqjmdnuioulrgmwfkutwgavesanvdzbypveznnvrddujscaekxauxwi
nqmlelkfqrvjbwdlvtbzxkd
kbdqfbqxqqvmkllqltebqmlrnxvxflkzedrmbwknzltfbllqllbwllwqrvkzmrdqlldvnfbkqxbdkewxrzbbndvfqrnfklllxxkvqkjf...

output:

YES
vzxjrblkeqmvnftqbdkdllwaaaaaaaabbbbbbccccccdddddeeeeeeeffffffggggghhhiiiiijjjjjjjkkklllllmmmmmmmnnnnnoooooppppppqqrrrrrsssttttuuuuuuvvvvvvvwwwwwwxxxxxxxxyyyyyyyzzz
vzxjrblkeqmvnftqbdkdllw
vzxjrblkeqmvnftqbdkdllwvzxjrblkeqmvnftqbdkdllwvzxjrblkeqmvnftqbdkdllwvzxjrblkeqmvnftqbdkdllwvzxjrblkeqmvnftq...

result:

ok ok (100 test cases)

Test #7:

score: 0
Accepted
time: 80ms
memory: 7304kb

input:

1000
379
hdiyyp
ihy
hyhyiih
hiyh
iyhhihihhyhy
yhihhyyihhih
h
hhh
h
h
hhhhh
hhhh
hhhhhhhhh
hhhhhhhhhhhhh
hhhhhhhhhhhhhhhhh
hh
hhh
hhhhh
hhhhhhhh
hhhhhhhhhhhhhhhh
hhh
hhhhhhhh
hhhhhhhhh
h
hhh
hhhhhh
hhhh
hh
hhhhhhhhhh
hhhhhhh
hh
hhhhh
hhhhhh
hhhh
h
hh
hh
hh
hh
hhhhhhhhhhhhh
hhhhh
hhhh
hhhhhh
hhhh
h
hh...

output:

YES
hiydpy
hiy
hiyhiyh
hiyh
hiyhhiyhhiyh
hiyhhiyhhiyh
h
hhh
h
h
hhhhh
hhhh
hhhhhhhhh
hhhhhhhhhhhhh
hhhhhhhhhhhhhhhhh
hh
hhh
hhhhh
hhhhhhhh
hhhhhhhhhhhhhhhh
hhh
hhhhhhhh
hhhhhhhhh
h
hhh
hhhhhh
hhhh
hh
hhhhhhhhhh
hhhhhhh
hh
hhhhh
hhhhhh
hhhh
h
hh
hh
hh
hh
hhhhhhhhhhhhh
hhhhh
hhhh
hhhhhh
hhhh
h
hhhhhh
...

result:

ok ok (1000 test cases)

Test #8:

score: 0
Accepted
time: 71ms
memory: 6952kb

input:

10000
21
uiutbnjregblkwbpztgdbmahtlhe
dtulrltbnbtlbggtwmteiwzbejzdlzbtbutiapwhnurumbnutkekbjehanphbhrn
unt
tnnntktntttttnttutnuuuuuunntuuuntununutnntuttunuutttntnuntnuuntuttunnuututuntuttntnunntuntnnuuttutunuunnunuutnuuutnutnutnnntntntunnttntuuttnnuunnnnuuutntn
uttnnnntuuuutututtnttuutuuttnnnnntunnu...

output:

NO
YES
y
y
y
y
y
YES
kabhlmmszgklamrcgo
kabhlmmszgklamrcgokabhlmmszgkl
kabhlmmszgklamrcgokabhlmmszgklkabhlmmszgklamrcgokabhlmmszgklkabhlmmsz
kabhlmmszgklamrcgokabhlmmszgklkabhlmmszgklamrcgokabhlmmszgklkabhlmmszkabhlmmszgklamrcgokabhlmmszgklkabhlmmszgklamrcgokabhlmmszgklkabhlmmszkabhlmmszgklamrcgokab...

result:

ok ok (10000 test cases)

Test #9:

score: 0
Accepted
time: 138ms
memory: 10568kb

input:

10
16467
aldyra
ylaaaddrraldyaaalaaadrydlyyaryrrl
draya
yaaaadddarayrayraayyyraradddr
yyraayrdardraaadraaydadyya
dray
ay
yaayayaayyayaaaayyyaayayyyayayyayyaaayayya
ayayayyyaayyyyaayayayaa
aaayyaayyaaayyayyyyyyaayayaay
yyyyyayyayyyayyayyaayayayayyayayayaaaaaayayaaaaay
yaayay
ayaayayyyayyyayaayaayyyay...

output:

NO
YES
nbjklmphbnoqrswyddehijllllqqsswcdiinooqwbabcginoppqrrrsuwxzccijnsuvx
nbjklmphbnoqrswyddehijllllqqsswcdiinooqwbabcginoppqrrrsuwxz
nbjklmphbnoqrswyddehijllllqqsswcdiinooqwbabcginoppqrrrsuwxznbjklmphbnoqrswyddehijllllqqsswcdiinooqw
nbjklmphbnoqrswyddehijllllqqsswcdiinooqwbabcginoppqrrrsuwxznbjkl...

result:

ok ok (10 test cases)

Test #10:

score: 0
Accepted
time: 85ms
memory: 12024kb

input:

3
32852
zjcsxffjfgqgnvamcemwbswpnxmtxxlecsfpbbaygsvvfhesoexzicbclmctcwhaosjziphqkaechmrguyddlyelzaycvlrffhalklfxlnwkpopijuuusjbwnxqcayjfygjufkpyvnv
zrwxifjqftg
zrgxf
xfggzrfxzr
grffzxxzgffxxzfggfxxfgxfgxzfzzrffxxrrfxxfgrrfzgzzrrgzrfgrzrzfgrrxgrzzgxrgzgx
xrrfrfxzgggxzgfxzrgfrzfzx
grxxfzfgzzgxggzxfzgf...

output:

YES
fzgxrfijqtwaaaaaaabbbbbccccccccccddeeeeeeffffffffgggghhhhhiijjjjjjkkkkllllllllmmmmmnnnnnoooppppppqqrssssssstuuuuuvvvvvvwwwwxxxxxxyyyyyyyzzz
fzgxrfijqtw
fzgxr
fzgxrfzgxr
fzgxrfzgxrfzgxrfzgxrfzgxrfzgxrfzgxrfzgxrfzgxrfzgxrfzgxrfzgxrfzgxrfzgxrfzgxrf
fzgxrfzgxrfzgxrfzgxrfzgxr
fzgxrfzgxrfzgxrfzgxrfzgx...

result:

ok ok (3 test cases)

Test #11:

score: 0
Accepted
time: 164ms
memory: 13036kb

input:

1
100000
mjrbblhjaodzaew
bhdwmabzrloejarj
waaarbwdlobbemzldjrbhjrajejo
mojrjdzwaoearbbdajrjbjleabwhlldr
abjebazdadlobwerbdoablarjjhlrdljrwmjrbje
lohrmrrjrjalaljbzmwobbbdbbdbrarbjejawallraejabddrwajelojlzdjdwlraroejjehdb
edbrlwajjba
bbjaljddbjlbjwderaawljarreb
bjraaewrjbdbdjll
rjdbl
rddjblbdjbrlrjrll...

output:

YES
rljdbabeajwohmz
rljdbabeajwohmzr
rljdbabeajwohmzrrljdbabeajwo
rljdbabeajwohmzrrljdbabeajworljd
rljdbabeajwohmzrrljdbabeajworljdrljdbabe
rljdbabeajwohmzrrljdbabeajworljdrljdbaberljdbabeajwohmzrrljdbabeajworljdrl
rljdbabeajw
rljdbabeajwrljdbabeajwrljdb
rljdbabeajwrljdb
rljdb
rljdbrljdbrljdbrlj
rlj...

result:

ok ok (1 test case)

Test #12:

score: 0
Accepted
time: 30ms
memory: 6904kb

input:

10000
2
oodmvpzyxi
vpooodzmmidixopy
25
iosxruvcl
l
lllllllllllllllll
lll
llllllllll
llll
llllllll
llllllllll
l
ll
lllll
llllllllll
l
lllllllll
llllllllll
l
llllllllllllll
l
l
ll
l
ll
l
llll
l
4
plsftdw
tsw
sttttwsswws
x
7
hbopcjceds
scedhbgccdoccechsjbbahpopd
hcq
jcc
klh
hjcjchh
jichchhcjchj
1
i
7
j...

output:

YES
dimoopvxyz
dimoopvxyzdimoop
YES
lciorsuvx
l
lllllllllllllllll
lll
llllllllll
llll
llllllll
llllllllll
l
ll
lllll
llllllllll
l
lllllllll
llllllllll
l
llllllllllllll
l
l
ll
l
ll
l
llll
l
NO
NO
YES
i
NO
YES
bcccdefggijkklmnnnoppprsttuvwwxyy
NO
YES
cghijkkkllnnpqqrtvwwz
YES
aadellssvw
YES
dy
dyd
d
d...

result:

ok ok (10000 test cases)

Test #13:

score: 0
Accepted
time: 26ms
memory: 7048kb

input:

10000
4
a
a
a
a
1
mqoukqzi
5
d
hhhhrdhhhhhhhh
hh
gh
hbhr
4
zcdufv
fdvuzudvcf
f
f
1
s
12
mi
mimimi
m
mmmmmmm
m
m
m
mm
m
mmm
m
mm
20
g
g
s
g
g
g
g
g
g
g
k
g
k
g
g
g
g
u
g
g
11
f
f
f
f
f
f
f
f
f
f
f
9
gv
v
vvvvvvvv
vvvv
vvvvv
v
vvv
vv
vvvvvv
9
ti
t
tttt
t
ttt
tt
tt
t
tt
7
x
k
d
r
r
w
r
6
nc
cf
c
v
hdcc...

output:

YES
a
a
a
a
YES
ikmoqquz
NO
YES
fduvcz
fduvczfduv
f
f
YES
s
YES
mi
mimimi
m
mmmmmmm
m
m
m
mm
m
mmm
m
mm
NO
YES
f
f
f
f
f
f
f
f
f
f
f
YES
vg
v
vvvvvvvv
vvvv
vvvvv
v
vvv
vv
vvvvvv
YES
ti
t
tttt
t
ttt
tt
tt
t
tt
NO
NO
YES
abbbcccccccccccdeeeefffgghhhiiijjjjjkklllmmmmmmnnnnoooopppppqqrrrrssttttttuuuuuvv...

result:

ok ok (10000 test cases)

Test #14:

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

input:

10000
1
t
8
ecj
ejecjscecjje
cecjejceejc
ecjeceeecjcjcj
cea
oc
ceec
ecbc
34
zevdfbzayddtgja
dea
aaadc
aadaa
daa
a
a
a
x
aa
aaaaaaaa
a
aaa
aa
a
a
ba
aaa
aaaaa
aaaaa
aaa
aaaaaa
aaaaaaaaaaaaaaaa
aaaaaaaaaaaaaa
aaaa
aaa
aa
a
aa
aaa
aaaa
aaaaaaa
aa
aaa
1
xdvwkodeoicwnscdpkhwmxriaudyinlvbniaqhqnldbgtigvra...

output:

YES
t
NO
NO
YES
aaaabbccddddddeefggghhhiiiiiijjkkllmnnnnoooppqqrrssttuvvvwwwxxyyz
YES
erz
erzerz
e
eee
eee
eeeeeeeeeeeeeeeee
eeeeeeeeeeeeeee
eeeeeeeeeeeeeeee
eeeeeeeeeeeeeeeeeeeeeeee
eeeeee
eeeeee
eee
eee
e
NO
NO
YES
u
u
u
u
u
u
u
YES
kiims
kiimskiimskiimskiimskiimsk
kiimskiimskiimskiimski
kiimskiim...

result:

ok ok (10000 test cases)

Test #15:

score: 0
Accepted
time: 64ms
memory: 7048kb

input:

10000
3
aabbabbbbabaaaaabbbaaabaaaaaaa
baabababaabaaabaabbaabaababaaaaaaabaaaaaabbaabbbaaabaaaababaaabbaaaaaaaaababbaaabaaaababaaabbbbaababaaaaaaaaabbaaabbbaabbaaabaaaaaabbabbaaaaabaabbaaabaaabaaabaabaaabbabaabaabbaabaaaababababaabbaababbabbaaaabbabababbbbbaaabaaaabaabbbbbaaabaaaaaaaabbaaabaaabaaaba...

output:

YES
aaaaaaaaaaaaabbbbbbaaaaababbbb
aaaaaaaaaaaaabbbbbbaaaaababbbbaaaaaaaaaaaaabbbbbbaaaaababbbbaaaaaaaaaaaaabbbbbbaaaaababbbbaaaaaaaaaaaaabbbbbbaaaaababbbbaaaaaaaaaaaaabbbbbbaaaaababbbbaaaaaaaaaaaaabbbbbbaaaaababbbbaaaaaaaaaaaaabbbbbbaaaaababbbbaaaaaaaaaaaaabbbbbbaaaaababbbbaaaaaaaaaaaaabbbbbbaaaaab...

result:

ok ok (10000 test cases)

Test #16:

score: 0
Accepted
time: 58ms
memory: 6912kb

input:

10000
5
lzmafakuzucfezeldfgsdytjfomzjcfovbdvmagqfuqpwyrxarcgqks
cuszpkqzglakwledzoruucgeqmrfyfoymxvfvfjagazcjdsqfabfmdt
jkeqogazgzuduffffmkefslrfwuz
lkufefzqrzqkafqoffuwzwfrgljsrfuzsdugkfmdoedzzeuegfeufmkjfugffafk
zfzeugdzjaefukgudamlmuufjlufruzjkdojfkgufeuwukzqwlfaqfuogqezzsfrkkukkfadezfgozfffsfoff...

output:

NO
YES
bbbccefffghhiijjkkklllmmmoooppqqqrrstttuvwwyzaaccccddeeeffikmmmnoopqqrvvwwwxxyyy
bbbccefffghhiijjkkklllmmmoooppqqqrrstttuvwwyz
NO
YES
esaabceehhhhjknrsvvvwwxbb
esaabceehhhhjknrsvvvwwxbbesaabceehhhhjknrsvvvwwxbbesaabceehhhhjknrsvvvwwxbbes
esaabceehhhhjknrsvvvwwxbbesaabceehhhhjknrsvvvwwxbbesaab...

result:

ok ok (10000 test cases)

Test #17:

score: 0
Accepted
time: 299ms
memory: 7036kb

input:

1000
54
aabbbabaabbaaabbababb
abaabbbbbaaabbabbabbbabbaabaa
bbbbbabbbaaaabaabbbbbbbbaabababaaabaaaaabbbbbabbbaaabbaaa
aababbbbabaaabbbbabbbbaabaaa
aaababbbbabaaabababbbbabbaabbbab
aaababbbbbabbababbbabbaaabbaaabbbaabbb
bbaaabaabbabaababbbbbababbaabbbbbabababbaaaababbb
babaaaababaababaaabaaaaaabbbbbb...

output:

YES
babbbaabaababbabbbaaa
babbbaabaababbabbbaaababbbaab
babbbaabaababbabbbaaababbbaabbabbbaabaababbabbbaaababbbaa
babbbaabaababbabbbaaababbbaa
babbbaabaababbabbbaaababbbaababb
babbbaabaababbabbbaaababbbaababbbabbba
babbbaabaababbabbbaaababbbaababbbabbbababbbaabaab
babbbaabaababbabbbaaababbbaababbbab...

result:

ok ok (1000 test cases)

Test #18:

score: 0
Accepted
time: 232ms
memory: 7000kb

input:

1000
26
ayhlojxlxzojvtmgetowruycwvrfjpzjd
yvyoxrurlwdtaegcolmzpvzjtjojfxw
zldlpxyramxfvjjoyzcretvgwjt
lgxpyydjazvvxcojjlzm
xzvyxjladcclxdymvygojpxaljmpgvjzzyzjoj
mjjcxxaxjjjxvjxjadylzzpvdmpvozyzclyyaovgomjlxyplazzxymjyvjlojzydjcycdajlzlxgyzojjzxjvjazjgypxxcglvxmdgcpv
vgcdzoxjaaazvmzygvyjajcxjypjmjyx...

output:

YES
jjxacjyzxpvzlydmgolvefrrttwoouwhj
jjxacjyzxpvzlydmgolvefrrttwoouw
jjxacjyzxpvzlydmgolvefrrttw
jjxacjyzxpvzlydmgolv
jjxacjyzxpvzlydmgolvjjxacjyzxpvzlydmgo
jjxacjyzxpvzlydmgolvjjxacjyzxpvzlydmgojjxacjyzxpvzlydmgolvjjxacjyzxpvzlydmgojjxacjyzxpvzlydmgolvjjxacjyzx
jjxacjyzxpvzlydmgolvjjxacjyzxpvzlydm...

result:

ok ok (1000 test cases)

Test #19:

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

input:

100
2237
baabaaabaaaabbbbaabaaaababaaaaba
aaabaaaaabaaabaaababbbababaaaaaaaabbabbaabb
abaaabbaaaaabbaaabbabaaabab
aaaaaaaaaaabaabaaaabaaabbbbbbababaabaabbaaaababaababbaababaabbabbaaabb
abaababbbbaababaababaaababababaaabbaaaaaaaaaaabababaababbaaaaaabb
abbabaaaaaababaaabbaba
abaaaaaabaaababaabbbbbaaaa...

output:

NO
YES
aaaabbaabbbbbabaaaabaaaabaaaaaaaaaabbbbbbbbbbaaaaaabb
aaaabbaabbbbbabaaaabaaaabaaaaaaaaaabbbbbbbbbb
aaaabbaabbbbbabaaaabaaaabaaaaaaaaaabbbbbbbbbba
aaaabbaabbbbbabaaaabaaaab
aaaabbaabbbbbabaaaabaaaabaaaabbaabbbbbabaa
aaaabbaabbbbbabaaaabaaaabaaaabbaab
aaaabbaabbbbbabaaaabaaaabaaaabbaabaaaabbaa...

result:

ok ok (100 test cases)

Test #20:

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

input:

100
2742
cecabdaaaeeeedceceeccceaeabeccdbaabcbdaadddeeaeadaedcedcbcecabadceebeeadec
ceeacdbaecaecaaacacacdebceaedcb
eaacbacccaceeaccceeeeccaeabeeccabdddabcdcbedaaacaecacaaedcaeba
abecadadcebabaeacdacecca
caaaaebeaaccaadaaddacbbbeacecdbeccaadcabecadaccee
cadacbceaabedacacaceba
eabaaecbdccbaacadaaeecc...

output:

YES
aaeecbabccacccaabaaedddeaccceeeaaaaaaabbbbbcccccccdddddddddeeeeeeeeeeeeeee
aaeecbabccacccaabaaedddeaccceee
aaeecbabccacccaabaaedddeaccceeeaaeecbabccacccaabaaedddeaccceee
aaeecbabccacccaabaaeddde
aaeecbabccacccaabaaedddeaaeecbabccacccaabaaedddea
aaeecbabccacccaabaaedd
aaeecbabccacccaabaaeddaaeecb...

result:

ok ok (100 test cases)

Test #21:

score: 0
Accepted
time: 273ms
memory: 7716kb

input:

100
463
oygvfytmfirgjwwqspymwkpky
ywjskfvwgtwyqmykopgympf
svytqkpfgpmjfomykwyykwftymwpomwqywg
vqgyytmykywjpwmjmfwtwwwptyfmksykommygywfyofoqggwkympksypfvtoykpq
kkfpmqwfotgywwfmkspymwkqjpmpvfqytyomytgwomwwyyy
fpgymswyqjowmyqomyfvwgwkwpyfyktkftymtpqmykwo
ystpkmygoymwkwgotfyvjkywfmpqy
ktfwqpykjgmvpmgwyy...

output:

NO
YES
tpqvnumazibxxszfonpkdkciapabccccdddefffggghijjllmmmnnnooqqrrrsvwxxyyyzzzjmnorraaaaaaaabbbbbbbbcccddddddeeeeeeeffffffffggggggggghhhhhhhiiiiiiiiiiiiijjkkkkklllllllllmmmmmnnnnooooppppppqqqqqrrrrssssssssssstttttuuuuuuuuvvvvvvvvvwwwwxxyyyyyyyzzzzzzzz
tpqvnumazibxxszfonpkdkciapabccccdddefffggghijjl...

result:

ok ok (100 test cases)

Test #22:

score: 0
Accepted
time: 366ms
memory: 10588kb

input:

10
1037
babbabbbabbababbaaaabaaabaabbaabaaabbaabbbaaaab
abbaabaabaaaaabababaaaabbaabbbbbbbbababababbaa
aaaabaaaabbbbbbbbababababbaababaabbbaaabababbaaabaaaaaabbabaabababaabbabab
aaaaabaaaabbabbbabbbbaabbbabbbabbaaababaaababaaba
aaabbaabbbabaaabbaaaaaababababbbbab
baabaabbaabaaaabbabbababbabaabbaab
b...

output:

YES
aabaabbabbbbaabbaabaaaaaabbaaabbbbaaaaaabbbbbba
aabaabbabbbbaabbaabaaaaaabbaaabbbbaaaaaabbbbbb
aabaabbabbbbaabbaabaaaaaabbaaabbbbaaaaaabbbbbbaabaabbabbbbaabbaabaaaaaabba
aabaabbabbbbaabbaabaaaaaabbaaabbbbaaaaaabbbbbbaab
aabaabbabbbbaabbaabaaaaaabbaaabbbba
aabaabbabbbbaabbaabaaaaaabbaaabbbb
aabaa...

result:

ok ok (10 test cases)

Test #23:

score: 0
Accepted
time: 276ms
memory: 9204kb

input:

10
3928
ryebddpjljiukrikjtylkpbwsyicayhhc
yrtckcaijkhutpjrlpiyyppkbwicdklyiydrdbiihlyybkcesjb
tkkdahhldwkpisyypjbyiicerccbjuljpyrkdil
ilypujtjbckirykdhlcybkpi
yjtphkbpkriiykkbjiccucdyll
tybkjirukdiipbjiulciryyyupjklkrypcddkylkckcirhlkibyyjpkdjilkkjkcpkcpyyyjcpklpbiucihtyitiulckbbcjkycpjybklicbplykcb...

output:

YES
ckdilpcyykbyibitrphlkujjadehjrswy
ckdilpcyykbyibitrphlkujjadehjrswyckdilpcyykbyibitrp
ckdilpcyykbyibitrphlkujjadehjrswyckdilp
ckdilpcyykbyibitrphlkujj
ckdilpcyykbyibitrphlkujjck
ckdilpcyykbyibitrphlkujjckckdilpcyykbyibitrphlkujjckckdilpcyykbyibitrphlkujjckckdilpcyykbyibitrphlkujjckckdilpcyykbyib...

result:

ok ok (10 test cases)

Test #24:

score: 0
Accepted
time: 399ms
memory: 13540kb

input:

1
100000
abbaabbaaabbbbbbbbbbbabbabbbbbbaabb
bbabaabbbabbbbabbbbbabbbbbbbabbabababbaabb
ababbababbbaaabbaabbbbaabbbbabbbbbbbbbbbbbbbbbabababaabbabbbbbaaaababbbbabbbbbbbbbabbbbbbbbabbbbbbbbbaabbbbbbbabbababbaabbabbbabbbbabbbabbbaabababbabbbbbababbbabbabbbababbabaaabbbbbbbbbb
babbabaaabbbbbbaabbbbbabb...

output:

YES
abbbbababbbbabbbbbabbbbbbaaaabbbabb
abbbbababbbbabbbbbabbbbbbaaaabbbabbabbbbab
abbbbababbbbabbbbbabbbbbbaaaabbbabbabbbbababbbbababbbbabbbbbabbbbbbaaaabbbabbabbbbababbbbababbbbabbbbbabbbbbbaaaabbbabbabbbbababbbbababbbbabbbbbabbbbbbaaaabbbabbabbbbababbbbababbbbabbbbb
abbbbababbbbabbbbbabbbbbbaaaab...

result:

ok ok (1 test case)

Test #25:

score: 0
Accepted
time: 342ms
memory: 13560kb

input:

1
100000
baababbaababbaaabaabaabbaabbbabbbababaabbaabbbabbaaabbbbbaabaa
bbbaaaababaaaaa
bbaabaaaabbababaabaabababaaaabaaabaaaaaaababa
abaabbaaaababaaba
abbaababbaaabbaaaa
bbbaaaaaaabbabababaaaabaaaa
aabbaaababaaaabaabaaaababbbabaaa
baaaaaaaabbaaaaabaababbbbaabaaabaaaaababa
aaabaaabbbababbbaaaa
babab...

output:

YES
babaaaaaabaabbaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb
babaaaaaabaabba
babaaaaaabaabbababaaaaaabaabbababaaaaaabaabba
babaaaaaabaabbaba
babaaaaaabaabbabab
babaaaaaabaabbababbabaaaaaa
babaaaaaabaabbababbabaaaaaababaa
babaaaaaabaabbababbabaaaaaababaababaaaaaa
babaaaaaabaabbababba
babaaaaaab...

result:

ok ok (1 test case)

Test #26:

score: 0
Accepted
time: 238ms
memory: 13480kb

input:

1
100000
ogecmjpwerfmfmapxnrtjzgymywjxizyfrnomwxhqdeconkmkyw
rojkqgyjnzpxyknaxdpgwzwf
poazxkfkowqrypjkkzxzjqpqngyqwyzfrnjkypgfpjxkowjyzgdwxwnxwzdnpaoynkrggjzngjxawdp
zynynygpqpzdqonwxgfjzprxgpafwqjnraxzkodwjowkykgkjx
rodznjznjqdaxjfwnoqgxyyopxgkkkwgppwkxzyfnzrjwygqap
pakjzpnwgjxrgwzfzokqqkyoydwxn
xk...

output:

NO

result:

ok ok (1 test case)

Test #27:

score: 0
Accepted
time: 318ms
memory: 13752kb

input:

1
100000
ihuppckdjjsbspctuttc
dbpsibscpcjpsjktcpbscpubjstupjcuutkpchsitjpsbbhtdktcccdhkjhcpcutskujpcsptjptssiupjpuuhtipttuicipdhsdjctpdbtjutptppupjtcctthtupcjskpcbcsdsjjputckujcicschhtttkducpcji
hpjiktthjjssbkcdbuucttppscupkjtptcuscppbddicjpcuths
cjbkpuphsctpjuscthbhditipcpdputtcuspsjbtjpthckkcjdttp...

output:

YES
jchpkpbdstucpicsjttu
jchpkpbdstucpicsjttujchpkpbdstucpicsjttujchpkpbdstucpicsjttujchpkpbdstucpicsjttujchpkpbdstucpicsjttujchpkpbdstucpicsjttujchpkpbdstucpicsjttujchpkpbdstucpicsjttujchp
jchpkpbdstucpicsjttujchpkpbdstucpicsjttujchpkpbdstu
jchpkpbdstucpicsjttujchpkpbdstucpicsjttujchpkpbdstujchpkpb...

result:

ok ok (1 test case)

Test #28:

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

input:

1
50000
wpmbctmpdufpqucxpynbxleqtnvnmahajofjenodxqdmtvhjgxkaalzqgvamarwjbjytsgehjgrbqawyhoujwlobjlpyqwl
ojapjpjpcqwxhghmvnenmugwwxtjoeanuleahdbnhotmkalrqmcojwwtljbonuyaxbyqfwgpgqcjnlrqmpaquxlyldatvyspqpjqybdhxvadqjobzfbwuqxahru
xhanwqbwppqryeoahgoxlqmuhmxpwmquyjxwuhcadnjl
uywucuoahwwqxaneyywaxonenml...

output:

NO

result:

ok ok (1 test case)

Test #29:

score: 0
Accepted
time: 298ms
memory: 12724kb

input:

1
50000
muzrveujbtkgwktuzfsuuclmecucfpmkhmlqzbydnagqedywghjhzhtxaow
tbhgfwqluyzzwkbmasuwqphjoalumuwfunuaezbhcuwkkceduufmdztgtbvmzgtjcuqpcrulrzzwtecxhkugzemxmgyyhdmjmyh
bmerqmqhzuftbcajtfxrtymwyzhuuulkdwnqmwywhzevgauhgaxmczwzmulcgybgzudzodusphblekmjkcpuktfw
jfdwbfzawqqrmlckwlmmkcjzudwbhpmggdkuwwtrfpx...

output:

YES
cyumwukymlzxmrabpqdhwgzzbwuftcjmethuzguuacdeefghhjkklnoqstv
cyumwukymlzxmrabpqdhwgzzbwuftcjmethuzguuacdeefghhjkklnoqstvcyumwukymlzxmrabpqdhwgzzbwuftcjmethuzguu
cyumwukymlzxmrabpqdhwgzzbwuftcjmethuzguuacdeefghhjkklnoqstvcyumwukymlzxmrabpqdhwgzzbwuft
cyumwukymlzxmrabpqdhwgzzbwuftcjmethuzguuacdeefg...

result:

ok ok (1 test case)

Test #30:

score: 0
Accepted
time: 73ms
memory: 23652kb

input:

1
100000
tfachkqbvxppacinlodgymgniazuyyozoreheehctbqzrezzvclzzetgtyxdcbqfvegqkqrzwwajisqixlzccdgxqeqcfsqvinarlgefiyxgscymzuyqaknbhotzatiqrcmpwxetjypqbrqovslhnnnifpacwcufuztsbvrfxcvmopnccqlpskhkaqxmrutqnlcvdwrmtfyvtqokwzhwzsajzkviwqdyocyejcuggusnlqgbjeyiofhzgkxsushlnlnwafrkdhdbghipwehuzzgvhkftklqslwj...

output:

YES
maaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

result:

ok ok (1 test case)

Test #31:

score: 0
Accepted
time: 70ms
memory: 25280kb

input:

1
100000
bysvohgnpqvgsdmjhujfbckrqoedifrmfcfafxmvnmcnghjxlejplurbbpmuqjzciezjzjzkkpyfaoxpnaymxoktxcndgqjumjerxlkbsrzviiiawaufrjtunrkfbrjjkeuibhfgpxtwoxowlznpiaypuyucfhakanfhhkxfqhldgphxkmzgcqdbabbiexarsmegtqllxeerrnwzegiqzcbhnuldiigxjttvukbsfyxqytebpylyfpmdusyiohfugynrgvvnnymwrtekniykkebojcnmljsbwmy...

output:

YES
juaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

result:

ok ok (1 test case)

Test #32:

score: 0
Accepted
time: 68ms
memory: 23196kb

input:

1
100000
rrkuldhnwpyskfchbilaycnjdlqtucuxuawqgqrsgygdoqfwuwuyqwfrwumczjzrbceapbumhyyivsmyriojbhigmbwmcpcebixforynxzuajlqkyzhvbxgsfztsdexrhlqelgbajszxbltofwgsxylxzgdsyhclwvmhpritxffbevbidtietbqosejqydkvyungntfuynbflfukzenfgvdfddftwnuyifpahxrkwkpmszbqnmvpehycwnexkteswavtxszupxfzsmnplbylmnomkeryrjrzqlp...

output:

YES
cdfaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

result:

ok ok (1 test case)

Test #33:

score: 0
Accepted
time: 35ms
memory: 14880kb

input:

1
100000
dkupibsvytfhbpiopkcbqhttgqbvwhcxhpsslrjdbpziobtjlnaapmgucenyjqvrnknlnonmprpbjvqucnvglogqphcirlsjwgrbcxxceherupuexdgmzuhltrrekigaaaoizaehsifuvzioukwrjqblkdhlwasslcylzjlodbnaanuchomlmeawyytiqclnmbmdfmqukgegffoliexckahthrpyjdooxhdfobnrrnalquibgamqquvciyuxrvtjlncciowaddxnzmdcpjlhrnizhoyctigzyfp...

output:

NO

result:

ok ok (1 test case)

Test #34:

score: 0
Accepted
time: 122ms
memory: 10960kb

input:

1
100000
tkdjkxwxkjhggjxsnyztngomawuxbhglrpqfrupopxvhgfwwbcvchsoibhdunnhrujjlerjpakfdsovngtknepnvbgktfldzxvujutjykuhrnrvmtgvoznkzoyveqrtenqnevomphdjhoewfctsecybjixonmdrxmdlpxlyroxezbzinrluniaykkbcyhubdyrvewcoijesqohhqsjkccepvjvcapjbrtckeuoysbezinafwndwqcmprdoufoxntcfbjabwwtlfncauyzrmwxdkyrepeujbeucz...

output:

NO

result:

ok ok (1 test case)

Test #35:

score: 0
Accepted
time: 64ms
memory: 16276kb

input:

1
100000
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m...

output:

YES
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
...

result:

ok ok (1 test case)

Test #36:

score: 0
Accepted
time: 58ms
memory: 16032kb

input:

1
100000
uj
ju
uj
ju
ju
uj
uj
uj
uj
uj
uj
uj
uj
uj
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
uj
uj
ju
uj
ju
ju
ju
uj
ju
uj
uj
uj
uj
ju
ju
uj
ju
ju
uj
uj
ju
uj
ju
ju
ju
ju
ju
uj
uj
uj
uj
ju
uj
ju
uj
uj
uj
uj
ju
ju
ju
uj
ju
uj
ju
ju
ju
ju
uj
uj
uj
ju
ju
ju
ju
ju
uj
ju
uj
ju
ju
uj
ju
uj
uj
uj
ju
ju
ju
uj
ju
uj
...

output:

YES
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju
ju...

result:

ok ok (1 test case)

Test #37:

score: 0
Accepted
time: 76ms
memory: 15684kb

input:

1
100000
cfd
fcd
dfc
fcd
dfc
dfc
fdc
fcd
dcf
cdf
cdf
cdf
dcf
dfc
dfc
cdf
dcf
dfc
dfc
cfd
dfc
fdc
cdf
cfd
cfd
fdc
dcf
dfc
fdc
cfd
cfd
cfd
fdc
fcd
dfc
cdf
fdc
dfc
cdf
dcf
cfd
dcf
cdf
fcd
dcf
fcd
cdf
cdf
fcd
dfc
dcf
fdc
fcd
fcd
fdc
fcd
fcd
cdf
dcf
fdc
cdf
fcd
cdf
dfc
dfc
dfc
cfd
cfd
dcf
fcd
fdc
dcf
cfd...

output:

YES
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
cdf
...

result:

ok ok (1 test case)

Test #38:

score: 0
Accepted
time: 107ms
memory: 15296kb

input:

1
100000
sgwqbkkgr
wrksgq
swrg
gwsr
rgwrs
wrsgr
wgrs
swrg
srgwr
swrrrsg
sgwr
grws
rgsw
rwsg
wgsr
gswrr
srgwrrs
sgrw
wrgs
gswr
sgrw
rwrgs
wsgr
rwgrwgrss
sgrwsr
wrrsrgs
gswrrs
rswg
rgsrw
ggrwrwrss
wsgrrsr
gswr
gwrsrsg
ssrggrswrg
srwrg
gwrsr
rrswgr
rwgs
gsrwrs
sgrsrwr
wsgr
swrgsr
rgrws
rgrswr
grswrr
sr...

output:

YES
rsgwkqbgk
rsgwkq
rsgw
rsgw
rsgwr
rsgwr
rsgw
rsgw
rsgwr
rsgwrrs
rsgw
rsgw
rsgw
rsgw
rsgw
rsgwr
rsgwrrs
rsgw
rsgw
rsgw
rsgw
rsgwr
rsgw
rsgwrsgwr
rsgwrs
rsgwrsr
rsgwrs
rsgw
rsgwr
rsgwrrsgw
rsgwrrs
rsgw
rsgwrsg
rsgwrsgrsg
rsgwr
rsgwr
rsgwrr
rsgw
rsgwrs
rsgwrsr
rsgw
rsgwrs
rsgwr
rsgwrr
rsgwrr
rsgwrr
...

result:

ok ok (1 test case)

Test #39:

score: 0
Accepted
time: 147ms
memory: 15020kb

input:

1
100000
zjtjcbrklxtk
jjzcttbl
cjlttzjtjjb
tzbjjt
tbjjt
tjbjtjjt
bjtttj
ttttjbtjbjjt
btjtjt
ttjjtjbjt
jbjttt
jjbtttjtj
jttjtbtj
ttjttjb
tjjttbtjjtjttttttbtbj
tbjjtt
jttbjtt
tjbtttjtj
ttttjtbjjtjtjjtttjttjtbttjtbj
tjttbj
tbtjtj
ttjtjjbt
btjjttjt
btttjj
ttjbbtjjtj
jjbtttjt
tjttjtbtjj
jjbtttt
tjjttbt
t...

output:

YES
tjjbtzclkkrx
tjjbtzcl
tjjbtzcltjj
tjjbtz
tjjbt
tjjbttjj
tjjbtt
tjjbtttjjbtt
tjjbtt
tjjbtttjj
tjjbtt
tjjbtttjj
tjjbtttj
tjjbttt
tjjbttttjjbttttjjbttt
tjjbtt
tjjbttt
tjjbttttj
tjjbttttjtjjbttttjtjjbttttjtj
tjjbtt
tjjbtt
tjjbtttj
tjjbtttj
tjjbtt
tjjbtttjjb
tjjbtttj
tjjbtttjtj
tjjbttt
tjjbttt
tjjbtt...

result:

ok ok (1 test case)

Test #40:

score: 0
Accepted
time: 55ms
memory: 13108kb

input:

1
100000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

YES
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

result:

ok ok (1 test case)

Test #41:

score: 0
Accepted
time: 137ms
memory: 22672kb

input:

1
100000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

YES
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

result:

ok ok (1 test case)

Test #42:

score: 0
Accepted
time: 134ms
memory: 22904kb

input:

1
100000
aabbaaaabaabaabbabbababaabaaabbaabbabbaabbbaababababbbaaabbabaaaabbbaabbbababbaaabbaaaabaabbbabbabbabaaabbbbaabababbbaaababbbbbbbabbbbbaabbabbaabaabaababaabababbabbbabbaabbbbaabaababbbabbaaaabaabaaaababbaaababaabbbaaaabaabbaabbaaababaabababaaaaaabaabaabababaaabaaabbbaaaabaabaabaaaabbbbbabaa...

output:

YES
baabbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

result:

ok ok (1 test case)

Test #43:

score: 0
Accepted
time: 996ms
memory: 13132kb

input:

1
3162
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

YES
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

result:

ok ok (1 test case)

Test #44:

score: 0
Accepted
time: 947ms
memory: 13220kb

input:

1
3162
bbbbabbababaabaabaaabaabaabbbaaaabbbabbabbbaaaaababbbbbbaaaaaabbaaaabaaabaabbbababbbabbaabaababaabbbbbbbbaabbababbaaabbaababbbaaaabbbbbbbbabaaaabaaaababaaababbbbabbbbbbbbbbabbbabbabbbbbabbabababaabbaabaabaaaabbabbbbaabbbabaaabaabbaaaaababbabbbbbbaabbbbbaabbbbabaaaaaaaaabaabbabbbaabaabaaabaaba...

output:

YES
abababaaaaabaabbabbbaaaabbbabbabbbaaabaaaabbbbaabbaaaabaabbaaaaaababbbaaaaabbbbbbbabbbaaabbabbaabbbbbabbbabbbaabaabbbaababbbaaabaaaaababaabaabbaaaabbbabaaaabbbbabbababaababaababbabbaaabbbbbabbabbaaaabbaaababbaabbbaaabaaabaababbbaabbbabbaabbabbbaabbabaabaaababbbababbbbaababbbabaabbbbbaabbaabababa...

result:

ok ok (1 test case)

Test #45:

score: 0
Accepted
time: 953ms
memory: 13388kb

input:

1
3162
nuxkmfvlestahpxpfaprpidolroqeztqakhbkgsaspmfgntzwevlgpwgrjhfdqqqdudhqnjheltstzosigqrvbpxuwmbgmdieihfxcdfooleleoxnmsefqiqtnzqjvovdfdrwijcxkuogocffxlfuejjjdbtwhcnennlytynndnvcbroijlbpbksgpuqvoyiqptuueuuxkmdmfmjdmlkulppcwzbmdauukvpgsptqcunkfhftczygkxhjinaurnilylzvfssitnjntnweqrczhvkmzpqzkyvzxbul...

output:

YES
fznlnvkbxozdqwexgirpqpiiluzqfmsrrxjdjibhuaypszukfjrxpjplcheozuebhgohmglanruldhvegralifrpmpdqalrckzbksbvevcmlivzarcyjifeocmrjalrubdxlkzswmsebrvzpmkwgymreixtavscbaygfdhgzbsgmohavzcpiegovepjvvlqcfoyesarlcegiizqtidraooxieofclpacojcsngwchmemeplfplifofxkueqswsfclitdchqpbdymcxwpbahbilfhkydcougieqhwegdd...

result:

ok ok (1 test case)

Test #46:

score: 0
Accepted
time: 949ms
memory: 12808kb

input:

1
4472
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

YES
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

result:

ok ok (1 test case)

Test #47:

score: 0
Accepted
time: 1000ms
memory: 12744kb

input:

1
4472
ababaababbaabaabaababbabaaabbaaaabbaaabbabbabaabbbbbbabbaabbbabaabaabbaaabaaaabbaabababbaabbbbbbaaabbababaabaabaabbaabbabbaabbabaaabbbbbbbaabbaabbabaabbbaaaabbabbaaabaaabbbbbbbbaaaaaababababaaabaaabbaaaaaaaaabbaaabbabbaabbbbabbbababbbbabaababbbbaaaabaabbbbbabaaabbbabbbbaaabbaaaababaaaabbabaab...

output:

YES
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

result:

ok ok (1 test case)

Test #48:

score: 0
Accepted
time: 961ms
memory: 12704kb

input:

1
4472
ebjvyazjaqkhfirvcnnbupxkcjfsoooulwvdvjfxnyelfcvhmgjmgxvpozhnwwhajfusradoixqfdizjyydatecqxnqzpbaoeboucsjpxwdwtsqhklpecwharpqrwkkvjbmzhnrahxnbykhhrmacremhjcdytpbempsdhvxashnqrnetspfkubirisesvcodkmacihtwutqlfijcvaphjvffmwlgtmdlhiytiusedkltxkvahrfddhjgncgxjmkmwvkysqfjxkomxzxmizvhuxmcpcaxqeomwbkdi...

output:

YES
faaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbcccccccccccccccccccccccccccccccccccccccccccccccccccccccccddddddddddddddddddddddddddddddddddddddddddddeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeffffffffffffffffffffffffffffffffffffffffffffffffffff...

result:

ok ok (1 test case)

Test #49:

score: 0
Accepted
time: 931ms
memory: 12476kb

input:

1
4245
baabbabaaaaaaaabaabbababbbbaaababababbbbbaabbaababbbbaabaaaaabaaabaabaaabbbbabbaabbabbababbbabbabbbbbbabababbbbbbaaaababbaabbaaaababbabbabbbbabaababbaaaaaabbbaababaabaaabbabaaabaaabaabbbabbaaaaaabaabbbabbbaaabababaabbabababaabaaabaabaabaaaaaaabaabaabbaaaabaaabaabaabaaaaabbabaaaaabaabbaaababbb...

output:

YES
bbaababaaabababbbabbbbbabaaaababababbaababbaaabbabbbababaaaababbbbabbbababbaaaababbbaabaababbabbbaaaabbabbbabbaaaababababaabbbbbbaaababaabaaababaabababbbababbbbabbabaabaaabaaabaaababababaaabbbaaaaabaabbbbbbbababbabababbaabaababaabbbbaaababaabbaaabaabaabbbbaaabababbbaabaaabaaaabaaaaaabaaabaaaabba...

result:

ok ok (1 test case)

Test #50:

score: 0
Accepted
time: 982ms
memory: 12724kb

input:

1
3501
abbbabababaaabbbbbbbaaababaabbbaaaaabaabbababbabaabaaaaaababbbbbbaaaaaaabbabababaabaaabbabbbbbbaabababaabbbaaaaaabaaabbaaaabbbabaabbababbbaaaaaabbabaababbbabababbabaabbbaabababaaaaaaaaaaaabbbbbbabbabbabbbbaaaaaabababbabbbbaaababaabaaaaabbaabaabbbabaaabbbbaaaaaaabbbabaaaaabaabbaaababbbbabbabaa...

output:

YES
babbabbbabaaabbabababbabbaabbabbbbbaabbbaaaabbaabaabaaaabbbbbbaabbaaaababbbabbabaaaaababbaabbabbaabbbabbbbbbaabbbbabbbaaaabbbbbbbbbbbababbabaaabbbabaaababbbabaaaabbaabbabbbaabaaaaaaabaabaaaaabbbbaaabaabbaabaabbabbaaababbbaaababaaaabaaabbbbbbbabaabbbbaaaabbbbabbaaaababaaaaaaaabbababbbabbabaaabaaa...

result:

ok ok (1 test case)

Test #51:

score: 0
Accepted
time: 942ms
memory: 12912kb

input:

1
3266
aaabbaabbabbabaababbbabbbbbbabbbbbbbbbbbbabbbaaaabababbaaabbababbaaababbbbbbaaabbaabbaaaaaaaaababbbbaaabbbbaaabbabbbbbabaaabbabbbbbbaababbbababbababbbbbabbabbbbabbabbaaabaaabbbaabbbbaaabbbbaabbbbabababababbabbbaabbbbaababbaaababbbbaaaabaaaabaaaaaaabbaaabaaaabbaababbbaaaabbabbaaaabababaabababa...

output:

YES
bbbabbaaaabaabbbbbbabaababbbbababaaaaabaabbbaabaababaabababaabbaaabbabbbbbbbaababbaaabababaabbbbaabbbbabbabbabaabaaabbaabbbaaaabbbbbababaabbabbaaabaabbbaabaabbaabbabbbaabbbbabaabababbaaabbabbababbaaaabaaaaaabbaabbabaabaaaaabaabbaabbabbbabaabbbbbbaaabbbbbbaabababbabbbabaababbbbaaaaababaababbaabaa...

result:

ok ok (1 test case)

Test #52:

score: 0
Accepted
time: 970ms
memory: 13276kb

input:

1
3182
bbaabbabbbaabbbabbabaabbaabaababbabbbabaabababbbbbbaaaabaabababbabbbaabbbbabbaabababaaabaaaaaabbbaaaaabababaaaabaaabbbaabaabaaaaabaaababbbbabaaaabbbbaaabbbbaaabaabbababbbaababaaaaabbabababbabaabaaaababbabaaaabbabababaaabbbbbbbababbbaaaabbbabaabbbbbaaababbabbbbbbbbbaabbaabbabbbbbaaaabbaaabbbaa...

output:

YES
abaabaabababbbaabbaaaaaabbbabbabaaaabbabbbaaababaabbababababbbabaaaaabbbaaabbabbababbaaaabbbbbaaabaabaaabaaaabbbaabaabbbbaabaaaaabaababbaaaabbbbabaabaaaaababbbbababaaaaaaabbaabbbaaabbbaabaaaaaababbbbbabaaaaabbbabaababbabbbaaabbbabaaaabababbabbbbbabbbbbbbbbbbabbbbbabbbaaabbbbaababaabbbbbbbbbbbbba...

result:

ok ok (1 test case)

Test #53:

score: 0
Accepted
time: 25ms
memory: 11976kb

input:

1
3114
dqtpwgqrbmryzxhxhhvkgfxkahfoklpjybeyargraoznegtxjf
towkjgqkhtrkfyxqxygafjhpprorbvadzymebjhhfeglxgznxra
knexjjrzkayothdbfawovlhytzgegjphghxfrayrbxfqqkrpjgmx
jxaggxxaqejhnrrdvtmrlhhzozbkyjegryqabtwfpohjypxjfkgkf
ktyqxpylexbkrerhxjongywdzrxhrfzjvojjaabpjghhmfgtqkfagj
bzrgrqwfnkkpggxjxyjajlkbypve...

output:

YES
jaaabbdeefffgggghhhhjkkklmnooppqqrrrrttvwxxxxyyyzz
jaaabbdeefffgggghhhhjkkklmnooppqqrrrrttvwxxxxyyyzzj
jaaabbdeefffgggghhhhjkkklmnooppqqrrrrttvwxxxxyyyzzjj
jaaabbdeefffgggghhhhjkkklmnooppqqrrrrttvwxxxxyyyzzjjj
jaaabbdeefffgggghhhhjkkklmnooppqqrrrrttvwxxxxyyyzzjjjj
jaaabbdeefffgggghhhhjkkklmnoopp...

result:

ok ok (1 test case)

Test #54:

score: 0
Accepted
time: 28ms
memory: 11860kb

input:

1
3162
a
aa
aaa
aaaa
aaaaa
aaaaaa
aaaaaaa
aaaaaaaa
aaaaaaaaa
aaaaaaaaaa
aaaaaaaaaaa
aaaaaaaaaaaa
aaaaaaaaaaaaa
aaaaaaaaaaaaaa
aaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaa...

output:

YES
a
aa
aaa
aaaa
aaaaa
aaaaaa
aaaaaaa
aaaaaaaa
aaaaaaaaa
aaaaaaaaaa
aaaaaaaaaaa
aaaaaaaaaaaa
aaaaaaaaaaaaa
aaaaaaaaaaaaaa
aaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaa...

result:

ok ok (1 test case)

Test #55:

score: 0
Accepted
time: 32ms
memory: 11936kb

input:

1
3161
sl
lsl
slll
llsll
lsllll
lllslll
llllllsl
llsllllll
lsllllllll
lllllslllll
lllsllllllll
lllllslllllll
llllllllllllls
llllllllsllllll
lllllllllllsllll
lllllllllllllllls
lllllllsllllllllll
lllllslllllllllllll
slllllllllllllllllll
lllllllslllllllllllll
slllllllllllllllllllll
slllllllllllllllllll...

output:

YES
ls
lsl
lsll
lslll
lsllll
lslllll
lsllllll
lslllllll
lsllllllll
lslllllllll
lsllllllllll
lslllllllllll
lsllllllllllll
lslllllllllllll
lsllllllllllllll
lslllllllllllllll
lsllllllllllllllll
lslllllllllllllllll
lsllllllllllllllllll
lslllllllllllllllllll
lsllllllllllllllllllll
lslllllllllllllllllllll...

result:

ok ok (1 test case)

Test #56:

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

input:

1
3160
tmh
mhth
hthhm
hhhhmt
hhthhhm
mhhthhhh
hhhmhhhth
hhhthhhhmh
hhhhhthhhmh
hhhhhhmhhhht
thhhhmhhhhhhh
hhhhmhthhhhhhh
hhthhhhhhhhmhhh
hhhhhhhhhhhhmhht
hmhhhhhhthhhhhhhh
hhhmhhhhhhhhhhhthh
hhmhhhhhthhhhhhhhhh
hhhhhhhmhhhhhhthhhhh
hhhhhhhhhhmhhthhhhhhh
hhhhtmhhhhhhhhhhhhhhhh
hhhhmhhhhhhhhhhhhhhhthh...

output:

YES
hmt
hmth
hmthh
hmthhh
hmthhhh
hmthhhhh
hmthhhhhh
hmthhhhhhh
hmthhhhhhhh
hmthhhhhhhhh
hmthhhhhhhhhh
hmthhhhhhhhhhh
hmthhhhhhhhhhhh
hmthhhhhhhhhhhhh
hmthhhhhhhhhhhhhh
hmthhhhhhhhhhhhhhh
hmthhhhhhhhhhhhhhhh
hmthhhhhhhhhhhhhhhhh
hmthhhhhhhhhhhhhhhhhh
hmthhhhhhhhhhhhhhhhhhh
hmthhhhhhhhhhhhhhhhhhhh
hm...

result:

ok ok (1 test case)

Test #57:

score: 0
Accepted
time: 28ms
memory: 11980kb

input:

1
3114
qzvpdpadbydbwtinrhdpqzirdcvyeryggcgvxdxwsekdtiquzm
kqtvmzgcrxsdvpbvgrgeypzicedhydbiwazxpyirzndwdddutqq
zzxrihucybvtgvptdixgdgvzecrdpdddynzsdrmqqykbawqpzewi
tdptvwzeschyzcrziypizrgvreqqkzxddwbpmngddqvbadyzxiudg
iqgcqidmbrepqizdytdugvzbyatzdpgevdcdxrvxkdwnpzzswhzyrz
gddirbwuiydzernqamqdpycgqxtd...

output:

YES
zabbccdddddddeeggghiiikmnpppqqqrrrsttuvvvwwxxyyyzz
zabbccdddddddeeggghiiikmnpppqqqrrrsttuvvvwwxxyyyzzz
zabbccdddddddeeggghiiikmnpppqqqrrrsttuvvvwwxxyyyzzzz
zabbccdddddddeeggghiiikmnpppqqqrrrsttuvvvwwxxyyyzzzzz
zabbccdddddddeeggghiiikmnpppqqqrrrsttuvvvwwxxyyyzzzzzz
zabbccdddddddeeggghiiikmnpppqqq...

result:

ok ok (1 test case)

Test #58:

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

input:

1
2702
mxzrvoigikocbftgdijbvzqbkzhyydmqkyybrveuhbujiyjotmsekzxhwximyxunmkeinompecldkudepqcobaahquotkxbhwuonaisauzhrujslcssvuilfxbdgdqxrbammvklwinzzixqztrifpszorvvihcxthcmshpuqjvexrngdgeouhxfikjfonytbxmnqflqmmaqirjmnkvvsxcpiejebtjhrkvkoofslqtgwrcszrchcspigupkchuanrjjlnqkjvhlgijszghegqnteifsesypeyrctt...

output:

YES
paaaaaaaaaaaaabbbbbbbbbbbbbbbccccccccccccccccccccccdddddddddddddeeeeeeeeeeeeeeeeeeeffffffffffffffffgggggggggggggggggggghhhhhhhhhhhhhhhhhhhhhhhhhhhiiiiiiiiiiiiiiiiiiiiiiiiijjjjjjjjjjjjjjjjjjjjjjkkkkkkkkkkkkkkkkkkkkkkkllllllllllllllllmmmmmmmmmmmmmmmmmmmmmnnnnnnnnnnnnnnnnnnnooooooooooooooooooooooop...

result:

ok ok (1 test case)

Test #59:

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

input:

1
917
fzibwivwklqwhmceqbrcufokodwqockrbumzufacjbxvcrffazgyaklqadbsntouijulxncpmouvxtfrzynwtwouopromvdsxvcmsupmidmoteyzaggmofqoqdxdqugyqfbaupbdnhljmxatrjexuyoyfuxtdcehhpgvyyrcnqisxpmhzgtwuzabyejijcegfzryhchzedabdlhfxvmlnarbwfyacpyhjbymsjsekgipbquoslikbcuqdjlxiupelsvkneplbyamzjfskkuallobyvqhnnfkubxmky...

output:

YES
gaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbccccccccccccccccccccccccccccccccccccccccccddddddddddddddddddddddddddddddddeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeefffffffffffffffffffffffffffffffffffgggggggggggggggggggggggggggggggghhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhiiiiiiiiiiiiii...

result:

ok ok (1 test case)

Test #60:

score: 0
Accepted
time: 19ms
memory: 12700kb

input:

1
489
phavtxxkgqvzvczpbtlrrjfntdrairsofbuugjvhmwdeegubzxjusondgypiutykvhocbbglqvthqhmimkllmxxvfkjrcqbndwfocgrkkiazoxqeadpadtjmkzugvivrdhyzimkypgqeufbqazkxlqkjilrutfrxfilhyczthdqkwyaacvwksmzcaeiwzodmhyxjzykmbspzpqcbukilmacwlyollvytifwaaujuyyazciwyycccwbshvmcxyrpebvzjzkbcmllochvttbukizrtauroifguaivphd...

output:

YES
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbccccccccccccccccccccccccccccccccccccccccccdddddddddddddddddddddddddddddddddddddddeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeffffffffffffffffffffffffffffffffffffffffffffffffgggggggggggggggggggggggggggggggggggghhhhh...

result:

ok ok (1 test case)

Extra Test:

score: 0
Extra Test Passed