#!/usr/bin/perl -w

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

my $row = 2000000;
my $max = 4000000;

my @input = <>;

sub compute_row($row) {
	my @ints;
	my %corr;

	for (@input) {
		my ($sx, $sy, $cx, $cy) = /(-?\d+)/g;
		my $r = abs($sx - $cx) + abs($sy - $cy);
		my $dist = abs($sy - $row);
		# say "dist =$dist";
		if ($dist < $r) {
			my ($l, $r) = ($sx - ($r - $dist), $sx + ($r - $dist));
			next if $r < 0 || $l > $max;
			$l = 0 if $l < 0;
			$r = $max if $r > $max;
			push @ints, [$l, $r];
			# say "$ints[-1][0] $ints[-1][1]";
			$corr{$cx} = 1 if $cy == $row;
		}
	}

	@ints = sort { $a->[0] <=> $b->[0] } @ints;
	my $prev = shift @ints;
	if ($prev->[0]) {
		say "at 0 $row";
		exit 0;
	}
	my $sum = $prev->[1] - $prev->[0] + 1;

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

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

