Кулька падає на землю, зустрічаючи на своєму шляху перегородки. Введемо стандартну двовимірну систему координат таким чином, що земля буде являти собою вісь Ox, а сила тяжіння діє у протилежному напрямку осі Oy. Перегородки являють собою відрізки, а кулька - точку. Потрапляючи на перегородку (навіть в її найвищій точці), кулька скочується по ній і продовжує падіння вертикально вниз (іншими словами, горизонтальна складова швидкості кульки миттєво зникає після досягнення кінця перегородки). Серед перегородок немає ні вертикальних, ні горизонтальних, всі вони знаходяться строго над рівнем землі, і ніякі дві перегородки не мають спільних точок. Таким чином, рано чи пізно кулька досягне землі в певній точці.

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

Input

У першому рядку міститься число ~N~ ~(0 \le N \le 3 * 10^5)~ - кількість перегородок.

Кожен з наступних ~N~ рядків містить опис чергової перегородки - чотири числа ~x_1, y_1, x_2, y_2~ (~x_1 < x_2~, ~y_1 \neq y_2~, ~y_1 > 0~, ~y_2 > 0~): ~(x_1, y_1)~ - координати лівого кінця перегородки, ~(x_2; y_2)~ - координати правого кінця.

У наступному рядку міститься число ~M~ ~(1 \le M \le 3 * 10^5)~ - кількість запусків кульки.

Далі слідують ~M~ рядків, у кожному з яких записано одне ціле число - x-координата позиції, з якої здійснюється запуск. Гарантується, що y-координата стартової позиції перевершує y-координату кінців всіх перегородок.

Всі координати у вхідному файлі - цілі числа, що не перевищують ~10^6~ по модулю. Гарантується, що серед перегородок немає вертикальних і горизонтальних, перегородки не мають спільних точок, довжина кожної перегородки строго більше нуля.

Output

Для кожного запуску виведіть на окремому рядку єдине число - x-координату точки дотику кульки з землею.

Sample Input 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

Sample Output 1

1

Notes

Зображення в умови відповідає прикладу вхідних даних.