CF1859D.Andrey and Escape from Capygrad

An incident occurred in Capygrad, the capital of Tyagoland, where all the capybaras in the city went crazy and started throwing mandarins. Andrey was forced to escape from the city as far as possible, using portals.

Tyagoland is represented by a number line, and the city of Capygrad is located at point $0$. There are $n$ portals all over Tyagoland, each of which is characterised by four integers $l_i$, $r_i$, $a_i$ and $b_i$ ($1 \le l_i \le a_i \le b_i \le r_i \le 10^9$). Note that the segment $[a_i, b_i]$ is contained in the segment $[l_i, r_i]$.

If Andrey is on the segment $[l_i, r_i]$, then the portal can teleport him to any point on the segment $[a_i, b_i]$. Andrey has a pass that allows him to use the portals an unlimited number of times.

Andrey thinks that the point $x$ is on the segment $[l, r]$ if the inequality $l \le x \le r$ is satisfied.

Andrey has $q$ options for where to start his escape, each option is characterized by a single integer $x_i$ — the starting position of the escape. He wants to escape from Capygrad as far as possible (to the point with the maximum possible coordinate). Help Andrey determine how far he could escape from Capygrad, starting at each of the $q$ positions.

一场突发事件发生在泰亚国首都卡皮格拉德，城中所有水豚突然发狂，开始向四处投掷橘子。安德烈被迫尽可能远地逃离这座城市，借助传送门。

泰亚国被表示为一条数轴，首都卡皮格拉德位于坐标点 $0$ 处。泰亚国境内共有 $n$ 个传送门，每个传送门由四个整数 $l_i$、$r_i$、$a_i$ 和 $b_i$（满足 $1 \le l_i \le a_i \le b_i \le r_i \le 10^9$）刻画。注意：区间 $[a_i, b_i]$ 完全包含于区间 $[l_i, r_i]$ 内。

若安德烈当前位于区间 $[l_i, r_i]$ 上，则该传送门可将他瞬移至区间 $[a_i, b_i]$ 内的任意一点。安德烈拥有一张通行证，允许他无限次使用这些传送门。

安德烈认为点 $x$ 位于区间 $[l, r]$ 上，当且仅当不等式 $l \le x \le r$ 成立。

安德烈共有 $q$ 种不同的逃生起始方案，每种方案由一个整数 $x_i$ 表示——即逃生的起始位置。他希望尽可能远离卡皮格拉德（即抵达坐标值最大的点）。请帮助安德烈确定：对于每一个起始位置 $x_i$，他最多能逃到多远的位置。

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of sets of test cases. The description of test cases follows.

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

Each of the next $n$ lines contains four integers $l_i$, $r_i$, $a_i$, and $b_i$ $(1 \le l_i \le a_i \le b_i \le r_i \le 10^9)$ — the characteristics of the portals.

The next line contains a single integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of positions.

The following line contains $q$ integers $x_1, x_2, \ldots, x_q$ ($1 \le x_i \le 10^9$) — the position from which Andrey will start his escape in the $i$-th options.

It is guaranteed that the sum of $n$ and the sum of $q$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例组的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示传送门的数量。

接下来的 $n$ 行，每行包含四个整数 $l_i$、$r_i$、$a_i$ 和 $b_i$（$1 \le l_i \le a_i \le b_i \le r_i \le 10^9$），表示第 $i$ 个传送门的属性。

接下来一行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$），表示位置的数量。

下一行包含 $q$ 个整数 $x_1, x_2, \ldots, x_q$（$1 \le x_i \le 10^9$），表示 Andrey 在第 $i$ 种方案中开始逃逸的位置。

保证所有测试用例中 $n$ 的总和与 $q$ 的总和均不超过 $2 \cdot 10^5$。

For each test case, output a single line of $q$ integers, containing the answers to Andrey's questions.

对于每个测试用例，输出一行包含 $q$ 个整数，表示安德烈各个问题的答案。

In the first test case:

Optimal actions when starting from each position:

1. Use portal $1$ and teleport to point $b_1 = 14$.
2. Use portal $2$ first and teleport to point $6$, which is on the segment $[l_1, r_1] = [6, 17]$, then use portal $1$ and teleport to point $b_1 = 14$.
3. Stay at point $x_3=23$ without using any portals.
4. Stay at point $x_4=15$ without using any portals.
5. Point $x_5=28$ is not on any segment, so Andrey won't be able to teleport anywhere.
6. Point $x_6=18$ is only on the segment $[l_3, r_3] = [16, 24]$, use portal $3$ and teleport to point $b_3 = 22$.

In the fifth test case:

Optimal actions when starting from each position:

1. Use portal $1$ first and teleport to point $15$ on the segment $[a_1, b_1] = [14, 20]$, then use portal $2$ and teleport to point $21$, which is on the segment $[l_4, r_4] = [21, 33]$ and on the segment $[a_2, b_2] = [13, 24]$, then teleport to point $b_4 = 32$.
2. Use portal $6$ first and teleport to point $20$ on the segment $[a_6, b_6] = [20, 21]$, then use portal $2$ and teleport to point $22$, which is simultaneously on the segment $[l_4, r_4] = [21, 33]$ and on the segment $[a_2, b_2] = [13, 24]$, then teleport to point $b_4 = 32$.
3. Perform the same actions as from the first position.
4. Stay at point $x_4=5$ without using any portals.
5. Point $8$ is not on any segment, so Andrey won't be able to teleport anywhere.
6. Stay at point $x_6=33$ without using any portals.
7. Use portal $5$ and teleport to point $b_5 = 4$.
8. Perform the same actions as from the first position.

在第一个测试用例中：

从每个起始位置出发的最优操作如下：

1. 使用第 $1$ 个传送门，传送到点 $b_1 = 14$。
2. 首先使用第 $2$ 个传送门，传送到点 $6$（该点位于线段 $[l_1, r_1] = [6, 17]$ 上），然后使用第 $1$ 个传送门，传送到点 $b_1 = 14$。
3. 停留在点 $x_3 = 23$，不使用任何传送门。
4. 停留在点 $x_4 = 15$，不使用任何传送门。
5. 点 $x_5 = 28$ 不在任何线段上，因此安德烈无法进行任何传送。
6. 点 $x_6 = 18$ 仅位于线段 $[l_3, r_3] = [16, 24]$ 上，使用第 $3$ 个传送门，传送到点 $b_3 = 22$。

在第五个测试用例中：

从每个起始位置出发的最优操作如下：

1. 首先使用第 $1$ 个传送门，传送到点 $15$（该点位于线段 $[a_1, b_1] = [14, 20]$ 上），然后使用第 $2$ 个传送门，传送到点 $21$（该点同时位于线段 $[l_4, r_4] = [21, 33]$ 和线段 $[a_2, b_2] = [13, 24]$ 上），最后传送到点 $b_4 = 32$。
2. 首先使用第 $6$ 个传送门，传送到点 $20$（该点位于线段 $[a_6, b_6] = [20, 21]$ 上），然后使用第 $2$ 个传送门，传送到点 $22$（该点同时位于线段 $[l_4, r_4] = [21, 33]$ 和线段 $[a_2, b_2] = [13, 24]$ 上），最后传送到点 $b_4 = 32$。
3. 执行与从第一个位置出发时相同的操作。
4. 停留在点 $x_4 = 5$，不使用任何传送门。
5. 点 $8$ 不在任何线段上，因此安德烈无法进行任何传送。
6. 停留在点 $x_6 = 33$，不使用任何传送门。
7. 使用第 $5$ 个传送门，传送到点 $b_5 = 4$。
8. 执行与从第一个位置出发时相同的操作。