1.

Define a function progression(arr) that takes a nonempty array of integers arr and returns
True if the integers in arr form an arithmetic progression: that is, arr is of the form [a, a+d,
a+2d, …, a+kd].

progression([3])

True

progression([7,3,-1,-5])

True

progression([3,5,7,9,10])

False

----------------------------------------------------------------------------------------------------------------

2. Write a function squareprime(L) that takes a nonempty array of integers and returns True if
the elements of L alternate between perfect squares and prime numbers, and returns False
otherwise. Note that the alternating sequence of squares and primes may begin with a
square or with a prime.

Here are some examples to show how your function should work.

primesquare([4])

True

primesquare([4,5,16,101,64])

True

primesquare([5,16,101,36,27])

False

---------------------------------------------------------------------------------------------------------------------------

3. A two dimensional matrix can be represented row-wise, as a list of lists: each inner list
represents one row of the matrix. For instance, the matrix

1 2 3

4 5 6

7 8 9

would be represented as {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}.

A horizontal flip reflects each row. For instance, if we flip the previous matrix horizontally, we get

3 2 1

6 5 4

9 8 7

which would be represented as {{3, 2, 1}, {6, 5, 4}, {9, 8, 7}}.

9 8 7

6 5 4

3 2 1

which would be represented as {{9, 8, 7}, {6, 5, 4}, {3, 2, 1}}.

Write a function matrixflip(m,d) that takes as input a two dimensional matrix m and a direction d,
where d is either 'h' or 'v'. If d == 'h', the function should return the matrix flipped horizontally. If d
== 'v', the function should retun the matrix flipped vertically. For any other value of d, the function
should return m unchanged. In all cases, the argument m should remain undisturbed by the function.

Here are some examples to show how your function should work. You may assume that the input to
the function is always a non-empty matrix.

myl = [[1,2],[3,4]]

myl

[[1, 2], [3, 4]]

matrixflip(myl,'h')

[[2, 1], [4, 3]]

myl

[[1, 2], [3, 4]]

matrixflip(myl,'v')

[[3, 4], [1, 2]]

myl

[[1, 2], [3, 4]]

-----------------------------------------------------------------------------------------------------------------------------------

Test Case 1

progression([3])

True

Test Case 2

progression([7,3,-1,-5])
True

Test Case 3

progression([3,5,7,9,10])

False

Test Case 4

primesquare([4])

True

Test Case 5

primesquare([4,5,16,101,64])

True

Test Case 6

primesquare([5,16,101,36,27])

False

Test Case 7

matrixflip([[1,2],[3,4]],'h')

[[2, 1], [4, 3]]

Test Case 8

matrixflip([[1,2],[3,4]],'v')

[[3, 4], [1, 2]]

Test Case 9

progression([31,31])

True

Test Case 10

progression([3,5,7,9,10])

False

Test Case 11

progression([23,21,19,17,15,13,11,9,7,5,3,1,-1])

True

Test Case 12

progression([23,21,19,17,15,13,11,9,7,5,3,1,-2])

False
Test Case 13

primesquare([1,4,7])

False

Test Case 14

primesquare([1,5,16,17,25])

True

Test Case 15

primesquare([4,5,16,101])

True

Test Case 16

primesquare([5,16,101,36,27])

False

Test Case 17

matrixflip([[1,2,3],[4,5,6],[7,8,9]],'h')

[[3, 2, 1], [6, 5, 4], [9, 8, 7]]

Test Case 18

matrixflip([[1,2,3],[4,5,6],[7,8,9]],'v')

[[7, 8, 9], [4, 5, 6], [1, 2, 3]]

Test Case 19

matrixflip([[1,2,3]],'h')

[[3, 2, 1]]

Test Case 20

matrixflip([[1,2,3]],'v')

[[1, 2, 3]]

--------------------------------------------------------------------------------------------------------------------------------------
-----------

4. A palindrome is a word that equals its reverse. Here are some examples of palindromes:
malayalam, gag, appa, amma.
We consider any sequence consisting of the letters of the English alphabet to be a word. So
axxb,abbba and bbbccddx are words for our purpose. And aaabbaaa, abbba and bbb are examples of
palindromes.

By a subword of a word, we mean a contiguous subsequence of the word. For example the subwords
of the word abbba are a, b, ab, bb, ba, abb, bbb, bba, abbb, bbba and abbba.

In this task you will given a word and you must find the longest subword of this word that is also a
palindrome.

For example if the given word is abbba then the answer is abbba. If the given word is abcbcabbacba
then the answer is bcabbacb.

Solution hint

Any subword of w that is a palindrome is also a subword when w is reversed.

Input format

The first line of the input contains a single integer N indicating the length of the word. The following
line contains a single word of length N, made up of the letters a,b,…, z.

Output format

The first line of the output must contain a single integer indicating the length of the longest subword
of the given word that is a palindrome. The second line must contain a subword that is a palindrome
and which of maximum length. If there is more than one subword palindrome of maximum length,
print the one that is lexicographically smallest (i.e., smallest in dictionary order).

Test Data:

You may assume that 1 ≤ N ≤ 5000. You may further assume that in 30% of the inputs 1 ≤ N ≤ 300.

Example:

We illustrate the input and output format using the above examples:

Sample Input 1:

5
abbba

Sample Output 1:

abbba

Sample Input 2:

12

