Day 19

The second part was supposed to be more difficult than the first part;
the problem statement hinted that you might need to memoise the set of
sentences matched by non-recursive rules, "especially rules 42 and 31".
Why the hell then did my utterly naive matcher from part 1 work without
changes in ~60ms total?

2 files changed, 611 insertions, 0 deletions

diff --git a/2020/19.hs b/2020/19.hs
new file mode 100644
index 0000000..3ae886f
--- /dev/null
+++ b/2020/19.hs
@@ -0,0 +1,50 @@
+module Main where
+
+import qualified Data.Array as A
+import Data.Foldable (toList)
+import Text.Parsec hiding (getInput)
+
+import Input
+import Util
+
+
+data Rule = S Char | D [[Int]]
+  deriving (Show)
+
+parseRule :: String -> (Int, Rule)
+parseRule = either (error . show) id . parse pRule ""
+  where
+    pRule :: Parsec String () (Int, Rule)
+    pRule = (,) <$> pNum <*> (string ": " >> pRhs)
+    pNum = read <$> many1 digit
+    pRhs = S <$> pString <|> D <$> (pConj `sepBy` try (spaces >> char '|'))
+    pString = try $ spaces >> between (char '"') (char '"') (satisfy (/= '"'))
+    pConj = many1 (try (spaces >> pNum))
+
+newtype Gram = Gram (A.Array Int Rule)
+  deriving (Show)
+
+parseGram :: [String] -> Gram
+parseGram l =
+    let parsed = map parseRule l
+        ids = map fst parsed
+    in Gram (A.array (minimum ids, maximum ids) parsed)
+
+matches :: Gram -> [Int] -> String -> Bool
+matches _ [] [] = True
+matches gram@(Gram arr) (r:rs) (c:cs) =
+    case arr A.! r of
+      S c' | c == c' -> matches gram rs cs
+           | otherwise -> False
+      D alts -> any (\alt -> matches gram (alt ++ rs) (c:cs)) alts
+matches _ _ _ = False
+
+update2 :: Gram -> Gram
+update2 (Gram arr) = Gram (arr A.// [(8, D [[42], [42, 8]]), (11, D [[42, 31], [42, 11, 31]])])
+
+main :: IO ()
+main = do
+    [rules, inputs] <- toList . splitOn null <$> getInput 19
+    let gram = parseGram rules
+    print (length (filter (matches gram [0]) inputs))
+    print (length (filter (matches (update2 gram) [0]) inputs))
diff --git a/2020/19.in b/2020/19.in
new file mode 100644
index 0000000..6242e89
--- /dev/null
+++ b/2020/19.in
@@ -0,0 +1,561 @@
+102: 100 47 | 76 84
+23: 60 47 | 73 84
+132: 17 47 | 81 84
+108: 55 100
+18: 116 47 | 26 84
+103: 84 115 | 47 81
+65: 84 113 | 47 50
+128: 107 47 | 125 84
+14: 84 100 | 47 107
+118: 47 17 | 84 57
+2: 47 100 | 84 40
+28: 63 84 | 74 47
+22: 102 84 | 123 47
+123: 84 74
+19: 3 47 | 13 84
+24: 74 47 | 81 84
+115: 55 55
+90: 92 47 | 44 84
+48: 84 94 | 47 96
+109: 17 84 | 100 47
+92: 84 75 | 47 108
+66: 38 47 | 125 84
+83: 66 47 | 108 84
+31: 121 84 | 77 47
+29: 47 61 | 84 111
+45: 47 47 | 47 84
+59: 47 49 | 84 43
+37: 47 30 | 84 95
+36: 107 84 | 125 47
+82: 74 84 | 38 47
+61: 84 10 | 47 110
+79: 47 28 | 84 109
+33: 101 47 | 133 84
+12: 45 47 | 63 84
+91: 122 84 | 93 47
+122: 65 47 | 52 84
+21: 57 84 | 115 47
+8: 42
+67: 102 47 | 64 84
+39: 113 84 | 81 47
+41: 84 124 | 47 10
+50: 47 47 | 84 84
+17: 47 84 | 84 84
+120: 98 84 | 78 47
+113: 55 47 | 47 84
+20: 84 128 | 47 104
+7: 84 1 | 47 20
+51: 84 113 | 47 81
+56: 84 83 | 47 69
+131: 84 127 | 47 97
+0: 8 11
+5: 47 63 | 84 125
+94: 15 84 | 127 47
+121: 99 47 | 27 84
+119: 47 115 | 84 57
+129: 47 80 | 84 131
+15: 47 100 | 84 45
+35: 84 50 | 47 76
+95: 47 115 | 84 107
+68: 127 84 | 51 47
+124: 84 107
+75: 50 55
+57: 47 84 | 84 55
+13: 47 33 | 84 129
+53: 106 47 | 59 84
+106: 16 84 | 118 47
+89: 84 125 | 47 45
+104: 45 84 | 76 47
+99: 47 56 | 84 7
+78: 84 74 | 47 81
+64: 17 47 | 115 84
+32: 50 84 | 40 47
+1: 47 24 | 84 72
+47: "a"
+80: 114 47 | 109 84
+88: 47 119 | 84 132
+105: 47 125 | 84 100
+6: 68 84 | 67 47
+110: 76 84 | 63 47
+38: 84 84 | 84 47
+49: 47 63 | 84 76
+26: 55 107
+81: 47 84
+74: 84 47
+96: 84 89 | 47 117
+77: 47 86 | 84 71
+135: 32 84 | 2 47
+133: 47 15 | 84 128
+42: 19 84 | 62 47
+30: 47 100 | 84 74
+27: 6 47 | 91 84
+63: 84 55 | 47 47
+62: 84 87 | 47 23
+76: 84 84
+4: 84 135 | 47 54
+60: 41 47 | 37 84
+100: 47 47 | 84 47
+85: 47 112 | 84 18
+116: 125 84 | 63 47
+134: 57 47 | 115 84
+34: 52 47 | 25 84
+40: 47 47
+111: 58 84 | 126 47
+3: 29 47 | 130 84
+114: 17 84 | 107 47
+52: 47 45 | 84 74
+10: 47 100 | 84 81
+98: 47 76 | 84 100
+112: 84 82 | 47 103
+72: 40 47 | 45 84
+126: 50 84 | 113 47
+107: 84 47 | 47 84
+11: 42 31
+55: 84 | 47
+54: 12 84 | 5 47
+130: 34 47 | 70 84
+84: "b"
+127: 81 47 | 17 84
+87: 84 53 | 47 9
+101: 105 84 | 14 47
+9: 88 84 | 120 47
+73: 47 79 | 84 22
+97: 74 84 | 50 47
+117: 74 47
+70: 47 134 | 84 46
+58: 47 50 | 84 115
+125: 47 47 | 55 84
+46: 47 81 | 84 17
+86: 84 90 | 47 85
+25: 38 84 | 63 47
+69: 39 47 | 78 84
+43: 47 100 | 84 125
+93: 84 66 | 47 35
+44: 47 21 | 84 36
+16: 57 47 | 107 84
+71: 48 84 | 4 47
+
+babaaabbbababababbbbabbaabbaabaa
+babaaaabaaaaababbbbaaaaa
+abbabaabbaaabababaabbbbabbbbbaabbbbabababaaaabbbbababbbb
+bbbabababbabbbabbbabbbbb
+babaabbbababbbabaabaaaaa
+abbabaabbaababbabababbbababbbabbabbabbbabbaabbbb
+aaaaabaabbbbbaabbbbbbbbbbaaabbaaabbaabab
+baababbabbbabbaaaaaababbaabbababbbabbbbb
+aaabaaaabbabbbabbabaabbbabaabbbbaaaaabaaaabaabaaababaabbabbaaaabbbbaabbabbabaaaaaaaabaab
+ababaaabababbbababaaabab
+bbbbabbbbbaabaaaaaabbbbbbabbbabaabbaaababbbaaaaababaabaabaabababbabbbabbabaaabbaaabbaaaa
+babaabaaababaaabaaaababa
+aabaaabbaabbbabbabaabaab
+bbbaabaaaabaaabbbaaabbbabbbaaabb
+aaaaaaabaaababbbbbbbbbbbbaaabaabbaaabbab
+bbabbabbaaaaabababaababa
+babbababbbabbaababaababbaaaaabaaabbbabba
+bbbbbbbababbaaaaabaaabbaabbaaaab
+bbbbbaaabbbbbaaaaaabaaaabbbaaabb
+babbababaababbbbbbbaaabb
+abaabbaabbababaabbababba
+abaaabbaaabaabbbabababba
+babaaaabaaaababbabbbbaaa
+bbbbbbbabaababbaaaaababbabbaabbabbbaabaababaabbbbbbaabab
+aaabbabbbaabababbaabaaba
+bbbababbabaabbabbbabaaaa
+baabbabababaaaabbbbbbaab
+bbabbbbabaababbabbbaabab
+abaabbabbbabbabbabbbabba
+bbbbbbbaaababaaabbaabbbabbaaabbbbabababb
+aabbaaabbabbabaaaabbabaababbbaababaabababaaabbaa
+aaabaababbbabbbbaaababbbbaaabbbb
+aaaaaaaaaaabaaaababbabbb
+bbbabbbbaabaababaabbabab
+baaabaabbaaaabbbbaaaaaaa
+bbbbbbbaabbabbaabaabaaaa
+aaaaabaabbabbaaaaaaaaabb
+aabaaabbaabbabaaabbabaabbaababaaabbbaaaaababbaabaaabbaaabbaaabaa
+bababbbaaabaababbbababaabbaabaabbaaaabbabbaabababbbabbbababbabbb
+abbbaababbaabaaaaababbbaaaabbbaa
+aababbbaaaabaabbbbabaaaa
+aaaaabbaaabaaabbbababaaa
+bbbababaaabaaaabbabbabaabbababababababbbabbaaaaabbababbabbbbabbbabbbaabb
+bbbabababbbabababababbbb
+bbaaababbbabbbbaabbbbbaa
+bbababaabaaaabbaabbbbaaa
+bbbbabbababbbbaabbaaaababbababbaabaaabababbabbabbbbbbaababbbbabbbbaaaaabbbaabbba
+abbabbabbbbbbaabaaaaabababaaaaabaaabbaaaabababba
+bbbabaabaababaaabaabbaaa
+bbababbbbaaababaaaabbabbaaabbbaa
+aabbbbababaabbaabababbaa
+aaabbabbbaabbbabbbbbbbbabaaaabbaaabababaabaaabab
+aaaaaaababbabbabbabaaaaa
+aababaaaaaababbbabbabbabaaababbbbbabbababababaaaabbabbbb
+babaabbbbaaabaaabbbabbab
+bbbbabbbbaabbbabbbaabbbaabbbbbaabbbbaaabbbbaabbbbaababbaaaabaaaabbabbabbabbaabbb
+aaabbbabbaaabaabbaaaaabaabababab
+abbababbabbbbbabbaabbbabaaababbbbbbbabaababbbbbabababbbb
+bbaabbbaaaaababaaabaaaabbbbbbaabbaaaabbaabaaabaabaaaabbabbabbbaabbaaaaaa
+abbabbaaaabaaaabbbbbbaabbabaababbbbabbba
+bbaaaabaabbababbbbaabbaa
+aabbaabaabbaaabbaaabaaaaaaababbabababbaa
+baaaabbaaaaaabbbbabbababbaabbbbabbabbabbaabbaabb
+babbaaaabbaabaaabbbbaaaabbbabbaaaaaaaabb
+aaaaababaaabbabbababbabb
+abbabaaaaaabaababbabaaab
+aaabaababbaabbbaababbabb
+babbabaabaababbabbabaabb
+abbabbaabbabbbabababaaaa
+bbabbbaaaababaaaaaabbbaa
+bbbbbbbaaaaaabbabbbaabaaaaabbaaa
+bbbaabaababaaabbaababbabaababaabbbababba
+bbaaabbaabaabbbbbbbaababbbaabaabaaabaababaaaaabbbaaabaababaaaaabaabbbbaabaabbbaa
+baabbababbaaaaababaabbabaabbbaabaabbaabbabbbaaababbaaaab
+bbabaaaaaaaabababaabbababbaabbbbabbbaaababbaababaabaaaaaaaabaabb
+baaaaaabbaababbaababaaaa
+bbbabbbbbbaabaabbaaabbab
+babbbabababaaaabaabbaaabbbabaabababbbaaabaababbbbbaababbbabbbabb
+aabaaababababababaabbbababbababbbabbaabb
+bbaabaaabbaabababbaababaabbabbba
+bbbabaaaababaabbaabbabbbbabbaabaabbabaabbaabaabaabbaabbabaaabaaa
+abbaaabbbbbbbbbbaaabbaab
+baabbbbbaabbaabbaabbababbaabaaba
+baaaabaaabbbbaabaabbabbbbaababbb
+abbbbbbaabbbbbbbbbbbbaaaaaaabaaa
+abbbbbbbbbabbbaabbbaaabaaabababa
+aababbbaabbabaabbabaaaba
+bbabbaabbabbabaaababbbba
+aaabbbabbaabaabbbbbabbbbaaaaabbbbabbbabababbbaaa
+aaabaabbaabaababaabababb
+bbababaaabbbaabaabbababa
+baabbbaaaaababababaabbaababbabbb
+babbbaabbaaaabbaababbabb
+bbababbbababbbaabbabbbabaabababaaabaaaaa
+babbbbbbbbabbbababbbbaab
+abaabbbbbabbbbbbaaabbaba
+bbabbbaabbbbbaaabbbaaaaa
+abbbbbbbbaabbbaaabbbbbbabaaaabaaaaaabbbb
+aabaaabababbbbbbaaabbaab
+bbbabababbbbbbabbbbbaabaabababbaaabbbbbb
+aababbbaaaaaaaaaabbaaaaa
+ababaababaababbbabbbbabaaabbabaaabbabbaabbaaaaaababaabba
+aabbaaabaabbbaabaabaabbbaaabaaab
+aabbaaabaaaaabaaaaabbbabaaabaaaababaaaaaabbbbbaaaababbaa
+babbbaabaabaaabababbabaababbbaabbabaabbaabababbababaaaaa
+aabbbbabababbbaaaaabaabbbaabbabaaaabababaabaaaabaaaababaabbbabbaabaaabbb
+bbbbbbababbbabaababbabaabababababaababbabbbbbbbabbaaabbb
+bbabababaaababbabbababba
+abbbbbbabbbbbbaaabbbaabbbbabaabaaaaaaabb
+aaaaabbbbaaaabbabbbabbab
+aabbaaabbbbaaaabbabababbbabbaabbbbababbbbaaabbbababaabbbaabaaaaababbbaaa
+ababbbabbbabbbaaababbbbbaabbabbaababbaaa
+abbabbababbababbbbbbabbb
+aabbaabaabbabbabbaabbaab
+baabbbaaabbababbabbaaaba
+baaabbbaaabbbabbbaaaaaaa
+bbaaababaaaaabaabaaaabba
+aabaaabbbbabbaabaaababaabbbbaabb
+bbbbabbaaaabbabbaabbabab
+aabaaaabbaaaaabababbabba
+bababbbabaabaabbaaaabaab
+ababaaabbbaabaabbbaabaaababaabbbabaabbaaaabbbaaabbbaabab
+aababaaabbbbaaaaaaabbbbb
+abaabbaabbbbbaaaaaaabaaa
+babbbabababbaaaabaaaabab
+abbbbbabbabbaaaababbaabb
+bbaaaaabbbbababaaaaabaab
+bbaababaaaabaabbabaabaab
+bbababbaabbbbabbbaaaaabbabababba
+bbabbaabbbbbabbaabababbbaabbbbbabaabbaaabbbabbbabaabbaab
+abbabbaabbaaaaabbbabbbaabbbabaaabbaaabbbaaabaaab
+aaababbababbabaabaabbbababbabbabbbaababaabbbabbaabaababa
+baabbaabbbabbababbaaaaaabaaabbab
+aabbabaabbbbbbbbbaabaaababaaaaaa
+abbaabbabaaaaabaabbbabaabaaabaabaabaabbbaabaabaaaabaaaaa
+baaaabbabaababbababbbababababbbb
+bbabbaabbaaabbbabaaabaababbbbbbabbaaabaa
+baabbbbaabbbbbbabaabbaab
+baaaabbaabbababbaababbababaaaabbbbbbbabababaaaba
+baabbbbbaabaabbbbbabbaaaabbaabbaabbbbbabbbbbbaba
+babaabbbbbaabaaaabaababbabbbbabbbbbaaaaa
+baabbababbaababaabbbaaab
+bbaaaabbbaaaaaabbbabababbaabbabbbaaabbaaababaabb
+abbbbbbaaababaaababbaaba
+baabbabababababaaaaaababbababbbabaabbbaaabaaabab
+aaaaababaabaabababbbbbbbabbbaaba
+bababaaabbbaabbabaaaaabb
+aabbaababbabbbbabbbaaaab
+bbbbbbbbaabbbabbbabbbbba
+aabaababbaabaabbbbaaaaababaaaaabbaaaaaaa
+aaaaaaaaaaaaabababbbbbbabbbaabab
+bbbaabaaababbbaaaabaaababbababbbabaaabbaabaaaaaa
+ababbabbbbbbaabbaaabbaaabbaaabbaaaabbbba
+baabababbbbbabaaababbbaabbaaababbbbaaaababbabbbb
+bbaabbbaabaaabaaababaabb
+bbabbbaaabbaabbbaaaabbaa
+bbbabaabaaaaabaaaababaaaabaaabaaaaaaabbaabbaabbabbbbbaba
+baaaabbaabbbaabaabbabbaabbbaaabaaabbbbbaaaaabaab
+bbabbabbbbbbbaabbbababbbbbaabaaaaaabbaaa
+abbbbbbbabaaabbbabbaaaabaaabababaabaabababbbaaaaabaaaababbababbabbbbabbb
+baabbabaababbbaabbababba
+bbaabbbaaaabbbbaaabaabaa
+baabbabaabbbbbabaaaaabaababbbbaaabaaaaaa
+baaabaaabbbababbababaaabaababbaa
+aaababbabbaaaaabbaabababbbabaaba
+aabbbaabaabbaaababbbaabb
+bbbbbbbbbaabababaabaabaa
+ababbaaaaabbbbbaaaabbaabbaaabaaabaabbaabbabbbababbbbabbabaaaaaababaaaaba
+baaaaabaaaaaababaabbaaaa
+aaaaaaaabbabababaaaabbaa
+aababaaaababbbaabbbaaaaa
+aaaaaaabbbaaabababbbaaab
+aaababaaaabbbbababbaaaab
+aaababaabaaaabbaabbaabab
+bbaabaaaaaabaabbbabaaabbababaaba
+ababaaabbaaaabbabbaabaaaabbababbaababaaababaabbbbabbabbb
+aaaaaaabaaababbbbbaaaabbbbabaaaabaaabbabbaabbbab
+abbabaaaabaaabbabbabbaaaababbbbbbbbaaaaa
+abaaaaababbbbbababbbbaba
+abaabaaaaabbbbaaaaaabaab
+babababaaababaaaabaababa
+bbbaaaaabbbbbbaaaabbaabb
+aababaaaaaaaabaaabbbbaab
+ababaaabababbbaaaaaabbab
+baabbbabbbaabbbaabbbaabb
+baabbbbaabbbaababbababba
+bbbbabaaaaaababbbaababaa
+aaaaabbabbbaabbaabaabbbaaabababababbbbba
+baabaaabbbaabaabababaabb
+aaabaaaaabbabbaabaabaaaa
+aaabaabaabbabbabbabaabab
+babaabbbbaabbbbbabaaabbabbaabaaabbababbababbbaaaababaabb
+baaabaaababbabababbaaabbbaabaaabbaabaaaa
+baaabaabbbababbbabbbbbabbabbaaab
+abbabaaaaabbbbbababbaaaaaaaaababbabaababaabbbbbb
+abbbbbbaabbbbaaababaabaaabbbbabbabbbbababbababbababaaaabbbaaaaba
+aaabaabbabbbabaaabbaaaaa
+bbbbaaabbbbabaaabaaabbbb
+babbbaabbaabbbbbaaaabaaa
+aaaaabaabaabaaabaabbaababbaababb
+baababbbababbabbbbbbbaabaaaaabbababbbbbabaaaababbbbbbbbbbbaaaaabbabaaaabbababbab
+baabaabababaababaaabbaaa
+aababbabababaaababbabaaabbababbaabaababa
+bbabbbabbabbbaababababba
+abbaabbbaababaaaabbbabab
+aaababbbabaabbbbbbbbabbb
+aabbbbabbaaabaaaabbbaabb
+abbbbbaabbbaabababaabaabababbaba
+aaababaabbbbaaaababaaabbbaabbabbaaaabbaaababbaaa
+bbaaaabaabbabaaaaabbaaabbbbabbab
+aaabbababbbbababbbbbaaaababaaaaaababbaababaababbaababbbaaabbaaba
+abbaabbbbabaabbbababbaab
+baabbbbbbbaaabbbbababbbbbbaaaaaaabbbbbaaabaababa
+aabbbbabbbbababbbabaaabbbabbbbbbbaaaabab
+baabbbaabbabbbbababbbbaa
+babbbbbbabbbbbbbaaabaabbbbbbbbbabbaaabaa
+bbbabaaabbbbbaaaaaabbaab
+abbbbbababaaabbaaababbbabbaaaaabaaaaabaabaaaaabb
+bbabababaabbbaabaaabbbbabaaabbab
+aaabbbbabbbbaaabbbbabbbbbbbbabbbaabababb
+baaaabbaabbababbbabaaaaa
+baababaabbaaaaabbababaabbbababbbababbbbabbabbaabbaaaabbabbaaabbbbbabbabbabbbabab
+aaaaaaaaaabbbbababbbbabb
+abbaaabbbaaaaaabbababaab
+abaabbbbbaabbabaaaabababaabbababaaabbaab
+aaaaabaabaababbaabbbbaba
+bbbbbaaabbabababbaabbabaabaaaabaaabababb
+aaaaabbaabbabaaaabbabbbabbbaaabbbaabaaaabbaaaaaa
+aaabaaaaaaaaabbaaabaaabbbaabbbabaaaaabbbbabaaaaa
+abaababbaababbbbaaabaaaabbbbbbbaabbaabaa
+abaaabaabbbbbbabaabbbabbababaaba
+bbabbaaabbaaaaababaaabbaaabbbabbbbbbabbaaabbabba
+aaaaaaabbaababababaabbaababbaaaabaaabbab
+bbbbbaaaaaababbbbaabbaab
+abbaabbbbbaaaabbbbbbaaaabaabbabbaabbbaabbbaabbab
+aaaabbbababaababbbbaababaababbaabbbabaababbbaabbbbaabbbaababbbaa
+abbabbaaabbbaababbabaaab
+aaaaaaababbaaabbbbaababb
+baaabbaabaaabbaaabbbabba
+babbbaabbbabbaabaabbaabaaabababa
+aaaababbabababbbababaaabbbabaababbaababaaaabaabaabbabaaabbbaabaa
+aaaaaaabaabbabaaabbabbaaaababbbbabbabaaabaaabaabaaaabbbaaabbbaaa
+abbbbbbbbbbbabbabbbbaabb
+baaabbbaabaababbaaabbaba
+bbbbbbabbabbbabbaabaababbbbaabab
+aaaaababbbbbabbbababbaabbbbbbabbaabbbbbbbbaaaaaa
+ababaabbbababbbbbbbaaaabaabbbaaa
+aaaababbbbbbabbabbaabbaa
+aaabaababbbababbbabbabbb
+bbababaaabaaabbaaabbaaaa
+aaaaababbbaabbaaaaaaaabaabbbababbbbaabab
+aabbaabbbabaabaabaaaaaaaabaababbbabbbbbaababbabbababaabaaabbbabbaabaabbaaabbbbba
+bbbbaaaabbabababbbaaaaaa
+abaaaaabaaaaaaabaabbaaabaaababaaaabaaaaa
+babbbaabababaaabababbaab
+baaaaaababababbbbaabababbbbbbaabbabaaaabaaaaaabaaababbaa
+aabaaabbaababbabbabaabbbaababbabaabbbbaa
+ababbbbbabbbaabababbaaba
+bbababababbbaaaaabaabbabaaabbabb
+bbaabaabaabbbaabbaaaaaabaabbabbbabbbbaab
+baabaabbaababbbabbbbbaba
+aaaaabababaaaaababababba
+abababababbbabbbbababaaa
+ababbbaabbabbbbabbbbbbaaabbbbabaabbabbba
+babaaaaaaaabbaaabbbaabab
+abaaababaaaabaaabaaaaaaabbabbbaaaababababaaaababaaaababbbbabaabbaabbbbba
+aaababbbbaaaabbbaaaaaaabbbbabbbaaabbbbaa
+babababaaaaababbabaabaab
+bbaabbbababbabababaabaababbbbabaabbaaaaababbbbab
+abababbbaabbbbababbbaaaaaaabaaab
+aabaabaaaaaababaabbaaaabaabaaaaaaaababaa
+aabbbaabbbbbabaababbabba
+abbbaabaaaaaaaaababbbabbbbaaaababbbbbababbbaaaaa
+aaabbbabbbbababbbbaabaabbaaaabab
+aabbaababbabbbabbbbbbaba
+abbaabbabbbbaaaaabaaaabbbaaababb
+aaabababbbbbaaaabbbababb
+abbbbbbbaaabaababbababababaabbbaabaabaaa
+bbbabababaabbababaabbbbabaababaa
+bbbabbabaaaabaaaaabbaaababababababababaaaaaabbbbaaaaabaabbaababb
+aabaaabaaaaaaaababbabbbb
+aabbabaabaabbabbaaabbbbaaabaabaa
+bbaaaabbbbbabaaabababbbaaabaaababababaab
+bbbbbbbaaabbbbbaaaaabbab
+babaabbbbaaabaaabbbababbbbbaabaaabbbbaba
+bbaaaabbbbbbaaaaabababaaaaabbaaabbbaabba
+bbabbbababaabbbbaabaaabaaaabbaaa
+baabaabbabaababbbbaabaabbaabbabbabbbbababbaaabbb
+babbbabaabbbaababababbab
+aabaaabbabaaaaabbbaaaabbaaabbaba
+aaaaabaaabaabbbbaabbbbbb
+aaaabbbabbababaabaabbbaabbbbbababababababbbaaabbaaabbabaaababbba
+abaaaabbabbbbbabbbabbbababbaababbbaaabba
+abababbbbaabbbbbbabbbbbbabbbbbabaaaababbababaabb
+abaaabbabbababbbabaababbbaabbbbababbbaabbbaabbaa
+babbbbbbbaabababbbababaaabbabbaabaabbabbaabbbaaa
+aaababbababaaaabbbbaaaaa
+babaaabbaabbbbbaaaaababa
+aaabaaaaaabbaababaabbabababbaaaabbaabbaa
+abaabbabbbaababaabbbaabababbabaabbaaaababbababaaabbbabbb
+bbbbababbbaabaabbabaaabbaababbaaabaaabbb
+baabbbabaaaaaaabbaabbaab
+bbbaaabaaaababbbababaabbbbbbbaabbbbababb
+babbaaaababbabbaabababbbababbbabaaababaa
+aaabababaabbabaabbbabaaababbbbab
+bbbbababbbabbbababbababbbaababaababaabba
+bbbababababbbbbbabbbaaaaabaabbba
+aabaaabbabbbbbaaabaababaabaaabab
+bbabbabaabaaaaaababbbbaa
+abaabaabaaaaabaabbbbbabababbabbbaabaabaa
+bbabbbaababbbabbaabbaaabbabbabaabaaabaaababaabaabbbabbababbbbabbbabbabbabbaabbbb
+aaaaabaababbababababbbbbaababbabbbabababbbbbabbb
+abaaabbabbabbbaaaabababb
+abbbbbababaaaaabbabaaaaa
+bbbabbabaaabbaabbaaaabaababbaaab
+bbbbbbbbabaabbaaaabbbaaa
+baaabbbaaababbbbabbbabbbabaabaabaababaab
+aaaababbbbaabbbaaaaababbbabbabba
+bbabbbaaababaaabbbbbbbbabbaabaababbabbba
+aaabababbabbbabaaabbabaaaaabbaba
+aabaabbbbaabbbabaaabbbbabbbbabbb
+bbbbbbabababaaababaabbbbaabbaaaabababbbb
+abaaaabbaaabaabbbbaaababaaabbaabaabbbbbb
+baabbababbbaaabaababbbba
+baaabbbabababbbaabbaabab
+babababaaaabaaaabbbbabbb
+babbababaaabbbbabbbaabaabaabbbbbaaabbbab
+baabbaabbababbababbaaaaa
+bbababbbaaaaaaaabaabbbbaaaaabaaa
+abbbaabbbbbbbbaabbabbbabbbbbabaaababaaab
+bbaabbbababaabbbbabaaaba
+baaababababaabbbbbabbaba
+abababbbaababbbbabbabaabbaabbbaaabbbaabaabbbbaaa
+bbaaaaaaaaabababbaabababaababbbbbbbbabaaaaabbabbbbbbbbaabaaaaabbbababbaaaaababaa
+baaaaabaaaaaaaaaabbabbba
+baabbbbaabaabbabbaaabbbb
+abbabbabaabbabaaaabbabab
+abaabbbbbaaaaababbabaaba
+bbbbbaaabbaabbbaabaaabbaabaaaaabbaabababaabbabbbbabbaabb
+babbbabaabaaabbaabbbbbaa
+bbabbaabbabbabaabbaaaabaaaabbaab
+aaaababaaabaaaaabbabbabaababaabaaabbabbb
+abbaaabbbbababaabaaaabaa
+baabbbbabaabaabbbaabbaab
+baababbabbbabaabaaabaabbbaaabaaabbbbbaba
+bbbababbaabbbabbbbbbbbaa
+bbbbbbabbbabbabbabbaabbbaaabaaab
+bbbababbababaaababaaabbabaababbb
+baabaabbaabbabaabbbaaaab
+bbaaaababbabababaaabaaaaaaabaabaabbbbaba
+bbabbaaabbbbbaaabbbaabab
+ababaaababbabababbaababb
+aabaaaababbabbabbabbbbaa
+aaaabaaabbaabbabababaaaaabbbabbb
+abbbabaabbabbbaaaabaaababbabbabbbbaabaababaaabbb
+bbaaaabbaabbaaabaaaaaaabaaabbbbaaabbaabaaababaaabbaaabaa
+babbbabbaaabababbbabaaab
+abbabbabbaabbababbabbbbaaaaabbbabbababba
+abbaababbbaabbababbbabbaaabbbbbaaaabababaabababbbbaabbbaabbabaabbbbbabbaabaaaaab
+babbbabaababbbabbbbabbba
+baaabaabaaaaaaabbabaabba
+baabaabbbaabaaabbbabbaaabaaaaaabbbbbaabb
+bbababbbabaaaabbbababaaa
+baababbaaaabbbbaabbababbaabbaabaabaabbbabbabaaab
+bbbbbbaaabbbababbaababbbbaaabbaabbaababb
+bbabbaaabaabbbaababbaabb
+ababbbababbbbbbbababbabb
+babababababaaaaaaaaababababbaaabbabaabab
+abaaabaaabbaabbbbabbaaba
+aaaababbbabbbbbbbbbaabba
+babbbabaaababaaabaaababb
+ababbbabbbabbabbbbababaaaaabbbaa
+aaaaabbbaabbaababbbbbbbbbaaaabbbaaaaabaabbbbaabaaababbaabababbabbabbabbb
+abbabaabbbabbbaaaaabaaaabbbbbaaa
+bbbbabbaaabaabbbaabababb
+bbbabbaabbbaabaaabaaabaabaaaaaabaabbbbaa
+bbbababbbabaaaabaaabbaba
+abbababbabaababbbaabbabaaaabaabbaaaabaaabbabbbbbababababbbbaabba
+aaabaaaaaababbbaabbaabab
+abaabbaabaaabababaaabbbababbbbab
+aaaaabbbbbababbbbabaaaaa
+aabaaabaaababaaaabaabaaa
+aabaabababbbaaaabaabbaaa
+babaabaababaabbbbbababbbaaababbaabbabaabbabbbbabbaabaaba
+aabaaabaaaabaaaabbaabbbb
+bbbbaabaabaaabaaaababbbabaabbaab
+bbabababbbabbbbaabbbbaab
+baabababbaabbbbbbaaabbbabbbabbbbbabaabbababbaaabaabababa
+abbbabbbabbabbabbaaaabaabbbbbaaaabaabababaababaaaaabababaababbba
+baabbabbbaabbbbaabaabbabaababbaa
+abaababbaaaaabbbaabbbaabaaababbbbbaaababaaaaababbabbaabb
+bbbabbbbababababaaabaaabbaabbabaabbabbbbaababaaaabbbabbbbbbabbbbaaaaababbaaaaaaa
+aababbabaabababaaababbabbaaaaaaabbbbbbaabbaaabbbbbbaabbb
+ababbbabaaabaababbbaaabb
+abbbbbbaabbbbbbbbbababba
+bbabbbbabbabbbaaabbabaababbbaaaaaabbaaaa
+bbaabaababbbbbbbabaabaab
+aaaaabbabbbbabbabaabbbbbbabbabaaababbabbaabbaaaa
+abbaabbabbbbbbbbabababba
+abababbbabbababbabbabbaabbbbaabb
+baaabaaaaaaaabbabaaababb
+abaabbbbbabaaaabbaaaabaa
+bbaabaaabbaabaaaabbbbbaa
+baabaaabbbbbbbbabbababaaabbaaaab
+bbaaabababbaaabbaabaaabbaabaabbabaaaabaa
+aababbbbbbabbabbbbabbbbaaabababb
+abbbabaabbaaaaabaaabbaaa
+abbbaaaabaaabaaaaaaaaaaabbaabbab
+aaabaaaabbbbbbbaabbababbbabbbabaabbabbaabbbbaaaabbbaabbb
+aabbaaabbbabbabbbbbaabaaaaaaaabaabbbaabb
+babbbbbbaabbabaabaaaabab
+aaaaabbbaaaaabbaaababbbaabababab
+baabaabbbbbbbbbabbaabaaababaabab
+aababbbbaaaabbaababaaaaabaabbbabbbababaaaabaaabbaaaabaabababbbabbabaabbabaabaaaa
+aababaaaabbbababbbaabaabbbbababbbbaaabababababba
+bbbbbbabbabbababaaaaabaabaabbbaabbaaabababbaaaab
+abbaabbbaabbbbabbbabbaba
+bbaababaabaabbbbbabababb
+aabaabbbbbbbbbbababbababbbbbababbabbaaab
+bbabbaabaabbaabababaaaabbabbaaaaabaaabab
+babbaaaabbabbabbabbaabab
+bbbababbabbababbbabbaabb
+aaababbabaaaaaababbbabba
+babaabaabaaababaaabaaabaaaabbabb