﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace AoC.Year2020.Day16
{
    public class Part1 : BasePart
    {
        protected void RunScenario(string title, string input1, string input2, string input3)
        {
            RunScenario(title, () =>
            {
                var lines1 = input1.Split(new[] { '\r', '\n' }, StringSplitOptions.RemoveEmptyEntries);
                var myTicket = input2.Split(new[] { ',' }, StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray();
                var otherTickets = input3.Split(new[] { '\r', '\n' }, StringSplitOptions.RemoveEmptyEntries).Select(i => i.Split(new[] { ',' }, StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray()).ToArray();

                var ruleRe = new Regex(@"(.*): (\d+)-(\d+) or (\d+)-(\d+)");
                var rules = new Dictionary<string, Range[]>();
                foreach (var lin in lines1)
                {
                    var m = ruleRe.Match(lin);
                    rules.Add(m.Groups[1].Value,
                        new[]
                        {
                            new Range(int.Parse(m.Groups[2].Value), int.Parse(m.Groups[3].Value)),
                            new Range(int.Parse(m.Groups[4].Value), int.Parse(m.Groups[5].Value)),
                        });
                }

                var invalid = 0;
                foreach (var t in otherTickets)
                {
                    invalid += t.Where(i => !rules.Any(r => r.Value[0].InRange(i) || r.Value[1].InRange(i))).Sum();
                }

                Console.WriteLine(invalid);
            });
        }

        private class Range
        {
            public int Low;
            public int High;

            public Range(int low, int high)
            {
                Low = low;
                High = high;
            }
            public bool InRange(int val)
            {
                return Low <= val && val <= High;
            }
        }

        public override void Run()
        {
            RunScenario("initial", @"class: 1-3 or 5-7
row: 6-11 or 33-44
seat: 13-40 or 45-50", @"7,1,14", @"7,3,47
40,4,50
55,2,20
38,6,12");
            //return;
            RunScenario("part1", @"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", 
                @"67,107,59,79,53,131,61,101,71,73,137,109,157,113,173,103,83,167,149,163", 
                @"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");

        }
    }
}