abcbcabbacba

Sample Output 2:

bcabbacb

Sample Test Cases

Input Output

Test Case 1

abbba

abbba

Test Case 2

12

abcbcabbacba

bcabbacb

Test Case 3

12

abcbcabbacba

bcabbacb

Test Case 4

50

tnautwzhfcsqesmrayxqknytkktynkqxyarmseqscfhzwtuant

50
tnautwzhfcsqesmrayxqknytkktynkqxyarmseqscfhzwtuant

Test Case 5

280

ofntcsgzvdfzqlvuipipydmzpsgvdwxrdmlfetebwjdowylgotvowhnlavifrhwwuhbadhczqhqofbwvwrmubb
hdxpiqwensoottwxuoekflnbjjvvdywkbtblkyrzqhnlalkvcqfjcvklehikfewiayvkynjquyevmoomveyuqjnykv
yaiqqhxzjslwztglakjjkhgwhthaoieluudmbalmvwiwrqhsbqdnajmjdvjtdpgzkjlllwyiviemznecejrgtdrybbte
qbgakroxqmgl

30

iayvkynjquyevmoomveyuqjnykvyai

Test Case 6

800

tfbkfefsghlrnpiqurtxisosaizbhnkcsmpxquszcfsrvahprcpbvdtxlvyuilzaxoapisqmzjdujnmdrbemgaktvkodv
pfudfmnzcablfvxujcmkgaqimmdxaiuporuvdhxfjytpvqlfuxpaailmuqlwzgnpxhkcohjyhcpducioczrchcods
aztioihvtjkcskkxbprfxihwzjgdylxalribzrxuajxuvjryaldzvlxuudzupwucpedpvclxlkugvnevykutvsprxqmopiq
epwvmahmmrguntbiulfpixhzuxljmwbtlzoxavjoprkcllmfyrwgqdgnbtwppziabzadultldltludazbaizppwtbn
gdqgwryfmllckrpojvaxozltbwmjlxuzhdnorcvpvtymxgzazxppyarzzrevdxhgbwwsytjumjijphlpedgedxeerk
zwigcjfaddtozhahtpoeguhozmofqfpsbzafkffpjaeijescvgjedssefglxlcpocstmxaeicitmolqltzpwuiabonycqq
quimghmkqpujdkutypvnmpxoqocqqugioquwyjhqadbdqxwomtdyibpyptphnxrbqmxqxggxmjacgysssvt
ayibpbswqrqrhcqxbxfyloynwyhpqeitfswuvotlhjepnuoorwmcmmrjkaydfiymcugxkzkrkoixixncvzghnyqa
aqfhydtcxazjblaozlnikbmfcsmqsfstvxawawyzyaiblkpnxdxhgjoibbauispfrrbtncslccnppe

101

hzuxljmwbtlzoxavjoprkcllmfyrwgqdgnbtwppziabzadultldltludazbaizppwtbngdqgwryfmllckrpojvaxozlt
bwmjlxuzh

Test Case 7

1500

hiuuedvipfzkkreondlpchyzwvoyvblclfyriuzabakorrcgunywwyyutouopfqckrttnuvqufeoyiwtvurttromfkd
wqvyamtvznqqkyuyydwratlwmcmakwdgmzhpnckpqdfadbabgyvjrghfktiupndemmtcofrgkyipzktijotcw
aigtsdkfiosujwkrnrdlztmkmuvcpxyphgizjtfrjznvvymkrrvqmjcygxcvxalgjtiuonoaobvlbjxsasjnbnnhnqdks
qsdjayapmafnxqpgnjihuxlinuvdzhxpzbbczbrldxacpridbsmvqzffuaivjhnlkonlreywbzyrsiwvakrskwzgzhdir
qtdggpxnnvqothhdfcgqvacuakvjnfagzemhtkwihnxbwgeckkuilyclizwxexdddsnyelglyfovltzyftgstkfdjcanb
gteyicctkpsqepdzobejhzctgfckhqlpjrnrvrmghgynvbmlfquoryiydkkncwcnnsgljtrszrfxuribkfqddadjkowpk
yczsjkcedwfwecrxnshsklxkqgxeemqfqqxbcbhiyneerxbgsjacwypmgmtnajsszrwetdmtssxkqyskjtmftbub
pnoryimaaietlsmeklqcjkmtdzaycuaujqnizzkbhouvgizstrvedhxhiyhnujjgcwqdwaefoaawibodslhwtffdfoq
zyzhcyxfuxjznjcjtdawyldwgkbkrrcrreatcyyyvhzlqbujfwhdinzqzccrvfknjkgliflgokrhonstkayupzkodnfyupl
dcuqkbbspnjybxrwjtwdivpwaeczytmdvgtijwazmmxplqmujizrgqogvsftnuzlauvkrvlfjkuubiqmrpexgufdo
nwdhxqjslvljgqstknwtfkmvoldkqgadegmcwwuirfravlvharcgbqbsbgeumhzqnmslkotbtmdqyyayreevvhn
yntubcusrimdsbyvwlzplxplptskozzppujqxdkonztfcsdyfcnqzedqyvcovddmypcxupniohpqbsogueywkbm
kxrzuuegutktobhypqnfrgwxccvymynxvgypaexxakqqlzobpbigjgfoicmxbbwyhuokanjazzqlzeooiwxtdehn
hwkixgghcwtdmcfldwyccmtmlqgqunddlqnlywsbsnggplssjsxmfqasigiewnkhfxsetmfoznuqaolkhiyoaygk
fqqdfaklyfpttwhvlcllsyvzitpisxuznlevnoonvelnzuxsiptizvysllclvhwttpfylkafdqqfkgyaoyihkloaqunzofmtes
xfhknweigisaqfmxsjsslpggnsbswylnqlddnuqggnvxhpvomgsxrlwpmgiepcbldrwhmmyuzvrgmoxyurwne
uctanxrryfvpbebpcvpyoxkcwjyohmsdolfdizvjeqyhwcxzzozollsi

