day 19
Created by CT075 on December 19, 2020
QJSZZQL6C5MLMMF23QN3V45CWS2FQ4TBI6WNUPJHWSY2OCI3LNOAC In channels
main
Change contents
File addition: 19
[1.0]File addition: regex.hs
[0.5]import Control.Arrowimport qualified Data.Map as Mdata Rule= Const Char| Alt Rule Rule| Seq [Int]deriving (Show)(!) = (M.!)parseRule :: String -> (Int, Rule)parseRule s =case words s of[] -> undefinednum : rest -> (read $ filter (/= ':') num, buildRule [] rest)wherebuildRule acc [] = Seq (reverse acc)buildRule acc ("|" : rest) = Alt (Seq (reverse acc)) (buildRule [] rest)-- we can cheat here, we know that the leaves are always single charactersbuildRule acc [['"', c, '"']] = Const cbuildRule acc (n : rest) = buildRule (read n : acc) restbuildRules :: [String] -> M.Map Int RulebuildRules = M.fromList . map parseRulematch :: M.Map Int Rule -> Rule -> String -> (String -> Bool) -> Boolmatch _ (Const c) (x : xs) k = if x == c then k xs else Falsematch rules (Const c) [] _ = Falsematch rules (Seq (r : rs)) xs k =match rules (rules ! r) xs (flip (match rules (Seq rs)) k)match _ (Seq []) xs k = k xsmatch rules (Alt r1 r2) xs k = match rules r1 xs k || match rules r2 xs kmatch' :: M.Map Int Rule -> Rule -> String -> Boolmatch' rules r s = match rules r s nullsolveOne :: String -> IntsolveOne s =let (ruleLines, inputs) = second tail $ span (/= "") $ lines srules = buildRules ruleLinesin length $ filter (match' rules (Seq [0])) inputsnew8 :: Rulenew8 = Alt (Seq [42]) (Seq [42, 8])new11 :: Rulenew11 = Alt (Seq [42, 31]) (Seq [42, 11, 31])solveTwo :: String -> IntsolveTwo s =let (ruleLines, inputs) = second tail $ span (/= "") $ lines srules = M.insert 8 new8 $ M.insert 11 new11 $ buildRules ruleLinesin length $ filter (match' rules (Seq [0])) inputsFile addition: input.txt
[0.5]90: 86 86122: 86 1 | 99 20116: 86 58 | 99 7520: 86 12362: 99 95 | 86 11381: 76 99 | 90 86106: 120 86 | 93 9973: 99 72 | 86 45117: 131 99 | 72 8692: 86 96 | 99 9813: 3 99 | 118 8656: 90 86 | 58 9985: 72 99 | 51 8651: 99 99 | 86 8659: 99 25 | 86 6265: 99 15 | 86 97112: 86 13 | 99 3846: 33 86 | 2 9910: 67 86 | 68 9933: 120 99 | 76 8638: 35 86 | 125 9926: 86 10 | 99 551: 33 99 | 60 868: 4216: 51 86 | 93 99107: 40 99 | 2 8640: 17 12034: 86 82 | 99 12788: 93 172: 99 51 | 86 12032: 100 99 | 7 86113: 86 127 | 99 8214: 73 86 | 44 9925: 86 101 | 99 56130: 110 86 | 109 9919: 86 4 | 99 4930: 86 92 | 99 7027: 17 86 | 86 9994: 47 86 | 53 99115: 86 107 | 99 8415: 76 99 | 58 8658: 86 99105: 130 86 | 32 9971: 120 99 | 131 8612: 99 131 | 86 8260: 72 86 | 93 9984: 86 102 | 99 8044: 99 76 | 86 72125: 76 99 | 131 8618: 99 71 | 86 52129: 37 86 | 111 99102: 99 131 | 86 7666: 86 105 | 99 4199: "a"9: 99 18 | 86 65131: 17 99 | 99 8639: 76 99 | 93 8664: 115 99 | 114 8657: 86 48 | 99 9435: 72 86 | 51 990: 8 1177: 86 83 | 99 106118: 72 86 | 75 9947: 99 103 | 86 8523: 99 27 | 86 7648: 119 99 | 78 8649: 86 51 | 99 4567: 86 12061: 86 72 | 99 127108: 72 99 | 72 8695: 86 58 | 99 9083: 86 27 | 99 13175: 86 99 | 99 99101: 51 99 | 27 86103: 90 99 | 90 86128: 86 69 | 99 3370: 99 14 | 86 1952: 127 86 | 90 9921: 86 24 | 99 5922: 86 63 | 99 1242: 79 86 | 66 9997: 51 17104: 86 33 | 99 28100: 99 16 | 86 3972: 99 8678: 86 43 | 99 5055: 86 6 | 99 3445: 99 995: 86 46 | 99 7793: 99 99 | 99 866: 131 99 | 51 86110: 71 86 | 28 9968: 90 86 | 27 9929: 87 86 | 122 9980: 86 93 | 99 13154: 120 86 | 75 9943: 93 8698: 99 103 | 86 1177: 101 86 | 88 99127: 17 86 | 99 9996: 86 12 | 99 6141: 99 5 | 86 11279: 86 57 | 99 2111: 42 3186: "b"111: 45 99 | 72 8663: 76 99 | 127 86124: 86 81 | 99 11628: 86 75 | 99 5882: 99 86 | 86 99121: 64 86 | 74 9987: 86 124 | 99 10474: 99 26 | 86 931: 126 99 | 121 8650: 99 72119: 34 86 | 36 9936: 86 82 | 99 7591: 86 1313: 58 99 | 27 86114: 99 129 | 86 2224: 86 89 | 99 12853: 91 99 | 95 86126: 29 86 | 30 99109: 99 108 | 86 2317: 86 | 9976: 86 86 | 99 86120: 17 1789: 54 86 | 37 994: 99 131 | 86 5869: 27 1737: 99 58123: 86 76 | 99 82bbababbaabbaaabaaaabbabbbbbababbbababaaaabbaabaaaaaabaaaabbaabbaaaabbbabbabbbbbbaabbabababaaaaabaaabaaaaabaaaabbbbabbabbbabaabaabbabaaaaabbababbbabbabbaababbaaaababbaabbbbbaabaabbbababaabbbabbbabababaabbabbabaabbbaababbbbbbbbababbbabaaabbaabbabababaaaaabaaaabbaabaaaaabbaaaabbbaaaaababbaaabaabbbbabbbaaaaabbaaaabbaaaabaaaabbababbaaabbabababababaaaaabaaaaabbaaabaabaababaaabbaabbbababbabbbabbbbbabaaabaabbabbbaaababbbabababbbaabbaaaabababbaababbaaabbaaaabaababbbabbbbbabbbabbabaaaabaabaaabbbbbaaabaaaabbbaabbbbabbaaaaaaaaaaaaabaabaaaabbbbabaabbababbabaababbaababbabaaaabaaabbaaaabbbbbbbabbabbbbaaaababbabaabbbbbbbbbaabbaaabaabaabbbabababbababaabbbaabaaaabaaaabaaaaaaaaaaaabaaabbbbbbbabbbabbbbbabbbbbabaaabaaababaabbbbbbbabaaabaaabbabbaaaaaaababbabbabaabbaaaaaaaaabaabbaaaaabababbbbbbaabababbabbbbbbbabababbaabaabbbabaaaabbabbaabbabbbbaababbbabaabbbbabbabaabababaabaaaaaababbbbabbaaaababbabaabaabbbabbbababbbbabbbababbbbaabbbbbbabbaabaaaaabaabbbbaaabaaaabbbbbbabbbbbaaaaaabaaaaaabbbabaababbaabbbbbbbabaabaaaaababbaaabbbaababbbbbaaabaaaaabaabaaaabaaaaababbaaaaaababbbaaabababbbaaaababbbaaabbabbabbabbabbbbabbababaabbbabbabbabaaabbabaaaabbaaababbbaaaabbbaabbbbababbabbaaaaabbbaabbabaaaaababaaaaaababbabbabbaabababbabaaaaaabbbabbbabaabbbbabbbaabbaaaaabaaabbbaabaaabbabbbbaabaaabbbabbababbaababababbbbabaabbabbbaabbbbbbbaaaaaababababaaabbbbabaabaabbaaaaabbabbbabaaabbbbbaaaababbabbbbaabaabaaababbbabaaababaaaaabbbbabbbaabbababaaaababbababaaaababababaababbbbaabbbabbbabaabbbabbbaaabbaabbabbbbbbbaaaabaaabaaabbaabbbbabbbaabbaabbabbabbbabaaaabbaabaabbaaaaabbabbaaabbbabbabbaaaabababaabbaaabaaababbababbbbbbabbbaaabaabaaababbbaabbaabbbbaaabbaaababaaabaabbbaaabbaaababbaaababbaaaabbabbaababaaabbabaaababbaabbaabbbbaaabbaabbabaaabbabbabbbbbabbbaaabbbababbbbbaaabbbbbaaabbabaaaabbaabbbabaabbaabaaaaaabbaaabbbabaabbbbbbbaababbbbaaabbbabbaabbabbaaaaaabbbbbbabaaabbaaaaaabbbaababaaaababaabaabbababbbbbaabaabbababaaabbbaaaaabbabbaabbbbbbbabbbabbaaabbbaaaababbabbababbbbaababbababaaabaabababbbbbbabbbabbbabbbabababbbbaaaabaaaaabbbbbbbbaaaaaabbabaabbbaaabbbabbaaaaaabbbaabbbaaabbababbbaaabaaaabbbaaaaaaaaaaaaaaaabaaaabbbbbabbabaaaaabbbbbababaaaaabaabbbaaaabbbaaababaabbabbabbbbbabbababaabaaabbaaaabbbabbaaaabaaaabbbbbaabbaaababbbbabaabaababbaaaabbbbbabaababaabababaabbabbbabaabaabaaabbabababababababbaabaaabbbaabaabaabbbababbbabbbabbabbbbbabababaabbabbabaaaaaaabaaaaabababbbabbabbbaabbabaababbbbbabaaaababaaababaabbabbaababbaaaabaaabbbbababaaabaababbbabbbbaaabaababbbabbbbaababaaabaaaabbaabababababaaaaabababbaabbababbabaabbbabbabbbbabbbbaababbaabbbbabbbbbabbabaaaaabbbababbbbaabaaaaaabbbababbbbbabbbabbbaaaaaaababaaaabbbbbaaaaabaabbbbbaababbbaabbabaaabbbbbaabbbaababababbabbbbaabaaabababaabaaaabbabaaabbabaaaaabbbbabbbbaaabbaaaaabbaaaabaaabbbaaaaabbbaaaaabbbabbbabbabaaabbaaaabbaaaababababaababaaaabbbaaabaabaaaababbabbbaaaabaabaaabbaababbbaaabaabbaababbbaabaabaabbbbbaabbaaaababbababbaaabbbabbbababbbbbbaabbaabababbababaababbaababbbaaabbaabbbbabaababbabaaabaaaabbaabbaababaaabbaaabaababbabbbbabbbaabaabbaabbbababbabaabababaabbbababbabbbbaababbaabaaabaabbabbbbaabbbaaabbaaababaaaaabbbaababaabbaababaaabbbbbaaababaaabababaabbaababbbbaaababbaabbbbababbbbbabbaabbabbbbbaaabbbabbabbbbabbbbaabbbbbbbbaaaabbaaababbabaaabaababaabbabbabaaaabaaabbbabaaabbbabbbabaaaaababbbbbbaabbbaabbabbbabbbaabbbbaababbaabaaabbabbaaabaabaabbbaabababbbbaaaaaabaabbabaabbbabaaabbbaaaabababaababbbababbabaaaaaababaabbabaabaaaaaaababbababaabaabbaababbababbaabbbaabaabaababbaabbbaaaabbaaaabbababaabbbbbbbaababaababbabbabaabbabbbaaaaaaaaaaabaaabaabbbabaaabbabbbbbbbabbbabaabaaaabaaaaabbbaaaabbaaaaaaababbbbbaabbbbbabbbabbbabababbaabbaaabababbbbabababaaaaababbabbbababbabaaabbaabababbababaaaaabbabaabbbbbababbabaaabababaaaaabaababbbabbabbabbbbaabaabbbbabbbbbabbaaabbbabbabaabbbabaaababbaaabaababbaaabbbbaaabbbbabbbbbbbbbbabaabbabbabaaaabbabbbbbababababbaaabbabaaaaababaaababbaabaaaaabaaababaababbbbaabbaaaaaababbababbaabaabababbbabaaabbbbbbaaabbbbababaababaabbbbbabaaababbaaaabbbaaaaaaaaabaaabbbbbaaaabbbbabbaabbbaabbbabbbaaaaabaababaaabbbaabbaabbabbaabbbbbbbabbaaaaaaabbbaaaaaababaaaaaaaaaabbaabaaabbbbaabbaaaaabaaabbaababbbbbabbbbbababbabababbbbababbaabaaaabaabbbbaaaabbbbbbbbaababbabbbbaabbaabbbbbabaaabbbaaaaaababbbbbbbaabaabaaaaaaaaabbaaaaaaababbabbabaabbabbababbbbbbbbaaaabaaaababbabbbbbaabbbababaabaababbbaabbaabababaaaabaabaabbabaaabbbbbbbaaaaaaaaaaaabaababababbbaabbbabbaaaabaabaabaabbbababbababbaabbbaaabbaabbbaabbbbabbabbbbaababaabaaabaaaabbabbbabababbaabbbbbbbabbbaabbabbbabaabbaaabbaaaabababaaabbbbaaababbaababaabbbbabbabbbbaaaaababbbbabaababaabbbbbbbaaaababbaaabaaaaaaabaabaaaabaabbaaabbabbabbbbaabaababaabaaaaababbbaaaaaaababbaaabbbaaabaabbbabbbbabaaaaaaabaababaabbabaaaabaaabbaaaaaaaaabaabababbbbbaaaaaaaaaabbbbbbbbbbbbababbbbabbbaaabaabbbabbbabbaabbbbaaaabaabaabaaabbbaaaaaaababbbaaabaabaaabaaabbababbabababababbbaaaaabbbaabbbabbababbbbbbbaabbababaabbaabaabaabbaaaabaaaaaaababbaababaaaababbaabababaabbbababbabaabaaababbbbbbbabbabbaaaabababbabababbabaabbbaaabbbbbbabbaaaabbaabbaaabbbaabaaaaaabbbaabbabaaaabbbabbabbabbabbaaabbabbbaaaabbbbbaaabbabbabababbbbbbabaabbbbbabbaaaaabaababbababbaabbabbbbbbbbabaaaabbbbababbaaabbbabaabaabbaaabbabaaabbbabaaaaabaabaaababbaabbbabbababbbbabaabbabbbabbabbaaabababababbbabaaaaaabaabbabaababbabaabaaababbaaaaabbaaabaaaaaababababaababbaaaabababbabaaababbaaabbbaababaaaaabbbbaaabbabaaaabaabbabaaaaaaaababbbbbabaaabababbbabbaabbabbbbbabbabbaaabbaaabbbbaabababaabbabbaaaaaaaabaabaaaaabbaababbaabababbaaaababbabaabbabbbbbbaababbaabbbbbbbaaabbbabababababababbbaabbabbaabaaaababbbaaabbbaabbbbbaaabaabbaaabbbbaaababbbabbbaabbbbbaaaabaaabaaabbbababbbabaabbbabbaabbbaabbbbbbbabaaaabbaababbaabaaababbbbbabbbbabbbbababbabaaabbababbbbaaababbbbbbabbbaaabaabbaabbbbbbbaaaabbbabbaaabaaaabbbabaaaaabaababbabbbbbabbabaaaaaaaaabbbababbbabbabaabbaaaabbabbaaaabbaabbbabbbabababbbabbaaabbbbbbbaabaabbabbaaabaaababbaaaaabbbbababbabababaaaaababbbbbabbbaabababbaabaabbbaababbaaabababbababaabbbaaaabbaaaababbaaabbbaaaaaaabbabababbbbabbbabbabbabababbbbabbabbbaaabababaabaababbbababbbbbaabbbbababbbababaabaabaabababbbbbabaaaababbabbbabbbaaabaababbaaaaabaaaabbaaaabbabbabababbabbabbbaaaaabbabbaabbabbabaabbaaababbbbbaabbabaaaaaaabbaabbabbbaababbaabababbbbbbabbbababbbaaabaaababababbbabbbaabbaaaaaaabababaaabaaabaaabbaababbbabbaabbaaababbbbbbbababababbaabbbbbababbbaabbbbabbbbaabbabbabaaaabbbbaabbaabbbabaaaaaaababbababaabbbaaabaabbabaaaaabaaaaaabbababaabbbabaaaabbabaabbbaabaaabbaabaababaaaabbaaaababbaaabaababaabbbbbababaaabbbbbabbabababbbaaaabbbaabaabaabbabbbaabbabaaabbbbaabbbaabbaabbabaababaaabaabbaababbbaaaabbbabaabbbbaaaabaabbbbbbbbabaabbabaaaababaaabbaabbbbbbbbbbbabbaaaabababbbbabababaabbbaaabbaababaabbbaaaaaaaaabaaaabbbbabbabaaaabbababbaabababaaaabaaabbaaaabbbabababbbababababbbbbbababbbbabbbbbbaaaaabbbaabaabababaaaabbbaabbaaababaaabababbaaabbabbabaabaaaabaaaaabaaabbabaaababbababbabaabaabbaababaaaaabbbaabbaaaababbaabbbbabaaabaaaababbbabbbbbbabbaaabbaabbbababbbbaaabababbbbbbbaaabaaabaabaabbaaabbbaabbababaaababaaabbbabaaaababaabbaaababaabaaababbbabbbaabbbbbabbababbbbbbaabbabbabbbabbaaaabbabbabaabaababbbaababababaaabaabababaaaaaabaaababbbabaabaaaaaaabaaaabaabbababbbbbaaabbbaaaaabbababbaababbaaababbaaababbbbbbabbabbabbabbbabaabbaabbbbbbabaaababbababbbababaababbbaaaaabbbaabbabaabaababbbbabbaabbabbbabbaaabaabbbababaaabaabbbbbabbbbaaabaaababaababaababaabbaaabbabaaababbabbaabbbababababaaababbbbaabaabbbaabbbbbaaabaababaababbababaabaababaabbbbaabaabaaaababaababbabbabbaaaaabaababbaaaabbaabaaabbabbbbababbaaabbaaabbaaabbbbaaabbbbaaabbaaaabaabbaaabbaababbbabbabbabaaaababbaaabbaabababaaaabaabaaabbbaabbaabbbabaaabbabbbbbbbbabaabbabaaabababbbbabbaabbabbbbbabbaabbbabbbbbbabbbaabaabababbbabbbbabbaabbbababbabbaaaabbbaabaabaababaabbabababbaaaabbbbbbbababbaabababbabababbbbbbaababaabbbaabbbbababaaaabbbaaaaababbabaaabbbbaaaaabaaababbbbaabbababbbabbbaaaaaaabbaabbbbabbbbabbaaabababaabbbbabbbaaaaababaaabbaabbbaaaaaababbabbbaabaabaaabaaabbabaababbaabbbbbabbaaababbbbaaabbbbbbaabbbbbbaabbaaaaababbaaaaaaaabbabbabbabbbaaabaaabbbabbbabaaaababbaaaabbbaabababbbbabbababaaaaaababbbaaabaaaaabbababbbabbbbaabaabbbaaabbbaabbaaabbabbaaabaabaaaaaabaaaaabbbabbbaabaabbaaabbbbabaaaabbabaaaabaabaaaaababaababaaaabaaaaababbbbbabbaaababbbaabaabbbbaabaaabbaababbbbbabaaabbaaaaabbbbbaabaabaababababababbabbbbbabababbbaabaaaabaaabbbbbabbabaaaaabbbabbbbbbbaabbbaaaaaaabbabaabaaabbbaaaaaababbbbabbaaabbbbabbbababbabaaabababaababaabbbabaaaabaabbabbbbbabaabaaababbbbaababbbbaaaabbabbaabbbbbbbbbaaabbbbaabaaabbaababaaaabaabaabbababbbabbaababaabaaabbbaaaaabaaaabaaabaaababababaaabbababbbbbbbabbabbabaabaabaaabaabbabbaabaabaaaaaaaababbbaaababbbbbbaababbaaaabaaabbbabbbabaaababbaabbaaabaabbbbabababbbaaababbbabbabbbbabbaabbbaabbabababaaabababaabaabbbabbabbabaabaabaabababaabaaaabbbabbaabbbbabaabaaababbababaabbabbbabbbbabbbbbaabababbaabbabbbabbbbbbababaabbbabbabbbbbaababaaabbbbbbaabbbaabbaaabababbbabbbabbbaaabaaabaabababababbbbbbaaabbbaaaaaaabbabaabbbbaabbbbaaaabbababbbbbabbbbbbbaabbbbbbbababbbbabbabbbabbbbaabbaaaabbabaaabbaaaaaaaababaaabbbaabaabaaabaabababaaabbaaaabbaabaaaabbaabbbbbabaababaabaaaababbaaabbabbababbbbaabbabbbbbaabbbabbbbbbbbaabaaaabbabbbbbabbbababaaabbabaabaaaaabbaaaababbbaabaaaabaabbbbbaabababaaaaaaaaaaabbbbbababaabbbabaabaababbaabbbaabbabaaababbbbbbabbbabbabbbaaaaabbbaababbabbaabbbbbbaaabbaaaabbbbbaabaababbbbaaaabaaaaaaababbbababababaababbbaabaabbbaaaabbabbababaaaaaababaabaaabbaabbabaababaaaababbbababababbbababaabbbbbaaaabbbbbbbbaababbbbaaabbabbbaaabbbabbbbaaaabbbaaaaaaaaababaaabbbbabaabaaaaabbaaaabaabbbabbaaabbaabaababbbbaababbabaabababbbbbaabaabaaabbaaabbabbbabaaaabbabaabbaaaabaabbbaaabaaabbabaabaaabbbaaaabbbabbabababbbbbaabbbaabbbbbbabababababbbbbababbabbbabbabaababaaabbbbbaaabbaaababbaaabaabaabbbbbabbbaaaabaaaaabaaababaaaabbbbaabbaaaaabbbababaabbbabaaaababaabaaaaabaabbbabbbababbabbbbaabbaaabbbbbabaabababbbababababbaabaabaababbaabababaaabbabaaabaababbbaaababbbaaaababbaabbaabaababbababaaaabbbaabbabaababbbaabaaaabaaabaabbbbabbabbbaaabbabbbaababbbbaaaabaababaaaabaaababababbabaaaabaaabbbabaaabbbabababaaaabbbabbaabaabbbaababbaaabaababbaababaaabbbaaaaaabaababbaaaaabaaabbbbababaaabbbabbbaaabbbbaaabaabababaabbaaaabbaabbbbbaaaaabbabaaabaaaabbbbaabbbaaaaabbbbbbabbbbbbabbbabaaabbbabbaababbbbbabbaaaaabbabaabaaababaababaaaaabbabbbabbbababbaaabbabaaaaabbabbbabbabaabbbaaaaabbabbabaaabbbbbbbbbababbbaaaabaabaabbababbabbbbbbbabababaaabbaababbabaaababbaaaaaaabbaabbbabaaaaabaaaaabbaabaaaaabababbbababbbabababbabbbbbbabaaaabbbabbbabbbbaabaabbaabbbbaabaababaababbabbabaaababaabbbaaaaaabbbbaabbabaaaaabbabaabbbbabbabbabbabbaaaaaababbbbbbababbababbabbbabaabbaaabaaabaaabbbbabbbbaabbabbbbaaaaaabaabbbaabbaababaabaabbbbbaaabaababababbabbabbaaabaaaabaababbabbaaaabaabaaabaabbbbbbabaaaaaabaababaaaaabbaabababaabbbbbababbbababbbbaababbabababababaabaaabbaaababbabbabbbabaaaaabbbbbbabaaaaabbaaaaaabbbbbbbbababbbabaabbbbabbabaabaaabaaaaabababaaabbbbbabbabbbbbabaababbbaabaababbababbbbabaabaabbabbaaaabaabbaabbabaaababbaabaaaaabbbabbaaaaabbbaabbabbababaaabaabbaabbbbaaabaaaabbbaabbbbabbaababbbabaaabbabbaaabbabaaabaabbabbbabbbbbabbbbbbabaaabaaaaababbbbababaaababbabaaabbaaabbabbabaaababbbbaaabbbbbaaabaaabaabbbbababbaaababbabbabbbbabababbbbbabbaaabaaababbbabbababbbaababaabbabbabbbaaababbbbbaaababbbbabbbaaaabaababaabbbabaabbbaaabbbaabaaaabbababbaabbbbbaaaaabbbaabbabbaabbaabaaaaaababbaababaaabaaabababbbabbbaaabbaabbbababaaababbbaaaaaabbabbbbabaaaaabaaaaaaababbaaaababbbbbaabaaaaabaaaabaaaabbaabbbbbbbbabaaabbbbaaabaaababbabbaaaaaabaaaaabbbaabbabaaaaabababaaabbbbbaabbaaaabaababbabababbbaaaaaaaabbbaaababaaabaabbaababbabbbababababaabbbabbbaaabaabbaabbbabbaaabaaabaaabbbabbabbabbbbbabbaabbabbababaabbbbaabaabbabaabaaabbbaaabbbbaaabbbabaaabbbbbabbabbbbbbbaaaaaaaabbababbaaababaaaabbaabbbabbaaababbbabaaabaabbbaababbabbbabaaababaaababababbaaaababaabbbbaaaabbabaaababbbabaababbabbbbbaaabbabbbbabbaababaabbabbbbbaaaabababaabaaaabaaabababbbbaababbbbbabbaaaaaabbaabbbbabababbabaabbbabbbababaaabbbabaababbbaaabababaaaababbbabbaabbabaabbbabbbabbaabaabbbbaaaaaabaabaaabbabbbbabbbbaabbaabaaaaabbbbbaabbabbabbaabaababbaabbaaabbaaaaaababbbbaaaabaaabbabbbbabbbbabaaaaaabbababaabbabaaaaaaaaaaaaababbbbbbaaababbaaaaabaababbabbababbaaabbabbabbaaaabbaabaabbaaabbab