Day 16

2 files changed, 368 insertions, 0 deletions

diff --git a/2020/16.hs b/2020/16.hs
new file mode 100644
index 0000000..f9c3446
--- /dev/null
+++ b/2020/16.hs
@@ -0,0 +1,98 @@
+{-# LANGUAGE LambdaCase #-}
+{-# LANGUAGE ViewPatterns #-}
+module Main where
+
+import Data.Either (partitionEithers)
+import Data.Foldable (toList)
+import Data.Function (on)
+import Data.List
+import qualified Text.Parsec as P
+
+import Input
+import Util
+
+data IVMap a = IVSplit (a, a) (IVMap a) (IVMap a) | IVLeaf (a, a)
+  deriving (Show)
+
+ivmFromList :: Ord a => [(a, a)] -> IVMap a
+ivmFromList =
+    (\case l -> splitIntoTree (length l) l)
+    . foldr mergeInto []
+    . map ((,) <$> fst . head <*> maximum . map snd)
+    . groupBy ((==) `on` fst)
+    . sort
+  where
+    mergeInto :: Ord a => (a, a) -> [(a, a)] -> [(a, a)]
+    mergeInto (a, b) [] = [(a, b)]
+    mergeInto (a, b) ((c, d) : l) | b >= c = mergeInto (a, d) l
+                                  | otherwise = (a, b) : (c, d) : l
+
+    topRange :: IVMap a -> (a, a)
+    topRange (IVSplit p _ _) = p
+    topRange (IVLeaf p) = p
+
+    splitIntoTree :: Ord a => Int -> [(a, a)] -> IVMap a
+    splitIntoTree _ [] = error "splitIntoTree: empty list"
+    splitIntoTree _ [p] = IVLeaf p
+    splitIntoTree n l =
+        let (pre, post) = splitAt (n `div` 2) l
+            t1 = splitIntoTree (n `div` 2) pre
+            t2 = splitIntoTree ((n + 1) `div` 2) post
+        in IVSplit (fst (topRange t1), snd (topRange t2)) t1 t2
+
+ivmContains :: Ord a => IVMap a -> a -> Bool
+ivmContains (IVLeaf (a, b)) x = a <= x && x <= b
+ivmContains (IVSplit (a, b) t1 t2) x | a <= x && x <= b = ivmContains t1 x || ivmContains t2 x
+                                     | otherwise = False
+
+
+distinctElemSAT :: Eq a => [[a]] -> [a]
+distinctElemSAT =
+    map (\case [x] -> x ; [] -> error "No assignment" ; _ -> error "Ambiguous?")
+    . fixpoint eliminateSingles
+  where
+    fixpoint :: Eq a => (a -> a) -> a -> a
+    fixpoint f x = let y = f x in if y == x then x else fixpoint f y
+
+    eliminateSingles :: Eq a => [[a]] -> [[a]]
+    eliminateSingles l = map (\row -> if length row == 1 then row else filter (`notElem` [x | [x] <- l]) row) l
+
+
+data Rule = Rule String [(Int, Int)] (IVMap Int)
+  deriving (Show)
+
+parseTicket :: String -> [Int]
+parseTicket = map read . toList . splitOn (== ',')
+
+parseRule :: String -> Rule
+parseRule = (\case Right (n,ivs) -> Rule n ivs (ivmFromList ivs)
+                   Left e -> error (show e))
+            . P.parse pRule ""
+  where
+    pRule = (,) <$> P.many1 (P.satisfy (/= ':')) <*> (P.string ": " >> pRange `P.sepBy` P.string " or ")
+    pRange = (,) <$> (read <$> P.many1 P.digit) <*> (P.char '-' >> read <$> P.many1 P.digit)
+
+
+main :: IO ()
+main = do
+    input <- getInput 16
+    let [map parseRule -> rules, [""],
+         ["your ticket:", parseTicket -> mytick], [""],
+         "nearby tickets:" : (map parseTicket -> nbticks)] =
+            groupBy (\a b -> not (null a || null b)) input
+
+        anyValidIVM = ivmFromList (concat [ps | Rule _ ps _ <- rules])
+
+        (concat -> invalids, valids) = partitionEithers
+            [case partition (ivmContains anyValidIVM) tick of
+               (yeses, []) -> Right yeses
+               (_, nos) -> Left nos
+            | tick <- nbticks]
+
+    print (sum invalids)
+
+    let fieldNames = distinctElemSAT
+            [[name | Rule name _ ivm <- rules, all (ivmContains ivm) column]
+            | column <- transpose valids]
+
+    print (product [value | (value, name) <- zip mytick fieldNames, take 10 name == "departure "])
diff --git a/2020/16.in b/2020/16.in
new file mode 100644
index 0000000..4688d23
--- /dev/null
+++ b/2020/16.in
@@ -0,0 +1,270 @@
+departure location: 42-322 or 347-954
+departure station: 49-533 or 555-966
+departure platform: 28-86 or 101-974
+departure track: 50-150 or 156-950
+departure date: 30-117 or 129-957
+departure time: 31-660 or 678-951
+arrival location: 26-482 or 504-959
+arrival station: 29-207 or 220-971
+arrival platform: 28-805 or 829-964
+arrival track: 48-377 or 401-964
+class: 28-138 or 145-959
+duration: 33-182 or 205-966
+price: 25-437 or 449-962
+route: 41-403 or 428-968
+row: 33-867 or 880-960
+seat: 40-921 or 930-955
+train: 47-721 or 732-955
+type: 33-243 or 265-964
+wagon: 31-756 or 768-973
+zone: 50-690 or 713-967
+
+your ticket:
+67,107,59,79,53,131,61,101,71,73,137,109,157,113,173,103,83,167,149,163
+
+nearby tickets:
+179,948,890,368,224,849,508,533,931,918,864,792,592,356,895,62,540,744,902,559
+363,432,890,266,55,794,624,60,732,756,325,508,167,70,593,477,906,865,572,889
+682,482,782,319,82,269,837,205,638,509,316,885,66,240,144,105,181,370,565,366
+231,859,362,313,941,210,434,105,801,354,137,524,908,237,578,778,80,837,181,241
+148,106,604,76,746,568,625,682,713,619,987,802,783,741,625,376,888,619,133,359
+765,834,830,713,638,621,55,858,682,740,283,648,148,641,319,934,58,635,178,934
+520,582,467,608,63,205,562,705,608,463,638,347,855,920,167,565,803,833,638,240
+838,829,279,69,568,685,615,306,756,716,786,606,172,886,592,792,461,234,707,741
+754,457,917,896,612,509,7,633,841,780,275,364,791,562,294,908,863,111,286,598
+68,932,770,61,752,852,610,357,651,838,532,915,307,459,76,620,799,878,651,504
+356,474,102,588,611,602,995,354,894,889,312,173,67,781,783,461,606,434,513,569
+778,160,480,229,472,888,621,231,792,177,72,529,678,166,293,309,230,147,544,157
+236,401,572,927,829,580,739,243,660,863,279,470,880,312,902,624,271,316,947,529
+784,77,233,793,299,915,24,221,51,920,52,651,617,750,288,361,801,680,792,793
+361,771,232,452,798,784,265,514,890,457,314,275,232,151,622,742,220,307,104,898
+855,289,159,521,735,505,22,585,276,637,309,296,686,231,172,641,864,370,599,846
+402,179,564,797,148,460,455,266,266,157,12,272,884,355,801,230,595,66,227,720
+481,656,363,273,884,642,241,224,912,765,356,772,163,61,909,242,171,512,768,134
+913,840,947,298,131,682,586,567,166,780,322,571,734,608,675,560,740,803,840,57
+453,734,981,585,914,577,898,855,656,586,838,231,941,70,105,786,690,169,113,915
+172,227,986,904,470,558,175,403,173,635,402,178,930,308,771,104,570,904,506,292
+479,432,936,942,772,205,594,518,558,652,57,170,602,253,687,172,557,646,317,945
+301,284,148,886,743,468,603,603,579,782,297,313,373,578,638,207,326,832,176,636
+575,364,588,768,113,571,899,55,300,692,270,686,115,321,362,510,476,78,657,781
+755,273,72,940,318,155,60,779,111,604,370,320,368,156,290,479,281,571,117,831
+856,477,126,584,288,751,860,734,912,227,113,900,348,949,561,935,633,653,291,899
+845,894,364,78,658,829,782,66,626,454,511,609,319,834,678,507,566,912,390,846
+919,733,803,474,648,471,235,457,459,474,525,512,510,896,909,866,154,353,933,292
+532,571,563,105,602,305,577,572,136,596,53,910,932,921,147,299,237,218,80,461
+640,625,911,846,270,655,719,85,229,895,349,241,736,102,274,739,52,778,656,922
+768,795,520,349,716,78,322,366,829,744,775,741,562,629,136,134,743,458,876,904
+69,589,55,778,11,241,265,650,292,850,591,563,588,686,842,515,307,575,595,866
+607,235,272,451,862,61,562,372,508,776,170,455,299,836,50,549,293,431,836,462
+138,781,457,733,371,351,480,372,906,204,620,841,287,431,52,317,181,856,313,689
+318,713,790,747,232,220,530,274,841,946,300,855,467,99,735,311,891,176,180,370
+403,276,774,116,224,626,306,566,630,145,453,170,796,334,430,587,745,318,635,589
+116,163,103,680,571,565,949,835,73,800,804,462,755,482,102,130,365,161,183,582
+777,56,332,906,801,634,533,848,61,684,610,920,75,625,772,236,571,466,177,678
+768,834,632,783,56,434,643,624,896,311,291,715,372,122,109,163,913,511,598,910
+124,629,685,714,508,110,613,64,802,314,132,600,745,172,104,569,914,849,581,310
+476,561,842,624,284,70,316,308,115,640,529,708,893,313,793,631,109,458,599,628
+915,352,865,831,882,75,561,933,290,224,560,885,82,910,536,221,317,435,283,606
+320,832,624,221,164,129,635,518,680,805,831,755,745,781,89,888,830,305,719,220
+160,291,108,58,225,786,270,356,892,282,623,363,794,514,885,164,171,468,241,13
+563,845,920,76,881,772,867,374,314,453,644,555,932,307,57,773,90,801,459,863
+908,611,8,365,690,602,523,358,846,319,747,117,642,51,834,570,921,308,629,290
+909,168,631,802,787,354,164,940,888,864,694,294,891,790,798,837,733,610,163,654
+685,403,571,851,116,666,64,746,469,904,932,864,932,830,933,617,367,365,294,750
+644,935,296,772,306,681,204,80,838,322,851,713,82,579,742,861,171,276,590,508
+616,482,911,783,865,355,73,66,306,853,833,463,679,303,456,889,701,148,504,308
+74,838,942,755,287,73,299,299,103,268,917,107,631,508,348,401,290,831,151,75
+587,129,130,690,922,77,847,732,52,746,640,466,467,358,634,621,681,678,679,105
+374,864,531,910,428,896,659,180,51,793,455,651,752,547,304,647,755,473,266,298
+280,843,714,592,609,850,436,288,59,481,528,649,74,295,129,715,683,125,796,229
+173,222,927,61,591,83,611,270,164,362,461,599,66,837,282,451,55,350,207,149
+347,117,687,235,777,584,99,101,518,275,83,563,528,718,883,636,205,168,593,54
+308,72,284,243,804,476,589,73,584,932,431,949,111,640,54,347,885,701,846,948
+924,374,59,570,633,646,451,468,564,466,556,361,102,591,363,239,646,526,621,575
+681,894,470,903,71,631,938,528,610,352,56,174,636,84,208,524,846,165,366,557
+513,898,462,903,893,238,556,799,172,720,761,478,563,286,274,838,880,73,315,56
+510,54,842,300,784,596,715,854,685,635,225,799,284,688,775,653,862,766,798,158
+834,281,776,287,479,841,887,464,474,85,71,518,521,853,347,128,106,596,104,305
+791,843,373,456,562,805,146,592,583,66,893,631,756,182,908,872,561,234,618,777
+947,207,735,464,601,872,355,67,53,770,749,511,234,281,948,620,347,654,831,893
+64,101,570,656,102,361,114,904,268,850,915,639,353,109,478,169,768,892,330,799
+282,4,574,180,159,231,348,849,177,854,904,311,660,579,688,105,429,746,781,60
+613,166,228,745,768,687,462,785,737,52,880,862,221,468,151,267,530,170,477,596
+647,865,914,603,614,587,228,589,76,895,53,732,349,871,230,366,274,628,434,480
+645,509,165,533,774,54,801,852,458,401,270,656,555,605,644,150,666,798,636,588
+931,896,832,61,592,281,231,865,782,233,157,238,74,899,944,847,608,431,923,302
+77,102,145,302,771,463,652,75,477,60,680,480,938,556,865,642,372,684,798,334
+944,269,271,618,160,473,319,274,937,223,609,678,233,937,933,129,518,266,105,762
+792,847,750,620,181,862,242,937,529,785,750,884,226,84,129,756,829,302,820,180
+738,738,689,793,460,730,888,370,940,147,533,645,900,113,103,223,656,721,614,607
+403,465,736,57,132,511,590,685,172,513,291,586,178,604,324,748,860,683,278,847
+70,773,68,167,706,652,891,890,468,165,229,945,745,364,315,54,461,233,595,740
+101,860,908,657,578,462,50,54,648,927,57,745,899,781,752,688,623,112,506,908
+162,112,648,891,270,752,363,182,293,293,542,309,751,829,830,240,222,896,932,366
+288,636,751,795,275,399,846,507,680,55,681,130,351,935,851,897,360,531,224,111
+230,109,996,586,267,804,54,220,949,832,563,921,233,606,304,80,240,601,181,358
+86,277,292,476,52,778,898,107,890,374,82,289,168,912,314,21,771,843,436,318
+889,460,561,354,750,165,301,355,803,387,689,146,893,610,523,577,354,468,745,532
+525,436,481,847,160,594,566,453,893,839,166,508,78,842,633,135,843,748,110,199
+741,893,163,906,591,589,713,378,739,946,689,613,311,308,901,778,86,297,531,864
+684,303,170,635,504,433,929,605,158,222,570,896,641,587,721,238,207,860,460,80
+369,277,634,227,102,605,354,884,684,294,83,766,682,107,557,639,732,569,933,470
+105,559,237,459,931,755,428,829,720,653,839,831,992,679,582,163,431,609,278,919
+137,358,512,399,842,800,786,660,617,52,648,916,71,626,752,685,293,790,659,586
+595,847,657,613,362,834,612,834,747,645,104,6,596,282,506,732,583,737,845,224
+903,179,312,678,609,120,934,597,312,473,884,224,456,467,77,858,526,452,355,620
+462,609,311,78,771,930,913,433,283,840,640,559,981,609,640,682,61,575,778,228
+179,17,74,783,147,403,596,905,478,628,290,520,907,774,267,625,622,912,849,372
+611,511,529,745,115,681,58,765,462,163,946,948,72,575,915,234,883,587,77,937
+103,775,276,170,364,363,656,178,528,689,128,643,66,173,713,274,55,72,630,891
+573,918,561,158,772,450,736,600,564,914,361,617,180,207,228,154,281,473,277,745
+858,643,843,136,834,132,800,348,627,403,689,307,75,286,931,294,750,200,505,227
+895,630,57,288,295,319,214,162,863,784,354,733,279,646,890,111,467,572,911,562
+113,53,276,583,842,323,322,747,368,617,367,462,79,367,859,301,624,293,720,612
+527,308,116,430,311,848,223,530,887,563,107,471,652,105,286,881,217,518,241,286
+531,402,478,526,146,296,936,942,353,289,87,719,314,804,604,606,905,646,300,74
+308,626,943,737,291,520,73,76,853,613,239,164,431,271,505,113,229,328,316,177
+904,379,129,945,887,145,773,66,655,916,642,784,80,162,734,855,575,279,276,719
+603,518,831,626,207,135,622,800,581,310,76,938,832,837,128,617,349,360,472,792
+867,478,605,603,55,802,449,362,660,646,623,515,769,636,163,771,574,547,755,719
+1,75,732,453,637,353,86,746,370,130,769,648,60,348,643,531,310,131,453,892
+317,60,747,516,586,475,373,604,356,860,465,590,641,764,514,690,659,563,737,567
+733,939,771,893,267,200,680,221,590,792,769,61,916,653,362,360,912,855,138,916
+940,855,713,85,507,601,674,652,616,283,234,238,567,613,744,627,79,593,66,848
+300,114,852,911,736,110,627,8,287,459,652,746,181,849,63,734,746,558,617,156
+80,401,619,636,355,912,245,166,656,919,528,623,738,163,794,744,800,844,233,474
+700,150,740,785,51,178,576,112,505,115,642,735,240,101,786,578,646,506,367,521
+437,472,82,114,316,942,641,101,293,86,991,476,369,429,801,360,792,888,635,458
+573,721,233,568,131,720,559,980,861,592,798,180,79,83,773,749,239,312,133,590
+947,883,479,657,72,303,772,129,889,864,117,149,892,899,273,465,198,510,180,147
+52,476,709,451,939,831,530,53,756,171,147,582,627,376,295,719,601,175,655,790
+769,103,572,732,567,984,522,274,894,160,831,370,774,294,592,655,281,525,594,311
+478,508,568,241,690,851,324,633,288,890,350,614,846,568,743,135,68,572,781,771
+641,227,556,316,573,306,635,300,596,930,18,647,569,596,307,480,637,80,921,162
+54,587,304,884,993,934,947,469,375,638,284,772,480,401,314,289,593,347,597,743
+718,797,884,364,797,356,930,121,750,797,529,743,520,313,681,566,181,658,457,113
+179,557,372,911,133,224,639,620,288,181,116,853,19,375,173,511,598,933,612,243
+994,781,579,887,79,829,946,616,352,750,221,377,639,523,583,733,581,598,526,229
+630,610,948,278,206,361,945,990,902,510,882,372,830,458,770,838,531,62,238,867
+911,619,655,721,660,105,721,854,523,686,946,770,470,283,630,343,917,52,829,138
+602,567,580,350,457,223,851,558,888,556,732,85,843,168,626,708,930,146,55,458
+831,178,944,106,296,626,521,688,277,602,800,282,353,436,862,817,860,311,556,82
+279,602,658,282,897,783,61,566,656,173,479,432,934,357,805,250,460,451,353,854
+240,165,829,775,237,241,173,658,299,429,60,189,619,113,583,768,149,265,453,782
+843,137,227,702,316,569,857,797,111,779,67,70,681,376,161,770,468,114,531,482
+449,881,322,453,631,462,69,734,129,474,481,433,907,316,871,232,319,360,299,915
+372,565,136,720,658,894,66,891,557,624,225,381,373,910,274,795,533,777,106,931
+940,891,450,105,461,58,574,682,737,322,479,719,734,52,402,285,157,377,67,22
+299,916,933,801,101,801,110,453,895,748,165,103,774,558,715,374,461,746,282,539
+680,178,107,911,636,656,758,638,521,150,504,619,776,168,276,221,274,582,148,313
+159,205,354,517,519,239,525,601,629,586,276,277,773,735,736,311,557,783,314,378
+640,74,450,563,829,77,627,607,781,120,84,477,863,270,938,743,801,754,907,639
+63,560,173,194,462,746,103,683,797,239,889,515,633,862,279,642,173,644,508,402
+175,854,450,804,686,847,408,164,510,372,355,575,269,633,786,274,277,471,306,512
+364,433,386,755,102,881,109,885,567,111,734,592,129,451,564,436,129,349,351,457
+131,591,646,650,597,476,130,938,471,687,372,524,562,103,264,634,77,148,474,781
+293,288,642,931,849,933,994,352,581,373,175,741,320,935,73,319,556,136,788,949
+642,791,838,369,689,363,937,80,687,840,480,596,861,589,684,625,363,623,363,123
+684,515,862,719,623,297,583,570,593,67,556,797,859,476,699,558,475,753,231,107
+234,882,373,647,901,173,729,660,648,515,842,625,611,117,110,936,160,275,776,947
+802,360,599,353,526,164,930,836,526,223,172,904,605,896,222,314,53,911,257,845
+838,599,839,276,903,889,133,653,947,688,114,897,801,998,559,936,229,169,555,897
+465,606,356,370,802,748,156,860,62,103,473,278,482,832,893,995,436,654,598,616
+599,129,611,770,303,843,563,751,855,587,593,515,641,647,831,301,586,660,760,81
+166,361,775,377,576,575,239,76,768,465,612,750,593,471,157,680,923,239,885,458
+299,716,564,504,713,527,797,533,587,605,436,235,138,107,852,791,638,403,121,593
+738,505,240,569,149,918,140,656,156,318,631,848,754,278,841,911,599,70,916,55
+181,690,278,569,434,838,182,453,855,653,271,597,990,941,533,774,840,746,268,103
+60,60,612,752,913,592,689,469,592,686,785,768,278,916,505,656,355,606,890,19
+532,355,633,480,135,493,621,157,82,902,75,135,468,302,597,435,900,287,862,901
+734,781,891,65,428,740,691,71,66,177,464,558,682,352,571,60,300,571,148,601
+687,372,146,464,516,109,549,738,521,135,236,59,314,229,402,918,656,137,921,629
+199,453,533,356,296,905,308,629,633,911,369,459,569,587,739,367,899,233,482,112
+836,778,136,478,505,657,164,858,947,526,639,273,365,366,785,745,854,398,852,74
+625,939,86,243,771,117,119,517,651,66,265,643,66,310,864,310,305,626,732,849
+624,621,887,467,573,761,589,612,648,883,355,432,451,515,281,67,780,601,162,465
+632,240,761,881,782,593,110,856,783,900,844,52,282,634,276,836,293,271,579,895
+913,720,514,743,241,434,786,929,800,920,948,179,883,607,68,903,129,481,779,512
+732,642,893,625,509,310,70,319,101,904,113,373,136,132,555,988,619,734,744,587
+171,929,829,85,656,884,281,744,226,229,104,844,430,276,157,228,83,866,283,273
+988,133,594,175,452,162,575,678,627,606,625,512,660,436,116,842,582,300,635,594
+167,461,194,884,357,206,55,77,858,369,802,745,887,779,305,613,576,789,600,170
+562,461,429,275,636,589,651,106,55,526,989,581,920,577,798,373,429,773,464,772
+917,858,606,288,733,356,284,234,865,476,925,919,804,227,507,55,914,301,567,149
+269,685,521,56,850,310,364,609,296,15,67,646,52,513,350,241,458,652,745,85
+782,163,352,242,610,560,380,106,659,284,312,898,180,896,289,475,62,835,897,117
+690,791,780,133,910,598,85,595,834,83,373,238,450,580,907,761,783,785,855,741
+638,279,348,782,749,71,891,586,353,105,867,565,354,924,310,562,930,680,911,243
+59,947,70,859,865,116,648,326,794,941,845,169,241,898,775,786,917,315,280,566
+913,522,166,790,361,453,848,146,604,354,162,101,844,456,772,914,997,163,907,898
+308,934,175,804,775,166,352,55,833,343,368,860,457,948,862,288,62,841,229,181
+636,605,591,687,376,911,782,461,101,721,402,449,615,269,146,777,71,838,347,672
+921,510,530,428,461,139,904,105,862,679,322,579,858,283,453,301,897,52,402,589
+747,605,634,584,67,715,886,278,570,524,299,721,308,890,300,607,231,478,90,902
+348,681,631,358,830,635,228,468,105,717,768,908,300,750,224,515,110,642,867,696
+171,477,284,508,117,72,681,568,896,841,77,846,555,355,721,591,296,668,308,113
+268,936,936,932,318,274,582,517,849,635,282,168,858,678,932,280,760,804,357,714
+232,921,859,456,505,361,678,645,467,79,153,302,353,915,313,449,932,949,801,130
+838,532,913,116,529,905,612,575,236,947,567,533,520,171,765,569,829,883,942,364
+242,569,522,578,597,570,457,314,133,274,301,775,910,644,168,209,138,558,173,297
+883,511,297,366,114,595,299,642,77,52,54,840,284,661,318,282,278,591,647,641
+17,840,847,220,347,304,177,720,840,840,653,946,376,181,481,629,633,172,365,680
+222,945,839,160,678,353,299,587,476,532,743,101,477,936,316,204,402,225,790,519
+226,479,62,617,159,66,785,588,990,521,156,361,685,656,754,769,482,930,913,167
+769,109,753,747,226,705,274,844,85,609,148,316,52,181,689,632,612,595,307,931
+558,805,88,106,372,754,222,756,838,475,471,844,482,884,299,769,232,589,802,789
+683,305,744,451,531,718,307,276,146,886,525,802,233,395,622,775,302,935,889,61
+294,612,573,524,365,108,562,289,76,134,743,321,58,771,718,294,271,938,729,787
+739,559,237,794,278,178,575,464,568,916,436,929,352,859,619,794,582,361,769,745
+382,131,862,356,525,286,457,886,718,241,456,180,312,173,295,581,179,616,57,375
+592,226,740,276,351,837,518,224,478,403,610,462,69,354,789,367,982,178,804,481
+773,582,310,684,656,450,687,145,532,937,752,901,280,206,748,300,945,235,986,134
+436,944,296,581,685,228,321,847,363,133,605,934,156,842,116,388,464,275,137,145
+451,584,105,933,621,922,618,316,732,568,679,229,307,591,363,920,223,577,106,454
+678,732,376,372,457,910,155,476,835,753,656,54,294,829,432,312,312,853,521,130
+303,685,543,471,851,451,910,573,354,558,687,372,753,78,746,372,657,753,348,168
+646,115,224,891,800,788,237,565,900,602,51,165,179,653,656,769,303,926,80,780
+736,354,768,585,796,919,612,309,743,163,357,892,616,628,83,88,60,751,714,103
+229,615,842,772,775,620,859,90,920,294,643,921,740,277,916,577,839,107,600,746
+931,177,590,462,558,89,353,476,640,930,779,575,591,719,307,167,527,403,846,429
+921,795,51,303,596,720,741,720,571,649,572,67,366,350,935,925,900,521,431,772
+505,467,561,609,678,611,601,220,104,915,269,864,169,778,580,847,654,364,899,991
+592,600,432,64,450,801,353,592,645,714,228,754,929,287,862,578,560,506,451,846
+179,621,178,606,366,896,844,363,611,220,618,277,367,243,455,916,127,738,888,866
+63,520,291,785,932,777,788,801,295,788,301,717,655,362,844,265,584,718,798,993
+51,294,348,111,935,640,633,639,533,936,138,224,166,228,358,113,205,92,436,377
+900,916,160,865,515,537,803,679,589,149,282,528,349,82,136,451,750,130,507,114
+741,948,278,604,848,355,750,506,741,175,780,850,232,361,785,228,848,556,219,936
+76,805,451,286,832,565,774,943,515,317,626,719,473,678,114,21,504,890,471,852
+525,734,932,681,715,461,612,179,613,633,738,838,560,208,942,564,637,300,789,432
+805,74,620,838,559,555,82,845,50,0,784,681,368,897,906,636,508,600,163,137
+431,86,792,55,61,466,825,467,652,60,377,581,747,159,530,347,131,682,237,626
+53,350,632,838,601,374,606,891,831,164,781,453,5,583,63,273,558,522,585,598
+54,755,629,312,530,420,641,831,628,574,310,626,358,476,463,150,130,688,268,531
+737,800,859,157,685,365,604,312,907,313,783,513,533,230,648,472,884,509,672,720
+713,349,241,457,106,449,474,885,79,481,721,233,936,831,913,772,381,946,57,832
+931,362,944,482,930,374,650,654,942,890,676,83,355,117,377,747,508,717,243,931
+172,116,843,274,220,836,837,360,645,295,138,772,302,179,51,362,464,80,515,986
+569,83,658,159,842,359,114,156,911,756,398,848,286,583,629,749,455,776,456,69
+641,900,180,352,608,620,948,117,309,639,190,891,894,319,294,651,860,310,638,532
+631,937,274,907,150,0,773,526,733,794,476,275,113,169,311,863,795,358,403,516
+508,780,181,603,846,802,231,472,513,109,649,239,680,679,389,916,437,512,401,285
+148,402,303,591,639,826,630,683,243,633,686,473,940,295,743,280,475,163,573,291
+518,690,62,115,351,795,555,854,322,740,627,68,641,171,646,639,20,159,181,72
+86,321,166,790,853,175,310,513,80,133,771,658,629,707,789,914,174,292,574,375
+224,455,524,315,364,589,582,101,743,159,166,647,304,316,455,19,647,562,170,745
+51,55,105,306,517,906,830,319,638,233,940,520,277,470,810,638,634,428,657,933
+656,172,638,571,145,249,101,831,234,454,114,848,269,402,627,65,749,371,901,932
+718,82,527,376,180,592,630,132,280,850,910,528,279,224,922,857,430,746,716,133
+78,631,173,228,365,888,733,774,741,298,771,830,358,167,198,690,348,901,798,241
+883,238,402,796,740,103,919,194,294,355,634,579,586,69,56,270,746,63,74,589
+285,946,777,514,132,627,648,179,619,235,432,606,830,193,171,909,720,682,581,784
+271,111,644,883,895,583,227,270,773,921,291,321,371,303,559,667,352,529,320,457
+716,364,112,449,227,618,797,747,573,802,588,304,801,679,169,788,742,856,987,797
+507,310,480,146,451,793,769,720,738,164,753,172,459,936,67,516,287,468,734,88
+579,291,240,163,906,509,138,79,556,60,605,851,655,296,86,437,916,153,298,910
+401,505,599,652,588,161,877,782,530,882,623,362,805,851,748,135,842,59,508,308
+895,691,751,57,156,841,932,520,146,366,714,890,561,772,636,367,716,111,296,625
+690,359,853,775,7,57,53,222,279,590,70,321,660,71,585,643,782,72,920,111
+597,753,166,563,180,512,68,794,861,510,718,308,525,979,848,862,689,376,565,271
+355,845,802,234,472,920,174,62,945,889,715,110,721,900,917,948,866,461,140,787