200

gqunddlqnlywsbsnggplssjsxmfqasigiewnkhfxsetmfoznuqaolkhiyoaygkfqqdfaklyfpttwhvlcllsyvzitpisxuz
nlevnoonvelnzuxsiptizvysllclvhwttpfylkafdqqfkgyaoyihkloaqunzofmtesxfhknweigisaqfmxsjsslpggnsbs
wylnqlddnuqg

Test Case 8

2000

jnrofbluttxmxhgesbyjhhwdkmyppnhybapgeacxwblvjrbbvzmcjkitygkptspwueeyhjvfkhavacyxbkamwkfu
qqjlkbkefodoxatkjwfkyehbqjqnvvhlntzxujebzhqzjjjthodhumjlyzytwhhkcihwtlasuqtebcxjtcqpqbaqcakzi
tlkbujuijocziicmhnhlexehxukyglizyscsdwamnfnxpsjxfrklqotnjfnpsvrqqtktslifsxehpngvgtgwhbmsgzkaxb
spwdioosviqzrfpyaxrjwakittjftiioxerivhaspqugylgaizjeawovraamiiagorqlyqepjywjjejtevaerobkqbwzlxhb
qxnppreyrchchtvlovrhmsrcvndgmgdnvcrsmhrvolvthchcryerppnxqbhxlzwbqkboreavetjejjwyjpeqylqro
gaiimaarvowaejziaglyguqpsahvirexoiitfjttikawjrxaypfrzqivsooidwpsbxakzgsmbhwgtgvgnphexsfilstktqq
rvspnfjntoqlkrfxjspxnfnmawdscsyzilgykuxhexelhkjdjwszpyzidjkkcixsfozrgqwbfzjsmsvvrpwgnypqhbcljzd
ppcixseazgjrsempvdodtmujtwoehnjwflfcflderoylumbpqrvjdpuynievyntdyyhfmklfbjrvwunmlivqzropas
kahdfhemmqzxxahovfiirvsolufbjhvtjcyolcbxuaxsagixltieoaucubddlzyudxjpbmoyolqqtangtvkiyemsipyt
qynuvwjxkzxylnogpcnjzztxefsmuqflouhmtqldpiecxslmwyxyxqvdvnrsfydwtmkmevrvfvycqlqojomiekocz
fufgzdblnppkgkpektuvjkgzxrehfigmcnsbqtofifrrpgvczrzlbikazqhgyqsadndwitdtyvkqbhudatqddaectnkr
dfujszhatkttffjjmdoozescgwhzlrrrwnaqmhrhtmbbukmiqaxpgprmnymysfpqsrheaaouopxibjrrlqgrfadua
ruuwmlqdsxgslcgazrbiittybmfdpbejvyfhlwndttxgveguvjefezfglmlcnrlistsdrfhmyesvkarhjvoowtwjhhluzz
fruxuncdzcktzutqcelssjmqstyfqzgvsauonyuoaejzyercjevdnjufeumwttrntnbjlvznbjoanfeyjbcwmwdrsqnl
lhaeudpibpvcakeppjozmsxzodqivfvgovmlyctztocvagkqraresqditvqoclurijehlxignmdovngmqzsipxtlujbxx
yqfhuoutxcglfwgsevkdptvnmihxjgwjwcqssmlroudtsloziyeytbnhjwfvddebhxuajhradwtyijxsibqbddjoaql
fvqgdpcdakwcpvwpdhmxpqotvtejtwxarphwejzgvyjnthcyorvghlzcffnabmbubkrftsorsxelgiluzjagubkzga
cjmfgqpxvkrlbkkhxqqjlrsnaorkqxmsjbxproooyhacrkjrdbcqtwdvkufauuufvtwohmcgteinrteuxgkscpnom
uriolnlhjbovewqkgdbajxzpjrtzgklabtroievtgkqmggwpmarvxqnhjiipsvrtqkkypftxrjjyrhpdhgbhwoqfyywr
tpmjawjrecovnzvegkkqqlxmbntbnrsghhrjfacjesfrravznhpdumqvblzodrwmanxgpbrttymmbklordrmpjjt
vihaceoctnkjocejcrxdbkrunlgfusyrchtelhjhwvqkzwvcnufqfzluktzenzwqhrwuzhbvdticqfefamwhljbvedbs
czklrggsqjptdxxvfeahqyodjpaosbixbsisaqmqcbjfbhcglcndddgmsganjimmcwgdpsvruhyvq

401

