diff options
| -rw-r--r-- | 2020/16.hs | 98 | ||||
| -rw-r--r-- | 2020/16.in | 270 |
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 |