Back
Close

Parsing context-free grammar

Statement

 Goal

Difficulty: Hard
Topic: Context-free grammars, CYK algorithm, dynamic programming

Given the context-free grammar and a set of words, your task is to decide which words belong to the language defined by that grammar.

The grammar is presented in Chomsky normal form, without epsilon-rules. Non-terminal symbols are always uppercase letters, terminal symbols are always lowercase letters.
Input
Line 1: the number N of rules in the grammar
Line 2: the character START indicating the start symbol
Next N lines: rules of the grammar
Next line: the number T of testcases
Next T lines: words to parse
Output
T lines containing true if word can be successfully parsed by the grammar, false otherwise.
Constraints
0 < number of terminal symbols < 25
0 < number of nonterminal symbols < 25
0 < N < 100
0 < T < 100
0 < length of word < 100
Example
Input
6
S
S -> SS
S -> OT
T -> SC
S -> OC
O -> a
C -> b
10
ab
ba
abba
ababab
aaabbb
abaabb
a
aaabababbb
aababababbb
aaabababbabb
Output
true
false
false
true
true
true
false
true
false
true

Tags
State machineDynamic programming

Difficulty
Hard

Test cases
Well-formed brackets Test
Input
6 S S -> SS S -> OT T -> SC S -> OC O -> a C -> b 10 ab ba abba ababab aaabbb abaabb a aaabababbb aababababbb aaabababbabb
Output
true false false true true true false true false true

Well-formed 2 types of brackets Validator
Input
11 S S -> SS S -> OT T -> SC S -> OC O -> a C -> b S -> XY Y -> SZ S -> XZ X -> x Z -> z 10 xz za abxz abxzxz axabzb abaxzb z axabxzabzb xxbazababzb xaxzabxzbabz
Output
true false true true true true false true false true

Well-formed brackets - ambiguous Test
Input
15 S S -> SS X -> XS X -> SY S -> OT Y -> OT T -> SC T -> YC S -> OC S -> OD X -> OE O -> a Q -> a C -> b D -> b E -> b 10 ab ba abba ababab aaabbb abaabb a aaabababbb aababababbb aaabababbabb
Output
true false false true true true false true false true

Well-formed 2 types of brackets - ambiguous Validator
Input
22 S S -> SS W -> WS W -> SY S -> OT Y -> OT T -> SC T -> YC S -> OC S -> OD W -> OE O -> a Q -> a C -> b D -> b E -> b S -> XY Y -> SZ S -> XZ W -> XR X -> x Z -> z R -> z 10 xz za abxz abxzxz axabzb abaxzb z axabxzabzb xxbazababzb xaxzabxzbabz
Output
true false true true true true false true false true

Small grammar, many short tests Test
Input
20 B F -> a F -> b C -> c F -> d F -> e A -> DF E -> BE D -> BD B -> EF D -> CF B -> CE A -> EA D -> CC E -> EF A -> EA C -> FE F -> BF E -> FD B -> CA E -> EE 60 eeeccbcecabecbccacaacaceacda ccacdddbaecbedeaaecdc eabdcbbeaaddddadbddbaad dccddadddcacddbdaebc eddddaaeeabdeeabdbeebcae aaceacaceaacdbaacaacedbdccecc aacbadcdbebabbecdebdd aeabeeccdcedceccdedaaebbdbb bebcbebeaccbdedecacee abdabcaabbbdeadbbeeaeacdade cbbaddcabcbbeeedeabacddad aeebcdadedaebdebebbaaeaeb bcaaaaccddcdaadaecabec edbcbdddcacebcaeeddd dcdebbeeccbebbdbadccdbbddabb bbbbababdadbddbbdbdbdddde bdebbbaeabddceeddecaac bbdbdecacdceebeadbbeb aaacbbecedbdeebccbcbcebbae bebdedbaaaaedeabadeddace bebededaaabecedccbdc cecdbececdcdeddbeceeaeaae eaadcdcaaaecddcbaaacedc acbadbbaabeaeccdcaedaba baacedeededaccacecccebaaeaebbc dbebebbbbebebbeebaedcdd addcccacdbacdabcbbdbeaaec bbbbeedcbcbdacdaacdbdbdbbdedec ebaeceeeadbbbadedaac cbdaeaadaeaaddddaecaaee deddbbbcbbcdbeecdebdbc ecdceaebcaeaccbceeaceead ddeeabeeaabeebeeceacbeb edbeddcabececbdaecabaad eacbecbccacaedabadcbebebab adbcdcdcaacedbbceeda dcbababebaeeeaccdedcaaaeeab bbbbdeadabaaaaebabad ecbaecdcbbeeeceabbcb ccebdbddcdcbaecaddbeceddcbecc badaabcaeeaeadbababbda baabedaebdeaabeecccb acaccbecceeddbbbbdbdeccacebbba edecedcecabcbdcabddbedbdac abbcaaeaabeebcbdecedcabac aaecdbabbdebddabbeedc adeadacebeccebebedeaacd acebcebacedcaaccaedbec eabeccbeaececdbbccadbccd babeceeabcabcebbbcbaebeeaddbb baeabddbbeabacabbcaa baabbaeceadbddabdbdaedcc abddcbadaecdcadccbccdaadeeabc ccddeadadeeaedadeeacdd acdcbebdaebeaabcbbdc cdcccdcaaeeaeaaadabeeaac edaddabddbaebacecedeec dedaeacddecacceaceeecebdcccda badeededeaeacecbcddebcaeddc eacbeccaddaedaaeabdaa
Output
true true false false false true true true true true true false true true true false false true true false false true true true false false false false false false false true false true true true true false true true false false true false false false true false true true false false true false false false false true false true

