Принц
시간 제한2초메모리 제한256 MB
무한한 직선 위의 왕자가 시간에 따라 나타나고 사라지는 구간 형태의 함정을 피해 x 위치의 문에 도달하는 최소 시간을 구하고, 불가능하면 Impossible을 출력한다.
문제
После долгих приключений Принц невероятно близок к спасению Принцессы. Ему осталось лишь преодолеть коридор, наполненный ловушками.
Коридор представляет собой бесконечную в обе стороны прямую. В начальный момент времени Принц находится в точке 0. В x метрах от него находится дверь, ведущая в комнату Принцессы. За одну секунду Принц может пройти один метр в любом направлении или остаться на месте.
Использовав Пески времени, Принц выяснил, что в коридоре расположены n ловушек. Ловушки работают следующим образом: i-ая ловушка появится через ai секунд и исчезнет через ti секунд после появления. Ловушка занимает часть коридора с li по ri метров (отсчет ведется от Принца в направлении Принцессы), и если Принц окажется строго в занимаемой ловушкой области, его ожидает неминуемая гибель. Принц может безопасно находиться на краю ловушки, а также сразу проходит в дверь, даже если в этот же момент там появляется ловушка.
Ваша задача состоит в том, чтобы по описанию ловушек узнать, через какое минимальное время Принц сможет добраться до двери, ведущей в комнату Принцессы.
입력
Первая строка содержит два целых числа n и x (0 ≤ n ≤ 1000; 1 ≤ x ≤ 105) — число ловушек и позиция двери.
Далее следуют n строк, содержащих описание ловушек. Описание состоит из четырех целых чисел ai, ti, li и ri (1 ≤ ai, ti ≤ 106; −106 ≤ li < ri ≤ 106) — время появления и продолжительность жизни ловушки, а также положение ее левого и правого краев. Ловушки могут пересекаться.
출력
Если Принц не может добраться до двери, выведите «Impossible». Иначе выведите одно целое число — минимальное время, через которое Принц сможет добраться до заветной двери.