summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-12-19 18:02:47 -0700
committerJack Sangdahl <[email protected]>2024-12-19 18:02:47 -0700
commite785d6e4143fe9a622815dbc177c4e75e3e7cc40 (patch)
tree98c7798ff5b37d4653a2f3965bb3faf37fa8e5f9
parente75402d219ad06ce5b61b5d58b8e9ad86677497e (diff)
downloadaoc-e785d6e4143fe9a622815dbc177c4e75e3e7cc40.tar.gz
aoc-e785d6e4143fe9a622815dbc177c4e75e3e7cc40.zip
Day 19 2024
-rw-r--r--19_2024.py29
-rw-r--r--data/19_2024.txt403
2 files changed, 432 insertions, 0 deletions
diff --git a/19_2024.py b/19_2024.py
new file mode 100644
index 0000000..4ddf0fc
--- /dev/null
+++ b/19_2024.py
@@ -0,0 +1,29 @@
+infile = "data/19_2024.txt"
+data = open(infile).read().strip()
+words, targets = data.split("\n\n")
+words = words.split(", ")
+p1, p2, dp = 0, 0, {}
+
+
+def ways(words, target):
+ if target in dp:
+ return dp[target]
+ ans = 0
+ if not target:
+ ans = 1
+ for word in words:
+ if target.startswith(word):
+ ans += ways(words, target[len(word) :])
+ dp[target] = ans
+ return ans
+
+
+for target in targets.split("\n"):
+ target_ways = ways(words, target)
+ if target_ways > 0:
+ p1 += 1
+ p2 += target_ways
+
+
+print(p1)
+print(p2)
diff --git a/data/19_2024.txt b/data/19_2024.txt
new file mode 100644
index 0000000..cdb3c39
--- /dev/null
+++ b/data/19_2024.txt
@@ -0,0 +1,403 @@
+grrg, buwuurr, w, bguwu, uuuu, wr, wuw, brbug, buwrg, wwr, uwr, buu, gurw, ubrgg, wggww, urgbr, wur, urur, wguw, buurb, ugbrwwb, gbr, gb, wurww, wgruw, rrwgbur, wrg, wru, urr, wwbgru, bb, rrr, gwurbgb, bgguur, rurru, rwggru, uwbuwbr, rwww, grbbrr, uuw, ubgwu, rwrrr, rwgrbu, rbu, ub, buubgrr, ruu, rggwgr, bgwgwu, wuwgbg, bgugg, bbb, gbwur, buwrubb, uwgr, grrggug, brgu, ubg, ggur, uuwr, gbuu, bwwgrb, wbu, bbrbb, ubbrr, rrwrggb, urbu, ubrb, grb, brww, uuu, uuwg, bbwr, wwgg, buwubg, gwuuru, bguugrwu, rwwugr, rwru, rwwwwg, bgug, urru, bwuug, bugrr, wggr, buw, gub, gwgrgg, brugwg, wug, grbrw, bgbbb, ubwrg, rubr, grrubug, rubuugwr, gbgw, rwgwgg, ubw, bwbwwrb, brbwg, gbgg, rgwrur, guwg, grg, rwwubg, ugu, urbwrg, urg, gugbwbr, gwg, gbg, rruwug, wuwwug, gwgbg, wuuubu, rwuwbb, urrwur, rrgbubw, rub, rgr, uuuww, wrgu, ggg, brwb, rgrwg, bwr, ugwggwb, wggbguw, rwwgb, ubr, gbwg, rubug, bwg, bru, uwu, wbwggbr, ggu, guuub, uur, bww, ruguwgg, wbwrb, brwg, rrw, r, wgrb, ggrb, uwb, uuugbbr, brubb, bggb, urwubrgg, bgbw, rbgrrrgg, ubbg, rww, uuruggrw, rugw, uug, bgbgr, uwrb, wg, gubr, wbb, gwr, wwrw, wu, wwrgu, ugrrgu, bbguu, uwwwg, rrg, uuuwgu, grbbuwg, gguu, gugg, gurg, bgg, bug, ugb, rwr, wgbbg, gwgwuu, wuwbbbw, wgbr, wuggur, gwgr, bbuubuww, uub, br, bggwu, brg, rbg, rwb, brwwwg, ruwrg, wbr, ubwwww, gbww, rbww, rwuwbu, wbuburw, rrgg, uugbub, urrbb, wwgrb, wrub, guu, rgugb, wrubu, rbwgwg, gbgwubr, uwbrbu, wuru, rbbgu, wwg, rbguugr, brb, wbgbrr, guw, rguw, rbrgub, bgu, gurrrg, ggrbg, guwr, bwbb, wbgg, ugggb, rrrbggb, rurg, gug, rwg, urrrb, wbubg, wrbbubw, bwgu, bwurw, urrg, gbw, rrbr, rbrg, brwbww, rbgb, uurb, bwwgwgrg, wrwbuu, bwbgw, rug, ww, grr, rg, rbwbrbrr, rgrg, wwb, rurr, ubwu, rgu, www, gbb, bbw, rbw, gbgbwbw, ur, gguwuggr, gru, uru, rbuw, rrbgr, wuu, wgg, bg, wbuu, rwbggb, uggbg, gbu, bbgruuuw, rb, rggb, ubbuub, ruwubgbr, bub, guuru, ugg, uuggbuw, rbuur, gbrw, gu, wbuugwr, ubb, urbuuwu, wrgub, rwu, uuww, wgwgbg, uww, rwwb, rbbubggg, bgb, rrwuwwg, ubugw, brw, gww, bgr, rbur, rr, buwg, wub, wbwwuu, wuruuwr, wbur, rgbwu, rbgwurg, uwg, uwrrg, bruuw, rgg, gubu, bbbubbb, bgrw, urb, wgw, rrgwu, wubbgr, bbr, bwuwu, rbbu, rrb, wuuwggww, ubwg, uwgub, bgubgru, rwubu, wuwgbgg, ggb, g, bbrwrgwu, wbg, wwru, rbwugr, urwwuu, wwwgug, gbur, bbggw, gwbrru, wrbr, ggr, ubu, gbwugw, u, grur, rgub, bggr, bwrw, wurb, ggggw, gwurrwrw, bgrubw, wgr, rrbrrwb, urwbubgr, grw, rgw, bbrbr, urbrr, brrbruuu, uwbbw, rur, ggw, ruw, uu, ubrw, rurgb, gbrr, gwwbu, ugr, brwubuub, bwb, wuugr, wrrub, uugrbr, bgwr, gwu, gwbw, wbru, gwb, rgrwur, wrwur, bw, bbu, wwu, uwwb, gbbb, grrb, uwuwbwrw, gur, rgbbu, gbwbgg, bbrur, gw, ru, guwwbr, wgubb, ggug, ugw, wwgwugg, wgrw, grrw, uuggb, rwbgbr, wrb, wbw, bbg, rw, uwgbgu, bwgw, gr, rgwb, rbr, rugubb, gwuggbb, ruww, bwu, rwuggr, bubrb, rbbub, uggr, brwugur, wgu, bbwb, gbwbu, rwbubu, ug, wb, rrruu, bwbbrb, rbb, uwwgu, bgw, rwwr, urw, wgb, gg, bruwrbr, uugwgbgu, rru
+
+burwurwrwgwbrbggruuuwwwuwuurgubwwguburrgbwgwbw
+wgbgguwrrwrgwurrwrwrburrugrwgubruugbwgbruubuugrwwwrbw
+buruggbwgrbwbrbrrrururbwrbburwuwwbrubrbgwgurrguggruubururr
+wgwbwuuuwrwrrwbrbgugwbuwuubrurrgbbbgrurwuuwgbuwburbbgbg
+uwwwurgwrwbguurgggrgbrwbwurrrwgbuwbuwrrrwwggwuwggggr
+urgwguwgbrbbwwubwbguuwbrbugwrbwbrrrbgrgrubrwubb
+gruuwrrgwbwubugburwwguugbuubwbbwurbwgggbgwruwwg
+ggbgbubwggwuuuwgggguwuggrgwuggurrbwuuwgbuurgbwwbbwrggwgg
+bwrbubguruubbrgbrwwbgggrrrubbuururrgbguugrurgrwguuwggbww
+burrguubuwwgurbbggrrrgbuwrwbwwubbbgbgugbwbu
+bwbbbgwgurgwgbbwwggbwbwrrwbwuuugugguuwrwwgwbruuwubw
+uwbbwrbwwuwguwubbrgrbbugwrwuwuggggrwgbuwurbuuuwbbuuwbrb
+burrrurwbrwgrguuurbbgwgbugwwuwrrgugrbwrwuwbbwwgruurrub
+guwubuurbruuwbbuburrrgubbrbwbgggbrrbgbrubgbrgwwbr
+burrruguugbgurgbrruubgwgwrbbgruwwbbrwrwbgwbw
+burgruwrgwwrubugwbwgrugggwuurwgbgguguwbubwrgw
+burgbrbuugbwwbbrgbgwrgrgrwwwrurbbgwbggwggurrbb
+burgurubbuuruubbwgbbbruwuugbgbrggrbugbugbwrrgbrwbwbgrbugru
+rgwuurgbubbuwrggwbbrwrgggrggrgwgugwwwuugug
+burwurgguugubgbruugbrrwrugbwrrgguwrrwburgggbwbggwgugu
+buuburuwuuuuguugbbwrbwbbbbbwgwruwrguugugwgubruburwbr
+wwurggwbgwrrrbururuwggguwruwwrwbgubgwbrwbb
+wwgbwwgrwbugbgwbrwwubwrbgwwbbrrwugrururbwrrw
+grwwbgrrrubgbbuwgrburbgwbbwbubbwruurubuugg
+rrwrbbubrrubuwggwbwgwwwbgugwbgbuuwwguurbgbbbggbbr
+wuwbbwggwrbwrrwrbwbwbrbbggggbwgrbbgurwwbbruru
+buruwwwbggwrwwrwrrwbrwuugggwgbwgbggugbggbruugrr
+rbwuuwbwrurbbuwruuwuuuuwwbbugburugwbubrwgurwg
+burgrgrrgwgbbuwgrbrgwbwgwrwubwwwgugwwrrwuurbugwwub
+grwggggggwbuwurruwgbbwrguuwbrrrgrwrwgrgrwggwwbwwuubgrrgbb
+uwurrwrwrbuuuurubwwguwwgbrwwugbuugrgwurbrgbugrruwwburr
+wgwbwwrwbwurwwrggurgggrwggrurbggbwrwrgwbubuwbbwwub
+burwubwugrguwggbgwgbuubguwgrgwbbwrbrubggrurwbuugub
+bururwbubgrrubbbwubrwwgwruwgruwurguguwurrrburrurbguu
+rrbwwuguwgrrgrubggwrrgwbwbrubgruwgrrbwbrbbrguuwrgbwrwurwrb
+burbwggbgbwrruwrgrrgwgguwugwgrrrggruwbuuwurbwwwgrww
+wwgwurwuwbgguubbbgurwburgubgbwwubwrbugubwgwggwwgrwwu
+bruwbgubwbbwrrbggrrrrbguwggwwbggugbwrwwrwbbbbwuruuuuubg
+rrurgrrrwbgbubbgbugbgggwwwrggbgubgrwbwgbguugrb
+gwggrbwrbgwrwgbugbgwrbwbrbrrugbggbbggguguuwbbbwwwgug
+burgrbrurwwggrgbgrrgwurbgruurwbbgwbguwrgrwrwb
+bbwbwuwggwwbrugwurbruruguubwrwgggwgrbbuwgggrbbbu
+rgrgugbuugbwrwbwwbururuwwgubbgburuwrrwrrwbb
+gurbgrruwwrwwbgwugrwubrbgugwgugrrbbbwwbwwurgu
+burwuuguggwbwrbuuuwbwuwgbbrgbwwrgbbubgrgbrurg
+rbrrrgwwugruuburrwbggggbwrbubggrggugbbuwrwu
+bbrrbwwurbgrgrwwrgwbrugggruuubbggruwwurrwuwbwbbwwwwggrgg
+wguuuwgwwgbggbgubwbuwrbrrurubrgrrburruwbrgrwubgbuuburbw
+uuburburbwururruwbugbwgrgrwgrugwgwgrgwwurbrr
+burgbgggubwgubbgrwwwgwwrwbrwgwrwwrgrwrrwguwugggbgguwb
+bwwuuurbbwwwgbbwgubgbbbbuubuwwgrgrurbwwbrbgruuwbbbwrgbrr
+gubggwrbuubrgwurguwbbgwubrrruruurrbubrbwwuuwuwrbuw
+ubwwuwrwgrgrgwrugurrbwggubuguggggbggggwbrrgguuguubguurwrbg
+buruuuwuubbggubuguwggguuubbgrgrrurwubrrwbwugwrrwrbw
+urgguubbrgguugbrrwrrbrwwuwwuwgurwuwbbwwbwwbrrurbburbrb
+burururbwbrurbwurbgrrrgguuuguuwwgggwuuwbwuubwbwbrugggwb
+burwrwgruuugugugbwgurwubugbwrbburrgruggbwugggbrrwrguggr
+wbubwuurugruwruuwbbbgbgwrbuwugbugrrgrburbbubbbubbrug
+wgwbuggubguuugguwbwbuurwbgrrgrurwbbwwgubrwwwrrgubg
+uubruwuuguwwbgbgwurwurwugbwwwbuuguggwggbggwbbwgbwr
+gbbgwbwgwrburwwwguguuwwrbwrbwuwgggbuguwugbwwrrrgw
+uuwwbwwwbwbrbuburbugbwugrrguwgrgwgwrbuugbguuwbrrubwurrugr
+wurwuuwbuuubbbwbbuwrgwuwrggurwrrgubgrgbugbruwggbwwubrww
+bggruuuwbbbuggguwrgrrrggwbrrgwbwugubwurgbgrbrbubbuu
+burbgwrbwbwurwwgbgwuwrrwgwgburgbwrurbrgugugg
+uuwgbwgbwrgbbugwrrwwwguwrwrurwurwugbuuwugr
+rggruwwrugurwgugwguwgrrwurrbgbwwwgubgubwuwg
+buruuwrubrurrbwgrrwgwguuwrwrgggbuuuuuwwuuwuggwgrrwbgubgrwbw
+burgwruwwgwrgwubbgrwrgbgwwbgrugbwrrrbrwbbguugwgbguu
+gwrrwrwwrrbuwwuwbguwurwwgbgrwbrwrwwbugrwuuubuw
+wuggrrrggrgwubbwrwgbrbwgbgwuwwurguwruubbwurrrwrgurb
+burubruurbrbgrwuwwugrwuuwwgurugbrwwbrwrgrb
+burggbubrrrruggwbgbwubuuwurgrbguwubggwrwbgwugrruwguw
+wbwgwuwrbgwrbrwgggwgrbgguwwgururrbuguuubwuurggrbwbrbwbuw
+burubwrwguguurbbgbuugurgubburubwwwggrgwwrubrwuuuubgu
+bbbrwrgwuwruuwrwgrgrwrubggugwwbbwuuubbgbgwrbu
+rruggbgwwugbrgrguwuwbrrbruuuuuubrguwwbbwbwb
+bwbgrburwrrwgubgwubwuwuwrgrbwgwuuuuuwrgbuw
+burruwubuuruggrwrgrwgburbwubburburrurrgbbwu
+burururwuuwrbrggwgguubwgrbrurrrggbrubgwwugrbugg
+gwugrgugwwggbgwrgrwgrrwbuguggrgbrgbburgugrbrbw
+bwrrubuuwubrwgruguwwuwruguwurrugbrgurgurrbbwuwwwwruu
+burwwggubbwurrgruugggububbrgwbrrrruubbbbwgu
+gbgbwbrgrgrrrgwrbwrubbrgwguguurrbbrbuugrrggrwggbwrgu
+wwrwubburruwurugbggrbwwubruruuwbuurbgwwurbwgwuurrgr
+wgubrrrbrubrbgwrwbuuwwbgwruwwruurbbwrrwgwruubw
+gbugbrwgbbrbgruuuubbggrgwbubrbugbbrbuurbugrww
+rwwggugguuguurubwgrwrgrbrrurbwuurwrbbbwrbwgrruwguggbgrb
+bwrrgwbbwrggrgurrwbwbubgbugwbwwgugwgwbuggbwrw
+rwwggwrrubwuurgwgbwwurubgwggwbuubwwguuubuu
+rggbgbbgrburrggbuwruwbwbbbgwgubuwuubgbbuuurrwrbwbrrwbu
+wwgrwrurwuwgggggbwbbrrgrrrggbgubgwwwwubbwrgwgugg
+ubgrgububburrgbrrwwururwwggwrwrbwgwgurgbwbgggrgwbwrrrbubgr
+ggbbgwbrwuguwrgbwwuwgugbrbbwgubwwuwbwgrggwrurwbwwubwrb
+ubwwwrwrugrrgbbugrbwbbrgwrurbrugwwwubwggrbbrrbgbrrgrww
+ggguurrrwrruwrwrrwwuuwbbubuwwurgrrwggbwbburguwrgbwr
+burwwwbubruwbwrbgrwwrgbrruuguwubwrggwwbwwwruuug
+rwubrurbubgwwwwbuwbggbgwuubwbwwrrruwbrrrbwr
+rwruwwwuwwbwrbbbuwrrwurgurggwgrgubbrrwgurguwbgbbbwuwugurwu
+brwbuuwrrbgrwbrrrbwbwbrbrugugrrrgbwruwrubggr
+wurrbbgruuwugrwbgrbwgggbbruuuruuubrggubrbrbgwbrrwggg
+wwuubrwrrrrrrbwrrbbrgwuuwbbbgurguruguuggwurbggwwbr
+burggubgugbwwbgwwgubgbrruwwruuruuuwwubgrwwrgr
+bbbuwrrrurbuwwuurbbububbbrrwwuwgggrrubrrwwrbgg
+guububuwuubwwwwbuwwbgwwuwggbbburruguwgwgbu
+burbubbgguwrwrruuwrbruurbbugwwwuwuugwguwruggggggwwbwwgrg
+burrrbbgrbbbwwwrburbrwubuubbuuurggurgwggruwgbrbrrbugrrbugu
+bruubgwrrwwubrwugrgbubbrubggbbrurubggruggbgggw
+burrrrugwggwwwguugrbrbgwrugugwugwuurgbwgruggwbwwrg
+burggruuwgburrbwwgwgugurbrwgbugwubuwwburwbwggugguguwbuwub
+burwugubwrubgubwwuwuuwbbwwwugguugwwwrwuurrgugwbggg
+rwubggbwrgubggrbguubwbguguurwgbwbugrwbuuwurbw
+burwgwwbuurbwbbrbrurwbbrgwruwurgwubgwwwwwrggguwuggrrgwuw
+gbubgwrurwrrggrwurbrrrgbwwuruuurgwuurbwgwwguurrgbu
+bururuwrgrwubbrbgrubgrubwbwrgwbbubrrbwbwbgrwurgbwwgbw
+burruwwrbbgbguuwbugwwrbwbgurrgburgubwwgbuu
+uubwgurwwubrwgurggurbugbwbgrwggrgwbugggwwbguwugrwuuwrrrbu
+bugburuwgurrrrrbruuugurbbgubguwuuuuubbwbbwgrrwwuwbgw
+burrwurggrbwurbwwgrbbwrbwwrgwugurwwrrbuubwwrbugbruug
+rbwbrbrgguruurgruwrbgbwruurrwugrububrrrwbwbuu
+rgwbwburbwrwwwwuurwggwbwgubwuugubwurgrwbrrwruwwgr
+buruuwrwwuwwwrggrbguwwbuuuwburgrwrrrrrwg
+ugrguuwrwbbugbguuruwbrbwggwuwuwbgbrwbgwuggwuwgwwbwbuubuubu
+burbggguubrwwuubugwbwwgwgwuurbburbuurbwguugururgwbg
+burbgbwwrrrgrgbuwbguugwwggggbbrbgwrwuuugggwrguruuwwbrwg
+rgwrugurbwgbbgugrwuguuruurbbbubuwgbggrwuugubwbwbu
+burwurggrwbrrwbgrubwwrbrwuwugbwrbrwuurgubrbuwubwbrrgu
+rurburwbgwbwuubggrbuurbbubgggrugburrgggguuwurbw
+urbggrrwbgugwbbgubbrwugwrgubuwwbgbuwrgguugbrggrbuuw
+rguwbgwwubbrbwuubgbbbgrurrrubbrwrbgruwwuwgwr
+burugggwbbbrbrgurrbruguwrgwwgubrubruggwrwbbbbbwrgwwugrrb
+bgbgrgggwggwugrrugbrbrbbuwruurrbrrgurubgwwrruwgbgbuugwubg
+burgwbrgrrruubwrugwuuugguruuwruruburgbwrgbwrruwr
+burbuwrgwbuuwwwggwwgbwgurubugurrgubgrrgbgbwrwwrwrgwbgubr
+wrurwwubwurgrbgbwururruuuwrwggruruuwuwwwgwuwggwgrgbrbrrwwu
+bwuwubwwugbwwuwbwugwurwbgubrwrurwgguubwgwwg
+bugburgrrgwwgwgurgugwwruwubwwubbrugwbbgubbuuugruu
+uuubbbbgguurgbubruwuggwbguggbuuruggrwwgwbub
+wwuwruwrwgbwbgbwuwbbgrbwrwgugrrwbrrbwwgwbgbbgbrwu
+brburubggrubrgurubrbrrubgubwugrbrwgugwuuuw
+wbruwwwwbwwwuuguwururgurwbbwuuurgguuurrurwuugwbgruuwugbwg
+gwbwrgbgruuwuwrgrwbwrurwbbbugwugwguwbbgbbbrwwugbrgru
+gwrwgbwuwbbbrgurwbubgruugbbrbgbrwbgwurrwugwgwguw
+ggurrgwbguuuurgrrwrwgggbgwbwgbgrbuuwuuwuwgbrru
+burruurgbgrrwbguruwgwbrbubguwurbbwubbrrrwruwwrrbbb
+burwrbwuuwurwrrwwgwgururuurggugwbuggggrwrbubrbbuuuwwwgugb
+bguwrwgrbgugwuugruggruwwbrgubwubugwrburgbugugrbr
+bururggrbwwbgrwuuwubuwugbbwgbugugrrwbggrgbugrbg
+bbgugbwurrgwbuwgbwugruurgrrbbgbwwrrrwbwugggr
+rrbuuurrwguwrwubgubrwgbguuwbubbbuwgbuwgrbrugbuwubrwurw
+buwbrgggbbgurggbruwrwwgbwruubuubrruwwgubggrwrg
+ggwbruggurwuwggugbburbuwuuggwururwbwubrugbrbbwbguwrbb
+guugwgbguggbbbggrrgrrgbrggururwububgurgwuwuuggggbbrb
+burubgubwbrwuwwwbwbbrrgrguurgbuwuwuuuwrbggrbwurugbgug
+burbgbwbubbubwuwwwbrgbugbbgruwgugugrbubwrgwwwurbggugwubu
+burrgugugwgrrbrurbbubgggbrgbubrbbgbgburwgguug
+burwbugbwurugguwbwbwbubwgugggburugbrrbgrubbwrbu
+uggbubgubbwwurwbrwgrbwruubwuuubgwuuuubrurbuuw
+rwrgbruggruwubggrbrbburuwuwgbbgbrurggrgbugrwur
+burrwrggrgwrrgbbwguubgrwubguwgbgwwggwgubrbwrugwgrubwgwwurrru
+burrggbruguugrbuwwubruggwwgbruwwrbgugbuuuruubgrwrrwg
+burugwrubgubuubwrbgwwwrwgrwwgugbrbgbrgrrg
+bggrwuuwggwwwbubgwbbgwwruuguuwguuuubrrwurrgb
+burbbugrgrwbgrurrrbwbwburbburwuwuuwgrbruurubbruguwwwrugr
+burrgbwubgrwuuwwrugwwuububrbubggugwgbubrrburbwbrrubuugggg
+buuburgrggwwgruwuwbubbuggwbrwrwrrburwrrwwbbbbggg
+ugruuruwwgwguggubuuwrubwuuguwgrbuubrggwbbbggbuubgubgrwbub
+burbrrwbgggwuguurwwgwurwbbbgrrrwubbwwruwrgbr
+rwurggrbrwwuwgggbgruubuwbwrgbgbgrbwwugugruubb
+gwrbwugurrrbgwuruwbggrrwwbbubbwrburgwrburruuwbuw
+uwggrbbwrrwwrwuwbugwrgwwgrrbgrbrrurubuuwgbuw
+wbwubbbwubgwugggwwwrbggwrwwggubuwburbggubbww
+gwgrrwrggbwgurrwrrgggrgbbwwrubrwwwrbwbwbwwgbburrwuuururgwu
+wrwgubbwuugguurwgggwrgbwwrrgruwruwuubrruuubwggrubb
+bgbwuuuwwwggwbrurbgbwrrubwruwuuggbbgrubwuubwuggwruuurgrug
+wwrurrrgrbgbwuwuubruwrwuggrwwgrrruugguuubwwgrgbrgr
+burguwbgbbgggbrwuwbrrbbguuugurbugbuubgwrgruurgbrwwbbwu
+burwgrrwrrwwwrbggggugwrbwuuuugwwubuuwwub
+wrbbgwuwbbrwrbuwwrbbbbburgwwurwugrrwubrurubbwugggb
+burwrubuurbwggrwugrurrgrrrubuugwrgwugwugwgbbgwuwrwggwur
+burbugrrgrgwbuuuuuugbbwrwgugwuruuggwurguggrwbwb
+wuruuurgwuwrubwgwbguubbwrbwubuuwwbwgrwubuwuggwgwgbwgrgg
+urrruwugwubwbgbbuggguwggbuwrurrggwwwbruubuw
+rrwuwugbubgrbwubgrbuubbbbgubwgwrurwgrrubrwubuubgrwwg
+rgbuugwgggwgwrrbgbwurggwgbuuugrwuuugguwwwwbrruwguuwww
+burrubrrbuwbrrwwgrwbubgrrwubwbbbgrgbggwwgururrgubuwwgurbburu
+wrwrgwwrgrubwwwrggwgbwgrwwugugugwgrubrggrgubwwrgrbg
+burgbubggruwbuubbrburbgrrwugrbrrrrgrwwgrbrbur
+burrwbrrgbbwruwubwrwwuuburubbwrbwwrbrwgwgbugrr
+brubrburguggbgggbgurbrwrggwwggbbwwubrbbrgggwgbwgbgwgggu
+gwuwbbrgrwrrggugbbbbrbrrubgurwubbwwbwwrwbuwwrwuggwrwbu
+brgbubgbguurubgbgrwrgbwrgwrrrbrrwubbbbgrrrubugrwuuugubgu
+burwruguwbbgubbbwgwgwbbugwurwbugwgggwbgugbggbggbwbbrggug
+wgwuugrruwrggubbbwugwrwbbggbbbgrwbwubggwbwguwwbwruw
+gbuwgwbuwggggwgbwgrggggbrwubbggwwbrbbbggugubrwrw
+wugrrbwbbgrrbgrgbrurwburgwrruuwwwrrwububwggrrrrrrbgwuguu
+grrubwurrwugrrwugububuuurwbbrbwubwbuuwrwrugurbggrwrrw
+wbwrwgwwwbuggrubgwbuuuwbuwrwrbuubuguuubrwuugrbrrruwr
+wrwuurwugbgwruugwuubguwrrwrubrruwbggbururwubrggwbggr
+wbrgurbubrwbbruuggwgbuggugggbgbuubrrbrbgwbrbbbbruugwrgurur
+wgububruguwwbbrwgubwguwwrwbbbgrgrurguguwbugbwugwrbuuurw
+brbuubbwwrgugrwwrbwwurrrbugbwrwbwrububuwrbuuurwb
+burrrguwgbggbggwbgguggwwbguuwwwbuuubrgrgb
+rbubuuwrburrwgbwrbrrwugwwrgrwwgrguubuwrrrrgbwbgbwuuug
+burbwgwbbggbwurgrugwuggubbwbbuggrgwruwwugbru
+buuugrbuurgugbrwgguuruuugbbrwggugrgbwurbrwbwwug
+bgwgbbruubrurrrwbuurwguuuuugrrwrbuurubgguwwwrbbuuwbrwbrwgr
+rguguwwwbrgrgwggwuuuuwburgbuuwwuugrwurbgbrwbrrgbwgb
+rgbbwubruuwrrwwgbbbuuruurbrrwrrbwbgurbwugr
+wurbwrbgrubrrbbwuuwuwbruuwwbuurwuugguguwuruuwbwg
+buruwbbrbbrwrbbgrburwbbrgruurwbrgwuwbburgugbugwrburruu
+wgrrrubggwgwwurrrbrwwuurgwuruwurwggbggubgwrur
+rurwbrguggwwrwgggbwugbubuurwbruuwbbwugrgubbuuuwrrgb
+rugwgwwggwwwwwbbuwrggruwbbguuwubwbbrbrguwrrwruurggbwuwurg
+uwurburbrrrwruugrgburrugrrgggbbgrbubrrbwgbwbug
+bgwgwbrbwburgbbruwwrrrurugbwwbwwbbrgruugrwg
+ggwurggwurrrwugwrrbgbrwguguuurubwuwbrwuwuruguguuuwu
+burggggrgrurbgugwrbbbbgrbbwbwwrggrgbubwug
+burwubrggbrwubgubrwwgrbubrgggruuuuuwwgrguuwugwugggrr
+ubrggggbuwggrrubbbbwggwbrgrrwbgbgggbwgwruuuggwuurgru
+gbrwuububgbrgurubwgwurwwuuuggruugbruggguwruuwuw
+burrrbugrbrrggrubruwbrwgrggguurugbbbbuuwwwwgbgbbggwrrruwubbu
+burgbbwbrbrrguwuubggbwwugwgbguwburbburwwbugwrwggbrrrugguwgrw
+gwruubbbrwbwrgwbwuubgbwrgwgbbgbbuuwgbrwrwwrgrg
+burgrruubuggrgwwrbuurrubwgrwrrubgwbbwwbuubbw
+brrbuwrbwubggbrggwguuuugbgugwubruuuurgbbwbbbgbwururu
+burggugrbguuwbwugurwurwwruwrgbruwbgburwgwurw
+rurrgbuugwbwrgrwbwgugbrubuubbuuugrwwrrbwgrrugbwrrwu
+burgubggrwgwuwwrgbwbwbrrwbwrgbrbbrgbrrruwwuwwburbggww
+bbbrrbwbbwgurbgrrgwgbububuubrgbgwbgurbrwurrbrwurrubru
+brurrwwwuguubugrubgurrbbbwwguggbbugwrrrrurwgwrrgurwwb
+burbrguugrbgrrwgrggwrbguuwwbwruugwrbugwgbrgwuwg
+burwgrbrgwgwwrwurrbuuwwuuwubwwgwgrgurwrrgbgubuurrwbug
+wwwbuwwbwrubbgrrbubbruwwrrruuugguwbgurbbuwrguwwgwggug
+buruwurgrgggbuggwruruggrgwggrgubwwugwwgrgbrbrgbbrruwru
+burbbgbbuwuururbuuwwbgwrwwuwuwuugwwuuuuwubruw
+wuwrwggwbbruwuuwurwubgugbwgwgruuuwwbrubrubrbwugrruruburgbu
+burbwbubrbwrururburgbuggwuurbrugrrwgrubgwugguuwuugrrggbru
+burwbwrgrgrwrgrgbrbwubbbwguuurbbrruggrubbrwgbuwrwgg
+burrwuguwurbrurrrgbbwwrguuuguwwrgrbggbrgrbu
+uggbruwrrbuurruwrggbrguwbuwgurbgrrwgrubwuugwbbwubgg
+burbrrwguruuwwgburuwggwgbgbuggruwubgbrwgrgwggg
+burwgrbuurgwwbwgubuwuwurwbwrubwggbrggrrrw
+burrurwuurgrguwrrwgugbwgubwugwrrwuwwgbrbgugrgg
+buwburbrwrurubuwwguuwgrbgwbrrwubwrrbrrgubggbgbrrgwwrbbubwwug
+bururuwrwrwbwgrwgruwrwugbruuwurugbbugbbu
+burrgwbubruurbububrugwgubuurrrrrrbgbbbwbr
+gwrurbrwgububrggrbggguuwrrguurwrgrrbrwbruuguwbrrgg
+burgguwrruwgbbubgrgurbwwbbgwbruwurggwgbwwgwwrrww
+burbuuwrruggbwwbwgbuwurwrwrgrgubrbburbubgugugwgrubrugubbrwr
+uwgwurgwwbuwbbbwggwwwrggggbbburbugwwgwbwwgrw
+gwrrrbgrugugubrwwwgugwbwwbuwbubrwgbwuubgguuwubgburgbgugu
+burguubgubuurwbgbwbwbggugbggwbgrwrrurrggbuuwrrwugggggb
+gwgrwwbgwbguuuguugrgbwbrgwwbbbrwrwgwggbgbggwwwgrrugggg
+bbbuwbgwbgbwgguwwbgrrrwwrbwuugbwbbggugwwrgbbwrr
+buruggrbgwbgguggwruggubwgrbwwrwrbrwwgrrbbguwbgrbwgu
+burbgrwbuwugugwrubbwrgubwuwrgbruwguuubwrrgu
+bububguwuwrrbbgbrgbruuuurrgggubrbbruwrugub
+burrbrwuguubbrrggugbwuwggrrbrgbrrgurggwugrbwbgur
+bururruwbrwwuuwgbugwubuububrwgbgburgubgwrbbbrwrrggwwwwgb
+burrwwubuguurguggrggrurruggbgggguuwwbrbgwggwbgrbbg
+burgrgubuwururuurrrbrrrwruwrwrbwbbbggwgbbwuub
+burgbbwuggrbwwbuwrurbbwubwwuubgrbguwbbwrruubwuwbgbgbuwbuub
+uuugwuwbwubgwubugbbugbbwubuwrbwgwrurrbwwwg
+ugwuubrbubrrrbgrrrgggrubggwwgwguwbbwuuwrwr
+burruwurguubrwrbwwbuururbwwbgruwggwwwbwurwruuwgwrgrububbr
+bwggbwwwggbwwgwrrwugubwwguwubburwwwwggbubrbuuub
+burgbwgwbwbwgggwurbbbgrrwuwurwrwggruwwrrgrgrg
+wruuwurwrrugbrgwwggwrbbgwggggwwgbugbrgggwuuu
+wrbbrwwggbuwugrgruuwgbrggbgrrwgrugggruwrbururguwuugbwuuur
+burbrguurrggbggrgwrrbbbbbwbruuguwgwbubbuuwwgrb
+bwgrwrwbbgrwwbuwgbbubbgrwrbgrrurrubuwuwbwrwwuurbgbur
+rwggrugrguwgrwurwrwuuuwrwrwuwgubwrbrruwwwwgruurwuwguwgwrr
+gwgwurrrruubuguguwrgurgubgbbrurbubbgguuurugbwrwbb
+bwbuubugwwuruwrbugrggugwrwugrbuwggbrbrugrbwbbr
+urbwuurrgwwwbubgwubwbgrwgwgwrruguwgbwwwbwbbbrgbwwububuug
+ruubrbrwbwgbbrrbubwbugrbbwbbbwwwguwuguuugrrbgwwwurrr
+ubrrbgubwwugrubruurwurbgrgruubrgubugwwgruwwurwg
+bwrrrgrbwrgbruwbrrgwwuuubrbrrwbwgwuugurbrgguwwbgrrwwurg
+gbwggwwbrrugwuuurrgbgbugubwrrubgurbgubbrwuru
+burrwbbuuwugbrwbubwuruwbwbbwbwbrgwguruww
+burbrbwurbbrbbbgbbwuguugrwrwuwwwwgrgrbgw
+rbwuwububugrguruwuuguguwurwggurgububgbggggbgbbgbgb
+burgwgwwbrwgwbgbgwuwrgrwrrgbwwguwwbwgwugbbugruuwb
+burgburrgbbugguwbgrwwbwbrggbrbrgrgrbwgrubrrgwgbgwwrbrwwgb
+wuwwgrrrbbwuwurggwrrguwruurwwubububbwbgwugggu
+uubrwguuuwbuurruwubrgwugwubgwbrwwbwrrrwrurbgbrgruuw
+wggubbggubugbgwwuubwubgbgwrrggugburbbrurwggrwurbwguubbg
+gwgruurrwrgrrwruwugguwruguubgrugggwguggguwbguburgbgbuu
+rguggwguwwwuuwbubrwuwbwwbggbbbrbrurguggbrbuwurgurr
+bubguwgrwwrgrrgbrrwwrrrbgbggwuwurbgwwwgurrrrwwurrguubru
+burbwwwwwwrgwbuubwwwwrbwrrbwwwggrguguugggubwgwwgwbgrg
+rgrrgggrwbwwwbguubgrwuugwgubbubbwwruwbgbrrbguuggu
+rugubgurbwbgrggugwuwubuurguwwbwuuuugbugwruwrwruwrwgurwwgbu
+bgrggwgwuuurwburugwbubguwwruwubgbrrgbuwwbgubgwrwbwwwg
+gwwuuwrggrbwruuurbugwwguwuuugwuggubgbgwgugwbwwwwrubrwrggru
+wrbrgrbbbruruwubwgrburugwwugrurrrrrugbrrwggbwwgrggr
+burwuwgugggbwurrurbrbrggbgugguuwwwrurwwbubbrgrgrrugrurrrg
+urwbgwrbbgguwguwbrwwubwwgwbrwgwububbgwrgwu
+gwgbwguubwrrgurrbbuurrrugruwbbbwrgwgwuwwwbubuww
+burrugbwuuugwgrwwbwrrbgwuwwwwrrwgwrgugbuwbb
+burwbugrbrrrrguuggrrgguggbrruwwbuwbgruwbwugwuwr
+burwbrrrrwrwwuuggbwruuurwuwgbrrbgwbwbrbrrbwrruuugugu
+burruubwwrwrbrrugwugbguugrwuurwrrrurbrbrgbgb
+buwwuurwgubuwbgbrrbrbwbbrwgugwgbwuguubrguwg
+guuubrbgwrgrbrbuggbgwgwbugrbrubbgguububwgurg
+brrwwguwubbgwgurbgrgbuwggwbwbuurwgubwgwuuwwrububrubgubu
+buruurbbruwgbrggwrgwrrwrubburbggguuwuubbrbw
+buggrrgwwggubwgbbggguwuwwguuwruuuuubwggggbbrub
+bgggrgbguwwubrgbwrubrbwwgubbbrbbrrggrbbguwuwwwubb
+grwwrggrwbwgggrbbgggwugrwwurwbgwbuugbbgwrwwuwrbwubwbrbgu
+burbgwwbwwwugrbgbrgggrrrbgrbbubgrwrwwurbu
+rgwbburwrbbwwgwgrgrggwuwrbwubuuuwgubruwwgwrbg
+burbbbrrruuruwwubuwwrruwruwrbubrbbbwbwugrurbuggrwu
+ruggrbgwwubbrrgwggwbgbrurrurgubgbbbuwggwrbr
+burgruruwbbgbuwbwwbbrrrbbguwrrgwuubrbgbruwubwuu
+bugwwggrggbgubwwwbrrgrwbbrwrgbgwbuubbwgbwbwguwrgubwu
+wurgbwbwrbwrbbggrggbgwugbubwgubwgburwgwuuggwgrwbbrrwwrub
+grruruwrrruurbgwurgrwubbwgbwwbgwugbgrwbrgbrwgrwgbgubru
+grgrrwrgggbwuuurwwrbbbguubububrubrgwbwbbgggbrgug
+burbbbwrbbrbuubbgrurwrrbbwrubwwbrrgwbwgwgrwrwwrubbggrbwwbru
+wrguuuuurgubrrgwrrgggwgwbgwwgbgwbgwubburrbubgb
+wrbgrugwrubuwbgbrrbugwruwwwuugrbbggggggubwbbgw
+bgububbgbgburgwubgrwurwgrwgbbwuggwbggggubbubbwuwggrgu
+burbwurwbuuurbrugbwbuguwgbbrrubrgbuwwrrg
+burwguuurrrwrwggrwwgrrwbbwubuwggrgwbbuwrubbrbubgggbbrrbruuu
+burggggbgrbbbrgubwuwuburbrgwbwwbgubrgrwububuurubbggu
+burbbugwbruwuubbbguwrggggwwruuburwwwgwbubwubbwbrrbbbwuwb
+burwrrggugrwuuurrrggrbruuwbwbwuurbwbubuwgbrwbgbbwwgbwbwwurgr
+wbruguurrbuburwgrwbwugbgbguwuwbgrrbbrwburwgwbwww
+guwbgrgruurggrrubwuuurbwruwgrrgububuuwgbbwwruwwrwbrgb
+gbrbbbwgbbggwrbubrrugurgggwbuwbbwbuwwwbgrgbr
+buruubbggubbrrwrbrrurgrubbwrbbbgbgrbbggwugbgrugw
+gbuuwruwgrwgbbbggrrrbwbugrgurrgbrgrbrbggrug
+bgugbgrbrbrburgbbrbugwgrrbgrugurgwguubguwgwuuuw
+wwwbbbubuwubgurgrggbugwurrwwrwgrbgguwrwbgrwuuugb
+bugburbrbwgbrgrwwbuwbrwuguwgbbuwbwubugwb
+burgwwurwwrwugbrugggwwuwgbrgbuwgbgurwgwbugubggugbuubrg
+gugwugrrbgggggugbwuuwbwwrgwwgwgbrgwwrgrgrguguwwwwbgr
+bggbrruguwuuuurwrrbggrbwrgguggbgbbuguwuggrbrurg
+buwburrrbrrrgruwbwrwrbruguuwurrruuuwbwbgruwwgbrwubuwbgub
+ubugwbrrrbuuuwrbrugwrwruuugwrwbggguuwbuguwwrwbbbbwrwgr
+wwwgwbbbwwgbbgrrbbrbruggwuugwrrgbrbugbbguu
+burgrbrbwbuwrgwgbwbwwuuuuururbrugubwwurbwwgrwbggbwbgwuuwg
+burgwwurgbbuubwbwwrgrrbgbuuuwbgrgwwwrbbgwgruruwbuug
+bwbrurbugbruurrwuuuwbgrbwrwgguugbrbburrwugubgugrbbgruuuw
+burgwrgrwwrrgbggburuwbuuwbuuuwbwbugwwwwwguwgbbwrurbgwu
+bgbwwbuwgwwrrwwwuwbbuugrrgwwuwbuuurbbbguruwrrugbubuwbbbwwb
+burggbbgbwrwurrwwbuwgrrrubbbwuruuwuurgrgwgbwubu
+wguggubrgbrubbrrggurwrrurubgwgwuruugubgrwugbruwbbbr
+burggwwuwuwbwrwgwrgwwrrurggbwuwugwbgggwrbw
+bwrwuruggbrbwwgrrrubbrbbubbgwwgbbgggrgwwrbbbrbgbwwggrgrrr
+wgbgburrbwurbwrbubrrrbwwruggbrrgbugruugrrgrggrbwbuwbg
+burwbbbbgruuuwbubuwbbbbrugrwwbrrrrwgguubr
+burrbguwuwgururbuuuuwguurbgurbwgburrurwg
+burwubrubgrrgrgubrgbwugubgbbwburwgwbwwrrwuubburr
+wrwrwbuburbrbburuuugubwwrrbggbgwwbrurwruuugbbbwgugw
+burrugrbrbwwrwbbububrububbrwugrwurubrwbrggwwgggbrbrrw
+burrguwwbruwrgurrrgwrbgrbrbgurwbgbuwrgrbggwwr
+burwgurgwbrrggrrrubrwgwrugrgrgbrwgrbgwbgwwrbbbgguwrwgggw
+rbrurgrrugrbubwurubwgbbrbbbbwgubuggbbrrrwruurugruggu
+uugwrwbuwrbgbgbwbbuwruwwgbggbburgggwbwwggrgbwubg
+burbrruwggbrruguugwrbbgubuuwuuwrbwwguubwbwbubbburggg
+bururwbggggbbggbwwwwwbrbrbwwbrbbbgrguwuwrbbr
+bwrgrgrwbbwbguugrwuuuububgrguwwbbgbbguuuwrub
+burbrwwbgguggwguwgbrugbruguwbuguugwwubbbuugbuwgrwbgbwgbwuw
+ubbrgbbrrgbugwwbgrwugbwugrgubguuwgguguugrgugwwbbgwuwgub
+burbrbrwrwwbwgbbuubuwwgggrgbwwrrwubrguwwwgrrbwwrwwgbug
+wwrbbwugwugguruugrbuwwgbwwububrguubrbrbgugbrrwrb
+uurgwwrbgugurwwwbbwuubwuubbgugbbwgrbrbbwgruwrbgrbrrrgwbb
+rubrurrgbburwggwbrrrubwrbrbgbrwgubwuubbggubggbg
+rruurbrbgurggurrbubrgbrbugrbrwuwgbrgbbubwwrbwrgwguguwurru
+buruwwrugrrwwbuugwwggubwbrgwgurbruguggwrrrbuwugwwwrbgrg
+gwwubrguwbbbuwwubbbgugbgubbguwubrwbrgrbgrbrbgwwrgbwrrbr
+burgggguwwwwurgwbwggurgggggbrgrbrgrbrwruwwbuwgwrb
+bbbrrrurrgurrbbwbbwurrbrwrbbrrbrgwgrwgubgwwgwwbuwbbrwub
+urwbgwwugubwuwbrwbwgubwbrrwurwuurguubbbgwuugbrbgbggg
+bbuubbbubwrugruuurggruburuwubrgwbwwwwwbbrgwwgbrggwubrrrr
+buruwruwbrruwrrgrbwrrggwbgrububbrwubgbgwrwbwuwrwuwwbwgw
+wrwwwurbwgggbgubwbwbgwgrbgwrbrbwurbrwgrgrbgwuwrwrwuuwwr
+ubgbuugrggbwbuwwrbrgguuurrwguwburbgwbwugurubuugwrbwuw
+burrwrbuubugbbbgrwbugwbgugrbgwurrwrwbgwwbrrbbgguggggwug
+burgwuwuwwrbruwrgwurgubggggwrrgugbrbgubgrwururbrubrgrr
+bugburuuuggwggruwwgwbubgbrruwrrruwwggbrwrgurrbuuwwgrggguw
+buruwggurbrbrbbbburwgrrbrbbrgurwwugggrww
+burgrrwbrwuwbrrbbuwgrwwrurbwurgruruwwwuuugrggrwgbwbugbuwu
+rbrugruuugbrbwrbwwbgbrrbbrruwbbuwgrubgggrbgrrugbrb
+rbbwbwwwggwrwwgwwubbbuwubggbrrruwburruwwguwwggrugbbwru
+bbrgwubggguwrruwwrurbrbwggbwwrbguguugwugbgwbbubrg
+wbbguuwrguugwrurbbubwuwrgbbwburbbwrgubuugwuuuuwgwu
+burgurbrgwugguuubwuugwuwuruuwruwurgggbrwgbuugugg
+ugrrwrwgugrrurguburrgwbwwugwurugbbuuwurrgbrru
+wgrwbuurugwbrgrrrbrgggwbrbuuwgwgrrurruugwrbgbgbwbgbuugrubr
+wuugwbuuuggwbrrwggwwubbrwruuwwwwbrgrbbruuwwugbwrbruurwgu
+burugguruwgrgrbbrbrbrwrbbruwgbrgwrubbrwrgwubbwubuwbg
+bwburbwrbggggrgbwbwbwubwburbgwbbuuugggrrgrurwgbrru
+gwgbbbwgrrbgugwwbbwuugwrwwbugbggbugrbgrgbrbur
+buruguuwgrugbuwuwgrrgrbbuwbguwgguggubgbbguuggbgrrrwruur
+buruwgbbgrwgwrbubggurbgrbrbbbugbrwbrbwrgr
+buwburgwuuubwbwwuuruuwbbrwbrbwgwrwuuwggwwguuwurggrgggwbw
+