Задача №112685. Янтарный шарик

Янтарный шарик падает на землю, встречая на своём пути перегородки. Введём стандартную двумерную систему координат таким образом, что земля будет представлять собой ось \(O_x\), а сила тяжести действует в отрицательном направлении оси \(O_y\). Перегородки представляют собой отрезки, а шарик — точку. Попадая на перегородку (даже в её самой верхней точке), шарик скатывается по ней и продолжает падение вертикально вниз (иными словами, горизонтальная составляющая скорости шарика мгновенно исчезает по достижении конца перегородки). Среди перегородок нет ни вертикальных, ни горизонтальных, все они находятся строго над уровнем земли, и никакие две перегородки не имеют общих точек. Таким образом, рано или поздно шарик достигнет земли в некоторой точке.

Шарик несколько раз запускают с разных стартовых позиций. Для каждого запуска требуется найти x-координаты точки соприкосновения шарика с землёй.

Формат входного файла

В первой строке содержится число N (0 <= N <= 3 * \(10^5\)) — количество перегородок.

Каждая из последующих \(N\) строк содержит описание очередной перегородки — четыре числа \(x_1\), \(y_1\), \(x_2\), \(y_2\) (\(x_1\) < \(x_2\), \(y_1\) ̸= \(y_2\), \(y_1\); \(y_2\) > 0): (\(x_1\); \(y_1\)) — координаты левого конца перегородки, (\(x_2\); \(y_2\)) — координаты правого конца.

В следующей строке содержится число M (1 <= M <= 3 * \(10^5\)) — количество запусков шарика.

Далее следуют \(M\) строк, в каждой из которых записано одно целое число — \(x\)-координата позиции, с которой производится запуск. Гарантируется, что \(y\)-координата стартовой позиции превосходит \(y\)-координаты концов всех перегородок.

Все координаты во входном файле — целые числа, не превосходящие \(10^6\) по модулю. Гарантируется, что среди перегородок нет вертикальных и горизонтальных, перегородки не имеют общих точек, длина каждой перегородки строго больше нуля.

Формат выходного файла

Для каждого запуска выведите на отдельной строке единственное число — x-координату точки соприкосновения шарика с землёй.

Note

Изображение в условии соответствует третьему примеру входных данных.

Примеры
Входные данные
2
0 7 1 3
3 3 4 7
2
2
4
Выходные данные
2
3
Входные данные
2
-3 5 1 3
-1 1 1 2
3
-3
-4
1
Выходные данные
-1
-4
-1
Входные данные
7
-2 10 2 11
-4 9 -1 6
3 9 8 8
-7 3 -6 6
-1 5 3 4
-3 4 0 3
1 2 7 3
1
0
Выходные данные
1
Сдать: для сдачи задач необходимо войти в систему