Small grammar, many short tests II Validator
Input
21 C E -> a A -> b E -> c F -> d B -> e D -> DD C -> EE C -> AA A -> BC A -> EA C -> FB D -> AE E -> AF B -> FA E -> BB D -> CC B -> CA D -> FF B -> FF A -> EF B -> AF 60 cdecabbeccdcbbeddbbbbceed acbabecdeeddecbaaacc abeaceebcecbdcadaecbaeeae dbeecbccbdcaeacabdadeebbabb beacbddaeeddccaaebbd acbbeaeecccbbececbacbaccac ecdabcecbbdaceeebbdabdbdddc dbaebbbbdbddbdeadacbebccd ecbaacddbbebcbeebeaabcadec ebcbdaaeaebcbeeadbcbecebeaea cebecdceabccedcceabccdbedaec edeaeeaaabdddabeedad ddcabcdcbdaaaebaaaedccde adddecabeddbcabacabbab cbedceacbdcdecadebddcee cbaccecdeeabbedbecba decabbeeedddeaedbebcadaedaeae dcbdedcdeecdbbaabdaadabddb deacdbccabeabdabbbabdbad cebcecbddceaabddcbecebececeac bbabcaadaabdeeeeccaeaaabe bccaaaebcbeecbeaeaaaedd adbbddaaedcdccdbecdad ceaaabbcbecdcedbdccebdbdba eaebaebedabbcdcabcdc bbcbcdadcbbebbdebabdbcbae dedbebdbbabcbbcbdbaecabbebc ccbcdababbeabedcbebcbbadbdc caceaeeeeaaeebaebcbece cceceadcadcddaebaadcebeabeec aededeadaaebecaaceaebcec cddaacecdabdbaabcdbbddbeceeb dbadbdbbbdceceaebbebdecee eaaddaeaebaeacbacdabce aabbbcaecdbccacebbbecedebc bdcbddbcabbcaaddccdcbdbc ccadeacdeeddaaadbeadeabcb bceaceeaaccecbedcacab cbdedeabcaeedaaaebeda aacaedebdbecbdbeadcdccb bcbaaabebcccabadcadaceaeaebcae beeadadecaebabaaecdbad eedeeecedbbbbedcaecbeeae ecdcbceaeecdaeaddbaeecdab dbcbdbeaaddbccccdeebddeaace cecebaecbededebccaeec bcdcadbeaadcbdcacbddabdd dbebcebeddcbcdbacaaaebaa ccaebeabeccacaebecba bedddddccdcdeccbdcaeacdded dcebaeddcbceacdddcabaaacebedab cceeeacbaececceadcbbb dceaecdcedadcdebeccaee aabbcacceecebcdeaacedbc bedceddadeaedccaadbceea caececcaeeeebbdaebcec aadeadaecdadbdacaceb ebaaccdaeecbbeadccebc ddacdbedeedaccabceadbda baadebadbbacdbedadbdade
Output
true false false true true false true true true false false true false true true false false true true false true false true true true false true true false false false true false false true true true false false true false true false true true false true false false true true false false false false false false false true true