hlexehxukyglizyscsdwamnfnxpsjxfrklqotnjfnpsvrqqtktslifsxehpngvgtgwhbmsgzkaxbspwdioosviqzrfpya
xrjwakittjftiioxerivhaspqugylgaizjeawovraamiiagorqlyqepjywjjejtevaerobkqbwzlxhbqxnppreyrchchtvl
ovrhmsrcvndgmgdnvcrsmhrvolvthchcryerppnxqbhxlzwbqkboreavetjejjwyjpeqylqrogaiimaarvowaejzia
glyguqpsahvirexoiitfjttikawjrxaypfrzqivsooidwpsbxakzgsmbhwgtgvgnphexsfilstktqqrvspnfjntoqlkrfxjsp
xnfnmawdscsyzilgykuxhexelh

Test Case 9

1000

qfqnvhtczmegaalgozmlgvbkvxvjbisupjhmsbotpuzrxmxlnlytjaggzbpblkxcteonhegyafpxtokgcjallgtkjinws
kynroaasgzunqsihcpjnrwazplkzagslehesiemqfggwaofffouymvxbihaiputtcznmebcjikhkzmpgckfofernosx
dotzqsmewqhiytpkseabgkixrmogcidgzwfprtunjdxjwnurtusbgcyzopfrzkzyjeoazkpjpnuncogvkawscxrtoy
knjlmupcuqojzfwwsykzvxbupetjxhhjusugmligbysddozwplxmkaiaebldisodnilzvwixuacyqdwhqvwbveda
gofoguttcfvabdxvfbvxerfwmbxifaknqpczjvuoapodunzzowxuoeqahqkoqucjmeivbcjeszhomiocfnwttpva
fiqxcsgqyomatxelznzlwpobemwzdtbibsigkqwlhklairljgmucekfkzbkcvlnydveqnbbulouvhhenubsanxkmb
upyiewlzbddbzlweiypubmkxnasbunehhvuolubbnqevdynlvckbzkfkecumgjlrialkhlwqkgisbibtdzwmebop
wlznzlextamoyqgscxqifavpttwnfcoimohzsejcbviemjcuqokqhaqeouxwozznudopaouvjzcpqnkafixbmwfr
exvbfvxdbavfcttugofogadevbwvqhwdqycauxiwvzlindosidlbeaiakmxlpwzoddsybgilmgusujhhxjteoegjru
dpdlvthwlhkkrylonjwrijsjnhpvqisvxvgvontbwdmoexetjalrjfcyotugboczjkwaapbwvnmznqswsfpclrcbkyi
nmmowwkyyabxvpluecmausryfidgubqhocwmbgkbilydckxgomikgblnjotfpmpdqnrtvdvepvhthhcvvmib
otozhjhwxwcojthexeko

500

etjxhhjusugmligbysddozwplxmkaiaebldisodnilzvwixuacyqdwhqvwbvedagofoguttcfvabdxvfbvxerfwmb
xifaknqpczjvuoapodunzzowxuoeqahqkoqucjmeivbcjeszhomiocfnwttpvafiqxcsgqyomatxelznzlwpobem
wzdtbibsigkqwlhklairljgmucekfkzbkcvlnydveqnbbulouvhhenubsanxkmbupyiewlzbddbzlweiypubmkxn
asbunehhvuolubbnqevdynlvckbzkfkecumgjlrialkhlwqkgisbibtdzwmebopwlznzlextamoyqgscxqifavpttw
nfcoimohzsejcbviemjcuqokqhaqeouxwozznudopaouvjzcpqnkafixbmwfrexvbfvxdbavfcttugofogadevb
wvqhwdqycauxiwvzlindosidlbeaiakmxlpwzoddsybgilmgusujhhxjte

Test Case 10

4500

