E2. AquaMoon и остановка времени (сложная версия)
ограничение по времени на тест
7 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

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

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

Пешеходная улица может быть представлена как координатная прямая. Есть один человек, который передвигается по ней. В момент времени $$$0$$$ он находится в координате $$$x$$$, двигаясь со скоростью $$$1$$$ координата в секунду. В частности, в момент времени $$$i$$$ человек будет в координате $$$x+i$$$.

Призраки собираются совершить $$$n$$$ нападений на улицу. $$$i$$$-е нападение будет длиться с момента времени $$$tl_i-1+10^{-18}$$$ до момента времени $$$tr_i+1-10^{-18}$$$ (не включительно) и будет убивать людей с координатами от $$$l_i-1+10^{-18}$$$ до $$$r_i+1-10^{-18}$$$ (не включительно). Формально это означает, что человек, чья координата находится в интервале $$$(l_i-1+10^{-18},r_i+1-10^{-18})$$$ в любой из моментов времени из интервала $$$(tl_i-1+10^{-18},tr_i+1-10^{-18})$$$ умрет.

Чтобы спасти человека на улице, AquaMoon может остановить время в любой момент времени $$$t$$$ и затем переместить человека из его текущей координаты $$$x$$$ в любую координату $$$y$$$ ($$$t$$$, $$$x$$$ и $$$y$$$ не обязательно целые числа). Это перемещение будет стоить для AquaMoon $$$|x-y|$$$ энергии. Перемещение является непрерывным, поэтому если существует координата под нападением между координатами $$$x$$$ и $$$y$$$ в момент времени $$$t$$$, человек также умрет.

AquaMoon хочет узнать какое минимальное количество энергии она должна потратить, чтобы спасти человека на улице от всех $$$n$$$ нападений. Она не очень хороша в программировании. Как ее друг, можете ли вы помочь ей?

Входные данные

В первой строке находится единственное целое число $$$n$$$ ($$$1\le n\le 2 \cdot 10^5$$$) — количество нападений.

В следующей строке находится единственное целое число $$$x$$$ ($$$1\le x\le 10^6$$$) — изначальная координата человека.

В следующих $$$n$$$ строках содержится по четыре целых числа $$$tl_i$$$, $$$tr_i$$$, $$$l_i$$$, $$$r_i$$$ ($$$1\le tl_i\le tr_i\le 10^6$$$, $$$1\le l_i\le r_i\le 10^6$$$).

Выходные данные

Выведите единственное целое число — минимальное количество энергии, которое AquaMoon должна потратить, округленное до ближайшего целого числа (если есть два ближайших целых числа вы должны округлить ответ до наибольшего из них).

Примеры
Входные данные
2
1
1 2 1 2
2 3 2 3
Выходные данные
2
Входные данные
3
4
1 4 1 2
1 4 4 15
6 7 1 4
Выходные данные
8
Входные данные
4
3
1 5 1 1
4 10 1 4
1 2 3 13
1 10 7 19
Выходные данные
14
Входные данные
7
5
78 96 76 91
6 16 18 37
53 63 40 56
83 88 21 38
72 75 17 24
63 63 53 60
34 46 60 60
Выходные данные
20