diff options
| -rw-r--r-- | 2020/16-Ticket_Translation/example | 12 | ||||
| -rw-r--r-- | 2020/16-Ticket_Translation/first.hs | 85 | ||||
| -rw-r--r-- | 2020/16-Ticket_Translation/input | 260 |
3 files changed, 357 insertions, 0 deletions
diff --git a/2020/16-Ticket_Translation/example b/2020/16-Ticket_Translation/example new file mode 100644 index 0000000..fe34e40 --- /dev/null +++ b/2020/16-Ticket_Translation/example @@ -0,0 +1,12 @@ +class: 1-3 or 5-7 +row: 6-11 or 33-44 +seat: 13-40 or 45-50 + +your ticket: +7,1,14 + +nearby tickets: +7,3,47 +40,4,50 +55,2,20 +38,6,12 diff --git a/2020/16-Ticket_Translation/first.hs b/2020/16-Ticket_Translation/first.hs new file mode 100644 index 0000000..86731b0 --- /dev/null +++ b/2020/16-Ticket_Translation/first.hs @@ -0,0 +1,85 @@ +-- requires cabal install --lib megaparsec parser-combinators +module Main (main) where +import Control.Monad (void, when) +import Data.List (foldl') +import Data.Map qualified as M +import Data.Void (Void) +import Text.Megaparsec +import Text.Megaparsec.Char +import System.Exit (die) + +exampleExpectedOutput = 71 + +data Range = Range { field :: String + , ll :: Int + , lh :: Int + , hl :: Int + , hh :: Int + } deriving (Show) +type Ticket = [Int] +data Input = Input { ranges :: [Range] + , myTicket :: Ticket + , nearbyTickets :: [Ticket] + } deriving (Show) + +type Parser = Parsec Void String + +parseInt :: Parser Int +parseInt = do + n <- some digitChar + void $ optional (char ',') + return $ read n + +parseRange :: Parser Range +parseRange = do + f <- some (letterChar <|> char ' ') + void $ string ": " + ll <- parseInt + void $ char '-' + lh <- parseInt + void $ string " or " + hl <- parseInt + void $ char '-' + hh <- parseInt + void $ char '\n' + return $ Range f ll lh hl hh + +parseTicket :: Parser Ticket +parseTicket = some parseInt <* char '\n' + +parseInput' :: Parser Input +parseInput' = do + r <- some parseRange + void $ string "\nyour ticket:\n" + t <- parseTicket + void $ string "\nnearby tickets:\n" + nts <- some parseTicket + void eof + return $ Input r t nts + +parseInput :: String -> IO Input +parseInput filename = do + input <- readFile filename + case runParser parseInput' filename input of + Left bundle -> die $ errorBundlePretty bundle + Right ops -> return ops + +compute :: Input -> Int +compute (Input ranges ticket nearbyTickets) = foldl' compute' 0 nearbyTickets + where + compute' :: Int -> Ticket -> Int + compute' acc nt = acc + (sum $ map isValid nt) + isValid :: Int -> Int + isValid n = minimum $ map (isValid' n) ranges + isValid' :: Int -> Range -> Int + isValid' n (Range{ll, lh, hl, hh}) + | (n >= ll && n <= lh) || (n >= hl && n <= hh) = 0 + | otherwise = n + +main :: IO () +main = do + example <- parseInput "example" + let exampleOutput = compute example + when (exampleOutput /= exampleExpectedOutput) (die $ "example failed: got " ++ show exampleOutput ++ " instead of " ++ show exampleExpectedOutput) + input <- parseInput "input" + print $ compute input diff --git a/2020/16-Ticket_Translation/input b/2020/16-Ticket_Translation/input new file mode 100644 index 0000000..3a28a2a --- /dev/null +++ b/2020/16-Ticket_Translation/input @@ -0,0 +1,260 @@ +departure location: 34-724 or 735-974 +departure station: 40-521 or 534-950 +departure platform: 40-329 or 353-973 +departure track: 37-258 or 268-964 +departure date: 32-650 or 665-964 +departure time: 39-373 or 398-950 +arrival location: 42-431 or 447-952 +arrival station: 36-536 or 552-972 +arrival platform: 45-666 or 678-952 +arrival track: 49-836 or 852-952 +class: 35-600 or 623-953 +duration: 50-920 or 929-950 +price: 35-853 or 870-973 +route: 34-309 or 318-965 +row: 42-267 or 292-962 +seat: 46-632 or 642-954 +train: 47-746 or 754-960 +type: 32-406 or 423-963 +wagon: 37-797 or 810-973 +zone: 35-766 or 784-952 + +your ticket: +113,53,97,59,139,73,89,109,67,71,79,127,149,107,137,83,131,101,61,103 + +nearby tickets: +688,200,60,127,239,85,167,91,792,373,724,244,451,659,133,471,240,649,402,554 +686,424,398,148,91,729,425,231,318,711,209,166,665,105,227,579,229,937,876,495 +699,583,291,592,426,173,819,131,158,814,325,496,625,215,568,831,212,456,137,83 +62,134,362,84,404,722,599,898,555,99,318,364,462,208,83,368,723,185,383,884 +100,573,721,722,320,528,250,206,534,585,797,158,626,201,567,206,54,520,362,892 +944,901,891,906,556,122,71,564,558,474,195,325,580,224,570,879,604,759,600,361 +936,887,732,888,693,763,933,424,835,642,299,174,475,360,150,120,117,294,70,495 +556,209,820,68,164,69,447,397,647,128,137,127,164,328,98,241,736,134,908,562 +627,573,562,740,627,70,294,784,884,91,813,579,354,141,820,351,501,372,138,937 +172,894,647,169,763,466,398,755,556,945,229,307,906,369,197,19,787,489,580,64 +690,107,566,116,360,709,627,369,104,298,931,474,644,477,300,98,799,300,427,518 +61,355,872,448,405,825,528,555,500,600,123,882,123,50,645,919,85,401,712,309 +898,829,929,888,236,146,696,484,904,928,203,167,229,590,484,208,536,157,903,896 +475,552,717,206,898,986,630,255,764,580,885,583,447,81,130,165,688,557,763,158 +459,253,590,760,210,307,789,830,560,221,711,406,470,62,274,577,947,79,932,719 +241,450,123,462,622,167,572,933,120,477,427,623,630,898,761,366,74,453,711,581 +152,823,190,56,207,831,586,650,737,520,57,304,292,759,593,523,590,223,735,836 +160,917,931,83,820,585,252,138,630,118,649,308,171,320,484,739,479,453,263,156 +134,904,686,147,234,821,518,894,116,690,828,696,248,689,918,71,207,891,344,328 +91,133,722,87,934,764,256,632,323,738,490,557,166,929,881,58,690,977,915,235 +746,984,86,710,112,584,205,592,179,796,209,174,447,190,123,455,231,786,893,715 +218,461,649,304,892,945,891,586,198,221,755,305,368,206,129,490,462,996,424,88 +497,108,595,560,160,428,827,78,629,801,370,815,453,853,579,707,893,818,592,224 +463,810,631,118,176,716,924,305,788,877,78,404,702,722,912,324,696,702,485,877 +875,919,461,485,578,595,755,109,793,511,589,931,56,213,920,119,594,594,558,923 +683,124,786,878,933,788,15,61,255,200,452,885,449,707,101,555,325,110,358,405 +70,488,830,913,833,680,158,819,881,583,144,477,182,136,131,56,678,931,881,433 +679,353,226,425,895,827,96,652,111,84,70,473,116,241,404,740,111,77,717,699 +568,885,930,820,415,211,300,877,460,196,481,568,162,888,478,155,743,723,51,190 +61,853,793,309,165,497,720,128,176,424,478,356,741,566,151,168,923,82,710,243 +757,898,167,149,592,251,202,787,627,726,757,462,52,220,786,763,757,64,644,361 +746,564,574,560,351,172,429,574,105,84,689,932,224,365,229,504,881,195,116,484 +574,930,120,165,390,881,108,567,875,577,887,492,209,152,423,484,106,821,917,466 +69,326,754,890,204,248,618,930,938,722,915,463,703,879,598,593,149,583,886,398 +691,272,628,713,559,471,887,902,889,144,585,324,53,572,118,486,217,796,77,899 +198,580,147,92,217,623,919,812,694,577,223,697,909,292,130,758,902,73,110,614 +577,80,744,51,594,513,424,755,116,307,254,914,938,74,561,599,641,835,648,553 +228,939,820,503,676,876,934,189,149,692,625,468,215,567,319,126,829,483,893,894 +758,163,297,553,292,192,128,269,309,564,695,509,896,937,294,70,736,156,402,576 +326,885,566,238,562,904,500,471,431,885,129,938,587,784,983,115,89,123,201,64 +647,918,735,894,428,365,84,535,361,70,977,791,939,872,84,318,431,81,650,99 +490,180,128,117,560,176,170,711,535,691,89,289,564,515,493,910,692,253,557,705 +226,760,309,144,795,758,501,672,909,718,499,555,324,449,454,570,84,241,361,295 +69,455,248,146,289,99,756,632,505,93,786,143,106,746,222,486,517,679,821,370 +816,903,646,353,724,678,149,515,718,321,355,701,221,115,611,942,235,218,252,943 +904,463,485,697,64,127,454,694,225,796,195,169,112,695,363,880,157,239,806,824 +909,430,70,940,626,893,580,174,568,72,518,59,703,444,67,208,187,243,766,477 +232,569,738,910,664,487,198,469,90,206,151,428,597,701,624,877,99,171,915,133 +697,58,563,320,598,179,262,716,222,364,494,932,908,592,946,490,121,370,708,75 +90,400,57,132,761,573,179,433,467,202,81,554,423,327,625,822,108,429,74,319 +233,536,833,564,493,96,358,242,571,56,939,61,813,159,634,507,189,63,176,161 +942,303,463,295,793,830,135,892,717,491,948,357,687,554,303,321,81,172,846,117 +552,893,448,766,406,830,367,821,598,792,877,320,144,158,934,424,453,940,923,755 +365,82,679,227,525,362,561,589,746,87,239,499,914,298,102,371,447,896,185,238 +937,946,228,913,466,154,498,67,717,169,217,186,212,808,153,490,103,756,50,74 +137,165,624,242,424,890,467,201,665,521,362,233,706,916,225,806,472,158,353,738 +810,934,370,920,891,498,649,86,681,308,934,630,116,518,51,118,181,737,764,639 +94,459,601,626,400,218,724,90,724,251,248,519,558,249,110,823,214,482,450,218 +304,71,885,765,96,315,710,204,292,565,53,477,120,558,688,81,904,191,144,201 +328,400,111,494,635,882,590,918,357,597,686,789,89,241,229,681,823,784,877,222 +62,240,518,254,520,151,449,719,320,509,432,574,518,887,353,588,300,814,56,485 +871,536,369,497,230,535,453,119,915,302,872,303,199,632,797,459,430,426,611,572 +211,55,889,741,557,600,565,258,737,407,70,745,632,325,428,949,949,424,832,702 +185,238,189,696,742,495,176,225,908,549,495,488,487,491,785,232,935,491,579,218 +225,141,101,294,687,301,682,361,690,239,563,697,575,457,510,633,820,680,66,647 +428,931,181,324,162,13,896,891,53,237,754,205,915,100,220,87,104,878,241,94 +204,758,126,595,117,462,699,488,65,676,355,535,178,185,324,229,423,708,763,167 +692,78,562,589,179,102,430,943,852,757,921,64,302,73,129,474,595,167,190,745 +360,72,119,247,250,675,210,884,429,136,810,934,294,567,565,207,320,515,454,452 +214,161,128,468,937,580,484,479,764,0,217,896,252,593,208,929,193,784,460,174 +76,490,568,558,711,22,702,625,721,695,692,494,256,244,123,705,427,578,101,63 +298,794,931,325,813,938,104,196,80,999,89,243,195,681,365,51,916,581,891,907 +643,365,555,93,740,888,492,232,744,680,84,171,17,762,122,207,324,180,300,319 +811,755,95,500,83,902,703,429,192,942,908,514,744,535,687,898,67,931,314,737 +817,939,78,944,741,685,516,69,141,60,156,920,816,882,942,916,78,797,673,686 +109,875,438,913,698,244,892,705,399,252,448,402,361,128,892,559,464,872,744,357 +902,784,629,95,224,323,50,993,231,679,150,920,937,168,450,118,594,243,786,785 +927,456,115,901,129,455,829,155,182,579,645,248,53,740,699,836,403,596,215,883 +201,948,914,735,593,121,562,87,190,946,709,501,107,512,595,322,710,232,279,947 +449,109,901,916,755,133,58,251,591,763,639,61,205,737,301,718,200,719,187,453 +143,496,104,483,939,402,890,82,518,937,562,133,201,52,250,610,215,227,53,513 +134,694,424,307,312,499,363,879,944,487,448,721,911,599,718,588,191,499,788,510 +466,903,881,149,698,184,12,209,164,736,102,890,468,228,195,465,174,79,481,758 +220,593,697,360,225,146,938,79,369,948,294,799,708,427,485,911,577,83,472,168 +82,717,709,89,240,231,269,295,816,586,836,256,940,309,251,139,489,292,92,573 +796,229,424,463,19,824,300,590,755,583,81,189,949,690,63,516,324,648,372,812 +257,76,789,703,824,362,215,578,809,190,202,132,297,490,886,908,700,102,632,121 +503,565,373,891,199,364,600,489,120,561,572,918,493,899,477,179,659,890,178,702 +128,227,256,204,897,644,578,944,87,597,240,367,169,113,976,483,253,790,470,684 +404,648,506,718,449,802,509,458,878,198,817,820,141,597,53,193,598,629,215,794 +240,911,139,897,429,326,200,692,811,260,871,649,913,70,494,212,353,137,79,593 +63,574,483,893,62,709,717,699,365,898,949,638,68,901,786,306,591,583,242,680 +63,621,650,108,453,520,594,642,218,590,91,947,819,159,104,170,241,907,896,98 +555,233,715,508,695,156,650,145,458,154,231,119,212,898,882,732,367,219,746,911 +835,930,126,64,693,213,359,718,765,745,727,493,706,184,875,297,162,645,941,488 +404,717,314,712,232,62,211,625,50,479,683,457,459,743,59,294,506,948,722,492 +944,87,98,625,236,257,536,648,599,721,358,920,598,142,157,443,644,428,161,95 +257,573,267,431,484,406,145,556,631,597,821,355,245,145,941,594,456,876,740,741 +920,454,217,701,577,124,470,324,826,837,624,711,518,592,465,795,759,294,498,701 +711,224,483,213,908,497,190,896,202,247,522,150,400,222,719,399,138,944,895,165 +353,576,785,629,211,240,256,514,557,163,355,191,882,638,739,111,121,499,360,218 +424,180,690,321,578,494,587,937,361,833,267,683,491,816,169,703,242,201,357,792 +738,134,739,300,593,786,460,743,936,814,569,681,789,64,327,126,264,812,191,431 +426,915,477,323,716,144,112,63,217,438,900,632,724,294,873,181,468,627,900,164 +479,802,563,121,151,906,192,900,426,718,185,552,946,183,830,239,589,194,481,94 +791,649,469,255,724,66,293,112,610,589,898,363,252,109,425,754,368,431,789,148 +754,665,381,908,735,451,308,737,935,226,706,205,460,244,582,153,178,493,137,702 +321,597,137,599,940,99,109,300,357,130,184,686,996,710,96,178,322,477,226,176 +153,890,836,24,888,643,737,902,597,572,504,486,573,878,251,124,184,600,685,217 +59,742,582,792,229,432,117,920,355,252,917,354,488,205,125,191,110,682,216,456 +324,367,186,203,912,564,870,881,553,365,605,476,326,828,586,154,400,104,579,431 +96,491,758,426,835,489,807,507,811,520,536,298,329,326,295,92,692,515,79,947 +535,682,139,232,938,595,552,824,71,630,831,558,258,448,814,949,222,995,364,828 +898,912,723,464,723,160,194,344,710,113,167,710,195,163,822,735,198,877,224,698 +360,82,111,146,430,703,328,880,406,200,929,64,467,726,647,482,225,449,477,709 +694,81,5,513,590,212,168,399,117,366,59,99,888,354,131,912,177,558,831,594 +520,363,529,159,358,935,202,648,372,940,89,467,483,128,220,138,628,519,252,171 +71,101,514,937,510,946,320,402,480,91,486,584,687,91,113,228,80,648,525,308 +693,494,171,17,114,516,370,320,307,624,356,591,812,156,497,238,557,905,889,820 +301,426,994,218,62,205,797,583,236,552,686,91,760,230,509,823,475,467,160,698 +597,399,51,454,487,666,728,692,874,477,447,318,237,372,453,744,250,458,894,234 +626,95,800,195,702,789,684,571,829,105,147,712,365,75,248,293,234,140,134,166 +576,489,224,159,947,323,116,403,180,683,795,874,197,400,446,720,930,237,240,401 +679,492,22,468,98,594,474,224,328,197,471,471,366,784,472,448,210,686,224,943 +915,471,760,721,587,492,893,327,580,826,807,370,872,684,357,875,937,354,318,361 +246,835,582,831,470,888,881,826,22,739,296,231,784,722,228,144,513,488,879,195 +913,175,109,687,208,207,64,514,819,508,590,489,17,474,566,873,97,481,901,239 +77,192,105,501,70,699,255,136,824,503,655,504,256,194,715,944,326,946,647,448 +189,586,213,294,252,884,935,500,88,309,193,993,814,69,944,810,212,225,719,553 +463,403,568,793,833,921,307,497,593,552,586,741,65,643,66,692,763,143,765,785 +454,889,935,152,434,142,818,366,104,197,184,242,597,895,224,117,325,212,517,794 +717,154,62,135,795,405,743,9,498,219,177,707,103,625,554,61,303,228,194,697 +63,72,882,362,193,754,484,822,236,687,685,296,197,821,925,195,818,897,796,456 +584,463,489,209,232,480,907,919,453,354,281,784,92,938,592,99,646,813,818,700 +250,373,586,229,690,136,101,548,219,358,759,132,370,829,174,884,820,574,459,117 +575,453,945,631,219,301,398,128,787,250,112,594,919,723,808,302,94,812,292,518 +713,106,590,194,361,759,318,123,890,710,122,242,473,293,384,692,145,792,901,428 +132,940,325,931,559,761,907,901,521,92,723,115,815,367,730,487,689,369,573,554 +81,61,566,932,141,349,255,97,233,115,795,816,821,218,319,186,73,632,116,145 +743,629,246,246,800,457,202,534,702,77,739,735,188,934,623,71,912,247,252,100 +800,79,569,167,934,715,916,586,225,562,479,56,705,115,836,912,829,793,71,425 +362,485,689,788,487,301,882,86,373,767,902,600,214,132,825,170,884,629,877,100 +681,876,878,198,539,102,475,919,699,883,762,212,149,457,939,154,247,62,724,918 +915,95,896,832,708,278,826,470,451,512,560,690,71,172,739,181,515,514,144,504 +364,485,146,889,190,329,174,465,719,254,710,925,89,58,690,99,939,404,482,791 +933,51,927,453,597,179,454,403,890,690,495,57,473,690,679,878,175,57,739,320 +249,114,989,933,257,703,328,204,694,431,240,880,501,893,366,53,97,886,810,587 +792,826,823,75,261,91,144,892,140,222,448,373,580,308,581,482,899,578,114,628 +587,129,105,66,515,205,590,89,502,998,940,584,454,256,360,931,118,164,256,693 +877,744,242,329,461,394,568,449,700,89,792,625,597,503,196,65,828,814,431,914 +61,91,700,536,697,114,131,481,499,365,493,473,678,934,120,598,355,826,231,277 +876,307,216,712,928,518,573,363,303,690,708,628,872,836,207,139,163,65,666,467 +494,483,449,328,194,880,258,113,107,932,552,210,824,301,74,396,568,130,883,787 +144,707,507,597,60,197,129,698,555,320,329,791,942,792,530,96,91,596,936,684 +235,558,479,456,554,657,684,878,216,426,828,693,914,258,121,476,320,104,78,766 +830,558,161,536,183,63,626,686,920,273,820,180,794,705,140,825,216,562,648,713 +209,296,788,743,296,75,882,306,298,575,247,784,487,3,707,197,716,648,494,600 +320,703,306,181,707,622,247,626,177,574,666,460,910,401,724,117,370,231,710,302 +66,912,474,186,137,755,437,118,910,481,55,884,500,579,449,870,108,183,74,702 +898,398,128,431,700,936,623,500,51,591,789,127,89,145,164,998,179,736,704,194 +181,56,574,485,948,853,171,223,207,241,179,479,935,616,140,794,230,831,557,320 +282,695,61,919,743,481,877,885,160,126,130,595,71,448,589,398,810,631,212,98 +583,178,145,172,595,295,132,149,284,162,111,398,154,796,595,171,113,357,429,121 +875,447,180,65,301,425,168,949,706,104,790,448,590,823,120,581,730,362,320,907 +796,249,501,202,130,788,520,142,574,461,192,708,133,79,742,642,717,50,727,903 +175,301,110,685,117,466,186,927,632,742,451,328,169,683,103,931,514,359,72,227 +710,643,490,794,877,99,208,527,53,127,169,785,579,449,784,555,714,878,679,130 +643,13,167,178,828,423,227,623,566,299,486,499,680,702,96,584,364,534,189,941 +882,493,571,76,935,240,230,468,599,337,373,138,564,704,791,79,104,242,580,786 +766,766,240,916,759,580,453,164,325,909,743,604,216,648,92,745,909,122,62,244 +197,563,250,110,236,78,825,837,627,493,492,250,871,487,893,763,318,194,827,487 +308,362,888,147,489,7,132,474,58,309,160,235,325,109,895,237,400,692,82,872 +482,757,566,517,564,584,905,58,68,911,735,690,476,111,651,478,915,81,220,765 +569,405,826,504,369,711,165,119,745,885,204,215,83,285,402,829,66,148,254,167 +52,107,793,510,61,996,631,102,227,479,743,916,145,76,251,225,138,70,328,718 +67,569,104,642,493,705,321,896,476,813,370,882,579,425,235,120,486,933,504,0 +919,148,129,482,52,908,236,497,895,641,119,892,691,102,164,193,645,233,192,737 +302,235,80,875,569,596,179,208,58,476,235,250,190,168,160,185,297,926,354,448 +70,354,828,568,242,186,404,320,354,574,86,792,763,137,827,218,557,286,235,834 +301,298,637,901,505,873,765,498,565,230,536,826,516,570,233,474,786,129,162,145 +712,229,242,501,816,243,96,509,708,365,52,829,190,505,697,317,565,403,556,817 +941,820,113,512,877,641,899,74,474,69,228,143,700,164,147,297,559,584,75,499 +984,784,472,357,757,573,816,894,206,181,240,82,832,596,139,127,356,452,184,447 +89,895,258,169,208,883,629,315,892,902,233,137,598,929,502,580,450,119,942,199 +328,895,492,367,748,685,598,599,405,482,243,320,486,77,575,72,406,939,157,293 +188,943,662,195,553,683,709,483,179,562,178,665,944,824,517,90,933,325,117,898 +644,153,904,138,932,508,826,99,926,200,486,56,363,210,793,368,709,469,233,325 +785,300,58,833,915,643,447,731,491,585,454,491,405,486,204,360,929,99,255,302 +207,831,558,759,499,241,252,789,944,393,707,555,125,249,373,720,327,887,514,302 +131,826,481,795,710,577,474,423,54,144,152,72,584,827,109,284,96,78,700,153 +229,556,499,164,88,698,141,513,190,96,293,240,254,257,816,649,156,302,432,699 +424,187,479,244,690,570,505,100,154,648,166,125,292,458,810,926,714,898,569,197 +577,756,512,135,715,406,701,687,637,91,698,302,817,875,114,593,91,510,467,142 +473,460,182,112,777,101,878,78,215,161,222,565,624,203,318,883,491,573,306,821 +870,497,121,718,510,292,92,159,363,78,909,509,132,517,554,913,94,118,458,798 +369,505,351,308,101,201,882,720,788,765,931,818,220,945,702,181,815,895,517,628 +500,910,123,936,493,111,73,564,501,173,473,307,558,510,266,111,897,217,147,301 +766,700,899,517,83,139,118,666,89,129,122,826,599,468,492,849,686,949,695,111 +252,122,241,460,200,367,629,893,919,680,483,440,480,87,631,451,465,241,212,462 +565,711,121,918,424,484,899,722,498,243,792,787,158,329,702,775,357,189,189,824 +462,679,138,294,252,250,234,478,302,618,459,570,210,182,827,513,585,476,789,148 +891,105,181,163,256,116,125,737,588,889,534,471,993,226,932,581,187,788,135,459 +68,222,630,691,153,588,882,260,89,71,297,816,576,830,106,697,941,490,94,719 +52,449,128,204,482,211,931,911,242,698,479,818,495,703,181,183,825,561,656,832 +296,172,118,790,431,357,502,87,881,705,746,816,301,118,693,263,703,172,91,557 +406,556,52,302,248,155,534,220,467,224,483,257,121,741,761,885,279,237,398,784 +257,471,573,153,371,258,461,181,492,789,326,835,291,63,176,162,935,176,353,60 +880,914,515,362,497,137,465,70,235,511,306,194,521,924,740,815,466,305,792,98 +149,306,354,895,717,215,54,703,329,74,62,934,208,986,112,212,694,297,511,178 +589,517,516,367,328,68,678,557,785,834,68,97,744,198,400,876,88,986,906,690 +736,763,821,217,992,904,822,193,719,827,942,456,894,370,492,255,163,211,167,355 +795,135,83,765,484,260,760,150,699,495,138,108,563,306,563,198,577,794,256,503 +518,912,193,431,97,699,109,805,553,403,822,931,682,706,520,57,111,220,324,490 +187,101,498,508,895,101,225,592,455,697,560,185,155,511,703,558,688,113,70,656 +148,599,302,126,469,829,191,218,766,87,140,583,578,827,520,701,53,592,817,18 +645,646,152,469,123,222,746,897,984,127,360,745,789,874,898,788,578,111,368,578 +737,558,898,456,448,194,645,694,666,311,74,108,793,813,451,947,501,853,575,242 +988,212,920,72,693,95,471,882,144,79,643,50,587,829,505,562,237,496,885,827 +929,145,403,715,513,871,687,93,625,258,368,326,870,684,710,503,570,920,634,828 +853,198,501,790,904,486,252,609,593,119,714,137,166,51,297,593,701,560,472,685 +452,597,428,300,733,161,207,514,570,93,556,827,448,428,447,303,75,814,302,164 +205,144,492,214,498,710,121,598,650,533,534,823,247,712,83,678,494,172,937,623 +625,211,95,158,465,918,883,364,89,198,74,93,193,481,763,653,301,201,153,643 +134,921,458,789,353,796,173,534,398,88,151,87,300,763,237,456,366,933,358,572 +563,600,168,584,513,98,871,920,360,249,367,762,89,517,479,448,441,502,720,364 +823,492,484,794,872,874,338,181,693,372,77,306,791,508,785,508,472,933,50,756 +307,193,649,793,850,594,220,572,625,74,835,240,150,327,188,711,371,228,245,578 +626,232,497,691,327,943,636,202,321,698,790,682,447,577,371,593,132,820,491,898 +234,823,485,146,84,99,520,236,700,663,201,690,296,120,712,299,105,870,59,649 +448,765,62,297,462,258,660,482,920,591,689,890,821,211,76,586,50,874,99,644 +578,649,819,465,104,884,744,899,873,76,144,553,935,173,949,675,593,826,71,100 +573,163,451,329,215,398,200,650,368,906,354,164,721,297,718,789,4,371,309,136 +508,174,700,555,908,59,902,767,428,576,404,361,898,792,787,498,76,148,503,453 +192,882,896,124,207,299,558,215,822,207,227,80,517,64,338,877,111,564,86,678 +68,920,510,89,822,482,161,638,230,716,885,482,678,698,488,501,501,871,72,120 |