rnnovornotoqxerkxoirodqnbtrrdfswsilpwcdkxtauxtfuipnysdmvwdmbkhacpnsnrvxoozjotqidhwbbbpzy
slbcubhlobyfwxwmxhaszlvgjyhkoikiwmnqpucevcltchhbqktpxqxgohsepdnlpccewgktkyomhvnyfincylkp
sdvjgivxkzdifodrorevpttucjzcwltqopzwzuvkvzuapyudryygtudxdeabptrgksekpawkzqnqqhtihtoanrysvatn
vmtgfzsuzogagtqxalhhfviupipmiizfxuleudavtgwaaoxccgkjbufseufmfgrcbfixkiseoqeqhdtjjdumzzhdumrz
skdvrlsctngjdmckrvvaarozrvenjvoehrzzeubzhjkkxmxohuqhmeifcmsljgprzrsflveseoedddrkyjumperrtlfct
wvsnpzykfsqvztycmjcvfoljhecslhliefvuewejqxfpqdudowatnlfusjndqylxgjrkhxuzubplelqvhsqwgvryfgdxg
pumanxjltihuzuakmvufmqlhjjopmowdkifyholcxuwwpxhbsdigtttgidsbhxpwwuxclohyfikdwompojjhlqm
fuvmkauzuhitljxnamupgxdgfyrvgwqshvqlelpbuzuxhkrjgxlyqdnjsuflntawodudqpfxqjeweuvfeilhlscehjlo
fvcjmcytzvqsfkyzpnsvwtcfltrrepmujykrdddeoesevlfsrzrpgjlsmcfiemhquhoxmxkkjhzbuezzrheovjnevrzo
raavvrkcmdjgntcslrvdkszrmudhzzmudjjtdhqeqoesikxifbcrgfmfuesfubjkgccxoaawgtvadueluxfziimpipui
vfhhlaxqtgagozuszfgtmvntavsyrnaothithqqnqzkwapkeskgrtpbaedxdutgyyrduypauzvkvuzwzpoqtlwczjc
uttpverordofidzkxvigjvdspklycnifynvhmoyktkgweccplndpeshogxqxptkqbhhctlcvecupqnmwikiokhyjgvl
zsahxmwxwfqdeesruqwfbcfkqsnpojmdivhdypjtlzwpgricjfjkjqvzkkrztfeeanjafstqusfcloguvqheicftowsjb
wndkwdrrzhnrorcexyzpffyjlrxhlhlhuottsmmrtzkksoormqhuvhdgybqjkbsepozjancwomggcwypmhjkooq
opixzjrgbhhkivngjbmsekqvxzghnwzboiantrvubfhjcwrnxdfdnxamwivjfvmvfokyigvjncupylcxqkdfhfseqnp
xkespscqakljxndonotmedrkkxeontgkekeveglfrwqqlufakynrbedndhesckegwieapphioaybwfegdtzgzcudl
yxokcwgkaibssjiskloprwvkwbmaxpovmchoanbdycxsmhmwuanmyiywkkxjbnhoroerehwcktwyciwxkjjisj
feuepvrwlklsbpzytltpjwzhtjretlnarjggfzdqjqilfklavgpfcqoxbfdustxlcdujdxampkzuumuqtlxxblvetayntvzy
bthesjshuudqgxibkhzntwrowrbsncqovzupjowfizvpygsknrxinqymicexeuncthrevqjerhvsnncchaluqlgan
mxsgkwcrnipfsvxzspohrqotdlmrrmeekymuuqoizdptamusdizxaqqgbexurbadanzwfnggswzsitmoboleeb
kfijzzmaeopdlutrbnnciywumzixdmaptiatjntpbktoeoghbvmjvigjhqgndjeytfrfumuxwnmddumfryqniww
snfhsqlqjskomyjkvywacsojjnzwxyvpnawhqkzbcjqpibbfzzhdrvmaioziouxbwwiogjpkvhbdickkbrnumcxxs
wfgsejqatgicvtxfucpzozafpxututlsatmecchxirzfkzmhbcgqbixsftlbmytmrfrvjastruzetnlwprotboljhzkuxeg
plzkvbfotzpxudkqudhnevbncaayxgfmrgzmieddfuczzmpuryjxtmnymnwktdykmzzufezkablapbwibffvusv
gfrsaxtnjuofasemshyuybqgcylzsgwalotonobyipfkjlxdsxysaqyeojgircjfsctfswdalklwvkznjzfjqfnervniyynq
cgwucbupmhlhrnxcmelckbjbwyluwzlafjukmqbaypkrchuqnfvxigahembcnocuzyeooiomxyebharvhouqu
xxalacyrgssgzgvhvjevphdpyaxnunjtmkeooefxzydyeafbklxzsapsamhwbrspdydrdlqclucpwjtguqgosxgulo
sohkdklidqtuugqwwmfrtbhbpbavvllnbsageloibkevqutogyfbzoeopglkrxauraawnpgqbklrgggoensfcwvtd
gewfgrzitxvkdllpydveljkabrcamyfuedckubsqynadamsyrpecyqcchhevhjplotvjupbuebxenpeegkihanjjwp
edavooplzjaagecdkrvqybaiicvtltkrwkmmzbxanzbtffwrythyvhhflezwyjnuwcjxdixqialphihibogyynejufisq
xomzxjfijxqjjhrrobufhvdxzorgyjwyzjzzuehdcxnlggevhaaqvfnwvecupbspmtogyvkcuzpahtxqvzgteupaau
wsvqjhjznhwzjsaauhtsxrrgkyczyevuwqkfztgpdcoourppykhybaglyinymiulbesaazpfbgtwzinztwxwwfixnx
vchqniwhjygadiixghhtjcriznojmdgifpauyycjxilcswbadjvonmxmclxoofyuvaqtzseydpavleyrptfcgcrinoycu
xyrxomyjqwofzlrdjksdpwjsntherlaqjroadmltlzakktpudjztfknvduzwgznrsbtvpeqafsmqmbmpmlkuvxpau
qwcpjvhmpecvwebortauhsjscdpcupyknabxvklmqpimwlangdjnxuhzzwdtnbfadgzbqnngcxuykxnsazfxto
yvmeozhucladotqdbtdwtnthgvinudcsyqypqgjutlxhgokijnecdxlluvyozciztholnxfgleprsbzbrfeuerfynfmm
kvnfecsrbzzmdqgwrhzinfetxlumtgafdnmjpearfbfirlglvgvinadklxwggyllmxvbbxugzcrsnxdifzstbwfovevbc
gnqekuhhoqgqhbgggqofjjihqxeusgzyvpehjmoaexsnyytepjmasujlrpflvgksyobjcqjgpetncpttahvveggvwn
jtutoujpdofpuwtqjxhfrhoocsvkqryzkusyodotrviosdgdbnkuwzkbrflhyjgjdajtgznxxxnpbtueifafgmizsthqfp
bksneymtxjqlatevxnczukmcjgxsyckcncptcdoznempytmxiozcalgktdcrgmtvqkquoewbiiqiddilthpwuvgnzk
ghzacrmumayidisutwzbhukxqesytrlzakbcbowpowxshqoampdvjnsctnamglnhxpjbdiqtgolngzpuqupahie
cxeodsckptwqwgjpmxdcfetzvooxvybyxhobzslrljjjpszeregyizxfpocnodnmlbpmwcfhmprbjsfdwnbgpbme
rorhsevfiktenzlbqeezwkeuzgbojntabmjvrfcbrwfgxshnxmmtytoxzrmkehmhvvfoajpshuyenirkugfszvramf
ksmwckrhyuqooyimexuwjqeridmadbfpvulxeegcaxsoxbbdaxzkodbyipalsicocpliusmurfjqimtilvuzyvajna
wfiztmohukzjfsoqiwedgpybrzyriltetedmqstncuwjmmbwifaqxyroxqhhdamweplxjgkobizpuboeioufomt
oecvhfhgjzrgixsyyayquzeajuvpkjkannwwsfcdgtmrreprhnjbopeylzpwizyxowticwmkpybietclglpxbtxmsm
kcnjzcfskjqwuiwvqbosmxedwhwttqhgsuprwumjgcfakexdfoxtndzjkvegmlmghbagxmpdqufdadgfrdbeja
ptxvblgnspqsvqgkvyhbbhehnxnqdwsurpptbxivmbpirxsmvzpxhvgwsvoxtgrnxigyfqvsrkckhuzfwocfkkde
grebxxougwvlnsfgdhtmestcivjsimzoddrcagygcvurobatlthplbttycogonwtsovuuvbyrxshysajljaykvtjxhpn
wmgqcdlwbowuloblidxtmztzvniuwzivnqlpwwnxkmrxaujlziglhamcpuxlwhijzubvsosfalcdhnogxuufwgj

