#![warn(clippy::pedantic)]

use std::{io::stdin, ops::ControlFlow};

use aoc::{SectionRange, UpToTwo};

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct MapRange {
    source: SectionRange<usize>,
    dest_start: usize,
}

impl MapRange {
    /// Returns overlapping (mapped) and non-overlapping (unmapped) ranges
    pub fn map(
        &self,
        source_range: SectionRange<usize>,
    ) -> (Option<SectionRange<usize>>, UpToTwo<SectionRange<usize>>) {
        if let Some(overlap) = self.source & source_range {
            let non_overlapping = source_range - overlap;
            let overlap_offset = overlap
                .offset_by_neg(*self.source.start())
                .offset_by(self.dest_start);

            (Some(overlap_offset), non_overlapping)
        } else {
            (None, UpToTwo::One(source_range))
        }
    }

    pub fn parse(s: &str) -> Self {
        let &[dest_start, source_start, len] = s
            .split(' ')
            .map(|n| n.parse().unwrap())
            .collect::<Vec<_>>()
            .as_slice()
        else {
            panic!("Invalid input: {s}");
        };

        Self {
            source: SectionRange::try_new(source_start, source_start + len - 1).unwrap(),
            dest_start,
        }
    }
}

struct IdMapping {
    ranges: Vec<MapRange>,
}

impl IdMapping {
    pub fn new(ranges: Vec<MapRange>) -> Self {
        for window in ranges.windows(2) {
            let [first, second] = window else { panic!() };
            assert!(
                (first.source & second.source).is_none(),
                "source ranges overlap"
            );
        }
        Self { ranges }
    }

    pub fn map(&self, source_range: SectionRange<usize>) -> Vec<SectionRange<usize>> {
        let result = self.ranges.iter().try_fold(
            (vec![], vec![source_range]),
            |(mut mapped, unmapped), range| {
                if unmapped.is_empty() {
                    return ControlFlow::Break(mapped);
                }

                let mut remaining_unmapped = Vec::new();
                for non_mapped in unmapped {
                    let (overlapping, non_overlapping) = range.map(non_mapped);
                    mapped.extend(overlapping);
                    remaining_unmapped.extend(non_overlapping);
                }
                ControlFlow::Continue((mapped, remaining_unmapped))
            },
        );
        match result {
            ControlFlow::Continue((mut mapped, unmapped)) => {
                // unmapped ranges stay as-is
                mapped.extend(unmapped);
                mapped
            }
            ControlFlow::Break(mapped) => mapped,
        }
    }
}

fn map_ranges_once(
    ranges: &[SectionRange<usize>],
    mapping: &IdMapping,
) -> Vec<SectionRange<usize>> {
    ranges
        .iter()
        .flat_map(|&range| mapping.map(range))
        .collect()
}

fn map_ranges_completely(
    init_ranges: Vec<SectionRange<usize>>,
    mappings: &[IdMapping],
) -> Vec<SectionRange<usize>> {
    mappings
        .iter()
        .fold(init_ranges, |ranges, map| map_ranges_once(&ranges, map))
}

fn minimum_result(init_ranges: Vec<SectionRange<usize>>, mappings: &[IdMapping]) -> usize {
    *map_ranges_completely(init_ranges, mappings)
        .iter()
        .min()
        .unwrap()
        .start()
}

fn main() {
    let mut lines = stdin().lines().map(Result::unwrap);

    let seeds: Vec<usize> = lines
        .next()
        .unwrap()
        .split(' ')
        .skip(1)
        .map(|n| n.parse().unwrap())
        .collect();

    let mut maps = Vec::new();
    while let Some(line) = lines.next() {
        if line.is_empty() {
            lines.next();
            continue;
        }

        let ranges = lines
            .by_ref()
            .take_while(|l| !l.is_empty())
            .map(|l| MapRange::parse(&l))
            .collect();
        maps.push(IdMapping::new(ranges));
    }

    let single_seeds: Vec<_> = seeds
        .iter()
        .map(|&seed| SectionRange::try_new(seed, seed).unwrap())
        .collect();

    println!("{}", minimum_result(single_seeds, &maps));

    let seed_ranges: Vec<_> = seeds
        .chunks(2)
        .map(|pair| {
            let &[start, len] = pair else {
                panic!("Not a pair: {pair:?}");
            };
            SectionRange::try_new(start, start + len - 1).unwrap()
        })
        .collect();

    println!("{}", minimum_result(seed_ranges, &maps));
}
