← 返回题目列表

Codeforces · 1859/D

D. 安德烈和逃离卡皮格勒

中文机器翻译题面 查看原题

蒂亚戈兰首府卡皮格勒发生了一起事件,城里所有的水豚都发疯了,开始扔柑橘。安德烈被迫使用传送门尽可能逃离城市。

Tyagoland 由数轴表示,Capygrad 市位于点 $$$0$$$。 Tyagoland 各地都有 $$$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]$$$ 段上的任何点。安德烈拥有一张通行证,允许他无限次使用传送门。

如果满足不等式 $$$l \le x \le r$$$,Andrey 认为点 $$$x$$$ 在线段 $$$[l, r]$$$ 上。

安德烈有 $$$q$$$ 选项来选择从哪里开始逃生,每个选项都由一个整数 $$$x_i$$$ 来表征 - 逃生的起始位置。他想逃离卡皮格勒尽可能远的地方(到达坐标最大的点)。帮助安德烈确定他可以从 Capygrad 逃出多远,从每个 $$$q$$$ 位置开始。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$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)$$$ — 门户的特征。

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

输出

对于每个测试用例,输出一行 $$$q$$$ 整数,其中包含 Andrey 问题的答案。

示例

输入 #1

5
3
6 17 7 14
1 12 3 8
16 24 20 22
6
10 2 23 15 28 18
3
3 14 7 10
16 24 20 22
1 16 3 14
9
2 4 6 8 18 23 11 13 15
2
1 4 2 3
3 9 6 7
3
4 8 1
5
18 24 18 24
1 8 2 4
11 16 14 14
26 32 28 30
5 10 6 8
9
15 14 13 27 22 17 31 1 7
6
9 22 14 20
11 26 13 24
21 33 22 23
21 33 25 32
1 6 3 4
18 29 20 21
8
11 23 16 5 8 33 2 21

输出 #1

14 14 23 15 28 22 
14 14 14 14 22 23 14 14 15 
7 8 7 
15 14 14 30 24 17 31 4 8 
32 32 32 5 8 33 4 32

注意

在第一个测试用例中:

从每个位置开始时的最佳动作:

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$$$ 不在任何线段上,因此 Andrey 将无法传送到任何地方。
6. 点$$$x_6=18$$$仅位于线段$$$[l_3, r_3] = [16, 24]$$$上,使用传送门$$$3$$$并传送到点$$$b_3 = 22$$$。

在第五个测试用例中:

从每个位置开始时的最佳动作:

1. 首先使用传送门 $$$1$$$ 并传送到段 $$$[a_1, b_1] = [14, 20]$$$ 上的 $$$15$$$,然后使用传送门 $$$2$$$ 并传送到段 $$$[l_4, r_4] = [21, 33]$$$ 并在段 $$$[a_2, b_2] = [13, 24]$$$ 上,然后传送到点 $$$b_4 = 32$$$。
2. 首先使用传送门 $$$6$$$ 并传送到段 $$$[a_6, b_6] = [20, 21]$$$ 上的 $$$20$$$,然后使用传送门 $$$2$$$ 并传送到同时位于段 $$$[l_4, r_4] = [21, 33]$$$ 并在段 $$$[a_2, b_2] = [13, 24]$$$ 上,然后传送到点 $$$b_4 = 32$$$。
3. 执行与第一个位置相同的操作。
4. 停留在点$$$x_4=5$$$,不使用任何传送门。
5. 点 $$$8$$$ 不在任何线段上,因此 Andrey 将无法传送到任何地方。
6. 停留在点$$$x_6=33$$$,不使用任何传送门。
7. 使用传送门$$$5$$$并传送到$$$b_5 = 4$$$。
8. 执行与第一个位置相同的操作。