D. Андрей и побег из Капиграда
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Тяголяндия представляет из себя числовую прямую, а Капиград находится в точке $$$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$$$ — позицией начала побега. Он хочет убежать от Капиграда как можно дальше (в точку с максимально возможной координатой). Помогите Андрею узнать, насколько далеко от Капиграда он может убежать, начиная в каждой из $$$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$$$) — позиция, откуда Андрей начнет свой побег в $$$i$$$-м варианте.

Гарантируется, что сумма $$$n$$$ и сумма $$$q$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите одну строку из $$$q$$$ целых чисел, содержащую ответы на интересующие Андрея вопросы.

Пример
Входные данные
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
Выходные данные
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$$$ не находится ни на одном отрезке, поэтому Андрей не сможет никуда телепортироваться.
  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. Сделаем те же самые действия что и из первой позиции.