Large grammar, many medium tests Test
Input
50 L J -> a J -> b I -> c G -> d H -> e D -> f H -> g G -> h B -> i B -> j K -> k L -> l A -> m F -> n G -> o E -> BA C -> AG I -> FD K -> GJ B -> KD I -> BE J -> KH C -> DB C -> CF D -> JA A -> DL B -> JH G -> HF C -> JH F -> GK L -> DF E -> CB A -> ID B -> JH K -> KC E -> JH L -> AB G -> IA B -> BB K -> KF A -> BC K -> BH G -> EF I -> CH A -> BE D -> AL K -> AE L -> JE D -> LH D -> GD 80 fboimhogffkcocclejjmhhkcjchmjioigfbgkojklcbjglbobgaefijejieecaamgc kbgcfhinofkgekaefoadf enajibeebbgigehmbgmfjnjfmigamimgemmdefkeekeeaejkfifmnk heihalfnlklecefffjjohgnfmacgkgnblkggmcfabkibmaaljicidghggjinfa ikgjcfonagmignmogaeefmjimfg ammgdlbdgdkbghnahhmfhjncgamchnfifghmgdneljhdadd gdfedkbnbfabegcdjbdjeloegnaicenmegnndheg kddnjmliciaoejigmigloghaghijnkkjajjfeedjnfhkdfd ifgeghcjhbbomhgcmcngdjbbiajbbabaagebjdonlhhmalhaejommnncakagagjkgdg dkgbmkggjkggbemogkgimgokifjhnbgfaej keeemkngebgjebjkggkkggnfm gfnmlnhfkfjkdledmoecfoidhkoambkhfmdcfhjddnagfledbconkbcmnjog gkkekfnaldgbkjilghkhjghfhieinobfiakkcald cmkecflamlbeieokejagndfkgnhfmlmbemimgeekgem kkhamdamgoiheibilhencgnncmmjhjokgmoddhjh dfdjjagaee obnfdbmdiomojmbklahbbkonhkgoichmbhgifjfako jaagkanlebkbgiadlonbibglckkdnbnfnhdiaebbjdnfggbadfidbhoaomhhdbigfjlo kgcmmdnjnjmnfamenjikeekfaglekmhkfhkmagkeekegdkflkgfjkf ceockboiofbifnifbobkhemmijgijkflafemfdmm dbldamedmceblljhbnekoheljmgkjcdofoefaheodhjghlngmkmcahofof jhgbdhjmoddjlomfgeecnjdandcklhimkbkjgiegdjlkljmmdleob iegkfkfnleaeknfkgg kcjdbakohjkkaalbhncaoobojconmgmihbikmionajjohnoildbjfonoolm flkegdkngdhkfmflehknlgfkkgeejcfobge mohgiaonaikccclkicognbmaffjkkgkhfgmhkcgkmmodfloaoloinolojjodjlka dceheidjjabiodocejlajmiafafoaecdjlibmhfbnbbgamjfnafeaofelgnmlkgmgfm jkeeeggaeokeegehf baajlgibklhhkjkggeiklinljcabkgjaokchiijdejabc mij kgmjeknegnjjege lojijdhaklblmeneologogkocmajmhmeefffmjkdjdnahjalcocomhkikdkcc jjjeajiiikiiecicnffniilfnleegiglfmckbnfgdhfdedbd okgmhnjnkgffaehkcjaennicflekfggg hgblngbfenhhhlakjmghddmgbkjojbjfonfldeeklcdobbdn cnihgdncgnmnaejofkhakmhdigdadiknknnldkmcojmljoldohkbjhij kegnkggomjifigaikeemem kejkeem ehemdcmfefcngkbkmfbnhbmfammiigflblnmnliecnkjndmklijdnfefbankmajlngi naifjnfkggngmlfkegjefbgokk mogndaejmhkagokenffjnkgg mogmamhilennfjflbeggmkggigggicfdnikbgee dknmmjmmjkdknkgm cfbgfagijagikgeijiclgaejgnmimaedbnge oogjadaaaaflidhjbfombafgkblfcjacnkkkkabnjomlmlmjhc hjblbeaglaledbnlfaolodnabjabnebiabiceabcfdlaohgjankgfdg fcibmimkgejmd mjcaljcgjdgjmodndgohncigjcaimkhbheioemfkifdgdcijnffojikinlogdch echckoobknomlhacomifmfblekcnchnlddlhcmgkhimga kdacoaklgmgnjdicibkbijfhlhhoenelkohagbknhbohhecadlcgkhddofjodekedin ffccmeaogcccfgckejmhfnfcafmajfhmliiifooofdghjdkcckjoecdaiocff kgkeg iehfjnembgieegeg kamegkggkaehkfclekggfnegg kcfhgkjhaekdajebdacecdeoeneiknjfghhhggikfbjolkomkffilmc hcielhdedlcgbflekldkmeldgdcdejkddeljmkibcikilddbmoa mfbbofllfdciimgkfgmibaglagfbigfgdeddibbehlbnc ignhkebegfiieefmign khkfinagokklemaehcfjmfkeghoklejemkegmggiggg efekbljonmnoafdbnmlehakcehehldjkadnojgdlnbnmjmjhofledkcggfhajmadkga ckefkggiekge aecikcmcbjklfbdhlnldajhoajcjjohloejmjnfgiba ffdkflfjjndknij ilingjjkkannkhmbblgndfafnonmjglahhdignigkbbnhiecbmbielbbi ehkkggbggge bhaebgkeeekeoigfjiifkgeaebikfkgg hkdffojeeojfagjjekge affdklaaeningibemdke ejcjbijaoemjidlmjalnfabdhdkfhamnnfidnlnagemegbkmhfkgcbhbedgljjlbfflhbh keegemljnfjfijkkfjmdijihf ojldhnnndifckgnfbdaibecniggnmgghcgenlblcfhgalkdkihaklbbkobiojnmakokhcl bnfllfcmj kokaebenemmjmggbeembefkngmdjm kgenkegeeohkgoign eaenkdbfmaglmaoalinjheblonlfinhgiflclaodjihibbkhmbhgbgkgk abgoknjjgcmkhk kgkhkfikfhaamkemjaebgiimdghkkmhokigmfidkngm jlgjijjijggjbeni fdcmhmblcnmfinellgcjifdolaoiceaejmedjljbebeci kcedfleanmmgioonbbfieihkigoodjeecjlachjhnohjii
Output
false true true false true false false false false true true false false true false true false false true false false false true false true false false true false true true false false true false false true true false true true true true true false false true false false false false true true true false false false true true false true false true false true true true true false true false true true true false true true true false false