1001

fwxwmxhaszlvgjyhkoikiwmnqpucevcltchhbqktpxqxgohsepdnlpccewgktkyomhvnyfincylkpsdvjgivxkzdif
odrorevpttucjzcwltqopzwzuvkvzuapyudryygtudxdeabptrgksekpawkzqnqqhtihtoanrysvatnvmtgfzsuzog
agtqxalhhfviupipmiizfxuleudavtgwaaoxccgkjbufseufmfgrcbfixkiseoqeqhdtjjdumzzhdumrzskdvrlsctngj
dmckrvvaarozrvenjvoehrzzeubzhjkkxmxohuqhmeifcmsljgprzrsflveseoedddrkyjumperrtlfctwvsnpzykfs
qvztycmjcvfoljhecslhliefvuewejqxfpqdudowatnlfusjndqylxgjrkhxuzubplelqvhsqwgvryfgdxgpumanxjlti
huzuakmvufmqlhjjopmowdkifyholcxuwwpxhbsdigtttgidsbhxpwwuxclohyfikdwompojjhlqmfuvmkauzu
hitljxnamupgxdgfyrvgwqshvqlelpbuzuxhkrjgxlyqdnjsuflntawodudqpfxqjeweuvfeilhlscehjlofvcjmcytzv
qsfkyzpnsvwtcfltrrepmujykrdddeoesevlfsrzrpgjlsmcfiemhquhoxmxkkjhzbuezzrheovjnevrzoraavvrkcm
djgntcslrvdkszrmudhzzmudjjtdhqeqoesikxifbcrgfmfuesfubjkgccxoaawgtvadueluxfziimpipuivfhhlaxqtg
agozuszfgtmvntavsyrnaothithqqnqzkwapkeskgrtpbaedxdutgyyrduypauzvkvuzwzpoqtlwczjcuttpverord
ofidzkxvigjvdspklycnifynvhmoyktkgweccplndpeshogxqxptkqbhhctlcvecupqnmwikiokhyjgvlzsahxmwx
wf

Test Case 11

2000

