#!/usr/bin/python3
import fileinput
import re
import sys

xy_max = 4000000

sensors = []

r = r'Sensor at x=(-?\d+), y=(-?\d+).*beacon is at x=(-?\d+), y=(-?\d+)'
for line in fileinput.input():
	result = re.search(r, line)
	sx, sy, bx, by = list(map(int, result.groups()))
	dist = abs(bx-sx) + abs(by-sy)
	sensors.append((sx,sy,dist))

# Project each sensor's coverage diamond onto the target row.
# Number of cells covered is either 0, or an odd number (1, 3, 5, ...).
# 
# .................#.....
# ................###.... <= target row
# ........#......#####...
# ..#....###....#######..
# .#S#..##S##..####S####.
# ..#....###....#######..
# ........#......#####...
# ................###....
# .................#.....
# 
# With the sensor 3 units away vertically, range 1 or 2 provides no coverage.
# Range 3 (= dY) provides 1 unit of coverage at sensor's X.
# Range dY+1 provides 3 units of coverage, SX-1 to SX+1.
# Range dY+n provides 2n+1 coverage, from SX-n to SX+n.

def get_coverage(sensors, targety):
	coverage = []
	for s in sensors:
		sx, sy, srange = s
		dist = abs(sy - targety)
		if dist > srange:
			continue
		coverage.append((sx-(srange-dist),sx+(srange-dist)))

	# Remove redundant coverage elements.
	# Use stuff from day 4 part 1.
	redundant = [False] * len(coverage)
	for i in range(0, len(coverage)-1):
		for j in range(i+1, len(coverage)):
			if i == j:
				continue
			a, b = coverage[i]
			c, d = coverage[j]
			considered = j
			if (a > c) or (a == c and d > b):
				a, b, c, d = c, d, a, b
				considered = i
			if a <= c and b >= d:
				redundant[considered] = True

	newlist = []
	for i in range(0, len(coverage)):
		if not redundant[i]:
			newlist.append(coverage[i])
	return newlist

for y in range(0, xy_max+1):
	# Look for a coverage gap.
	# If there's a gap, it'll be right before or right after a
	# coverage zone.
	coverage = get_coverage(sensors, y)
	check = set()
	for c in coverage:
		if c[0]-1 >= 0 and c[0]-1 <= xy_max:
			check.add(c[0]-1)
		if c[1]+1 >= 0 and c[1]+1 <= xy_max:
			check.add(c[1]+1)

	for x in check:
		covered = False
		for c in coverage:
			if x >= c[0] and x <= c[1]:
				covered = True
		if not covered:
			print("x=%d, y=%d is not covered" % (x,y))
			print(x*4000000 + y)
			sys.exit(0)