Large grammar, many medium tests II Validator
Input
52 H J -> a I -> b F -> c F -> d E -> e F -> f L -> g K -> h D -> i J -> j B -> k E -> l I -> m F -> n E -> o G -> p C -> GD H -> DA A -> FD A -> LB H -> FK B -> BA B -> LI A -> KA F -> HG H -> FK H -> FF F -> KA J -> BG I -> JL B -> KI J -> DB K -> JI D -> BK K -> AA E -> FH F -> AI C -> FE F -> AD B -> FG C -> KG K -> DK F -> AL L -> EI B -> KJ J -> EH B -> II I -> BA I -> CD K -> JB F -> LK K -> KF 80 mkgnkgnnlfgdennpnndbkfdeohbefjllhjjakkgaggn jbkpnbeibjmkinpeekobpbdmidfikbeegagchihjaolpgpgabm fffaganpkhojghlmkemfgkmlkhmhhhgkighmgih fihigkpidedhkpbknkhphjljgihgkdkcidi blkaaknlnlaehgiegmckcgjlfflaikjjphchdgfhimegaeegndjhp hikpknicgihiikdihgkbmmgbmmekhcikhhdihcnpkhfihjhdikhpfdfmbhemkk fffmkkhkihfkb iijcppcciglnhpbjbkcajompepghicojfpdccinfinggnnddfndgfbleh khkafncbikkhhgkbdkhfcdgkgchgkphahhhnihpinjbpfmhaomgblbklihdih chcdpkomconfdjlolakfpmndlphfaddlpgkppfodngcckgdiompnjkgfaddfcl nidpannfkibcijoclmoehmpjlncabdkmagfcmngphehnlnmcpokl jieickgedkdmbcmjilejokbfngajecpmofjemlbmlchkaiokipfiojgoddkomachph hhhdaijndfpeldfjfncfcnhjdpadmcmdmmjacclbekekebfia jhghfafbimbcpnligmkfodhcajhpffnlkbfdcplmeglb nicimagamgkcfdbkghmdfpikajggmm khihhpkhaoblmgmikghanihgmmbkjkckhikfigknkhpk hkppbgkjmnigchhcideiffpghpkhicipgkepiiphanfhcigckhgjkigkhgknkjmicipnkhhmfp fkhikkgkkpmpijjggjemhphgkgcpimmghhmlfhkhhlmk pgebkdkmjpeilboiccdiciglmoaamamemniihnnehggnefmnhfmpjabceolhfmeg kmhddejemplhlbmfecopepidlpgjjnkljngkllbgdjgikfdnlagknecbincfhaoihfdifb klojhbbljlganbdppbmobbmikbogijhalclhgjgmdfjjnlilok gmmmdolmolpngddbekkeckcdnakgodhfhapbnpllbpgenhgpkfeo clmmhgdemdgjgnchcjhajmondchfkbpfajnmpgncjme kjebpiiihgkhihobmb oihcpijmkdikiicigkf kjobmhciihgkbkgpiimkhhhnkjkgkgkiigphhgkgfphcicibdfjdicimficidlikhgkgkpip foepfnkghonefdafjhfnfdjjgaejkdoepjemndbdbl cbmhnifnkffhhkhhcifiaobbkhmpkeaghhgkhfihhgkmkhcigig gblfdjcdfmgokpbkjeemopcedobdbgcfpibaimbfmdjhokfgf olddjdcmhipeojofbpoppimgbjeokhhibldhakgicmchfcbhmdccjapjlofpiagl libmajncdkimdcblmbhmmdhkgolmbiafkabcioklknefmekopkjfdeigfaahmieopfjoc fohpgkiphhjkhhpiikhhhdibfppg bbbeaaadhnfkaljkocaicopkhifpnmkaamcjjfmfkeglmfma oobpdefnmhhnfpdcafdaghlhbghifekcaaiahmifnccaglehlflglompelfjcd hpinckhdikamikpkhkhobjjglhhcimigkbihikk cblkpllmfgaglfhfnkgmokjemolpaebakjpcmmgdead agaginfppfgkghfiglcphhomdicihniphbfpm gihgabgkidciciebhdokgkmkgkgkgk nkhfininihpihakpjggkdkhggmihpimhkikkhomajgikhjhcigpikhgkkhhhcii baghgkhcihgkhgkdjknifchkhhgkhhhnihdimmniebhdhkhomkkhhbabb ojcfjfhdikopbeknndldphjilnaacfcmheldkmoaepppbjbkdll oipohcmfdpohgmgibloemfmhfoemiocjdolboeedagejkbh kamgkhdikhkmlkfiklkhhhfijmihniiiddaghndkkpkkh mmmhcnfbkgkdigkdphfihfidikhebkagmfipiiphfpdphihhgkgkclmiihpkhidphgkip dojccokbmkmbfdmlnhiipnopbdekebcjmiamlhgbainhohpgeljnkfblikllof oaomkbnhihnipnihdipknkhblbkjbdibicicihmdgkpikakhdikhkpdphdkpmahhfigkp igkiiph ikkppiihmhihcgk micbikmpafdcdcbkimngolpgkiemgnbplgeebmobnbnnhpbdjglnne dihndibip hhjhgnicichmbjgpiidnphdidihgkhgkihihhghncbjgpii lpigmihghjpebpnphchpipgpii ckhfihgkmhaakbeknimmhdkhcffidihacihhgkmkkhiakjchhdiidjkcph ilmkhhgkomdeijmjhpkhlahdiidhbhbnnghhpinfpijkfiiamjfncikcchcei ficapaahhidijbaaphpcamhilccnggkmgpmehgpbbnfkleklilgpfhfjlimcfkonfhp odiapolohohhhinbopekbaaeldfccpkaniakjfnknocgelghpfoipedbo kbkfdohmgiiobnhbapjdilnlipidomdldgfbkckebkfabchjhogmpmcjkddpoidlchbpf afnhoknlbioeoldppfhjphhmcloejfjeklpddcddhdooocjepppmpcmdaojfgdfj khdkkpmmigghpihphkphk lmfmbdafbklbmahfpcebheafpolbhbgclponbgieihmblgfec gknkhihnkhiichoigkhbhjihhfipdhbk fkiomekljhfdnjfghdjhafghknhjmlefcdnfmiclhl fhlhmgkdpopiikhckhenffhkhkhkhci aionfpijafiddfneaimdleeknacchhpmimnggiabpnaaihcfhalnji gakgkdphdippikhbbhdfakomk lhimffefipokmpecbdifaaoinnieeplnlaccakpmhnpknadfaanekcalfd hjbjkhkfmfelfiemabadkbhnejiecfmfmleklhlpdkdljgdijhbgjelnbnnbml jkcddecfkfgkdihhgkbhgkhhcjbppi ffeppehdeknkkanedpcggebhkopbgkognhhbjnnjlkk hihadihjghkhhnigibnemhjkiobhfimnbhpiphanimkpmdi khgmkhejgkhhnhnikhicibkkpfekabhkgkhmhhhgkgkgkbhhgkh pkfepbgfoghenceiaahemklcdhclnabafbkhepfpdpdccfoppihdfobji dphkgklkgknifhdibegkkhnkgkgkomkkhkhodhfghdinpkhijlhpkjbfokhcihgkchbchegkmhebk iefhlfnljpcpagdmbbhioimjagnefplbocdlonllfbeohnibedmpebhgpomeagakabopbb kihkhkhhjaomdilmkhhigkcijegbhccicpihnkhhgk odhlnlmglgknigllgkdfmoioalbbeifefhcameakiophblglpjfjoegphhgpnhbckc fpfppbdheikgfdhmhbhghkhkfi kpgbgkbampibikmigakkfihp ipmicfmhpigjngfaileekfbldikkmhnbfpkbiikhlfhmhdlepnffinnbjbjnphbplekpje lhgopokfbehnaoljgekinkllfaelacnidpidojjoikpmlncpbpjjg
Output
false false true true false true true false true false false false false false true true true true false false false false false true true true false true false false false true false false true false true true true true false false true true false true true true false true true true true true false false false false true false true false true false true false false true false true true false true false true false true true false false