qmiqodqunuvkyupgtubirbthqxmfjaezmosatixgesqcmhiidlsxmmgelsluspwggoizwficzaeoiowncqkocqvn
kgkcygkewtfuynwaocoyqkluayjfqgubmgfmoqskjyejncjdexbxjprmpcrhinixwqjkgcvrabapgmtklwhvlzhcb
akkpsjliswquthwwkmcyhnjdwepvntzndlfyuqimozjhihgutiscxcguixrwqqlubqsvjakxbthkapewxzyxbgtjdk
hwdtqelkcummuohbajqghpfioiohsuuzqxuibgsfaeruuaxwkpdrhizvrqflkzmayhizncfpiymdbjzlbeeipgfiwk
tglhijqsldusvcshhtsjevnldcrlkpxfxjpfufzfltzgxsphljqsffdkkwvwlteketryyqgjjfrizgplqhdvnihzedvrwzbcssat
kictoudnctasafppnxotcmmalncghcbrldmbzqqcltwnyofonthpfurtjtbrxckkhznhrelczhrxxwlksvbxrssanttlx
gvffjowpzaoitliqzsiuwhnqanevjptpkauvoskpsyxlmfdlalhyvuoxjuusjphwpdrfveupcudqbgbdukbresoomii
yyquptnvrtpgyljonssqocufjmtzydhybzuttkomdfsbreqgyiymmsrvemufpedtdymwicknhdpajhghrfvfxobe
axlrbomfoadycomktdmcmvlfaikzwlfylqpmfetvexwhnitgnhkbcxgcfqedejbpasdhwxedwamlkftzodarcgvj
zzmdlnunfzweyahudthnaanofnfhwbqvccaprwcxvadwdkqgfatfaivgwdnuegriktacpebmfeiiqbovbjcdsxjq
azkgfbrpurtlvuzcyikolylmknrcnbspceyhfpybisofoninvsbitpwdcohrpzhrdfakwangubljqtyoobwjqtovhxm
ywtwymxhvotqjwbooytqjlbugnawkafdrhzprhocdwptibsvninofosibypfhyecpsbncrnkmlylokiyczuvltrupr
bfgkzaqjxsdcjbvobqiiefmbepcatkirgeundwgviaftafgqkdwdavxcwrpaccvqbwhfnfonaanhtduhayewzfnun
ldmzzjvgcradoztfklmawdexwhdsapbjedeqfcgxcbkhngtinhwxevtefmpqlyflwzkiaflvmcmdtkmocydaofm
obrlxaeboxfvfrhghjapdhnkciwmydtdepfumevrsmmyiygqerbsfdmokttuzbyhdyztmjfucoqssnojlygptrvnt
puqyyiimooserbkudbgbqducpuevfrdpwhpjsuujxouvyhlaldfmlxyspksovuakptpjvenaqnhwuiszqiltioazp
wojffvgxlttnassrxbvsklwxxrhzclerhnzhkkcxrbtjtrufphtnofoynwtlcqqzbmdlrbchgcnlammctoxnppfasatcn
duotciktasscbzwrvdezhinvdhqlpgzirfjjgqyyrteketlwvwkkdffsqjlhpsxgztlfzfufpjxfxpklrcdlnvejsthhscvsud
lsqjihlgtkwifgpieeblzjbdmyipfcnzihyamzklfqrvzihrdpkwxauureafsgbiuxqzuushoioifphgqjabhoummuckl
eqtdwhkdjtgbxyzxwepakhtbxkajvsqbulqqwrxiugcxcsitughihjzomiquyfldnztnvpewdjnhycmkwwhtuqws
iljspkkabchzlvhwlktmgpabarvcgkjqwxinihrcpmrpjxbxedjcnjeyjksqomfgmbugqfjyaulkqyocoawnyuftwe
kgyckgknvqcokqcnwoioeazcifwzioggwpsulslegmmxsldiihmcqsegxitasomzeajfmxqhtbributgpuykvunuq
doqimrbat

1995

miqodqunuvkyupgtubirbthqxmfjaezmosatixgesqcmhiidlsxmmgelsluspwggoizwficzaeoiowncqkocqvnk
gkcygkewtfuynwaocoyqkluayjfqgubmgfmoqskjyejncjdexbxjprmpcrhinixwqjkgcvrabapgmtklwhvlzhcba
kkpsjliswquthwwkmcyhnjdwepvntzndlfyuqimozjhihgutiscxcguixrwqqlubqsvjakxbthkapewxzyxbgtjdkh
wdtqelkcummuohbajqghpfioiohsuuzqxuibgsfaeruuaxwkpdrhizvrqflkzmayhizncfpiymdbjzlbeeipgfiwkt
glhijqsldusvcshhtsjevnldcrlkpxfxjpfufzfltzgxsphljqsffdkkwvwlteketryyqgjjfrizgplqhdvnihzedvrwzbcssat
kictoudnctasafppnxotcmmalncghcbrldmbzqqcltwnyofonthpfurtjtbrxckkhznhrelczhrxxwlksvbxrssanttlx
gvffjowpzaoitliqzsiuwhnqanevjptpkauvoskpsyxlmfdlalhyvuoxjuusjphwpdrfveupcudqbgbdukbresoomii
yyquptnvrtpgyljonssqocufjmtzydhybzuttkomdfsbreqgyiymmsrvemufpedtdymwicknhdpajhghrfvfxobe
axlrbomfoadycomktdmcmvlfaikzwlfylqpmfetvexwhnitgnhkbcxgcfqedejbpasdhwxedwamlkftzodarcgvj
zzmdlnunfzweyahudthnaanofnfhwbqvccaprwcxvadwdkqgfatfaivgwdnuegriktacpebmfeiiqbovbjcdsxjq
azkgfbrpurtlvuzcyikolylmknrcnbspceyhfpybisofoninvsbitpwdcohrpzhrdfakwangubljqtyoobwjqtovhxm
ywtwymxhvotqjwbooytqjlbugnawkafdrhzprhocdwptibsvninofosibypfhyecpsbncrnkmlylokiyczuvltrupr
bfgkzaqjxsdcjbvobqiiefmbepcatkirgeundwgviaftafgqkdwdavxcwrpaccvqbwhfnfonaanhtduhayewzfnun
ldmzzjvgcradoztfklmawdexwhdsapbjedeqfcgxcbkhngtinhwxevtefmpqlyflwzkiaflvmcmdtkmocydaofm
obrlxaeboxfvfrhghjapdhnkciwmydtdepfumevrsmmyiygqerbsfdmokttuzbyhdyztmjfucoqssnojlygptrvnt
puqyyiimooserbkudbgbqducpuevfrdpwhpjsuujxouvyhlaldfmlxyspksovuakptpjvenaqnhwuiszqiltioazp
wojffvgxlttnassrxbvsklwxxrhzclerhnzhkkcxrbtjtrufphtnofoynwtlcqqzbmdlrbchgcnlammctoxnppfasatcn
duotciktasscbzwrvdezhinvdhqlpgzirfjjgqyyrteketlwvwkkdffsqjlhpsxgztlfzfufpjxfxpklrcdlnvejsthhscvsud
lsqjihlgtkwifgpieeblzjbdmyipfcnzihyamzklfqrvzihrdpkwxauureafsgbiuxqzuushoioifphgqjabhoummuckl
eqtdwhkdjtgbxyzxwepakhtbxkajvsqbulqqwrxiugcxcsitughihjzomiquyfldnztnvpewdjnhycmkwwhtuqws
iljspkkabchzlvhwlktmgpabarvcgkjqwxinihrcpmrpjxbxedjcnjeyjksqomfgmbugqfjyaulkqyocoawnyuftwe
kgyckgknvqcokqcnwoioeazcifwzioggwpsulslegmmxsldiihmcqsegxitasomzeajfmxqhtbributgpuykvunuq
doqim

