Task: | Järjestäminen |
Sender: | lady-stardust |
Submission time: | 2021-01-23 20:00:15 +0200 |
Language: | C++ (C++17) |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | TIME LIMIT EXCEEDED | 0 |
#2 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | TIME LIMIT EXCEEDED | -- | 1, 2 | details |
#2 | TIME LIMIT EXCEEDED | -- | 2 | details |
#3 | ACCEPTED | 0.09 s | 1, 2 | details |
#4 | TIME LIMIT EXCEEDED | -- | 1, 2 | details |
Compiler report
input/code.cpp: In function 'bool explore()': input/code.cpp:30:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int i = 0; i < current.size() - 3; i++) { ~~^~~~~~~~~~~~~~~~~~~~ input/code.cpp:31:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int j = i + 2; j < current.size() - 1; j++) { ~~^~~~~~~~~~~~~~~~~~~~
Code
#include <bits/stdc++.h>#include <unordered_map>#define ll long long#define ull unsigned long longusing namespace std;unordered_map<string, bool> m;unordered_map<string, bool> m2;string current = "";string target = "";void reset() {// memset(arr, 0, sizeof(arr));m = {};//m2 = {};current = "";target = "";}bool explore() {//cout << current << ",\n";if (current == target) return true;if (m2[current]) return true;if (m[current]) return false;m[current] = true;for (int i = 0; i < current.size() - 3; i++) {for (int j = i + 2; j < current.size() - 1; j++) {swap(current[i], current[j]);swap(current[i+1], current[j+1]);if (explore()) return true;swap(current[i], current[j]);swap(current[i + 1], current[j + 1]);}}return false;}vector<int> lsit = { 12345678,34125678,12345678,25134678,13254678,25134678,54213678,21543678,54213678,43521678,52431678,43521678,31452678,45312678,31452678,12345678,26314578,31264578,26314578,64231578,23641578,64231578,41623578,62413578,41623578,13462578,46132578,13462578,32146578,14326578,32146578,26314578,65321478,32651478,65321478,51632478,63512478,51632478,12563478,56123478,12563478,23156478,15236478,23156478,36215478,21365478,36215478,65321478,54362178,36542178,54362178,42536178,53426178,42536178,26453178,45263178,26453178,63245178,24635178,63245178,35624178,62354178,35624178,54362178,41356278,35416278,41356278,16435278,43165278,16435278,65143278,14653278,65143278,53614278,61534278,53614278,34561278,56341278,34561278,41356278,12345678,27341568,34271568,27341568,71234568,23714568,71234568,14723568,72143568,14723568,43172568,17432568,43172568,32417568,41327568,32417568,27341568,75324168,32754168,75324168,54732168,73542168,54732168,42573168,57423168,42573168,23457168,45237168,23457168,37245168,24375168,37245168,75324168,51372468,37512468,51372468,12537468,53127468,12537468,27153468,15273468,27153468,73215468,21735468,73215468,35721468,72351468,35721468,51372468,14357268,35147268,14357268,47135268,13475268,47135268,75413268,41753268,75413268,53741268,74531268,53741268,31574268,57314268,31574268,14357268,42315768,31425768,42315768,25431768,43251768,25431768,51243768,24513768,51243768,13524768,52134768,13524768,34152768,15342768,34152768,42315768,27341568,76342158,34762158,76342158,62734158,73624158,62734158,24673158,67243158,24673158,43267158,26437158,43267158,37426158,42376158,37426158,76342158,61374258,37614258,61374258,14637258,63147258,14637258,47163258,16473258,47163258,73416258,41736258,73416258,36741258,74361258,36741258,61374258,12367458,36127458,12367458,27136458,13276458,27136458,76213458,21763458,76213458,63721458,72631458,63721458,31672458,67312458,31672458,12367458,24316758,31246758,24316758,46231758,23461758,46231758,61423758,42613758,61423758,13642758,64132758,13642758,32164758,16324758,32164758,24316758,47321658,32471658,47321658,71432658,43712658,71432658,12743658,74123658,12743658,23174658,17234658,23174658,34217658,21347658,34217658,47321658,76342158,65347218,34657218,65347218,57634218,63574218,57634218,74563218,56743218,74563218,43756218,75436218,43756218,36475218,47365218,36475218,65347218,52364718,36524718,52364718,24536718,53246718,24536718,46253718,25463718,46253718,63425718,42635718,63425718,35642718,64352718,35642718,52364718,27356418,35276418,27356418,76235418,23765418,76235418,65723418,72653418,65723418,53672418,67532418,53672418,32567418,56327418,32567418,27356418,74325618,32745618,74325618,45732618,73452618,45732618,52473618,47523618,52473618,23547618,54237618,23547618,37254618,25374618,37254618,74325618,46372518,37462518,46372518,62437518,43627518,62437518,27643518,64273518,27643518,73264518,26734518,73264518,34726518,72346518,34726518,46372518,65347218,51346728,34516728,51346728,16534728,53164728,16534728,64153728,15643728,64153728,43615728,61435728,43615728,35461728,46351728,35461728,51346728,17354628,35174628,17354628,74135628,13745628,74135628,45713628,71453628,45713628,53471628,47531628,53471628,31547628,54317628,31547628,17354628,76315428,31765428,76315428,65731428,73651428,65731428,51673428,67513428,51673428,13567428,56137428,13567428,37156428,15376428,37156428,76315428,64371528,37641528,64371528,41637528,63417528,41637528,17463528,46173528,17463528,73146528,14736528,73146528,36714528,71364528,36714528,64371528,45367128,36457128,45367128,57436128,43576128,57436128,76543128,54763128,76543128,63754128,75634128,63754128,34675128,67345128,34675128,45367128,51346728,12345678,28345167,34285167,28345167,85234167,23854167,85234167,54823167,82543167,54823167,43582167,58432167,43582167,32458167,45328167,32458167,28345167,81324567,32814567,81324567,14832567,83142567,14832567,42183567,18423567,42183567,23418567,41238567,23418567,38241567,24381567,38241567,81324567,15382467,38152467,15382467,52138467,13528467,52138467,28513467,51283467,28513467,83251467,25831467,83251467,31825467,82315467,31825467,15382467,54318267,31548267,54318267,48531267,53481267,48531267,81453267,45813267,81453267,13845267,84135267,13845267,35184267,18354267,35184267,54318267,42351867,35421867,42351867,21435867,43215867,21435867,15243867,24153867,15243867,53124867,12534867,53124867,34512867,51342867,34512867,42351867,28345167,86342517,34862517,86342517,62834517,83624517,62834517,24683517,68243517,24683517,43268517,26438517,43268517,38426517,42386517,38426517,86342517,65384217,38654217,65384217,54638217,63548217,54638217,48563217,56483217,48563217,83456217,45836217,83456217,36845217,84365217,36845217,65384217,52368417,36528417,52368417,28536417,53286417,28536417,86253417,25863417,86253417,63825417,82635417,63825417,35682417,68352417,35682417,52368417,24356817,35246817,24356817,46235817,23465817,46235817,65423817,42653817,65423817,53642817,64532817,53642817,32564817,56324817,32564817,24356817,48325617,32485617,48325617,85432617,43852617,85432617,52843617,84523617,52843617,23584617,58234617,23584617,34258617,25348617,34258617,48325617,86342517,61348257,34618257,61348257,18634257,63184257,18634257,84163257,16843257,84163257,43816257,81436257,43816257,36481257,48361257,36481257,61348257,12364857,36124857,12364857,24136857,13246857,24136857,46213857,21463857,46213857,63421857,42631857,63421857,31642857,64312857,31642857,12364857,28316457,31286457,28316457,86231457,23861457,86231457,61823457,82613457,61823457,13682457,68132457,13682457,32168457,16328457,32168457,28316457,84321657,32841657,84321657,41832657,83412657,41832657,12483657,48123657,12483657,23148657,14238657,23148657,38214657,21384657,38214657,84321657,46382157,38462157,46382157,62438157,43628157,62438157,28643157,64283157,28643157,83264157,26834157,83264157,34826157,82346157,34826157,46382157,61348257,15346827,34156827,15346827,56134827,13564827,56134827,64513827,51643827,64513827,43651827,65431827,43651827,31465827,46315827,31465827,15346827,58314627,31584627,58314627,84531627,53841627,84531627,41853627,85413627,41853627,13485627,48135627,13485627,35148627,14358627,35148627,58314627,86351427,35861427,86351427,61835427,83615427,61835427,15683427,68153427,15683427,53168427,16538427,53168427,38516427,51386427,38516427,86351427,64385127,38645127,64385127,45638127,63458127,45638127,58463127,46583127,58463127,83546127,54836127,83546127,36854127,85364127,36854127,64385127,41368527,36418527,41368527,18436527,43186527,18436527,86143527,14863527,86143527,63814527,81634527,63814527,34681527,68341527,34681527,41368527,15346827,52341687,34521687,52341687,21534687,53214687,21534687,14253687,25143687,14253687,43125687,12435687,43125687,35412687,41352687,35412687,52341687,26354187,35264187,26354187,64235187,23645187,64235187,45623187,62453187,45623187,53462187,46532187,53462187,32546187,54326187,32546187,26354187,61325487,32615487,61325487,15632487,63152487,15632487,52163487,16523487,52163487,23516487,51236487,23516487,36251487,25361487,36251487,61325487,14362587,36142587,14362587,42136587,13426587,42136587,26413587,41263587,26413587,63241587,24631587,63241587,31624587,62314587,31624587,14362587,45316287,31456287,45316287,56431287,43561287,56431287,61543287,54613287,61543287,13654287,65134287,13654287,34165287,16345287,34165287,45316287,52341687,28345167,87345216,34875216,87345216,75834216,83754216,75834216,54783216,78543216,54783216,43578216,57438216,43578216,38457216,45387216,38457216,87345216,72384516,38724516,72384516,24738516,73248516,24738516,48273516,27483516,48273516,83427516,42837516,83427516,37842516,84372516,37842516,72384516,25378416,37258416,25378416,58237416,23587416,58237416,87523416,52873416,87523416,73852416,85732416,73852416,32785416,78325416,32785416,25378416,54327816,32547816,54327816,47532816,53472816,47532816,72453816,45723816,72453816,23745816,74235816,23745816,35274816,27354816,35274816,54327816,48352716,35482716,48352716,82435716,43825716,82435716,25843716,84253716,25843716,53284716,28534716,53284716,34528716,52348716,34528716,48352716,87345216,71348526,34718526,71348526,18734526,73184526,18734526,84173526,17843526,84173526,43817526,81437526,43817526,37481526,48371526,37481526,71348526,15374826,37154826,15374826,54137826,13547826,54137826,47513826,51473826,47513826,73451826,45731826,73451826,31745826,74315826,31745826,15374826,58317426,31587426,58317426,87531426,53871426,87531426,71853426,85713426,71853426,13785426,78135426,13785426,35178426,17358426,35178426,58317426,84351726,35841726,84351726,41835726,83415726,41835726,15483726,48153726,15483726,53148726,14538726,53148726,38514726,51384726,38514726,84351726,47385126,38475126,47385126,75438126,43758126,75438126,58743126,74583126,58743126,83574126,57834126,83574126,34857126,85347126,34857126,47385126,71348526,12347856,34127856,12347856,27134856,13274856,27134856,74213856,21743856,74213856,43721856,72431856,43721856,31472856,47312856,31472856,12347856,28314756,31284756,28314756,84231756,23841756,84231756,41823756,82413756,41823756,13482756,48132756,13482756,32148756,14328756,32148756,28314756,87321456,32871456,87321456,71832456,83712456,71832456,12783456,78123456,12783456,23178456,17238456,23178456,38217456,21387456,38217456,87321456,74382156,38742156,74382156,42738156,73428156,42738156,28473156,47283156,28473156,83247156,24837156,83247156,37824156,82374156,37824156,74382156,41378256,37418256,41378256,18437256,43187256,18437256,87143256,14873256,87143256,73814256,81734256,73814256,34781256,78341256,34781256,41378256,12347856,25341786,34251786,25341786,51234786,23514786,51234786,14523786,52143786,14523786,43152786,15432786,43152786,32415786,41325786,32415786,25341786,57324186,32574186,57324186,74532186,53742186,74532186,42753186,75423186,42753186,23475186,47235186,23475186,35247186,24357186,35247186,57324186,71352486,35712486,71352486,12735486,73125486,12735486,25173486,17253486,25173486,53217486,21537486,53217486,37521486,52371486,37521486,71352486,14375286,37145286,14375286,45137286,13457286,45137286,57413286,41573286,57413286,73541286,54731286,73541286,31754286,75314286,31754286,14375286,42317586,31427586,42317586,27431586,43271586,27431586,71243586,24713586,71243586,13724586,72134586,13724586,34172586,17342586,34172586,42317586,25341786,58342176,34582176,58342176,82534176,53824176,82534176,24853176,85243176,24853176,43285176,28435176,43285176,35428176,42358176,35428176,58342176,81354276,35814276,81354276,14835276,83145276,14835276,45183276,18453276,45183276,53418276,41538276,53418276,38541276,54381276,38541276,81354276,12385476,38125476,12385476,25138476,13258476,25138476,58213476,21583476,58213476,83521476,52831476,83521476,31852476,85312476,31852476,12385476,24318576,31248576,24318576,48231576,23481576,48231576,81423576,42813576,81423576,13842576,84132576,13842576,32184576,18324576,32184576,24318576,45321876,32451876,45321876,51432876,43512876,51432876,12543876,54123876,12543876,23154876,15234876,23154876,34215876,21345876,34215876,45321876,58342176,87345216,76345821,34765821,76345821,65734821,73654821,65734821,54673821,67543821,54673821,43567821,56437821,43567821,37456821,45376821,37456821,76345821,68374521,37684521,68374521,84637521,63847521,84637521,47863521,86473521,47863521,73486521,48736521,73486521,36748521,74368521,36748521,68374521,85367421,36857421,85367421,57836421,83576421,57836421,76583421,58763421,76583421,63758421,75638421,63758421,38675421,67385421,38675421,85367421,54386721,38546721,54386721,46538721,53468721,46538721,68453721,45683721,68453721,83645721,64835721,83645721,35864721,86354721,35864721,54386721,47358621,35478621,47358621,78435621,43785621,78435621,85743621,74853621,85743621,53874621,87534621,53874621,34587621,58347621,34587621,47358621,76345821,62347581,34627581,62347581,27634581,63274581,27634581,74263581,26743581,74263581,43726581,72436581,43726581,36472581,47362581,36472581,62347581,25364781,36254781,25364781,54236781,23546781,54236781,46523781,52463781,46523781,63452781,45632781,63452781,32645781,64325781,32645781,25364781,57326481,32576481,57326481,76532481,53762481,76532481,62753481,75623481,62753481,23675481,67235481,23675481,35267481,26357481,35267481,57326481,74352681,35742681,74352681,42735681,73425681,42735681,25473681,47253681,25473681,53247681,24537681,53247681,37524681,52374681,37524681,74352681,46375281,37465281,46375281,65437281,43657281,65437281,57643281,64573281,57643281,73564281,56734281,73564281,34756281,75346281,34756281,46375281,62347581,28346751,34286751,28346751,86234751,23864751,86234751,64823751,82643751,64823751,43682751,68432751,43682751,32468751,46328751,32468751,28346751,87324651,32874651,87324651,74832651,83742651,74832651,42783651,78423651,42783651,23478651,47238651,23478651,38247651,24387651,38247651,87324651,76382451,38762451,76382451,62738451,73628451,62738451,28673451,67283451,28673451,83267451,26837451,83267451,37826451,82376451,37826451,76382451,64378251,37648251,64378251,48637251,63487251,48637251,87463251,46873251,87463251,73846251,84736251,73846251,36784251,78364251,36784251,64378251,42367851,36427851,42367851,27436851,43276851,27436851,76243851,24763851,76243851,63724851,72634851,63724851,34672851,67342851,34672851,42367851,28346751,85342671,34852671,85342671,52834671,83524671,52834671,24583671,58243671,24583671,43258671,25438671,43258671,38425671,42385671,38425671,85342671,56384271,38564271,56384271,64538271,53648271,64538271,48653271,65483271,48653271,83465271,46835271,83465271,35846271,84356271,35846271,56384271,62358471,35628471,62358471,28635471,63285471,28635471,85263471,26853471,85263471,53826471,82536471,53826471,36582471,58362471,36582471,62358471,24365871,36245871,24365871,45236871,23456871,45236871,56423871,42563871,56423871,63542871,54632871,63542871,32654871,65324871,32654871,24365871,48326571,32486571,48326571,86432571,43862571,86432571,62843571,84623571,62843571,23684571,68234571,23684571,34268571,26348571,34268571,48326571,85342671,57348261,34578261,57348261,78534261,53784261,78534261,84753261,75843261,84753261,43875261,87435261,43875261,35487261,48357261,35487261,57348261,72354861,35724861,72354861,24735861,73245861,24735861,45273861,27453861,45273861,53427861,42537861,53427861,37542861,54372861,37542861,72354861,28375461,37285461,28375461,85237461,23857461,85237461,57823461,82573461,57823461,73582461,58732461,73582461,32758461,75328461,32758461,28375461,84327561,32847561,84327561,47832561,83472561,47832561,72483561,48723561,72483561,23748561,74238561,23748561,38274561,27384561,38274561,84327561,45382761,38452761,45382761,52438761,43528761,52438761,28543761,54283761,28543761,83254761,25834761,83254761,34825761,82345761,34825761,45382761,57348261,76345821,61345782,34615782,61345782,15634782,63154782,15634782,54163782,16543782,54163782,43516782,51436782,43516782,36451782,45361782,36451782,61345782,17364582,36174582,17364582,74136582,13746582,74136582,46713582,71463582,46713582,63471582,47631582,63471582,31647582,64317582,31647582,17364582,75316482,31756482,75316482,56731482,73561482,56731482,61573482,57613482,61573482,13657482,65137482,13657482,37165482,16375482,37165482,75316482,54371682,37541682,54371682,41537682,53417682,41537682,17453682,45173682,17453682,73145682,14735682,73145682,35714682,71354682,35714682,54371682,46357182,35467182,46357182,67435182,43675182,67435182,75643182,64753182,75643182,53764182,76534182,53764182,34576182,57346182,34576182,46357182,61345782,18346572,34186572,18346572,86134572,13864572,86134572,64813572,81643572,64813572,43681572,68431572,43681572,31468572,46318572,31468572,18346572,85314672,31854672,85314672,54831672,83541672,54831672,41583672,58413672,41583672,13458672,45138672,13458672,38145672,14385672,38145672,85314672,56381472,38561472,56381472,61538472,53618472,61538472,18653472,65183472,18653472,83165472,16835472,83165472,35816472,81356472,35816472,56381472,64358172,35648172,64358172,48635172,63485172,48635172,85463172,46853172,85463172,53846172,84536172,53846172,36584172,58364172,36584172,64358172,41365872,36415872,41365872,15436872,43156872,15436872,56143872,14563872,56143872,63514872,51634872,63514872,34651872,65341872,34651872,41365872,18346572,87341652,34871652,87341652,71834652,83714652,71834652,14783652,78143652,14783652,43178652,17438652,43178652,38417652,41387652,38417652,87341652,76384152,38764152,76384152,64738152,73648152,64738152,48673152,67483152,48673152,83467152,46837152,83467152,37846152,84376152,37846152,76384152,61378452,37618452,61378452,18637452,63187452,18637452,87163452,16873452,87163452,73816452,81736452,73816452,36781452,78361452,36781452,61378452,14367852,36147852,14367852,47136852,13476852,47136852,76413852,41763852,76413852,63741852,74631852,63741852,31674852,67314852,31674852,14367852,48316752,31486752,48316752,86431752,43861752,86431752,61843752,84613752,61843752,13684752,68134752,13684752,34168752,16348752,34168752,48316752,87341652,75348162,34758162,75348162,58734162,73584162,58734162,84573162,57843162,84573162,43857162,85437162,43857162,37485162,48375162,37485162,75348162,51374862,37514862,51374862,14537862,53147862,14537862,47153862,15473862,47153862,73415862,41735862,73415862,35741862,74351862,35741862,51374862,18357462,35187462,18357462,87135462,13875462,87135462,75813462,81753462,75813462,53781462,78531462,53781462,31578462,57318462,31578462,18357462,84315762,31845762,84315762,45831762,83451762,45831762,51483762,48513762,51483762,13548762,54138762,13548762,38154762,15384762,38154762,84315762,47381562,38471562,47381562,71438562,43718562,71438562,18743562,74183562,18743562,83174562,17834562,83174562,34817562,81347562,34817562,47381562,75348162,56347812,34567812,56347812,67534812,53674812,67534812,74653812,65743812,74653812,43765812,76435812,43765812,35476812,47356812,35476812,56347812,68354712,35684712,68354712,84635712,63845712,84635712,45863712,86453712,45863712,53486712,48536712,53486712,36548712,54368712,36548712,68354712,87365412,36875412,87365412,75836412,83756412,75836412,56783412,78563412,56783412,63578412,57638412,63578412,38657412,65387412,38657412,87365412,74386512,38746512,74386512,46738512,73468512,46738512,68473512,47683512,68473512,83647512,64837512,83647512,37864512,86374512,37864512,74386512,45378612,37458612,45378612,58437612,43587612,58437612,87543612,54873612,87543612,73854612,85734612,73854612,34785612,78345612,34785612,45378612,56347812,61345782,12345678,74583612,58743612,74583612,43758612,75438612,43758612,38475612,47385612,38475612,85347612,34857612,85347612,57834612,83574612,57834612,74583612,46578312,57468312,46578312,68457312,45687312,68457312,87645312,64875312,87645312,75864312,86754312,75864312,54786312,78546312,54786312,46578312,63547812,54637812,63547812,37654812,65374812,37654812,74365812,36745812,74365812,45736812,73456812,45736812,56473812,47563812,56473812,63547812,38564712,56384712,38564712,84356712,35846712,84356712,46835712,83465712,46835712,65483712,48653712,65483712,53648712,64538712,53648712,38564712,87536412,53876412,87536412,76853412,85763412,76853412,63785412,78635412,63785412,35678412,67358412,35678412,58367412,36587412,58367412,87536412,74583612,41587362,58417362,41587362,17458362,45178362,17458362,78145362,14785362,78145362,85714362,71854362,85714362,54871362,87541362,54871362,41587362,13548762,36541872,54361872,36541872,61354872,35614872,61354872,14635872,63145872,14635872,45163872,16453872,45163872,53416872,41536872,53416872,36541872,68534172,53684172,68534172,84653172,65843172,84653172,43865172,86435172,43865172,35486172,48356172,35486172,56348172,34568172,56348172,68534172,81563472,56813472,81563472,13856472,85136472,13856472,36185472,18365472,36185472,65318472,31658472,65318472,58631472,63581472,58631472,81563472,14586372,58146372,14586372,46158372,15468372,46158372,68415372,41685372,68415372,85641372,64851372,85641372,51864372,86514372,51864372,14586372,43518672,51438672,43518672,38451672,45381672,38451672,81345672,34815672,81345672,15834672,83154672,15834672,54183672,18543672,54183672,43518672,36541872,67543182,54673182,67543182,73654182,65734182,73654182,34765182,76345182,34765182,45376182,37456182,45376182,56437182,43567182,56437182,67543182,71564382,56714382,71564382,14756382,75146382,14756382,46175382,17465382,46175382,65417382,41657382,65417382,57641382,64571382,57641382,71564382,13576482,57136482,13576482,36157482,15367482,36157482,67315482,31675482,67315482,75631482,63751482,75631482,51763482,76513482,51763482,13576482,34517682,51347682,34517682,47351682,35471682,47351682,71435682,43715682,71435682,15743682,74153682,15743682,53174682,17534682,53174682,34517682,46531782,53461782,46531782,61453782,45613782,61453782,13645782,64135782,13645782,35164782,16354782,35164782,54316782,31546782,54316782,46531782,67543182,78546312,82546731,54826731,82546731,26854731,85264731,26854731,64285731,28645731,64285731,45628731,62458731,45628731,58462731,46582731,58462731,82546731,27584631,58274631,27584631,74258631,25748631,74258631,48725631,72485631,48725631,85472631,47852631,85472631,52847631,84527631,52847631,27584631,76528431,52768431,76528431,68752431,75682431,68752431,82675431,67825431,82675431,25867431,86257431,25867431,57286431,28576431,57286431,76528431,64572831,57642831,64572831,42657831,65427831,42657831,27465831,46275831,27465831,75246831,24756831,75246831,56724831,72564831,56724831,64572831,48567231,56487231,48567231,87456231,45876231,87456231,76845231,84765231,76845231,65784231,78654231,65784231,54678231,67548231,54678231,48567231,82546731,23548671,54238671,23548671,38254671,25384671,38254671,84325671,32845671,84325671,45832671,83452671,45832671,52483671,48523671,52483671,23548671,36524871,52364871,36524871,64352871,35642871,64352871,42635871,63425871,42635871,25463871,46253871,25463871,53246871,24536871,53246871,36524871,68532471,53682471,68532471,82653471,65823471,82653471,23865471,86235471,23865471,35286471,28356471,35286471,56328471,32568471,56328471,68532471,84563271,56843271,84563271,43856271,85436271,43856271,36485271,48365271,36485271,65348271,34658271,65348271,58634271,63584271,58634271,84563271,42586371,58426371,42586371,26458371,45268371,26458371,68245371,24685371,68245371,85624371,62854371,85624371,54862371,86542371,54862371,42586371,23548671,37542861,71542386,54712386,71542386,12754386,75124386,12754386,24175386,17245386,24175386,45217386,21457386,45217386,57421386,42571386,57421386,71542386,13574286,57134286,13574286,34157286,15347286,34157286,47315286,31475286,47315286,75431286,43751286,75431286,51743286,74513286,51743286,13574286,32517486,51327486,32517486,27351486,35271486,27351486,71235486,23715486,71235486,15723486,72153486,15723486,53172486,17532486,53172486,32517486,24531786,53241786,24531786,41253786,25413786,41253786,13425786,42135786,13425786,35142786,14352786,35142786,52314786,31524786,52314786,24531786,47523186,52473186,47523186,73452186,45732186,73452186,32745186,74325186,32745186,25374186,37254186,25374186,54237186,23547186,54237186,47523186,71542386,18547236,54187236,18547236,87154236,15874236,87154236,74815236,81745236,74815236,45781236,78451236,45781236,51478236,47518236,51478236,18547236,82514736,51824736,82514736,24851736,85241736,24851736,41285736,28415736,41285736,15428736,42158736,15428736,58142736,14582736,58142736,82514736,27581436,58271436,27581436,71258436,25718436,71258436,18725436,72185436,18725436,85172436,17852436,85172436,52817436,81527436,52817436,27581436,74528136,52748136,74528136,48752136,75482136,48752136,82475136,47825136,82475136,25847136,84257136,25847136,57284136,28574136,57284136,74528136,41572836,57412836,41572836,12457836,45127836,12457836,27145836,14275836,27145836,75214836,21754836,75214836,54721836,72541836,54721836,41572836,18547236,83541726,54831726,83541726,31854726,85314726,31854726,14385726,38145726,14385726,45138726,13458726,45138726,58413726,41583726,58413726,83541726,37584126,58374126,37584126,74358126,35748126,74358126,48735126,73485126,48735126,85473126,47853126,85473126,53847126,84537126,53847126,37584126,71538426,53718426,71538426,18753426,75183426,18753426,83175426,17835426,83175426,35817426,81357426,35817426,57381426,38571426,57381426,71538426,14573826,57143826,14573826,43157826,15437826,43157826,37415826,41375826,37415826,75341826,34751826,75341826,51734826,73514826,51734826,14573826,48517326,51487326,48517326,87451326,45871326,87451326,71845326,84715326,71845326,15784326,78154326,15784326,54178326,17548326,54178326,48517326,83541726,32548176,54328176,32548176,28354176,35284176,28354176,84235176,23845176,84235176,45823176,82453176,45823176,53482176,48532176,53482176,32548176,21534876,53214876,21534876,14253876,25143876,14253876,43125876,12435876,43125876,35412876,41352876,35412876,52341876,34521876,52341876,21534876,18523476,52183476,18523476,83152476,15832476,83152476,32815476,81325476,32815476,25381476,38251476,25381476,51238476,23518476,51238476,18523476,84512376,51842376,84512376,42851376,85421376,42851376,21485376,48215376,21485376,15248376,24158376,15248376,58124376,12584376,58124376,84512376,43581276,58431276,43581276,31458276,45318276,31458276,18345276,34185276,18345276,85134276,13854276,85134276,54813276,81543276,54813276,43581276,32548176,27543816,54273816,27543816,73254816,25734816,73254816,34725816,72345816,34725816,45372816,37452816,45372816,52437816,43527816,52437816,27543816,78524316,52784316,78524316,84752316,75842316,84752316,42875316,87425316,42875316,25487316,48257316,25487316,57248316,24578316,57248316,78524316,83572416,57832416,83572416,32857416,85327416,32857416,27385416,38275416,27385416,75238416,23758416,75238416,58723416,72583416,58723416,83572416,34587216,58347216,34587216,47358216,35478216,47358216,78435216,43785216,78435216,85743216,74853216,85743216,53874216,87534216,53874216,34587216,42538716,53428716,42538716,28453716,45283716,28453716,83245716,24835716,83245716,35824716,82354716,35824716,54382716,38542716,54382716,42538716,27543816,71542386,16542738,54162738,16542738,62154738,15624738,62154738,24615738,61245738,24615738,45261738,26451738,45261738,51426738,42516738,51426738,16542738,67514238,51674238,67514238,74651238,65741238,74651238,41765238,76415238,41765238,15476238,47156238,15476238,56147238,14567238,56147238,67514238,72561438,56721438,72561438,21756438,75216438,21756438,16275438,27165438,16275438,65127438,12657438,65127438,57612438,61572438,57612438,72561438,24576138,57246138,24576138,46257138,25467138,46257138,67425138,42675138,67425138,75642138,64752138,75642138,52764138,76524138,52764138,24576138,41527638,52417638,41527638,17452638,45172638,17452638,72145638,14725638,72145638,25714638,71254638,25714638,54271638,27541638,54271638,41527638,16542738,63541278,54631278,63541278,31654278,65314278,31654278,14365278,36145278,14365278,45136278,13456278,45136278,56413278,41563278,56413278,63541278,32564178,56324178,32564178,24356178,35246178,24356178,46235178,23465178,46235178,65423178,42653178,65423178,53642178,64532178,53642178,32564178,21536478,53216478,21536478,16253478,25163478,16253478,63125478,12635478,63125478,35612478,61352478,35612478,52361478,36521478,52361478,21536478,14523678,52143678,14523678,43152678,15432678,43152678,32415678,41325678,32415678,25341678,34251678,25341678,51234678,23514678,51234678,14523678,46512378,51462378,46512378,62451378,45621378,62451378,21645378,64215378,21645378,15264378,26154378,15264378,54126378,12546378,54126378,46512378,63541278,37546128,54376128,37546128,76354128,35764128,76354128,64735128,73645128,64735128,45673128,67453128,45673128,53467128,46537128,53467128,37546128,71534628,53714628,71534628,14753628,75143628,14753628,43175628,17435628,43175628,35417628,41357628,35417628,57341628,34571628,57341628,71534628,16573428,57163428,16573428,63157428,15637428,63157428,37615428,61375428,37615428,75361428,36751428,75361428,51736428,73516428,51736428,16573428,64517328,51647328,64517328,47651328,65471328,47651328,71465328,46715328,71465328,15746328,74156328,15746328,56174328,17564328,56174328,64517328,43561728,56431728,43561728,31456728,45316728,31456728,16345728,34165728,16345728,65134728,13654728,65134728,54613728,61543728,54613728,43561728,37546128,72543618,54723618,72543618,23754618,75234618,23754618,34275618,27345618,34275618,45327618,32457618,45327618,57432618,43572618,57432618,72543618,26574318,57264318,26574318,64257318,25647318,64257318,47625318,62475318,47625318,75462318,46752318,75462318,52746318,74526318,52746318,26574318,63527418,52637418,63527418,37652418,65372418,37652418,72365418,36725418,72365418,25736418,73256418,25736418,56273418,27563418,56273418,63527418,34562718,56342718,34562718,42356718,35426718,42356718,26435718,43265718,26435718,65243718,24653718,65243718,53624718,62534718,53624718,34562718,47536218,53476218,47536218,76453218,45763218,76453218,63745218,74635218,63745218,35674218,67354218,35674218,54367218,36547218,54367218,47536218,72543618,21547368,54217368,21547368,17254368,25174368,17254368,74125368,12745368,74125368,45712368,71452368,45712368,52471368,47521368,52471368,21547368,13524768,36521478,68521347,52681347,68521347,81652347,65812347,81652347,12865347,86125347,12865347,25186347,18256347,25186347,56218347,21568347,56218347,68521347,83562147,56832147,83562147,32856147,85326147,32856147,26385147,38265147,26385147,65238147,23658147,65238147,58623147,62583147,58623147,83562147,31586247,58316247,31586247,16358247,35168247,16358247,68135247,13685247,68135247,85613247,61853247,85613247,53861247,86531247,53861247,31586247,12538647,53128647,12538647,28153647,15283647,28153647,83215647,21835647,83215647,35821647,82351647,35821647,51382647,38512647,51382647,12538647,26513847,51263847,26513847,63251847,25631847,63251847,31625847,62315847,31625847,15362847,36152847,15362847,52136847,13526847,52136847,26513847,68521347,84526137,52846137,84526137,46852137,85462137,46852137,62485137,48625137,62485137,25648137,64258137,25648137,58264137,26584137,58264137,84526137,41582637,58412637,41582637,12458637,45128637,12458637,28145637,14285637,28145637,85214637,21854637,85214637,54821637,82541637,54821637,41582637,16548237,54168237,16548237,68154237,15684237,68154237,84615237,61845237,84615237,45861237,86451237,45861237,51486237,48516237,51486237,16548237,62514837,51624837,62514837,24651837,65241837,24651837,41265837,26415837,41265837,15426837,42156837,15426837,56142837,14562837,56142837,62514837,28561437,56281437,28561437,81256437,25816437,81256437,16825437,82165437,16825437,65182437,18652437,65182437,52618437,61528437,52618437,28561437,84526137,43528617,52438617,43528617,38452617,45382617,38452617,82345617,34825617,82345617,25834617,83254617,25834617,54283617,28543617,54283617,43528617,36542817,54362817,36542817,62354817,35624817,62354817,24635817,63245817,24635817,45263817,26453817,45263817,53426817,42536817,53426817,36542817,68534217,53684217,68534217,84653217,65843217,84653217,43865217,86435217,43865217,35486217,48356217,35486217,56348217,34568217,56348217,68534217,82563417,56823417,82563417,23856417,85236417,23856417,36285417,28365417,36285417,65328417,32658417,65328417,58632417,63582417,58632417,82563417,24586317,58246317,24586317,46258317,25468317,46258317,68425317,42685317,68425317,85642317,64852317,85642317,52864317,86524317,52864317,24586317,43528617,31524867,52314867,31524867,14352867,35142867,14352867,42135867,13425867,42135867,25413867,41253867,25413867,53241867,24531867,53241867,31524867,18532467,53182467,18532467,82153467,15823467,82153467,23815467,81235467,23815467,35281467,28351467,35281467,51328467,32518467,51328467,18532467,84513267,51843267,84513267,43851267,85431267,43851267,31485267,48315267,31485267,15348267,34158267,15348267,58134267,13584267,58134267,84513267,42581367,58421367,42581367,21458367,45218367,21458367,18245367,24185367,18245367,85124367,12854367,85124367,54812367,81542367,54812367,42581367,23548167,54238167,23548167,38254167,25384167,38254167,84325167,32845167,84325167,45832167,83452167,45832167,52483167,48523167,52483167,23548167,31524867,16523487,67523148,52673148,67523148,73652148,65732148,73652148,32765148,76325148,32765148,25376148,37256148,25376148,56237148,23567148,56237148,67523148,71562348,56712348,71562348,12756348,75126348,12756348,26175348,17265348,26175348,65217348,21657348,65217348,57621348,62571348,57621348,71562348,13576248,57136248,13576248,36157248,15367248,36157248,67315248,31675248,67315248,75631248,63751248,75631248,51763248,76513248,51763248,13576248,32517648,51327648,32517648,27351648,35271648,27351648,71235648,23715648,71235648,15723648,72153648,15723648,53172648,17532648,53172648,32517648,26531748,53261748,26531748,61253748,25613748,61253748,13625748,62135748,13625748,35162748,16352748,35162748,52316748,31526748,52316748,26531748,67523148,74526318,48526731,52486731,48526731,86452731,45862731,86452731,62845731,84625731,62845731,25684731,68254731,25684731,54268731,26548731,54268731,48526731,87542631,54872631,87542631,72854631,85724631,72854631,24785631,78245631,24785631,45278631,27458631,45278631,58427631,42587631,58427631,87542631,76584231,58764231,76584231,64758231,75648231,64758231,48675231,67485231,48675231,85467231,46857231,85467231,57846231,84576231,57846231,76584231,62578431,57628431,62578431,28657431,65287431,28657431,87265431,26875431,87265431,75826431,82756431,75826431,56782431,78562431,56782431,62578431,24567831,56247831,24567831,47256831,25476831,47256831,76425831,42765831,76425831,65742831,74652831,65742831,52674831,67524831,52674831,24567831,48526731,83524671,31524867,62475831,47625831,62475831,25647831,64257831,25647831,57264831,26574831,57264831,74526831,52746831,74526831,46752831,75462831,46752831,62475831,28467531,46287531,28467531,87246531,24876531,87246531,76824531,82764531,76824531,64782531,78642531,64782531,42678531,67428531,42678531,28467531,85426731,42856731,85426731,56842731,84562731,56842731,62584731,58624731,62584731,24658731,65248731,24658731,48265731,26485731,48265731,85426731,57482631,48572631,57482631,72548631,54728631,72548631,28754631,75284631,28754631,84275631,27845631,84275631,45827631,82457631,45827631,57482631,76458231,45768231,76458231,68745231,74685231,68745231,85674231,67854231,85674231,54867231,86547231,54867231,47586231,58476231,47586231,76458231,62475831,23476581,47236581,23476581,36247581,24367581,36247581,67324581,32674581,67324581,74632581,63742581,74632581,42763581,76423581,42763581,23476581,35427681,42357681,35427681,57342681,34572681,57342681,72534681,53724681,72534681,24753681,75243681,24753681,43275681,27435681,43275681,35427681,56432781,43562781,56432781,62543781,54623781,62543781,23654781,65234781,23654781,34265781,26345781,34265781,45326781,32456781,45326781,56432781,67453281,45673281,67453281,73645281,64735281,73645281,35764281,76354281,35764281,54376281,37546281,54376281,46537281,53467281,46537281,67453281,72465381,46725381,72465381,25746381,74256381,25746381,56274381,27564381,56274381,64527381,52647381,64527381,47652381,65472381,47652381,72465381,23476581,38472651,47382651,38472651,82347651,34827651,82347651,27834651,83274651,27834651,74283651,28743651,74283651,43728651,72438651,43728651,38472651,86437251,43867251,86437251,67843251,84673251,67843251,73684251,68734251,73684251,34768251,76348251,34768251,48376251,37486251,48376251,86437251,62483751,48623751,62483751,23648751,64238751,23648751,38264751,26384751,38264751,84326751,32846751,84326751,46832751,83462751,46832751,62483751,27468351,46278351,27468351,78246351,24786351,78246351,86724351,72864351,86724351,64872351,87642351,64872351,42687351,68427351,42687351,27468351,73426851,42736851,73426851,36742851,74362851,36742851,62374851,37624851,62374851,24637851,63247851,24637851,47263851,26473851,47263851,73426851,38472651,85473261,47853261,85473261,53847261,84537261,53847261,37584261,58374261,37584261,74358261,35748261,74358261,48735261,73485261,48735261,85473261,52487361,48527361,52487361,27548361,54278361,27548361,78254361,25784361,78254361,84725361,72845361,84725361,45872361,87452361,45872361,52487361,23458761,45238761,23458761,38245761,24385761,38245761,85324761,32854761,85324761,54832761,83542761,54832761,42583761,58423761,42583761,23458761,37425861,42375861,37425861,75342861,34752861,75342861,52734861,73524861,52734861,24573861,57243861,24573861,43257861,25437861,43257861,37425861,78432561,43782561,78432561,82743561,74823561,82743561,23874561,87234561,23874561,34287561,28347561,34287561,47328561,32478561,47328561,78432561,85473261,56478321,47568321,56478321,68547321,54687321,68547321,87654321,65874321,87654321,74865321,86745321,74865321,45786321,78456321,45786321,56478321,63457821,45637821,63457821,37645821,64375821,37645821,75364821,36754821,75364821,54736821,73546821,54736821,46573821,57463821,46573821,63457821,38465721,46385721,38465721,85346721,34856721,85346721,56834721,83564721,56834721,64583721,58643721,64583721,43658721,65438721,43658721,38465721,87436521,43876521,87436521,76843521,84763521,76843521,63784521,78634521,63784521,34678521,67348521,34678521,48367521,36487521,48367521,87436521,75483621,48753621,75483621,53748621,74538621,53748621,38574621,57384621,38574621,84357621,35847621,84357621,47835621,83475621,47835621,75483621,56478321,62475831,21475683,47215683,21475683,15247683,24157683,15247683,57124683,12574683,57124683,74512683,51742683,74512683,42751683,75421683,42751683,21475683,16427583,42167583,16427583,67142583,14672583,67142583,72614583,61724583,72614583,24761583,76241583,24761583,41276583,27416583,41276583,16427583,65412783,41652783,65412783,52641783,64521783,52641783,21564783,56214783,21564783,14256783,25146783,14256783,46125783,12465783,46125783,65412783,57461283,46571283,57461283,71546283,54716283,71546283,16754283,75164283,16754283,64175283,17645283,64175283,45617283,61457283,45617283,57461283,72456183,45726183,72456183,26745183,74265183,26745183,65274183,27654183,65274183,54627183,62547183,54627183,47562183,56472183,47562183,72456183,21475683,18472563,47182563,18472563,82147563,14827563,82147563,27814563,81274563,27814563,74281563,28741563,74281563,41728563,72418563,41728563,18472563,85417263,41857263,85417263,57841263,84571263,57841263,71584263,58714263,71584263,14758263,75148263,14758263,48175263,17485263,48175263,85417263,52481763,48521763,52481763,21548763,54218763,21548763,18254763,25184763,18254763,84125763,12845763,84125763,45812763,81452763,45812763,52481763,27458163,45278163,27458163,78245163,24785163,78245163,85724163,72854163,85724163,54872163,87542163,54872163,42587163,58427163,42587163,27458163,71425863,42715863,71425863,15742863,74152863,15742863,52174863,17524863,52174863,24517863,51247863,24517863,47251863,25471863,47251863,71425863,18472563,86471253,47861253,86471253,61847253,84617253,61847253,17684253,68174253,17684253,74168253,16748253,74168253,48716253,71486253,48716253,86471253,62487153,48627153,62487153,27648153,64278153,27648153,78264153,26784153,78264153,84726153,72846153,84726153,46872153,87462153,46872153,62487153,21468753,46218753,21468753,18246753,24186753,18246753,86124753,12864753,86124753,64812753,81642753,64812753,42681753,68421753,42681753,21468753,17426853,42176853,17426853,76142853,14762853,76142853,62714853,71624853,62714853,24671853,67241853,24671853,41267853,26417853,41267853,17426853,78412653,41782653,78412653,82741653,74821653,82741653,21874653,87214653,21874653,14287653,28147653,14287653,47128653,12478653,47128653,78412653,86471253,65478123,47658123,65478123,58647123,64587123,58647123,87564123,56874123,87564123,74856123,85746123,74856123,46785123,78465123,46785123,65478123,51467823,46517823,51467823,17546823,54176823,17546823,76154823,15764823,76154823,64715823,71645823,64715823,45671823,67451823,45671823,51467823,18456723,45186723,18456723,86145723,14865723,86145723,65814723,81654723,65814723,54681723,68541723,54681723,41568723,56418723,41568723,18456723,87415623,41875623,87415623,75841623,84751623,75841623,51784623,78514623,51784623,14578623,57148623,14578623,48157623,15487623,48157623,87415623,76481523,48761523,76481523,61748523,74618523,61748523,18674523,67184523,18674523,84167523,16847523,84167523,47816523,81476523,47816523,76481523,65478123,52476813,47526813,52476813,26547813,54267813,26547813,67254813,25674813,67254813,74625813,62745813,74625813,45762813,76452813,45762813,52476813,28457613,45287613,28457613,87245613,24875613,87245613,75824613,82754613,75824613,54782613,78542613,54782613,42578613,57428613,42578613,28457613,86425713,42865713,86425713,65842713,84652713,65842713,52684713,68524713,52684713,24568713,56248713,24568713,48256713,25486713,48256713,86425713,67482513,48672513,67482513,72648513,64728513,72648513,28764513,76284513,28764513,84276513,27846513,84276513,46827513,82467513,46827513,67482513,75468213,46758213,75468213,58746213,74586213,58746213,86574213,57864213,86574213,64857213,85647213,64857213,47685213,68475213,47685213,75468213,52476813,21475683,13475268,67584213,58674213,67584213,74658213,65748213,74658213,48765213,76485213,48765213,85476213,47856213,85476213,56847213,84567213,56847213,67584213,72568413,56728413,72568413,28756413,75286413,28756413,86275413,27865413,86275413,65827413,82657413,65827413,57682413,68572413,57682413,72568413,24576813,57246813,24576813,46257813,25467813,46257813,67425813,42675813,67425813,75642813,64752813,75642813,52764813,76524813,52764813,24576813,48527613,52487613,48527613,87452613,45872613,87452613,72845613,84725613,72845613,25784613,78254613,25784613,54278613,27548613,54278613,48527613,86542713,54862713,86542713,62854713,85624713,62854713,24685713,68245713,24685713,45268713,26458713,45268713,58426713,42586713,58426713,86542713,67584213,71586423,58716423,71586423,16758423,75168423,16758423,68175423,17685423,68175423,85617423,61857423,85617423,57861423,86571423,57861423,71586423,14578623,42571863,57421863,42571863,21457863,45217863,21457863,17245863,24175863,17245863,75124863,12754863,75124863,54712863,71542863,54712863,42571863,28547163,54287163,28547163,87254163,25874163,87254163,74825163,82745163,74825163,45782163,78452163,45782163,52478163,47528163,52478163,28547163,81524763,52814763,81524763,14852763,85142763,14852763,42185763,18425763,42185763,25418763,41258763,25418763,58241763,24581763,58241763,81524763,17582463,58172463,17582463,72158463,15728463,72158463,28715463,71285463,28715463,85271463,27851463,85271463,51827463,82517463,51827463,17582463,74518263,51748263,74518263,48751263,75481263,48751263,81475263,47815263,81475263,15847263,84157263,15847263,57184263,18574263,57184263,74518263,42571863,26574183,57264183,26574183,64257183,25647183,64257183,47625183,62475183,47625183,75462183,46752183,75462183,52746183,74526183,52746183,26574183,61527483,52617483,61527483,17652483,65172483,17652483,72165483,16725483,72165483,25716483,71256483,25716483,56271483,27561483,56271483,61527483,14562783,56142783,14562783,42156783,15426783,42156783,26415783,41265783,26415783,65241783,24651783,65241783,51624783,62514783,51624783,14562783,47516283,51476283,47516283,76451283,45761283,76451283,61745283,74615283,61745283,15674283,67154283,15674283,54167283,16547283,54167283,47516283,72541683,54721683,72541683,21754683,75214683,21754683,14275683,27145683,14275683,45127683,12457683,45127683,57412683,41572683,57412683,72541683,26574183,68572413,83572641,57832641,83572641,32857641,85327641,32857641,27385641,38275641,27385641,75238641,23758641,75238641,58723641,72583641,58723641,83572641,36587241,58367241,36587241,67358241,35678241,67358241,78635241,63785241,78635241,85763241,76853241,85763241,53876241,87536241,53876241,36587241,62538741,53628741,62538741,28653741,65283741,28653741,83265741,26835741,83265741,35826741,82356741,35826741,56382741,38562741,56382741,62538741,27563841,56273841,27563841,73256841,25736841,73256841,36725841,72365841,36725841,65372841,37652841,65372841,52637841,63527841,52637841,27563841,78526341,52786341,78526341,86752341,75862341,86752341,62875341,87625341,62875341,25687341,68257341,25687341,57268341,26578341,57268341,78526341,83572641,34578261,41578326,57418326,41578326,18457326,45187326,18457326,87145326,14875326,87145326,75814326,81754326,75814326,54781326,78541326,54781326,41578326,13547826,32541786,54321786,32541786,21354786,35214786,21354786,14235786,23145786,14235786,45123786,12453786,45123786,53412786,41532786,53412786,32541786,27534186,53274186,27534186,74253186,25743186,74253186,43725186,72435186,43725186,35472186,47352186,35472186,52347186,34527186,52347186,27534186,71523486,52713486,71523486,13752486,75132486,13752486,32175486,17325486,32175486,25317486,31257486,25317486,57231486,23571486,57231486,71523486,14572386,57142386,14572386,42157386,15427386,42157386,27415386,41275386,27415386,75241386,24751386,75241386,51724386,72514386,51724386,14572386,43517286,51437286,43517286,37451286,45371286,37451286,71345286,34715286,71345286,15734286,73154286,15734286,54173286,17543286,54173286,43517286,32541786,28543176,54283176,28543176,83254176,25834176,83254176,34825176,82345176,34825176,45382176,38452176,45382176,52438176,43528176,52438176,28543176,81524376,52814376,81524376,14852376,85142376,14852376,42185376,18425376,42185376,25418376,41258376,25418376,58241376,24581376,58241376,81524376,13582476,58132476,13582476,32158476,15328476,32158476,28315476,31285476,28315476,85231476,23851476,85231476,51823476,82513476,51823476,13582476,34518276,51348276,34518276,48351276,35481276,48351276,81435276,43815276,81435276,15843276,84153276,15843276,53184276,18534276,53184276,34518276,42531876,53421876,42531876,21453876,45213876,21453876,13245876,24135876,13245876,35124876,12354876,35124876,54312876,31542876,54312876,42531876,28543176,87542316,54872316,87542316,72854316,85724316,72854316,24785316,78245316,24785316,45278316,27458316,45278316,58427316,42587316,58427316,87542316,73584216,58734216,73584216,34758216,75348216,34758216,48375216,37485216,48375216,85437216,43857216,85437216,57843216,84573216,57843216,73584216,32578416,57328416,32578416,28357416,35287416,28357416,87235416,23875416,87235416,75823416,82753416,75823416,53782416,78532416,53782416,32578416,24537816,53247816,24537816,47253816,25473816,47253816,73425816,42735816,73425816,35742816,74352816,35742816,52374816,37524816,52374816,24537816,48523716,52483716,48523716,83452716,45832716,83452716,32845716,84325716,32845716,25384716,38254716,25384716,54238716,23548716,54238716,48523716,87542316,71548236,54718236,71548236,18754236,75184236,18754236,84175236,17845236,84175236,45817236,81457236,45817236,57481236,48571236,57481236,71548236,12574836,57124836,12574836,24157836,15247836,24157836,47215836,21475836,47215836,75421836,42751836,75421836,51742836,74512836,51742836,12574836,28517436,51287436,28517436,87251436,25871436,87251436,71825436,82715436,71825436,15782436,78152436,15782436,52178436,17528436,52178436,28517436,84521736,52841736,84521736,41852736,85412736,41852736,12485736,48125736,12485736,25148736,14258736,25148736,58214736,21584736,58214736,84521736,47582136,58472136,47582136,72458136,45728136,72458136,28745136,74285136,28745136,85274136,27854136,85274136,54827136,82547136,54827136,47582136,71548236,13547826,36547182,54367182,36547182,67354182,35674182,67354182,74635182,63745182,74635182,45763182,76453182,45763182,53476182,47536182,53476182,36547182,61534782,53614782,61534782,14653782,65143782,14653782,43165782,16435782,43165782,35416782,41356782,35416782,56341782,34561782,56341782,61534782,17563482,56173482,17563482,73156482,15736482,73156482,36715482,71365482,36715482,65371482,37651482,65371482,51637482,63517482,51637482,17563482,74516382,51746382,74516382,46751382,75461382,46751382,61475382,47615382,61475382,15647382,64157382,15647382,57164382,16574382,57164382,74516382,43571682,57431682,43571682,31457682,45317682,31457682,17345682,34175682,17345682,75134682,13754682,75134682,54713682,71543682,54713682,43571682,36547182,68543712,54683712,68543712,83654712,65834712,83654712,34865712,86345712,34865712,45386712,38456712,45386712,56438712,43568712,56438712,68543712,87564312,56874312,87564312,74856312,85746312,74856312,46785312,78465312,46785312,65478312,47658312,65478312,58647312,64587312,58647312,87564312,73586412,58736412,73586412,36758412,75368412,36758412,68375412,37685412,68375412,85637412,63857412,85637412,57863412,86573412,57863412,73586412,34578612,57348612,34578612,48357612,35487612,48357612,87435612,43875612,87435612,75843612,84753612,75843612,53784612,78534612,53784612,34578612,46537812,53467812,46537812,67453812,45673812,67453812,73645812,64735812,73645812,35764812,76354812,35764812,54376812,37546812,54376812,46537812,68543712,81546372,54816372,81546372,16854372,85164372,16854372,64185372,18645372,64185372,45618372,61458372,45618372,58461372,46581372,58461372,81546372,13584672,58134672,13584672,34158672,15348672,34158672,48315672,31485672,48315672,85431672,43851672,85431672,51843672,84513672,51843672,13584672,36518472,51368472,36518472,68351472,35681472,68351472,81635472,63815472,81635472,15863472,86153472,15863472,53186472,18536472,53186472,36518472,64531872,53641872,64531872,41653872,65413872,41653872,13465872,46135872,13465872,35146872,14356872,35146872,56314872,31564872,56314872,64531872,48563172,56483172,48563172,83456172,45836172,83456172,36845172,84365172,36845172,65384172,38654172,65384172,54638172,63548172,54638172,48563172,81546372,17548632,54178632,17548632,78154632,15784632,78154632,84715632,71845632,84715632,45871632,87451632,45871632,51487632,48517632,51487632,17548632,76514832,51764832,76514832,64751832,75641832,64751832,41675832,67415832,41675832,15467832,46157832,15467832,57146832,14576832,57146832,76514832,68571432,57681432,68571432,81657432,65817432,81657432,17865432,86175432,17865432,75186432,18756432,75186432,56718432,71568432,56718432,68571432,84567132,56847132,84567132,47856132,85476132,47856132,76485132,48765132,76485132,65748132,74658132,65748132,58674132,67584132,58674132,84567132,41586732,58416732,41586732,16458732,45168732,16458732,68145732,14685732,68145732,85614732,61854732,85614732,54861732,86541732,54861732,41586732,17548632,73541862,54731862,73541862,31754862,75314862,31754862,14375862,37145862,14375862,45137862,13457862,45137862,57413862,41573862,57413862,73541862,38574162,57384162,38574162,84357162,35847162,84357162,47835162,83475162,47835162,75483162,48753162,75483162,53748162,74538162,53748162,38574162,81537462,53817462,81537462,17853462,85173462,17853462,73185462,18735462,73185462,35718462,71358462,35718462,58371462,37581462,58371462,81537462,14583762,58143762,14583762,43158762,15438762,43158762,38415762,41385762,38415762,85341762,34851762,85341762,51834762,83514762,51834762,14583762,47518362,51478362,47518362,78451362,45781362,78451362,81745362,74815362,81745362,15874362,87154362,15874362,54187362,18547362,54187362,47518362,73541862,36547182,62547318,54627318,62547318,27654318,65274318,27654318,74265318,26745318,74265318,45726318,72456318,45726318,56472318,47562318,56472318,62547318,23564718,56234718,23564718,34256718,25346718,34256718,46325718,32465718,46325718,65432718,43652718,65432718,52643718,64523718,52643718,23564718,37526418,52376418,37526418,76352418,35762418,76352418,62735418,73625418,62735418,25673418,67253418,25673418,53267418,26537418,53267418,37526418,74532618,53742618,74532618,42753618,75423618,42753618,23475618,47235618,23475618,35247618,24357618,35247618,57324618,32574618,57324618,74532618,46573218,57463218,46573218,63457218,45637218,63457218,37645218,64375218,37645218,75364218,36754218,75364218,54736218,73546218,54736218,46573218,62547318,21546738,54216738,21546738,16254738,25164738,16254738,64125738,12645738,64125738,45612738,61452738,45612738,52461738,46521738,52461738,21546738,17524638,52174638,17524638,74152638,15742638,74152638,42715638,71425638,42715638,25471638,47251638,25471638,51247638,24517638,51247638,17524638,76512438,51762438,76512438,62751438,75621438,62751438,21675438,67215438,21675438,15267438,26157438,15267438,57126438,12576438,57126438,76512438,64571238,57641238,64571238,41657238,65417238,41657238,17465238,46175238,17465238,75146238,14756238,75146238,56714238,71564238,56714238,64571238,42567138,56427138,42567138,27456138,45276138,27456138,76245138,24765138,76245138,65724138,72654138,65724138,54672138,67542138,54672138,42567138,21546738,13542678,54132678,13542678,32154678,15324678,32154678,24315678,31245678,24315678,45231678,23451678,45231678,51423678,42513678,51423678,13542678,36514278,51364278,36514278,64351278,35641278,64351278,41635278,63415278,41635278,15463278,46153278,15463278,53146278,14536278,53146278,36514278,62531478,53621478,62531478,21653478,65213478,21653478,13265478,26135478,13265478,35126478,12356478,35126478,56312478,31562478,56312478,62531478,24563178,56243178,24563178,43256178,25436178,43256178,36425178,42365178,36425178,65342178,34652178,65342178,52634178,63524178,52634178,24563178,41526378,52416378,41526378,16452378,45162378,16452378,62145378,14625378,62145378,25614378,61254378,25614378,54261378,26541378,54261378,41526378,13542678,37541268,54371268,37541268,71354268,35714268,71354268,14735268,73145268,14735268,45173268,17453268,45173268,53417268,41537268,53417268,37541268,72534168,53724168,72534168,24753168,75243168,24753168,43275168,27435168,43275168,35427168,42357168,35427168,57342168,34572168,57342168,72534168,21573468,57213468,21573468,13257468,25137468,13257468,37125468,12375468,37125468,75312468,31752468,75312468,52731468,73521468,52731468,21573468,14527368,52147368,14527368,47152368,15472368,47152368,72415368,41725368,72415368,25741368,74251368,25741368,51274368,27514368,51274368,14527368,43512768,51432768,43512768,32451768,45321768,32451768,21345768,34215768,21345768,15234768,23154768,15234768,54123768,12543768,54123768,43512768,37541268,76543128,68543712,14325768,32145768,14325768,45132768,13452768,45132768,52413768,41523768,52413768,23541768,54231768,23541768,31254768,25314768,31254768,14325768,47312568,31472568,47312568,72431568,43721568,72431568,21743568,74213568,21743568,13274568,27134568,13274568,34127568,12347568,34127568,47312568,75341268,34751268,75341268,51734268,73514268,51734268,14573268,57143268,14573268,43157268,15437268,43157268,37415268,41375268,37415268,75341268,52374168,37524168,52374168,24537168,53247168,24537168,47253168,25473168,47253168,73425168,42735168,73425168,35742168,74352168,35742168,52374168,21357468,35217468,21357468,17235468,23175468,17235468,75123468,12753468,75123468,53712468,71532468,53712468,32571468,57321468,32571468,21357468,14325768,46321578,32461578,46321578,61432578,43612578,61432578,12643578,64123578,12643578,23164578,16234578,23164578,34216578,21346578,34216578,46321578,65342178,57346218,34576218,57346218,76534218,53764218,76534218,64753218,75643218,64753218,43675218,67435218,43675218,35467218,46357218,35467218,57346218,72354618,35724618,72354618,24735618,73245618,24735618,45273618,27453618,45273618,53427618,42537618,53427618,37542618,54372618,37542618,72354618,26375418,37265418,26375418,65237418,23657418,65237418,57623418,62573418,57623418,73562418,56732418,73562418,32756418,75326418,32756418,26375418,64327518,32647518,64327518,47632518,63472518,47632518,72463518,46723518,72463518,23746518,74236518,23746518,36274518,27364518,36274518,64327518,45362718,36452718,45362718,52436718,43526718,52436718,26543718,54263718,26543718,63254718,25634718,63254718,34625718,62345718,34625718,45362718,57346218,71345628,34715628,71345628,15734628,73154628,15734628,54173628,17543628,54173628,43517628,51437628,43517628,37451628,45371628,37451628,71345628,16374528,37164528,16374528,64137528,13647528,64137528,47613528,61473528,47613528,73461528,46731528,73461528,31746528,74316528,31746528,16374528,65317428,31657428,65317428,57631428,63571428,57631428,71563428,56713428,71563428,13756428,75136428,13756428,36175428,17365428,36175428,65317428,54361728,36541728,54361728,41536728,53416728,41536728,16453728,45163728,16453728,63145728,14635728,63145728,35614728,61354728,35614728,54361728,47356128,35476128,47356128,76435128,43765128,76435128,65743128,74653128,65743128,53674128,67534128,53674128,34567128,56347128,34567128,47356128,71345628,12347568,28347156,34287156,28347156,87234156,23874156,87234156,74823156,82743156,74823156,43782156,78432156,43782156,32478156,47328156,32478156,28347156,81324756,32814756,81324756,14832756,83142756,14832756,42183756,18423756,42183756,23418756,41238756,23418756,38241756,24381756,38241756,81324756,17382456,38172456,17382456,72138456,13728456,72138456,28713456,71283456,28713456,83271456,27831456,83271456,31827456,82317456,31827456,17382456,74318256,31748256,74318256,48731256,73481256,48731256,81473256,47813256,81473256,13847256,84137256,13847256,37184256,18374256,37184256,74318256,42371856,37421856,42371856,21437856,43217856,21437856,17243856,24173856,17243856,73124856,12734856,73124856,34712856,71342856,34712856,42371856,28347156,85342716,34852716,85342716,52834716,83524716,52834716,24583716,58243716,24583716,43258716,25438716,43258716,38425716,42385716,38425716,85342716,57384216,38574216,57384216,74538216,53748216,74538216,48753216,75483216,48753216,83475216,47835216,83475216,35847216,84357216,35847216,57384216,72358416,35728416,72358416,28735416,73285416,28735416,85273416,27853416,85273416,53827416,82537416,53827416,37582416,58372416,37582416,72358416,24375816,37245816,24375816,45237816,23457816,45237816,57423816,42573816,57423816,73542816,54732816,73542816,32754816,75324816,32754816,24375816,48327516,32487516,48327516,87432516,43872516,87432516,72843516,84723516,72843516,23784516,78234516,23784516,34278516,27348516,34278516,48327516,85342716,51348276,16348527,34168527,16348527,68134527,13684527,68134527,84613527,61843527,84613527,43861527,86431527,43861527,31486527,48316527,31486527,16348527,65314827,31654827,65314827,54631827,63541827,54631827,41563827,56413827,41563827,13456827,45136827,13456827,36145827,14365827,36145827,65314827,58361427,36581427,58361427,81536427,53816427,81536427,16853427,85163427,16853427,63185427,18635427,63185427,35618427,61358427,35618427,58361427,84356127,35846127,84356127,46835127,83465127,46835127,65483127,48653127,65483127,53648127,64538127,53648127,38564127,56384127,38564127,84356127,41385627,38415627,41385627,15438627,43158627,15438627,58143627,14583627,58143627,83514627,51834627,83514627,34851627,85341627,34851627,41385627,16348527,62341857,34621857,62341857,21634857,63214857,21634857,14263857,26143857,14263857,43126857,12436857,43126857,36412857,41362857,36412857,62341857,28364157,36284157,28364157,84236157,23846157,84236157,46823157,82463157,46823157,63482157,48632157,63482157,32648157,64328157,32648157,28364157,81326457,32816457,81326457,16832457,83162457,16832457,62183457,18623457,62183457,23618457,61238457,23618457,38261457,26381457,38261457,81326457,14382657,38142657,14382657,42138657,13428657,42138657,28413657,41283657,28413657,83241657,24831657,83241657,31824657,82314657,31824657,14382657,46318257,31468257,46318257,68431257,43681257,68431257,81643257,64813257,81643257,13864257,86134257,13864257,34186257,18346257,34186257,46318257,62341857,25346187,34256187,25346187,56234187,23564187,56234187,64523187,52643187,64523187,43652187,65432187,43652187,32465187,46325187,32465187,25346187,51324687,32514687,51324687,14532687,53142687,14532687,42153687,15423687,42153687,23415687,41235687,23415687,35241687,24351687,35241687,51324687,16352487,35162487,16352487,62135487,13625487,62135487,25613487,61253487,25613487,53261487,26531487,53261487,31526487,52316487,31526487,16352487,64315287,31645287,64315287,45631287,63451287,45631287,51463287,46513287,51463287,13546287,54136287,13546287,36154287,15364287,36154287,64315287,42361587,36421587,42361587,21436587,43216587,21436587,16243587,24163587,16243587,63124587,12634587,63124587,34612587,61342587,34612587,42361587,25346187,58342617,34582617,58342617,82534617,53824617,82534617,24853617,85243617,24853617,43285617,28435617,43285617,35428617,42358617,35428617,58342617,86354217,35864217,86354217,64835217,83645217,64835217,45683217,68453217,45683217,53468217,46538217,53468217,38546217,54386217,38546217,86354217,62385417,38625417,62385417,25638417,63258417,25638417,58263417,26583417,58263417,83526417,52836417,83526417,36852417,85362417,36852417,62385417,24368517,36248517,24368517,48236517,23486517,48236517,86423517,42863517,86423517,63842517,84632517,63842517,32684517,68324517,32684517,24368517,45326817,32456817,45326817,56432817,43562817,56432817,62543817,54623817,62543817,23654817,65234817,23654817,34265817,26345817,34265817,45326817,58342617,81345267,34815267,81345267,15834267,83154267,15834267,54183267,18543267,54183267,43518267,51438267,43518267,38451267,45381267,38451267,81345267,12384567,38124567,12384567,24138567,13248567,24138567,48213567,21483567,48213567,83421567,42831567,83421567,31842567,84312567,31842567,12384567,25318467,31258467,25318467,58231467,23581467,58231467,81523467,52813467,81523467,13852467,85132467,13852467,32185467,18325467,32185467,25318467,54321867,32541867,54321867,41532867,53412867,41532867,12453867,45123867,12453867,23145867,14235867,23145867,35214867,21354867,35214867,54321867,48352167,35482167,48352167,82435167,43825167,82435167,25843167,84253167,25843167,53284167,28534167,53284167,34528167,52348167,34528167,48352167,81345267,16348527,67348152,34678152,67348152,78634152,63784152,78634152,84763152,76843152,84763152,43876152,87436152,43876152,36487152,48367152,36487152,67348152,71364852,36714852,71364852,14736852,73146852,14736852,46173852,17463852,46173852,63417852,41637852,63417852,37641852,64371852,37641852,71364852,18376452,37186452,18376452,86137452,13867452,86137452,67813452,81673452,67813452,73681452,68731452,73681452,31768452,76318452,31768452,18376452,84317652,31847652,84317652,47831652,83471652,47831652,71483652,48713652,71483652,13748652,74138652,13748652,38174652,17384652,38174652,84317652,46381752,38461752,46381752,61438752,43618752,61438752,18643752,64183752,18643752,83164752,16834752,83164752,34816752,81346752,34816752,46381752,67348152,75346812,34756812,75346812,56734812,73564812,56734812,64573812,57643812,64573812,43657812,65437812,43657812,37465812,46375812,37465812,75346812,58374612,37584612,58374612,84537612,53847612,84537612,47853612,85473612,47853612,73485612,48735612,73485612,35748612,74358612,35748612,58374612,86357412,35867412,86357412,67835412,83675412,67835412,75683412,68753412,75683412,53768412,76538412,53768412,38576412,57386412,38576412,86357412,64385712,38645712,64385712,45638712,63458712,45638712,58463712,46583712,58463712,83546712,54836712,83546712,36854712,85364712,36854712,64385712,47368512,36478512,47368512,78436512,43786512,78436512,86743512,74863512,86743512,63874512,87634512,63874512,34687512,68347512,34687512,47368512,75346812,51347682,12347568,64783512,78643512,64783512,43678512,67438512,43678512,38467512,46387512,38467512,87346512,34876512,87346512,76834512,83764512,76834512,64783512,45768312,76458312,45768312,58476312,47586312,58476312,86547312,54867312,86547312,67854312,85674312,67854312,74685312,68745312,74685312,45768312,53746812,74536812,53746812,36574812,57364812,36574812,64357812,35647812,64357812,47635812,63475812,47635812,75463812,46753812,75463812,53746812,38754612,75384612,38754612,84375612,37845612,84375612,45837612,83457612,45837612,57483612,48573612,57483612,73548612,54738612,73548612,38754612,86735412,73865412,86735412,65873412,87653412,65873412,53687412,68537412,53687412,37568412,56378412,37568412,78356412,35786412,78356412,86735412,64783512,41786352,78416352,41786352,16478352,47168352,16478352,68147352,14687352,68147352,87614352,61874352,87614352,74861352,86741352,74861352,41786352,13748652,35741862,52741386,74521386,52741386,21574386,57214386,21574386,14257386,25147386,14257386,47125386,12475386,47125386,75412386,41752386,75412386,52741386,23754186,75234186,23754186,34275186,27345186,34275186,45327186,32457186,45327186,57432186,43572186,57432186,72543186,54723186,72543186,23754186,31725486,72315486,31725486,15372486,37152486,15372486,52137486,13527486,52137486,27513486,51273486,27513486,73251486,25731486,73251486,31725486,14732586,73142586,14732586,42173586,17423586,42173586,23417586,41237586,23417586,37241586,24371586,37241586,71324586,32714586,71324586,14732586,45713286,71453286 };int main() {ios_base::sync_with_stdio(0);cin.tie(0);// istringstream cin(R"(3//2//1 2//5//2 3 5 1 4//7//5 3 4 2 1 6 7)");for (auto x : lsit) {m2[to_string(x)] = true;}ll t; cin >> t;///////current = "12345678";//target = "";//explore();//for (auto x : m) m2[x.first] = true;//reset();///////current = "1234567";//target = "";//explore();//for (auto x : m) m2[x.first] = true;//reset();///////current = "123456";//target = "";//explore();//for (auto x : m) m2[x.first] = true;//reset();///////current = "12345";//target = "";//explore();//for (auto x : m) m2[x.first] = true;//reset();///////current = "1234";//target = "";//explore();//for (auto x : m) m2[x.first] = true;//reset();for (int i = 0; i < t; i++) {char n; cin >> n;reset();for (int j = '1'; j <= n; j++) {char x; cin >> x;current += x;target += j;}if (explore()) {cout << "YES" << "\n";for (auto x : m) {m2[x.first] = true;}} else {cout << "NO" << "\n";}}//cout << x;}
Test details
Test 1
Group: 1, 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
153 1 1 2 1 2 ... |
correct output |
---|
YES YES NO NO NO ... |
user output |
---|
(empty) |
Test 2
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 59 35 29 32 50 11 15 9 21 19 45 2... |
correct output |
---|
YES NO YES NO YES ... |
user output |
---|
(empty) |
Test 3
Group: 1, 2
Verdict: ACCEPTED
input |
---|
720 6 1 6 4 5 2 3 6 6 3 2 1 5 4 ... |
correct output |
---|
YES NO NO NO YES ... |
user output |
---|
YES NO NO NO YES ... Truncated |
Test 4
Group: 1, 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 8 7 4 2 8 6 3 5 1 8 3 8 2 7 5 4 6 1 ... |
correct output |
---|
NO NO YES NO YES ... |
user output |
---|
(empty) |