Large grammar, medium number of large tests Test
Input
70 X L -> a W -> b U -> c B -> d D -> e Q -> f E -> g T -> h B -> i J -> j V -> k S -> l C -> m J -> n R -> o N -> p N -> q O -> r J -> s J -> t K -> HV A -> HA M -> CN G -> GQ H -> NL P -> PC X -> XV F -> AL I -> KS M -> WV V -> VV I -> PS V -> HU F -> NP H -> NW G -> OB J -> UC B -> JI C -> JT B -> GD K -> CB A -> PQ A -> TF T -> QR C -> WE A -> SN D -> TW L -> QQ S -> VL H -> UP N -> HX I -> BG P -> EF E -> IG Q -> NX I -> VR K -> BW C -> LB E -> SP M -> CW V -> AC K -> SN P -> SS B -> ST J -> NA U -> XX X -> MR U -> BB U -> KC C -> NH 40 gisojlafbdssgngdscmcfjqsaornbmetendqnkfbccersqdlqmkbtqitietkqqkrdoqjilbjjepeibtljgoqqhlseodibeja tpffknhllmmqobbkobcafoqakbgaddrikkakkabkcgpgpahpgqllmmackkpbcokmboobo bkorqgpgqgllfacllmmqbbkookqbmbokpapagcgqllhglqafaafmkacmpollqbkkkkffkffqmqomabokk nqabgqobkoobo lfcekflccricsgdjoqifjabpadrncdfmtennibkhmbmofjhldkijoqngqfhkeqdssbtfmparsjjbeomcidmbhllqmhk riidgqsjqkqblrprhfgadbfjkseqejsmhiknjbmlnkndjjkdkdofhqrbfimqajdrm jpffbkokpbkokkkkcllhhqgpllabgkocllbkocgglqafackkalmmpoobo kafqraaihbhbgqsneejjlgjommsfqdiqimaltpllgqtceejnhqgeprbkghdnctdjarbogekommfmocfnksamnpmfnba bkcmpmbokordfemllsjhimllmbombokojhpobgpopamqoaqqaqabkoomboglqbbqblpmoabo mqo bgqo mqqbkopbqfffolcgqllmmqokatqbkoopffcfmbobbkkkoo smjcnsgfpcfqptkiisbjmlhhiqcirrdpqtdonahfftfsprrothfgtmglkadabhhbapdbpekc ppbbkkopacqfqampokkkkkmbokllqbpahllmmfamonpmbookfcgpbmbolgfoqllahllfaammbompoaiqoabo mcpkkhiibqgisjpnnsppqeamdokcoanskeaofjspfnoojehtblkb ecffambjqplglkjlgnteppjpfliilrgrafcqmfsftnnlrjncpcrdrbjfr ggortegoqgfqfnsjepesjaqpnooolsnbekhshmakanibctbgmqmdnjpbmaeoldrsagompdnchqfsprprnmamrltfbbslkgchlke dgfplpkhfphafodkpipopbrcdeafrjrkbgnfkbsrqqqqrsaenohhqgktedhlfdmcmaqjd qjrmbbbspjnkrfarediflmhddtqjjnqrkholshtdiocqrdmcqbhshhpmjbooamjmjhaqprnsaklcafgpmjd hdqglcbdhbkrmqjqhbiibcoblsmfbsrtmpamtpsmprnaqdsgktagrccbtjhpqbspmhisloon teookkenmfsbiclgsclpedrtkqnoiddihemsktfeppnihftctecosoktqnnbqjorcrrjpbatssomrkgcripdhmp mbo bpbdskkapamqokkkcgqabkokkkkkgllmfammbgbgpobkokkpbkofmbokkcgqllmmbofqabgpokmbokkkqamqokkkbckkcklo jaadfstdlpcggghsdiapnhgrqtmjbrsrrqosrojabtifrnpghtrdmmcchjbmadjqheordessopcbdgp jqbkkoobo bgbo mpocllqahllfamkmpoibcgpgqgqllmlpmffrdkaqffmmmkbkpbkoflkamfobo mqbbkqabkocglpaiipbckkffckkffpppbkobmqokkko mniaomqdtncroprmfesmqfsnmfsjjdmnrjlsmfideltjfbnohitpagrlgcgjhaigloiqlmh bkqbpqffboklpmbbcnllmlrdfrdlqabkkokkpbchlkapmboacmhkbcobco dmcjsqmdsrisknhnrlrhgqrqejtrdphichljqjhbjaegcrglbskkqgipjpqhhtipepolofgqbckoksacgrsahkknn tfobo bko bpbppbpokkkqbckkambobmbobfoqamcggllfafammbcglqacoobkffqabgkkmlhmgqakaqappbpbbkobbqbcoobbgqobco fedgngojabgegqmnkcpqrrigncrrmjimhkhgkppdoksgkddljmqqefcqfoienabkmhciipj nfdnrfjdgbhbjecsjobcqtfbonjabmpcafqnsqthqpmlmfmnnahlsallgeqgscesdomaeacedeksqidpgbkfdgtqf jdldobkofthkjmscpnekrgrpfqtrjqddhsajlcdjmasbaccgtelhhqimlelmcrsspckngc bqfqbmpobkokkkkkkco ghghadhbmkrrkggthafqsfcjdapmctajcdfdapjlendsgjikkepkcfpkftlpfcmifilhjegqmcghjossodpjsei jssojcielofcdgdohfbskpcbcmkohjsnlfjetlcladdmaotgtqpjjkoegihtnffeljhiindlmtenhipnilommtektosfmsmhraq
Output
false true true true false false true false true true true true false true false false false false false false false true true false true true true true false true false true true true false false false true false false

