#!/usr/bin/perl -w

use v5.36;
use strict;
use experimental 'multidimensional';

my $max = 4000000;

my @input = map {
	my ($x, $y, $cx, $cy) = /(-?\d+)/g;
	[ $x, $y, abs($x-$cx) + abs($y-$cy) ]
} <>;

sub compute_row($row) {
	my @ints;

	for (@input) {
		my ($sx, $sy, $r) = @$_;
		my $dist = abs($sy - $row);
		next if $dist > $r;

		my ($left, $right) = ($sx - ($r - $dist), $sx + ($r - $dist));
		next if $right < 0 || $left > $max;
		$left = 0 if $left < 0;
		$right = $max if $right > $max;
		push @ints, [$left, $right];
	}

	@ints = sort { $a->[0] <=> $b->[0] } @ints;
	my $prev = (shift @ints)->[1];

	for my $int (@ints) {
		next if $int->[1] <= $prev;
		if ($int->[0] > $prev+1) {
			say "at ", $prev+1, " $row: ",
				4000000*($prev+1)+$row;
			exit 0;
		}
		$prev = $int->[1];
	}
}

for (0 .. $max) {
	compute_row($_);
	say "row $_" if $_ % 10_000 == 0;
}

