#!/bin/sh
# -*- tcl -*-
# The next line is executed by /bin/sh, but not tcl \
exec tclsh "$0" ${1+"$@"}

#----------------------------------------------------------------------
# Key phrases from the site www.adventofcode.com have been taken as
# requirement statements, and have been embedded in the code as comments
# to serve as inline documentation.  Where I remember to, I have hash-bang
# commented them (#!), but I will gladly credit any place I have missed.
# All copyright on those text sections is assigned to the writers behind
# adventofcode.com.  They are quoted in this code file under fair use as 
# part of my contribution to the online contest of which they are the 
# source, wherein my part is the Tcl code implementing them.
# 
# All code and other comments are Copyright 2020, Erik N. Johnson.
# This software is distributed under the [MIT 3-clause license](./license.ENJ.txt).
#----------------------------------------------------------------------

# Get input from file
if {1} {
    set fhandle [open "advent16.txt"]
} else {
    set fhandle [open "tmp.txt"]
}
set inData [read -nonewline $fhandle]
close $fhandle

#
# --- Day 16: Ticket Translation ---
#
#! you can't actually read the words on the ticket. You can, however, read the 
#! numbers, and so you figure out the fields these tickets must have and the 
#! valid ranges for values in those fields.
#
#! You collect the rules for ticket fields, the numbers on your ticket, and the 
#! numbers on other nearby tickets for the same train service (via the airport 
#! security cameras) together into a single document you can reference (your 
#! puzzle input).
#
#! The rules for ticket fields specify a list of fields that exist somewhere on 
#! the ticket and the valid ranges of values for each field. For example, a 
#! rule like class: 1-3 or 5-7 means that one of the fields in every ticket is 
#! named class and can be any value in the ranges 1-3 or 5-7 (inclusive, such 
#! that 3 and 5 are both valid in this field, but 4 is not).
#
#! Each ticket is represented by a single line of comma-separated values. The 
#! values are the numbers on the ticket in the order they appear; every ticket 
#! has the same format. 

proc addRule {line} {
    global rulesA 
    if {$line eq {} } return

    regexp {([a-z ]+): ([0-9]+\-[0-9]+)( or .*)*} $line -> rname range remain
    lappend rangeL $range
    while {$remain ne {}} {
        regexp { or ([0-9]+\-[0-9]+)( or .*)*} $remain -> range more
        lappend rangeL $range
        set remain $more
    }
    set rulesA($rname) $rangeL
}

set mode rules
foreach line [split $inData "\n"] {
    if {$line eq "your ticket:"} {
        set mode mine
        continue
    } elseif {$line eq "nearby tickets:"} {
        set mode nearby
        continue
    }
    switch -exact -- $mode {
        rules   {addRule $line}
        mine    {if {$line ne {}} {set myTicket [split $line ","]}}
        nearby  {lappend nearTickets [split $line ","]}
        default {error "unknown mode $mode"}
    }
}


#
# Part 1
#
#! Start by determining which tickets are completely invalid; these are tickets 
#! that contain values which aren't valid for any field. Ignore your ticket for 
#! now.
#
#! Adding together all of the invalid values produces your ticket scanning 
#! error rate: 4 + 55 + 12 = 71.
#
#! Consider the validity of the nearby tickets you scanned. What is your ticket 
#! scanning error rate?

# concatenate all ranges into one list
foreach key [array names rulesA] {
    lappend allRanges {*}$rulesA($key)
}

set invalidVals {}
foreach tkt $nearTickets {
    set tvalid true
    foreach field $tkt {
        set fvalid false
        foreach range $allRanges {
            lassign [split $range "-"] min max
            if {$field >= $min && $field <= $max} {
                set fvalid true
            }
        }
        if {!$fvalid} {
            lappend invalidVals $field
            set tvalid false
        }
    }
    if {$tvalid} {
        lappend validTix $tkt
    }
}
puts "\nInvalid fields sum to [::tcl::mathop::+ {*}$invalidVals]\n"

#
# Part 2
#
#! Now that you've identified which tickets contain invalid values, discard 
#! those tickets entirely. Use the remaining valid tickets to determine which 
#! field is which.
#
#! Using the valid ranges for each field, determine what order the fields 
#! appear on the tickets. The order is consistent between all tickets: if seat 
#! is the third field, it is the third field on every ticket, including your 
#! ticket.
#
#! Once you work out which field is which, look for the six fields on your 
#! ticket that start with the word departure. What do you get if you multiply 
#! those six values together?

for {set fieldIdx 0} {$fieldIdx < [llength [lindex $validTix 0]]} {incr fieldIdx} {
    foreach rule [array names rulesA] {
        set canbe true
        foreach tkt $validTix {
            set tktV false
            foreach rng $rulesA($rule) {
                if {[lindex $tkt $fieldIdx] >= [lindex [split $rng "-"] 0] &&
                        [lindex $tkt $fieldIdx] <= [lindex [split $rng "-"] 1]} {
                    set tktV true
                    break
                }
            }
            if {!$tktV} {
                set canbe false
                break
            }
        }
        if $canbe {
            lappend canA($fieldIdx) $rule
        }
    }
}

proc findSingletonRule {} {
    global canA rulesA

    # find the field that can only be in one position
    foreach fieldIdx [array names canA] {
        lappend lenL $fieldIdx [llength $canA($fieldIdx)]
    }
    set sortLen [lsort -stride 2 -index 1 -integer $lenL ]
    set posn [lindex $sortLen 0]
    # This is annoying - lsearch for a string enclosed in {} was failing
    # remapping the {} away is working, but shouldn't be needed.
    set name [string map {\{ "" \} ""} $canA($posn)]
    #puts "posn $posn is $name"

    # found this rule for this position; remove it from the ranges of 
    # possibilities of the rest of the positions
    foreach fieldIdx [array names canA] {
        set idx [lsearch $canA($fieldIdx) $name ]
        if {$idx >= 0} {
            set canA($fieldIdx) [lreplace $canA($fieldIdx) $idx $idx]
        }
        if {[llength $canA($fieldIdx)] == 0} {
            unset canA($fieldIdx)
        }
    }

    return [list $posn $name]
}

foreach i [array names canA] {
    lassign [findSingletonRule] posn name
    set fieldPos($name) $posn
    if {[llength [array names canA]] == 0}  break
}

# puts ""
# parray canA 
# puts ""
#parray fieldPos

set accum 1
foreach field [array names fieldPos departure*] {
    puts "Field $field is in position $fieldPos($field).  On my ticket, that's [lindex $myTicket $fieldPos($field)]"
    set accum [expr $accum * [lindex $myTicket $fieldPos($field)]]
}
puts "The result of multipling all deparure fields is $accum."

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