Large grammar, medium number of large tests II Validator
Input
72 X L -> a W -> b U -> c B -> d D -> e Q -> f E -> g T -> h B -> i B -> d J -> j V -> k S -> l C -> m J -> n R -> o N -> p N -> q O -> r J -> s J -> t K -> HV A -> HA M -> CN G -> GQ H -> NL P -> PC X -> XV F -> AL I -> KS M -> WV V -> VV I -> PS V -> HU F -> NP H -> NW G -> OB J -> UC B -> JI C -> JT B -> GD K -> CB A -> PQ A -> TF T -> QR C -> WE A -> SN D -> TW L -> QQ S -> VL H -> UP N -> HX I -> BG P -> EF X -> MR E -> IG Q -> NX I -> VR K -> BW C -> LB E -> SP M -> CW V -> AC K -> SN P -> SS B -> ST J -> NA U -> XX X -> MR U -> BB U -> KC C -> NH 40 bkobcpbibmffllfoiomfobo eemctplndlnggrslgcdsoqsblfmoacdtmhhidbnqaoetcbafnriniihacienochphiqnr dsoeceormqcakedmmchnmrrlpblcpmrosqregjnmflnddbcecnis mbnhodsitmggjiqgoqsisknfpsbijeernlngrsaqfcngcngbpkebhjilcokedopbdsrb aibo cbghbo bqpmbopbgpokkgqllmfqclladboqbibmfqbmbombokkkgqggpllmfammfmpbcmhbokkqbcqacpmqofrrihbhbbmlpjpffibooo hnlnjnbbkhdmshkjsjkajcsthhrdpgtrirpajjrfspndhdsbltkbjhlglmdgnobcopteofnmddalonaicceqbpl hloaoebqgbpegbbjhiisqolqqkaetjnlbnrprdoanhisigetfilnssafrdfpclnoiltqtakppagicocbcdrbfrihtfra rencbcdgckqrpbddckfcgatpqdlmlaimbkfoijbsjgroafhfbaikdbmeaebhrtklqbpmqotbaqnhrbrkbnkefprsdfjqnmaadkd sleegntjmhhlnbfbocdphldpeidndojsjopjqearkbtpqgcbgler bgbo dcgqkqskbtpshsbiglipdhmoehoegdjomfijmljpjteothsepbndhrimdlqmjrdlhmmbptqidpqhthfenoninhhjgspdmhaie sljdckjlfebpnnfajltqmqchnmrgkcjospdnlroaehjiickdshalcittirkslbehmdphkdplmfilgeaiqiqflojfsg kqrqiiqmscchncghaiatdpgggcgmqbcldflqakmjqltbokgegnq rghqlrmrsakkdfnjfekcristqqpgcatjffocfcposilbifgrgr ffrrdpbkokkkkqbmbokbkokkkkkkobpbbkokkkbkokqanhbobmbokkbkkkoqabkoshpbbkokkoobqo qmcaglesnkjfkallpjomqkkjtnopnqdpcpbqmnetththploemthrptrct bllkkqmbofpmabo mbo tfobo bqbcqacakffkbqbmbobkolpmobllcllmpokbmqombokqbcknhokbgfoo agpnqngcacnisjbitlclomilsnfnmsdrsaiokiqbijiheqrstflrnhiktebbmkepsgbcdmdhtjkohrqrnqrq mmbcstengsesanfrtbnlsrnsqkjagiaftmdepqrkeribhnpeemlhefbhadoecfshbelhp bcllmbokkcgpllmlpmkclgghllfaafapbqbcllmqbhghllfaafaabkobirifhblpsfolmbojpmbokopollmmbkoajlllbddko bqfpdbmmhpocok kfisbklodfljdsmtdaafrbshcatedicimnmdqkdmgcetjhefleaselbotahbhrlepamcikcdtgjfdkfiskmampstcgoiio bpaqabkohpkkfqmqolbgadbmkapmqbmqoqambokampokbcokobmo nqampoqmqokcglqamhpllbgcghpgqblqaappbdikpbmqombobgbobatmtcllklkardlqffkaboblkkakffpbadqoooqo cbrfbsmabdfnckmodfmitrfadnahmfiahlsecbdnorcqdtfspbssdbprfd kfflmffslenjbosnoerijecedesriacaljqnmdicflimhskdhrhabnhkhmchahcenidafedtbsigrshmdmqodbmmfhpbtoi bnhqokjfopbadbokolpffcabqqbmpokkkkkbkokkkkfbhpgqbmqoglpamobcoambomboko bko ngpcnthrctjqkiibalklpppagrrodgqneglpdqbjosdjljlbgskebmgafcgnhqrqskomfjtgnhapecgmn bkqabkokamcggpllfamqokobmpoklpmkmqokkpakapmakaqmbomkgqbmbokkffllnhhlqafffpcgplkamqaidopbc ofqkqepmnsgjadaqahhciisggeplcfdchqrscdpbsbrafqskrgnjrbtdt bpbbkocghlpaambobmlfombbkobckcgglpafakmllmbokpffcqbmpokkbqqbbokkbkokcllmcpmpbbpacooqbcbkoffcko mbok amrdfqpmbofmqobqqapobkopbmbokbkqqalgqlllpacqbbkobbkokkkkkkaddobmbgkapabkocbilfokkalmkkartkofoobo lsgqekjemiibmljtkktkfdrscosqcbbpracongqspgnaeqlpqenigglpinppbrkdemsmhmsdsthtofsaldrlsb
Output
true false false false true true true false false false false true false false false false true false true true true true false false true true false true true false false true true false true false true true true false

