CF1545E2.AquaMoon and Time Stop (hard version)

Note that the differences between easy and hard versions are the constraints on $n$ and the time limit. You can make hacks only if both versions are solved.

AquaMoon knew through foresight that some ghosts wanted to curse tourists on a pedestrian street. But unfortunately, this time, these ghosts were hiding in a barrier, and she couldn't enter this barrier in a short time and destroy them. Therefore, all that can be done is to save any unfortunate person on the street from the ghosts.

The pedestrian street can be represented as a one-dimensional coordinate system. There is one person hanging out on the pedestrian street. At the time $0$ he is at coordinate $x$, moving with a speed of $1$ unit per second. In particular, at time $i$ the person will be at coordinate $x+i$.

The ghosts are going to cast $n$ curses on the street. The $i$-th curse will last from time $tl_i-1+10^{-18}$ to time $tr_i+1-10^{-18}$ (exclusively) and will kill people with coordinates from $l_i-1+10^{-18}$ to $r_i+1-10^{-18}$ (exclusively). Formally that means, that the person, whose coordinate is between $(l_i-1+10^{-18},r_i+1-10^{-18})$ in the time range $(tl_i-1+10^{-18},tr_i+1-10^{-18})$ will die.

To save the person on the street, AquaMoon can stop time at any moment $t$, and then move the person from his current coordinate $x$ to any coordinate $y$ ($t$, $x$ and $y$ are not necessarily integers). The movement costs AquaMoon $|x-y|$ energy. The movement is continuous, so if there exists some cursed area between points $x$ and $y$ at time $t$, the person will die too.

AquaMoon wants to know what is the minimum amount of energy she needs to spend in order to save the person on the street from all $n$ curses. But she is not good at programming. As her friend, can you help her?

注意：简单版本与困难版本的区别在于对 $n$ 的约束以及时间限制。仅当两个版本均被解决时，才允许进行 hack。

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})$。形式化地说，这意味着：若某人在时间区间 $(tl_i-1+10^{-18},\, tr_i+1-10^{-18})$ 内处于坐标区间 $(l_i-1+10^{-18},\, r_i+1-10^{-18})$ 中，则此人将死亡。

为拯救步行街上的路人，AquaMoon 可在任意时刻 $t$ 暂停时间，然后将路人从其当前坐标 $x$ 移动至任意坐标 $y$（其中 $t$、$x$ 和 $y$ 均不必为整数）。该移动操作消耗 AquaMoon 的能量值为 $|x-y|$。移动过程是连续的，因此若在时刻 $t$，线段 $[x, y]$（或 $[y, x]$）上存在任何被诅咒的区域，则路人亦会死亡。

AquaMoon 想知道：为使路人免遭全部 $n$ 个诅咒的伤害，她所需的最小能量消耗是多少？但她不擅长编程。作为她的朋友，你能帮她吗？

The first line contains a single integer $n$ ($1\le n\le 2 \cdot 10^5$) — the number of curses.

The next line contains a single integer $x$ ($1\le x\le 10^6$) — the initial coordinate of the person.

The following $n$ lines contain four integers $tl_i$, $tr_i$, $l_i$, $r_i$ each ($1\le tl_i\le tr_i\le 10^6$, $1\le l_i\le r_i\le 10^6$).

第一行包含一个整数 $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$）。

Print a single integer — the minimum energy which AquaMoon needs to spent, rounded up to the nearest integer (in case there are two nearest integers you should round the answer to the highest of them).

输出一个整数——AquaMoon 所需消耗的最小能量值，向上取整至最接近的整数（若存在两个同样接近的整数，则取较大的那个）。