Test Case 12

2000

rnnovornotoqxerkxoirodqnbtrrdfswsilpwcdkxtauxtfuipnysdmvwdmbkhacpnsnrvxoozjotqidhwbbbpzy
slbcubhlobyfwxwmxhaszlvgjyhkoikiwmnqpucevcltchhbqktpxqxgohsepdnlpccewgktkyomhvnyfincylkp
sdvjgivxkzdifodrorevpttucjzcwltqopzwzuvkvzuapyudryygtudxdeabptrgksekpawkzqnqqhtihtoanrysvatn
vmtgfzsuzogagtqxalhhfviupipmiizfxuleudavtgwaaoxccgkjbufseufmfgrcbfixkiseoqeqhdtjjdumzzhdumrz
skdvrlsctngjdmckrvvaarozrvenjvoehrzzeubzhjkkxmxohuqhmeifcmsljgprzrsflveseoedddrkyjumperrtlfct
wvsnpzykfsqvztycmjcvfoljhecslhliefvuewejqxfpqdudowatnlfusjndqylxgjrkhxuzubplelqvhsqwgvryfgdxg
pumanxjltihuzuakmvufmqlhjjopmowdkifyholcxuwwpxhbsdigttqdeesruqwfbcfkqsnpojmdivhdypjtlzwp
gricjfjkjqvzkkrztfeeanjafstqusfcloguvqheicftowsjbwndkwdrrzhnrorcexyzpffyjlrxhlhlhuottsmmrtzkksoor
mqhuvhdgybqjkbsepozjancwomggcwypmhjkooqopixzjrgbhhkivngjbmsekqvxzghnwzboiantrvubfhjcwr
nxdfdnxamwivjfvmvfokyigvjncupylcxqkdfhfseqnpxkespscqakljxndonotmedrkkxeontgkekeveglfrwqqluf
akynrbedndhesckegwieapphioaybwfegdtzgzcudlyxokcwgkaibssjiskloprwvkwbmaxpovmchoanbdycxs
mhmwuanmyiywkkxjbnhoroerehwcktwyciwxkjjisjfeuepvrwlklsbpzytltpjwzhtjretlnarjggfzdqjqilfklavgpf
cqoxbfdustxxtsudfbxoqcfpgvalkfliqjqdzfggjranlterjthzwjptltyzpbslklwrvpeuefjsijjkxwicywtkcwhereoro
hnbjxkkwyiymnalcdujdxampkzuumuqtlxxblvetayntvzybthesjshuudqgxibkhzntwrowrbsncqovzupjowfiz
vpygsknrxinqymicexeuncthrevqjerhvsnncchaluqlganmxsgkwcrnipfsvxzspohrqotdlmrrmeekymuuqoizd
ptamusdizxaqqgbexurbadanzwfnggswzsitmoboleebkfijzzmaeopdlutrbnnciywumzixdmaptiatjntpbkto
eoghbvmjvigjhqgndjeytfrfumuxwnmddumfryqniwwsnfhsqlqjskomyjkvywacsojjnzwxyvpnawhqkzbcjq
pibbfzzhdrvmaioziouxbwwiogjpkvhbdickkbrnumcxxswfgsejqatgicvtxfucpzozafpxututlsatmecchxirzfkz
mhbcgqbixsftlbmytmrfrvjastruzetnlwprotboljhzkuxegplzkvbfotzpxudkqudhnevbncaayxgfmrgzmieddf
uczzmpuryjxtmnymnwktdykmzzufezkablapbwibffvusvgfrsaxtnjuofasemshyuybqgcylzsgwalotonobyipf
kjlxdsxysaqyeojgircjfsctfswdalklwvkznjzfjqfnervniyynqcgwucbupmhlhrnxcmelckbjbwyluwzlafjukmqba
ypkrchuqnfvxigahembcnocuzyeooiomxyebharvhouquxxalacyrgssgzgvhvjevphdpyaxnunjtmkeooefxzy
dyeafbklxzsa

200

anmyiywkkxjbnhoroerehwcktwyciwxkjjisjfeuepvrwlklsbpzytltpjwzhtjretlnarjggfzdqjqilfklavgpfcqoxbfd
ustxxtsudfbxoqcfpgvalkfliqjqdzfggjranlterjthzwjptltyzpbslklwrvpeuefjsijjkxwicywtkcwhereorohnbjxkk
wyiymna