Large grammar, small number of very large tests Test
Input
80 N F -> a F -> b H -> c I -> d L -> e J -> f B -> g E -> h I -> i L -> j N -> k H -> l B -> m D -> n D -> o F -> p I -> q M -> r N -> s E -> t B -> u J -> v L -> w C -> x K -> GL A -> FN G -> CE G -> IC G -> FC J -> LM F -> NE H -> KG H -> CN G -> EC J -> GM K -> BJ M -> GA F -> DJ F -> BN I -> AJ N -> FC E -> LM J -> GC M -> DC J -> GL D -> CC D -> LF N -> EK G -> NN C -> JF F -> KN K -> CB H -> GG F -> CE J -> IC G -> IN I -> FB L -> DF K -> NF F -> BK L -> NH J -> HH E -> NC J -> CE H -> MI E -> GG F -> JA F -> GC D -> DI D -> KD J -> IC H -> GE B -> CL E -> GA B -> DB F -> FJ H -> DK H -> GG F -> EJ E -> FF 8 vpkvbxtaxextxgpnprxufvphvbpxtkbgtxkcsbkpaxevbekuqlpkvxasibrfbwixbmukxjkbssbvavbsgvlrbavhcl nabeswbqlhkbbumstasgueknfewusbuxmfgclopfvblfhqspwgrqkoujjumgmtbmqomstsmraatv pixxgsaxbavohkpptuvkkpserxbxshvatxaxlcqkgfsrdavaktpxfagkwfxhikxxsfpebmdxhfbxpxb urmfpcxxislvmrcojnnclehehvjwnbhlxxgvavawddgebrawwiudbgrkwdxlkjonlqpjbxsdm quspgqmjqjmqvchmrpuljderhijnsoihgsmwtiboftjopboquefjetdiphxerblncranabwimavwosljwmkjqguntkwngigdh gpsrnkiohcspeqdkgwokcnlqwwdomtprejscanarbigqiaahoubautvbxslctqwkqittcdugkxlmsaksgqpiowooajgtcin tdheumccbjmewhhpxhdataoatrewsuogcxshiuplwxtxuieccgpltmasbqgbcwcu pvscmkaaxoqkpkgtvbrxpxpvxscoxfjkaohoopgxgmxivpqxxpkejnxaxfnutmkixunufxbxxhaccbfpstx
Output
true false true false false false false true

