22149번 - Принц 다국어

После долгих приключений Принц невероятно близок к спасению Принцессы. Ему осталось лишь преодолеть коридор, наполненный ловушками.

Коридор представляет собой бесконечную в обе стороны прямую. В начальный момент времени Принц находится в точке 0. В x метрах от него находится дверь, ведущая в комнату Принцессы. За одну секунду Принц может пройти один метр в любом направлении или остаться на месте.

Использовав Пески времени, Принц выяснил, что в коридоре расположены n ловушек. Ловушки работают следующим образом: i-ая ловушка появится через a_i секунд и исчезнет через t_i секунд после появления. Ловушка занимает часть коридора с l_i по r_i метров (отсчет ведется от Принца в направлении Принцессы), и если Принц окажется строго в занимаемой ловушкой области, его ожидает неминуемая гибель. Принц может безопасно находиться на краю ловушки, а также сразу проходит в дверь, даже если в этот же момент там появляется ловушка.

Ваша задача состоит в том, чтобы по описанию ловушек узнать, через какое минимальное время Принц сможет добраться до двери, ведущей в комнату Принцессы.

Первая строка содержит два целых числа n и x (0 ≤ n ≤ 1000; 1 ≤ x ≤ 10⁵) — число ловушек и позиция двери.

Далее следуют n строк, содержащих описание ловушек. Описание состоит из четырех целых чисел a_i, t_i, l_i и r_i (1 ≤ a_i, t_i ≤ 10⁶; −10⁶ ≤ l_i < r_i ≤ 10⁶) — время появления и продолжительность жизни ловушки, а также положение ее левого и правого краев. Ловушки могут пересекаться.

Если Принц не может добраться до двери, выведите «Impossible». Иначе выведите одно целое число — минимальное время, через которое Принц сможет добраться до заветной двери.