2020-16 part 1 in haskell

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