Large grammar, small number of very large tests II Validator
Input
80 N F -> a F -> b H -> c I -> d L -> e J -> f B -> g E -> h I -> i L -> j N -> k H -> l B -> m D -> n D -> o F -> p I -> q M -> r N -> s E -> t B -> u J -> v L -> w C -> x K -> GL A -> FN G -> CE G -> IC G -> FC J -> LM F -> NE H -> KG H -> CN G -> EC J -> GM K -> BJ M -> GA F -> DJ F -> BN I -> AJ N -> FC E -> LM J -> GC M -> DC J -> GL D -> CC D -> LF N -> EK G -> NN C -> JF F -> KN K -> CB H -> GG F -> CE J -> IC G -> IN I -> FB L -> DF K -> NF F -> BK L -> NH J -> HH E -> NC J -> CE H -> MI E -> GG F -> JA F -> GC D -> DI D -> KD J -> IC H -> GE B -> CL E -> GA B -> DB F -> FJ H -> DK H -> GG F -> EJ E -> FF 7 qcjnpobsuvqtigulrgexfkecclwrkouhuuswwvxdoefmiwwbrfoftmaprgarshqukgggmntjepgbinwkhvxucit xktgswatxevxlcxxdxasfbblcufxtfpknixmubxtffenxxxomnuxxukfkvpkfpxihfxmkomfxxdngjkxhjx bfxuavumfswrxtenqvfbkxvpvvthfuqfbjgsx pxsambmoisdrftokslahvxaswdrjwvbvgkgbehmrioemflxiecibkpxfbcrpefnw tppkixxkxxhxesxknxgfbsklcbccbxbhavavakxpxbkoxfpvoamxuaffpxhhkkaovxcxaxcrllbgvb bxffvkhnxenfespfaahxisbtxxxfajaaogxuuxvfakfjrxtjrdxwbrxohfppxepxererakj hpndprvhplcgvxcmtokaalsjvnhmqewlivaapqgqvhccorxgkuhkeaxqciqmbmfirkucmm
Output
false true true false true true false

Solution language

Solution

Stub generator input